Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

comparison of access performance of data in heap and stack

It is widely known common sense, that for most algorithms, allocating and deallocating data on the stack is much faster than doing so on the heap. In C++, the difference in the code is like

double foo[n*n]

vs.

double* foo = new int[n*n]

But there are any significant differences, when it comes to accessing and calculating with data that lie either on the heap or on the stack? I.e. is there a speed difference for

foo[i]

The code is ought to run on several different architectures, therefore try and measure will not work.

like image 853
shuhalo Avatar asked Aug 11 '10 06:08

shuhalo


People also ask

Is stack access faster than heap access?

What makes one faster? Stack is faster for the following reasons: access pattern : it is trivial to allocate and deallocate memory from it (a pointer/integer is simply incremented or decremented), while the heap has much more complex bookkeeping involved in an allocation or deallocation.

How much faster is the stack vs heap?

The stack is faster than the heap because stack memory is guaranteed to be released in the reverse order it is allocated. This makes it much easier to manage (no need to merge free areas for example) and optimizes the locality of memory accesses.

Is heap access slower?

Heap memory is slightly slower to be read from and written to, because one has to use pointers to access memory on the heap. We will talk about pointers shortly. Unlike the stack, variables created on the heap are accessible by any function, anywhere in your program. Heap variables are essentially global in scope.

Is accessing heap memory slow?

The processing time(Accessing time) of this memory is quite slow as compared to Stack-memory. Heap-memory is also not threaded-safe as Stack-memory because data stored in Heap-memory are visible to all threads. Size of Heap-memory is quite larger as compared to the Stack-memory.


3 Answers

There might be (highly system depending) issues about cache locality and read/write misses. If you run your program on the stack and heap data, then it is conceivable (depending on your cache architecture) that you to run into more cache misses, than if you run it entirely on one continuos region of the stack. Here is the paper to this issue by Andrew Appel (from SML/NJ) and Zhong Shao where they investigate exactly this thing, because stack/heap allocation is a topic for the implementation of functional languages:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3778

They found some performance problems with write misses but estimated these would be resolved by advances in caching.

So my guess for a contemporary desktop/server machine is that, unless you're running heavily optimized, architecture specific code which streams data along the cache lines, you won't notice any difference between stack and heap accesses. Things might be different for devices with small caches (like ARM/MIPS controller), where ignoring the cache can have noticeable performance effects anyway.

like image 102
Nordic Mainframe Avatar answered Sep 20 '22 07:09

Nordic Mainframe


The stack will be in the CPU cache more often, so that might be faster in some (most?) cases.

But the most precise answer is probably: it depends...

like image 29
Michel de Ruiter Avatar answered Sep 17 '22 07:09

Michel de Ruiter


Taken as single statements, it doesn't matter.
Little can be said without more context. There are a few effects in favor of the stack which are negligible virtually all of the time.

  • the stack is likely in the cache already, a freshly allocated heap block likely is not. However, this is a first execution penalty only. For significant amounts of data, you'd thrash the cache anyway

  • Stack allocation itself is a bit cheaper than heap allocation, because the allocation is simpler

  • Long term, the main problem of a heap is usually fragmentation, an "accumulated cost" that (usually) cannot be attributed to single allocations, but may significantly increase the cost of further allocations

Measuring these effects is tricky at least.

Recommendation: performance is not the decider here. Portability and Scalability recommend using the heap for all but very small amount of data.

like image 25
peterchen Avatar answered Sep 20 '22 07:09

peterchen