Basic concept of "Heap" and "Stack" (CC ++ beginner must read)

zhaozj2021-02-11  193

"Pile" and "Stack"

Author: arya

Heap and Stack (stack) is C / C programming inevitably two basic concepts that will encounter. First, both concepts can be found in the books of the data structure, they are all basic data structures, although the stack is simpler.

In the specific C / C programming framework, these two concepts are not parallel. Research on the underlying machine code can reveal that the stack is the data structure provided by the machine system, and the stack is provided by the C / C function library.

Specifically, modern computers (serial execution mechanisms) are directly supported by the stack in the code underlayer. This is reflected in that there is a special register point to the address where the stack is located, and there is a dedicated machine instruction to complete the operation of the stack out of the stack. This mechanism is characterized by high efficiency, limited data, generally integers, pointers, floating point numbers, etc., and other data types directly supported, and other data structures are not directly supported. Because this feature of the stack, the use of the stack is very frequent in the program. The call to the subroutine is done directly by the stack. The machine's CALL instruction implies to push the return address into the stack, then jump into the operation of the subroutine address, and the RET instruction in the subroutine is implied from the operation that ejaches the address and jumps from the stack. Automatic variables in C / C are examples of direct use stacks, which is why the function is automatically invalid when the function returns (because the stack restores the status before the call is recovered).

Unlike the stack, the data structure of the heap is not supported by the system (whether it is a machine system or operating system), but is provided by the function library. The basic Malloc / Realloc / Free function maintained a set of internal heap data structures. When the program uses these functions to get a new memory space, this set of functions first try to find available memory spaces from the internal stack. If there is no memory space available, try to utilize system calls to dynamically add the memory size of the program data segment. The newly assigned space is first organized into the internal heap, and then returns to the caller in an appropriate form. When the program releases the assigned memory space, this memory space is returned in the internal heap structure, which may be properly processed (such as incorporating other idle spaces into larger idle space) to make the next memory allocation application. This complex allocation mechanism is actually equivalent to a memory allocated buffer pool (Cache), using this mechanism has the following reasons:

1. System calls may not support any size memory allocation. Some systematic system calls only support fixed size and their multiple memory requests (by page assignment); this kind of waste will cause waste to a large number of small memory classifications.

2. System call requesting memory may be expensive. System calls may involve transformation of user-state and core states.

3. Memory allocation without management is easy to cause memory fragmentation under the distribution of complex memory.

Pile and stack comparison

From the above knowledge, the stack is the functionality provided by the system. It is characterized by fast and efficient, and the disadvantages are limited. The data is not flexible; and the stack is the function of the function library, which is flexible and convenient. The data adaptation is wide, but the efficiency has a certain decrease. . The stack is the system data structure, and the process / thread is unique; the stack is the internal data structure in the library, not necessarily unique. The memory logic of different stacks is not possible to operate. Stack space is static allocation and dynamic allocation. Static allocation is the completion of the compiler, such as auto variables (AUTO). Dynamic allocation is done by the alloca function. The dynamic assignment of the stack does not need to be released (it is automatically), and there is no release function. For the portable procedures, the dynamic allocation operation of the stack is not encouraged! The allocation of the stack is always dynamic. Although all data spaces are released back to the system at the end of the program, the exact application of memory / release memory is a basic element of a good program.

转载请注明原文地址:https://www.9cbs.com/read-4412.html

New Post(0)