How to use heap and stack in iOS

Both heap and stack are data structures where data items are arranged in order, and data items can only be inserted and deleted at one end (called the top of the stack). Heap means queue priority, first in first out (FIFO); stack means first-in/last-out (FILO). Generally speaking, if someone says stack together, it means stack, not heap.

Stack space allocation

1. Stack: It is automatically allocated and released by the compiler to store function parameter values, local variables, etc. Its operation is similar to the stack in the data structure.
2. Heap: Generally allocated and released by programmers. If programmers do not release it, it may cause memory leaks. It is similar to a linked list.

Stack Cache Mode

The computer memory used by applications in iOS is not uniformly allocated. The space used by running code is in three different memory areas, divided into three segments: "text segment", "stack segment", and "heap segment".

Text segment: It is the memory segment where the application code exists when the application is running. It is determined before running (determined at compile time) and is usually read-only. The instructions in the text segment include the operation code and the object to be operated (or the object address reference). The instructions in the text segment are executed in sequence according to the program design process. Every instruction, every single function, procedure, method and execution code are stored in this memory segment until the application exits. It is rarely involved in general use.

Stack: When we create a value type, such as a structure, the system stores it in a memory area called the stack, which is directly managed and optimized by the CPU. When a function declares a variable, the variable will be stored in the stack, and the stack will automatically release the variable when the function call is completed. Therefore, the stack is very easy to manage and efficient, and because it is directly controlled by the CPU, it is very fast.

Heap: When we create a reference type, such as a class, the system will store the class instance in a memory area called the heap. The system uses the heap to store data that is referenced by other objects. The heap is a large memory pool from which the system can request and dynamically allocate memory blocks. The heap does not automatically release objects like the stack, requiring additional work to do so. This makes creating and deleting data in the heap slower than the stack.

The stack uses the first-level cache. They are usually in the storage space when they are called and released immediately after the call. The heap is stored in the second-level cache, and its life cycle is determined by the garbage collection algorithm of the virtual machine (not once an object becomes an orphan, it can be recycled). Therefore, the speed of calling these objects is relatively slow.

A pointer in the stack is just an integer variable that stores data at a specific memory address in the heap. In short, the operating system uses the pointer value in the stack segment to access objects in the heap segment. If the pointer to the stack object is gone, the objects in the heap cannot be accessed. This is also the reason for memory leaks.

You can create data objects in both the stack and heap segments of the iOS operating system. The advantages of stack objects are fast creation speed and simple management. They have a strict life cycle. The disadvantage of stack objects is that they are not flexible. They are always the same length as when they were created, and their owner is always the function that created them. Unlike heap objects, which have multiple owners, multiple owners are equivalent to reference counting. Only heap objects are managed using the "reference counting" method.

Differences between stack data structures

• Heap (data structure): A heap can be viewed as a tree, such as heap sort.
• Stack (data structure): A first-in, last-out data structure.

What is the difference between the heap and the stack? The main differences are as follows:

1. Different management methods;

Management method: For the stack, it is automatically managed by the compiler and does not require manual control; for the heap, the release work is controlled by the programmer, which is prone to memory leaks.

2. Different space sizes;

Space size: The stack is a small but fast memory area. The memory allocation on the stack follows the last-in-first-out principle, and push and pop operations are implemented by moving the tail pointer of the stack. Our program is composed of methods, and the CPU is responsible for scheduling and executing these methods. When our program executes a method, it is necessary to open up space on the stack for the memory required by the method. At this time, the tail pointer of the stack is moved to the bottom of the stack. When the method is executed, the space needs to be released. At this time, the tail pointer of the stack will be moved to the top of the stack, which completes the memory allocation on the stack. As long as the remaining space on the stack is larger than the space requested to be created by the stack object, the operating system will provide this memory space for the program, otherwise an exception will be reported to indicate a stack overflow.

The heap is another area in the memory that has much more space than the stack, but runs slower than the stack. The heap can dynamically allocate memory at runtime to make up for the lack of memory allocated on the stack. Generally speaking, in a 32-bit system, the heap memory can reach 4G of space. From this perspective, the heap memory is almost unlimited.

The operating system uses a linked list to manage the memory heap segment. The operating system has a linked list that records free memory addresses. When receiving an application from a program, it traverses the linked list to find the first heap node with a space larger than the requested space, then deletes the node from the free node linked list and allocates the node's space to the program. iOS uses a technology called ARC (Automatic Reference Counting). In a multi-threaded environment, multiple threads share memory on the heap. In order to ensure thread safety, locking operations have to be performed on the heap, but locking operations are very performance-intensive. The data security you get on the heap is actually obtained at the expense of performance.

NSString objects are objects in the stack, and NSMutableString objects are objects in the heap. The length of memory allocated to the former is fixed and cannot be modified when it is created; the length of memory allocated to the latter is variable, can have multiple owners, and is suitable for count management memory management mode.

3. Whether or not fragments can be generated;

Fragmentation problem: For the heap, frequent new/delete will inevitably cause discontinuity of the memory space, resulting in a large amount of fragmentation and reducing program efficiency. For the stack, this problem does not exist, because the stack is a first-in-last-out queue, and they are so one-to-one that it is impossible for a memory block to be popped out of the middle of the stack before it is popped out.

4. Different growth directions;

Growth direction: For the heap, the growth direction is upward, that is, in the direction of increasing memory address; for the stack, its growth direction is downward, that is, it grows in the direction of decreasing memory address.

5. Different distribution methods;

Allocation method: The heap is dynamically allocated, there is no statically allocated heap. There are two ways to allocate the stack: static allocation and dynamic allocation. Static allocation is done by the compiler, such as the allocation of local variables. Dynamic allocation is allocated by the alloca function, but the dynamic allocation of the stack is different from the heap. Its dynamic allocation is released by the compiler and does not need to be implemented manually.

6. Different allocation efficiency;

Allocation efficiency: The stack is a data structure provided by the machine system. The computer will provide support for the stack at the bottom level: a special register is allocated to store the address of the stack, and there are special instructions to execute the stack push and pop, which determines the high efficiency of the stack. The heap is provided by the C/C++ function library, and its mechanism is very complex. For example, in order to allocate a piece of memory, the library function will search for available space of sufficient size in the heap memory according to a certain algorithm (the specific algorithm can be referred to the data structure/operating system). If there is not enough space (probably due to too much memory fragmentation), it is possible to call the system function to increase the memory space of the program data segment, so that there is a chance to allocate enough memory and then return. Obviously, the efficiency of the heap is much lower than that of the stack.

From here we can see that compared with the stack, the heap is prone to cause a lot of memory fragmentation due to the use of a large number of new/delete; the efficiency is very low due to the lack of special system support; and the cost of memory application becomes more expensive due to the possible switching between user mode and kernel mode. Therefore, the stack is the most widely used in programs. Even function calls are completed using the stack. The parameters, return address, and local variables in the function call process are all stored in the stack. Therefore, we recommend that you use the stack instead of the heap as much as possible.

But the disadvantage is that the size and lifetime of the data in the stack must be fixed, which lacks flexibility. In addition, stack data cannot be shared between multiple threads or multiple stacks, but multiple variables with equal values ​​inside the stack can point to the same address. Compared with the heap, it is not so flexible. Sometimes it is better to use the heap to allocate a large amount of memory space. Whether it is the heap or the stack, you must prevent the occurrence of cross-border phenomena (unless you deliberately make it cross-border), because the result of the cross-border phenomenon is either a program crash or the destruction of the program's heap and stack structures, resulting in unexpected results. Even if the above problems do not occur during the running of your program, you still have to be careful, because it may crash at any time.

Usage in Swift

The data types in Swift are divided into reference types (classes) and value types (enumerations, structures). Reference types are stored on the "heap" and value types are stored on the "stack". Swift manages reference types using the automatic reference counting (ARC) management method. Value types are managed by the processor and do not require management by the programmer.

In Swift, typical struct, enum, and tuple are all value types. The commonly used Int, Double, Float, String, Array, Dictionary, and Set are actually implemented by structures and are also value types. In Swift, the assignment of value types is deep copy, and value semantics means that the new object and the source object are independent. When the properties of the new object are changed, the source object will not be affected, and vice versa.

In Swift, classes and closures are reference types. Reference type assignment is shallow copy, and reference semantics means that the variable names of the new object and the source object are different, but their references (the memory space they point to) are the same, so when the new object is used to operate its internal data, the internal data of the source object will also be affected.

When a value type is passed as a parameter, its value cannot be modified inside the function body. When a reference type is passed as a parameter, the memory address it points to cannot be modified inside the function body, but the variable value inside it can be modified.

The advantages of value types are: immutability, value type variables are strictly controlled by an owner; independence, reference types are interdependent, which is an implicit dependency; and interchangeability.

For object-oriented programming, since instance objects are mutable, another owner of the object can change the properties of the object when appropriate. Swift supports single inheritance of classes, which leads to inheritance of more functions from multiple classes, increases complexity, and causes the problem of tight coupling of classes. In multi-threaded situations, the same reference can be changed at the same time.

One of the main reasons to choose value types over reference types is that it makes your code simpler. Swift is protocol-oriented at its core, and reference types have many owners. A value type is assigned to a variable or constant, and its value is copied when it is passed to a function as a parameter. This allows a value type to have only one owner at any time, thereby reducing complexity. In any case, you can assume that your other code will not change it, which is often useful in a multi-threaded environment. If the data used in one thread is accidentally modified by another thread, this will usually cause very serious bugs and is quite difficult to debug. Class = high complexity, value = low complexity. In addition, Swift has made some optimizations on the operations of value types, so there is a saying that Swift uses value types instead of reference types extensively.

Since the difference between the two is only reflected when you need to modify the data, value types and reference types look exactly the same when your instances do not modify the data. You might want to write a completely immutable class, implement an immutable class in Swift by using immutable storage properties and avoiding exposing interfaces that modify data. In fact, most Cocoa classes, such as NSURL, are designed to be immutable classes. However, Swift currently does not provide any language mechanism to force a class to be immutable (for example, subclassing can modify the implementation of a class). Only structures and enumerations are forced to be immutable.

In Swift, Array, String, and Dictionary are all value types, and their behavior is similar to int in C language. Each instance has its own data, and you don't need to do anything extra, such as making an explicit copy to prevent other code from modifying it without your knowledge, etc. More importantly, you can safely pass it between threads without using synchronization technology. In the spirit of improving safety, this model will help you write more predictable code in Swift.

In addition, Swift and OC have other type correspondences, the corresponding relationships are as follows:

However, it is important to note that for the reference type of data in the original OC, Swift does not really implement a complete set of data storage logic. It only saves the reference to the OC object internally, so that the behavior logic and value type are consistent when accessing the Swift API.