Hacker News Reader

Allocation on the stack is changing the stack pointer, space efficient heap allocation usually involves tracing through a bunch of tables to find space. It's the initialization that gets you, especially complex object construction, in either case.

View on HN

umm, for stop and copy and compact memory management, heap allocation is just a pointer increment

Exactly. In .NET heap allocations are practically as fast as stack allocations, although of course there are other things you need to be aware of when using a compacting generational GC, such as avoiding medium-lived objects at all costs. .NET does also provide value-types that can be allocated on the stack, and you use them for reasons that are better than "heap allocations are slow".

I think the moral of the story is: to get the maximum performance out of your memory management system, you need to know how it works. This applies equally well to C++.

Incrementing a pointer is an op. Doing it in a loop takes O(N) time, doing it in a nested loop takes O(N^2) time. These are the timings the author of the article considered terrible for heap allocation. If you have to trace through some tables, then allocating objects in a loop is not O(N), but rather some much more complex big-O, which would have to take into account things like how many objects have been allocated elsewhere and the time complexity of traversing the tables or whatever. Granted, he was wrong about the complexity here, but that is my entire point, he makes up all sorts of wrong facts.

Reply on news.ycombinator.com