Demonstration of garbage collection being faster than manual memory management

I have to disagree with the basic premise.

C++ (to use your example, though the same would apply to C, Pascal, Ada, etc.) doesn't give any real visibility into the heap. You can attempt to allocate some memory, which might succeed or fail -- but you have no visibility into why an allocation succeeded or failed, nor what other allocations may have lead to that success/failure.

In other words, allocating some memory in one place does not have an effect that's directly visible anywhere else. Yes, it's possible one allocation could lead to the failure of another, but 1) noting in portable C++ can put those together, and 2) it's usually next to impossible to make that connection even in a non-portable way.

In the other direction, nothing in Haskell (or any other language) can change the fundamentals involved anyway. Attempting to allocate more memory than is available (even as virtual address space) will fail, regardless of the language. If the user runs another program that hogs all the memory, neither C++ or Haskell (or much of anything else) can do much about that, so an allocation that would succeed in one run may fail in another.

In fairness, I suppose I should add that even though it's not portable, many (most?) heap managers include extra functions to walk the current heap, see what blocks are allocated, etc. Yes, I suppose such a thing could be seen as breaking "purity", but my guess is that people including heap-walking in their software probably aren't bothered a lot by that (and those who really care about purity just don't use that capability.

The fundamental observations which allow generational garbage-collection to avoid having to scan all older-generation objects are:

1. After a collection, all objects that still exist will be of some minimum generation (e.g. in .net, after a Gen0 collection, all objects are Gen1 or Gen2; after a Gen1 or Gen2 collection, all objects are Gen2).
2. An object, or portion thereof, which has not been written since a collection that promoted everything to generation N or higher cannot contain any references to objects of lower generations.
3. If an object has reached a certain generation, it need not be identified as reachable to ensure its retention when collecting lower generations.

In many GC frameworks, it's possible for the garbage collector to flag objects or portions thereof in such a way that the first attempt to write to them will trigger special code to record the fact that they have been modified. An object or portion thereof which has been modified, regardless of its generation, must be scanned in the next collection, since it may contain references to newer objects. On the other hand, it's very common for there to be a lot of older objects that do not get modified between collections. The fact that lower-generation scans can ignore such objects can allow such scans to complete much more quickly than they otherwise would.

Note, btw, that even if one cannot detect when objects are modified and would have to scan everything on each GC pass, generational garbage collection could still improve the "sweep" stage performance of a compacting collector. In some embedded environments (especially those where there is little or no difference in speed between sequential and random memory accesses), moving blocks of memory around is relatively expensive compared to tagging references. Consequently, even if the "mark" phase can't be sped up using a generational collector, speeding up the "sweep" phase may be worthwhile.