3 ms·
No, the important distinction is that typically GC iterates over something (incurring a cost of O(N)), whereas the C++ case iterates over nothing (incurring a c
by _bxg1 7y ago
No, the important distinction is that typically GC iterates over something (incurring a cost of O(N)), whereas the C++ case iterates over nothing (incurring a cost of O(1)).
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.
- DmitryOlshansky 7y ago> important distinction is that typically GC iterates over something (incurring a cost of O(N)) 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-memory-allocation-using-jemalloc/480222803919/ 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.