Hacker News Reader

Comment by DanielHB | Hacker News Reader

My gut feeling agrees with you but I would really like more detailed reasons why this is the case. Is memory fragmentation that big of an issue? Are heap allocations more expensive somehow (even if memory is not fragmented yet)? Is there something else? Does re-arranging memory in the heap makes performance unpredictable like GC languages?

View on HN

Memory allocation is slow and undeterministic in perf. Some allocations also require a global lock on the system level. It’s also a point of failure if the allocation doesn’t succeed, so there’s an extra check somewhere. Furthermore if every object is a pointer you get indirection overhead (even though small but existent). Deallocation as well incurs an overhead. Without a compacting gc you run into memory fragmentation which further aggravate the issue. All of this overhead can be felt in tight loops.

Due to the quick fit algorithm, fragmentation is no longer an issue for memory allocators. Heap allocations are still a bit slower than stack allocations since you need some way to release memory. Stack allocations are released at virtually zero cost (one assembly instruction). Hence sophisticated compilers perform escape analysis to convert heap allocations into cheaper stack allocations. But escape analysis, like all program analysis, is conservative and wont convert as many allocations as a human programmer could.

However, in the grand scheme of things heap vs stack allocation is minuscule. Many other factors are much more important for performance.

For one thing, allocating every object on the heap leads to a lot of cache misses because the data you're working with is not contiguous in memory. It may also make it harder for the CPU to do speculative fetches from memory because it needs to resolve the value of a pointer before it knows where to fetch data. With the stack, the address is much more obvious since it's all constant offsets relative to the frame pointer.

Also, heap allocation is unpredictable. It is more likely to cause unexpected page faults or thread congestion (multiple threads often share the same heap so they need to synchronize access to memory book-keeping structures). Especially when it comes to kernel drivers, a page fault can lead to a deadlock, infinite recursion, or timeouts.

I'm not saying heap is always bad, not even that it's bad most of the time. But if a language doesn't at least give you the _option_ of having objects live on the stack, I wouldn't consider it a serious systems programming language.

There is no inherent difference. It's all memory.

That said, as a sibling already pointed out, it's standard to control stack allocation with a single counter. It's kind of standard to control heap allocation with an index and a lot of book-keeping.

But you are allowed to optimize the heap until there's no difference.

Reply on news.ycombinator.com