Search code examples
c++timeheap-memoryallocationstack-memory

Why is there no time cost to large stack allocations

I tried this quick-bench test and I'm finding that it's the same cost timewise to allocate 200 bytes as it is to allocate 2000000 bytes.

allocation timings

How could that possibly be?

Solution

  • Why is there no time cost to large stack allocations

    Allocation need not be anything more than an accounting procedure. For stack allocation, nothing more may be necessary than changing the value of the stack pointer. Adding 2,000,000 to the value of the stack pointer does not take more time than adding 200.

    Once the stack is changed, there may be consequences from that. The program, which you have not shown, may go on to use memory around the new location of the stack pointer. The first use of such memory may incur some overhead if it is in a newly used virtual memory page, as the hardware will trigger an exception, and the operating system will provide physical memory for the page. However, this occurs as the memory is used and will be much the same whether 2,000,000 or 20,000,000 bytes are allocated. Compared to 200 bytes, it might or might not be the same, as the change by 200 bytes might or might not move the stack pointer into a new page.

    Attempting to use the newly allocated memory is a different matter, as the costs for reading or writing memory are generally linear in the amount of memory used (and may involve merely hardware access to memory or may involve further operating system interventions, depending on circumstances).

    Allocation using malloc is much the same. The accounting will be more complicated than just changing the stack pointer, but it is still basically just examining and updating a few data structures with a low overhead time, not proportional to the amount of space allocated.