Which I believe is the important distinction, and quite often it doesn’t know or care “which allocations to free” because it does it in bulk. That allows it to be efficient.
But my original point was just that it's interesting that there is an extra step at all in the C++ case, where we tend to think of collection as happening "for free". It has a constant-time overhead, which is not the same as zero overhead.
During _collection_ and N is size of live set, so divided by allocation the cost is amortized and can safely considered as O(1) much like appending a dynamic array where costly O(N) resize is amortized over N appends.
Typically GCs allocate via bump a pointer allocation which is actually faster then what pretty much all of libc malloc implementations would do.
> C++ case iterates over nothing (incurring a cost of O(1)).
Not quite, take a look at jemalloc paper for instance:
https://www.facebook.com/notes/facebook-engineering/scalable...
A lookup to get the metadata for this specific allocation could be anything from O(1) to O(lgN) depending on size and malloc strategy.