stack

iOS Questions: Pt. 1

In this (long) series of posts, I'll be posting groups of questions on iOS concepts as they come to me. I have no direction in the questions I'm choosing to answer, I'm simply going to go through notes of mine, find random questions, and answer them. If questions come up in this series that need deserve dedicated posts, I'll link to another blog post that discusses the topic more fully (think something like multithreading with GCD).

  1. Deep copy v. Shallow copy v. Assignment
    A shallow copy simply copies references to a place in memory. If object B is a shallow copy of object A, it simply copies object A's references (pointers) to objects in memory. Object B then refers to that same place in memory. Making changes to the data contained in one of the objects will impact the very same data being used by the other.

    In contrast, a deep copy makes copies of the actual data, storing it elsewhere in memory. Changing the data contained in one object will have no impact on the other.

    Assigning one object to equal another creates a pointer to a group of pointers, which point to memory. That is, if you have dictionary *A, and dictionary *B = A, then B contains a pointer to A's pointers, which point to the objects in memory. Although it will behave the same as a shallow copy, in a shallow copy, B would actually contain each pointer that A contains, still pointing to the same objects in memory. In either case, changing the values of one will change the other.
     
  2. Heaps and Stacks in iOS - how are they used?
    Almost all objects in iOS development are stored on the heap - they can be accessed globally and must be manually released and deallocated (pre-ARC). Stack objects disappear when a function returns and don't need to be manually managed. Imagine if stacks were widely used in iOS - what would happen if you needed to keep one around after the function returned? You could retain it, but after the function ended, that retain command would be pointing to a non-existent object - a dangling pointer. As a result, almost all objects are placed on the heap - the exception is blocks.

    Blocks are actually stored on the stack - that's why variables created within blocks aren't accessible outside of the block. They no longer exist when the block (which is treated like a function) ends; to continue to use them outside of the scope of the block, you must use a __block variable before entering the block. You can also create a copy of the block variable you wish to use, which actually places that copy on the heap.
     
  3. What are block variables used for?
    Using block variables (prefaced with a double underscore during declaration) is a way to access information created within a block outside of the block itself (remember that objects created within a block are stored on the stack, and as such disappear when the block exits). You could technically have an array created within a block, have an array property, and set the array property equal to the block array. However, this array is now accessible from everywhere else in the program since it's a global property - for the sake of data encapsulation, block variables are a better choice.
     
  4. What is a message in Objective-C? A Method? A selector?
    Messages and Methods are conceptually different in Objective-C but not so different practically.

    Objective-C runtime keeps a list of methods and functions it is aware of. When compiled, method names are turned into selectors (representations of the method name in memory). A function, objc_msgSend, is also called - it does a dynamic lookup, where it goes to the list of functions and finds the one we need (which is represented as a selector).

    This dynamic lookup allows us to do some interesting stuff - we can change the list at will. We can move values so that selectors point to different code than what was written. Additionally, the runtime asks objects if it recognizes methods before it actually sends a message. An object can then choose if it even wants to respond to that message.

    In short, when calling a method, there is little ambiguity - we know who is performing the action. The object did something.
    However, when we send a message, that ambiguity does exist. Something was done by the object. The emphasis is no longer on the object, but rather that “something” was done - when we send a message, we can’t be entirely sure what will respond, since dynamic lookup allows us to change certain things about our list of functions. The focus is more on the message itself.

Data Structures - Stacks & Queues

Today we're going to talk about stacks and queues - two abstract data types that just use data structures (arrays or linked lists) under the hood. For Objective-C support, head near the bottom of the post.

   LIFO (stack) vs FIFO (queue)

 

LIFO (stack) vs FIFO (queue)

To visualize a stack, think of a stack of dishes - you wash the first one, dry it, and place it on a table. Every other dish that is washed and dried is placed on top of this first one, creating a stack. Which dish comes off first when it's time to put them away? The conventional way to do it would be to pull the topmost item off of the stack and put it away. This explains the protocol followed by stacks which is LIFO, or last in, first out. The last item to go on the stack (dish at the top) is the first to come out.

Stacks are simple because you can generally perform three operations - push (add something to the top of the stack), pop (you can take something off the top of the stack), and peek (you can see what item is at the top of the stack without doing anything to it). They're sort of a wrapper around an array or linked list with limitations on what operations can be performed.

The term "stack" can also refer to a concept involving memory allocation - see the bottom of the post for information on this.

Queues can be visualized by thinking of a line in a store - the first person to get on line is the first person to be serviced at the counter. This data type follows the FIFO protocol - first in, last out. The first person in line is the last person to get out of the line. Often times, queues are used in concurrency situations - you can create queues to order processes and control what process runs when.

*In the context of this blog, we are talking about heaps and stacks as they exist within the realms of CPU memory. Keep in mind, however, that heap may also refer to the tree-based data structure, entirely separate from CPU memory. Heaps can be max or min heaps; there is a lot to learn about them, so we will not be covering them as data structures in this blog series.

OBJECTIVE-C SUPPORT:

Stacks are not explicitly supported in Objective-C, but they are simple enough to implement with, say, an NSMutableArray. You can add a category to the NSMutableArray class and add methods for pop, push and peek; it's that simple.

Queues are supported in Objective-C in a few ways: NSOperationQueue/NSOperations, and Grand Central Dispatch (GCD). GCD is lower-level than NSOperationQueue, and is written in C; however, it is important to understand that although it adds another layer of abstraction, NSOperationQueue uses GCD under the hood. You can also implement a queue yourself similarly to how we discussed doing so for a stack using a mutable array.

GCD provides queue implementation for use with many things, concurrency being one of them; it does so in the form of blocks (read up on them!). Both allow for priority queues, meaning you can insert processes to run into the middle of an existing queue by setting its priority.

Whether to use GCD vs NSOperationQueue is a point of contention, but it should be noted that GCD is much more light-weight than NSOperationQueue. It involves no thread-safety locking mechanisms, and is less taxing on the CPU. As such, some developers prefer to use it, as long as it suits their needs and they require none of the higher-level functionality of NSOperationQueue.

*In following convention, UI updates should happen on the main queue, and other processes should be executed on background queues. This ensures that there is minimal (or no) lag for the end-user of an application.

Left for review are hash tables, trees and a brief introduction to graphs. I will try and be brief with the last two so that we can move on to more iOS specific concepts.

 

Perhaps without realizing it, programmers use stacks every day in coding - the stack refers to a place in computer memory (along with the heap). The heap refers to memory on the CPU dedicated to items that are explicitly allocated memory in a program. It is up to the programmer to release the memory holding onto those objects when they're no longer needed. Heap memory is accessed using pointers (or some other reference), and as such, it is somewhat slow to read/write to. The stack, on the other hand, is an abstract data type used to "manage" a region of CPU memory that stores temporary variables which are created by functions. When we refer to "the stack", we are talking about the region of memory (versus just "a stack" which refers to some instance of the data type). Whenever we enter a function, all variables created are pushed onto a stack frame, which itself sits on the stack. A new stack frame exists for each function. When a function exits, the frame is popped off of the top; once a stack variable is freed, that piece of memory becomes available for other stack variables. FOR A LIST OF PROS AND CONS BETWEEN STACKS AND HEAPS, REFER TO THE BOTTOM OF THIS POST.

HEAP

PROS:

  • Variables can be globally accessed
  • There is no limit on memory size (limitations set by CPU)

CONS:

  • Relatively slow access
  • Programmer is in charge of allocating and deallocating variables
  • Efficiency regarding use of memory is not guaranteed.

STACK

PROS:

  • Fast access
  • Don't need to explicitly deallocate variables
  • Memory won't become fragmented from deallocation (efficient use of memory)

CONS:

  • Access to local variables (within function) only
  • There are limitations on size of the stack