8

As far as I can see, stack memory is contiguous in virtual memory address, but stack memory is also contiguous physically? And does this have something to do with the stack size limit?

Edit:

I used to believe that stack memory doesn't has to be contiguous physically, but why do we think that stack memory is always quicker than heap memory? If it's not physically contiguous, how can stack take more advantage of cache? And there is another thing that always confuse me, cpu executes directives in data segment, which is not near the stack segment in virtual memory, I don't think the operating system will make stack segment and data segment close to each other physically, so this might do harm to the cache effect, what do you think?

Edit again: Maybe I should give an example to express myself better, if we want to sort a large amount of numbers, using array to store the numbers is better than using a list, because every list node may be constructed by malloc, so it may not take good advantage of cache, that's why I say stack memory is quicker than heap memory.

7
  • 2
    We have virtual memory, not to care about physical memory layout. If you are not writing kernel or drivers (or designing hardware, or designing attacks to the cache) forget about physical memory. Commented Apr 1, 2018 at 5:13
  • 2
    Nah - process/thread stacks can be, and often are, paged out like any other virtual memory. Kernel stacks, as used for interrupt-handling, must be non-paged. Commented Apr 1, 2018 at 5:35
  • 2
  • @jww I have edited my question to show my real confusion, if you got an answer, please post your answer below or add a comment, thank you very much.
    – cong
    Commented Apr 1, 2018 at 8:47
  • 1
    On most architectures the stack can be grown or shrunk with a simple arithmetic instruction. malloc is a call to a function that needs to bookkeep an area of memory, eventually allocating new pages. That costs a lot. Simply put, the stack is a more restrictive data structure. Caching has little to do with it, the top of the stack is almost always hot in the caches because it is used very frequently but it is easy to construct a function that kicks it out of the caches. Commented Apr 4, 2018 at 11:32

4 Answers 4

11

As far as I can see, stack memory is contiguous in virtual memory address, but stack memory is also contiguous physically? And does this have something to do with the stack size limit?

No, stack memory is not necessarily contiguous in the physical address space. It's not related to the stack size limit. It's related to how the OS manages memory. The OS only allocates a physical page when the corresponding virtual page is accessed for the first time (or for the first time since it got paged out to the disk). This is called demand-paging, and it helps conserve memory usage.

why do we think that stack memory is always quicker than heap memory? If it's not physically contiguous, how can stack take more advantage of cache?

It has nothing to do with the cache. It's just faster to allocate and deallocate memory from the stack than the heap. That's because allocating and deallocating from the stack takes only a single instruction (incrementing or decrementing the stack pointer). On the other hand, there is a lot more work involved into allocating and/or deallocating memory from the heap. See this article for more information.

Now once memory allocated (from the heap or stack), the time it takes to access that allocated memory region does not depend on whether it's stack or heap memory. It depends on the memory access behavior and whether it's friendly to the cache and memory architecture.

if we want to sort a large amount of numbers, using array to store the numbers is better than using a list, because every list node may be constructed by malloc, so it may not take good advantage of cache, that's why I say stack memory is quicker than heap memory.

Using an array is faster not because arrays are allocated from the stack. Arrays can be allocated from any memory (stack, heap, or anywhere). It's faster because arrays are usually accessed contiguously one element at a time. When the first element is accessed, a whole cache line that contains the element and other elements is fetched from memory to the L1 cache. So accessing the other elements in that cache line can be done very efficiently, but accessing the first element in the cache line is still slow (unless the cache line was prefetched). This is the key part: since cache lines are 64-byte aligned and both virtual and physical pages are 64-byte aligned as well, then it's guaranteed that any cache line fully resides within a single virtual page and a single physical page. This what makes fetching cache lines efficient. Again, all of this has nothing to do with whether the array was allocated from the stack or heap. It holds true either way.

On the other hand, since the elements of a linked list are typically not contiguous (not even in the virtual address space), then a cache line that contains an element may not contain any other elements. So fetching every single element can be more expensive.

2
  • One more question: why is stack memory limited for like 8M in Linux?
    – cong
    Commented Apr 6, 2018 at 4:23
  • 1
    @cong So that a stack overflow crashes only the offending application without consuming all of the memory of the system, which may crash the whole system itself. Typically, applications are not expected to allocate large amounts of memory from the stack at the same time. Large objects should be allocated from the heap.
    – Hadi Brais
    Commented Apr 6, 2018 at 15:08
3

Memory is memory. Stack memory is no faster than heap memory and is no slower. It is all the same. The only thing that makes a memory a stack or a heap is how it is allocated by the application. It is entirely possible to allocate a memory on the heap and make that the program stack.

The speed difference is in the allocation. Stack memory is allocated by subtracting from the stack pointer: one instruction.

The process of allocating heap depends upon the heap manager but it is much more complex and may requiring mapping pages to the address space.

2
  • 1. maybe I should give an example to express myself better, if we want to sort a large amount of numbers, using array to store the numbers is better than using a list, because every list node may be constructed by malloc, so it may not take good advantage of cache, that's why I say stack memory is quicker than heap memory. 2. it is much more complex and may requiring mapping pages to the address space, so as for stack, I think stack memory must have entries in page tables, so when will mapping pages to the address space happen for stack memory.
    – cong
    Commented Apr 1, 2018 at 12:47
  • When you're down to outguessing the cache, your in trouble in programming. Memory is memory so the cache manager in the CPU cannot even tell the difference between heap and cache. Commented Apr 1, 2018 at 13:23
2

No, there is no promise of contiguity of physical addresses. But it doesn't matter, because user-space programs don't use physical addresses, so have no idea that this is the case.

5
  • I have edited my question to show my real confusion, if you got an answer, please update you answer, thank you very much.
    – cong
    Commented Apr 1, 2018 at 8:41
  • 1
    @cong: An L1 cache line is commonly 64 bytes but a single VM page is commonly 4096 bytes. So the idea that stack performance would increase by physical memory contiguity doesn't hold any water, because at the level of one cache line, memory is always physically contiguous. I think most of your new questions can be answered as "No, that's not how it works," and you'll need to start reading about how caches work in modern processors. Commented Apr 1, 2018 at 10:34
  • So, why do we always say stack memory quicker than heap memory? I think this must have something to do with cache, is it because heap memory is not contiguous physically?
    – cong
    Commented Apr 1, 2018 at 12:10
  • I know memory accessing itself is same for heap and stack, I can give an example to express myself better, if we want to sort a large amount of data, using array to store the data is better than using a list, because every list node may be constructed by malloc, so it may not take good advantage of cache, that's why I say stack memory is quicker than heap memory.
    – cong
    Commented Apr 1, 2018 at 12:41
  • 1
    @cong: Stack memory is not quicker than heap memory in terms of usage. It's only quicker in terms of allocation. Allocating on the stack is just incrementing the stack pointer. Allocating on the heap, in the worst case, requires a syscall (sbrk or mmap). Commented Apr 2, 2018 at 12:40
1

It is a complex topic.

Heap and stack have (usually) the same memory and memory type (MTRR, cache setting per page, etc.). [mmap, files, drivers could have different strategies, or when user explicit change it].

Stack could be faster, because it is often used. When you call a function, parameters and local variables are put into stack, so the cache is fresh. Additionally, because functions call and return often, probably there is some more stack in the other cache level, and seldom the top of stack is paged (because it was used recently).

So cache could be faster, but just if you have few variables. If you allow large arrays on stack e.g. with alloca, the advantage disappear.

In general, this is a very complex topic, and it is better not to optimize too much, because it could cause complex code, so more difficult to refactor and high level optimization of code. (e.g. on multi-dimentional arrays, the order of indices (and so memory) and loops could improve sensible the speed, but also quickly the code will be impossible to maintain).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.