Stack and the difference between heap and stack

Stack: The stack is a "last in, first out" main memory area located in the stack segment, and uses the SS segment register to record its segment address. It has only one entrance and exit, namely the current stack top, which is the end with a smaller address (low end), which is specified by the stack pointer register SP. The stack has two basic operations in word units, corresponding to two basic instructions: the push instruction PUSH and the pop instruction POP.

Difference between heap and stack

1. Preliminary knowledge - program memory allocation

The memory occupied by a program compiled by C/C++ is divided into the following parts:

1. Stack area (stack) - automatically allocated and released by the compiler, storing function parameter values, local variable values, etc. Its operation is similar to the stack in the data structure.

2. Heap area (heap) - usually allocated and released by the programmer. If the programmer does not release it, it may be reclaimed by the OS when the program ends. Note that it is different from the heap in the data structure, and the allocation method is similar to a linked list.

3. Global area (static area) (static) - Global variables and static variables are stored together. Initialized global variables and static variables are in one area, and uninitialized global variables and uninitialized static variables are in another adjacent area. They are released by the system after the program ends.

4. Text constant area - constant strings are placed here and will be released by the system after the program ends.

5. Program code area - stores the binary code of the function body.

2. Example Program

This is written by a senior, very detailed

//main.cpp

int a = 0; Global initialization area

char *p1; global uninitialized area

main()

{

int b; stack

char s[] = "abc"; stack

char *p2; stack

char *p3 = "123456"; 123456 is in the constant area, and p3 is on the stack.

static int c =0; Global (static) initialization area

p1 = (char *)malloc(10);

p2 = (char *)malloc(20);

}

The allocated 10 and 20 byte areas are in the heap area.

strcpy(p1, "123456"); 123456 is placed in the constant area, and the compiler may optimize it into one place with the "123456" pointed to by p3.

Theoretical knowledge of heap and stack

1. Application method

stack:

Automatically allocated by the system. For example, declare a local variable int b in a function; the system automatically allocates space for b in the stack

heap:

The programmer needs to apply for it himself and specify the size. In C, the malloc function

For example, p1 = (char *)malloc(10);

Using the new operator in C++

For example, p2 = new char[20]; //(char *)malloc(10);

But note that p1 and p2 themselves are in the stack.

2. System response after application

Stack: As long as the remaining space of the stack is larger than the requested space, the system will provide memory for the program, otherwise it will report an exception indicating stack overflow.

Heap: First of all, you should know that the operating system has a linked list that records free memory addresses. When the system receives an application from a program, it will traverse the linked list to find the first heap node whose space is larger than the space requested, and then delete the node from the free node linked list and allocate the node's space to the program. In addition, for most systems, the size of this allocation will be recorded at the first address in this memory space, so that the delete statement in the code can correctly release this memory space. In addition, since the size of the found heap node is not necessarily exactly equal to the size requested, the system will automatically put the excess part back into the free linked list.

3. Application size limit

Stack: In Windows, the stack is a data structure that extends to lower addresses and is a continuous memory area. This means that the address of the top of the stack and the maximum capacity of the stack are pre-determined by the system. In Windows, the size of the stack is 2M (some say 1M, anyway, it is a constant determined at compile time). If the requested space exceeds the remaining space of the stack, an overflow will be prompted. Therefore, the space available from the stack is small.

Heap: The heap is a data structure that expands toward higher addresses and is a discontinuous memory area. This is because the system uses a linked list to store free memory addresses, which is naturally discontinuous, and the traversal direction of the linked list is from low addresses to high addresses. The size of the heap is limited by the effective virtual memory in the computer system. Therefore, the space obtained by the heap is more flexible and larger.

4. Comparison of application efficiency

The stack is automatically allocated by the system and is faster, but programmers cannot control it.

The heap is memory allocated by new, which is generally slow and prone to memory fragmentation, but it is the most convenient to use.

In addition, under Windows, the best way is to use VirtualAlloc to allocate memory. It does not allocate memory on the heap or stack, but directly reserves a piece of memory in the process address space. Although it is the most inconvenient to use, it is fast and the most flexible.

5. Storage content in the heap and stack

Stack: When a function is called, the first thing pushed onto the stack is the address of the next instruction after the function call in the main function (the next executable statement after the function call statement), followed by the various parameters of the function. In most C compilers, the parameters are pushed onto the stack from right to left, followed by the local variables in the function. Note that static variables are not pushed onto the stack.

When the function call ends, the local variables are popped off the stack first, followed by the parameters, and finally the top pointer points to the address where the data was initially saved, which is the next instruction in the main function, and the program continues to run from this point.

Heap: Generally, one byte is used at the head of the heap to store the size of the heap. The specific contents of the heap are arranged by the programmer.

6. Comparison of access efficiency

char s1[] = "aaaaaaaaaaaaaaa";

char *s2 = "bbbbbbbbbbbbbbbb";

aaaaaaaaaaaa is assigned at runtime;

And bbbbbbbbbbb is determined at compile time;

However, on subsequent accesses, the array on the stack is faster than the string pointed to by the pointer (such as the heap).

for example:

#include

void main()

{

char a = 1;

char c[] = "1234567890";

char *p = "1234567890";

a = c[1];

a = p[1];

return;

}

The corresponding assembly code

10: a = c[1];

00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]

0040106A 88 4D FC mov byte ptr [ebp-4],cl

11: a = p[1];

0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]

00401070 8A 42 01 mov al,byte ptr [edx+1]

00401073 88 45 FC mov byte ptr [ebp-4],al

The first method directly reads the elements in the string into register cl when reading, while the second method first reads the pointer value into edx, and then reads the characters according to edx, which is obviously slower.

7. Summary:

The difference between the heap and the stack can be seen with the following metaphor:

Using a stack is like going to a restaurant to eat. We just order (submit an application), pay, and eat (use). When we are full, we leave. We don’t have to worry about the preparatory work such as cutting and washing vegetables, and the finishing work such as washing dishes and cleaning pots. Its advantage is that it is fast, but it has little freedom.

Using a heap is like cooking your favorite dish by yourself. It is more troublesome, but it is more in line with your taste and has a greater degree of freedom.

The main differences between the heap and the stack are:

The heap and stack in the operating system are as mentioned above, so I won’t go into details.

There are also heaps and stacks in data structures, which are different concepts. The heap here actually refers to a data structure of a priority queue (satisfying the heap property), where the first element has the highest priority; the stack is actually a mathematical or data structure that satisfies the last-in-first-out property.

Although the two words "stack" are called together, there are still big differences between them. The reason they are called together is just due to historical reasons.

Distribution of heap and stack ​

Replenish

A stack is a storage component that does not require an address to be provided for writing and reading data. Instead, the order of reading is determined by the order of writing.