3 ms·

GC doesn’t search for chunks that can be freed. Also “iteratively” - what do you mean by this? There is no known algorithm for GC that searches for garbage to

GC doesn’t search for chunks that can be freed. Also “iteratively” - what do you mean by this? There is no known algorithm for GC that searches for garbage to delete, the way GCs work is exactly opposite - find all live objects (reachable from roots - registers,stack, statics/globals) and the rest of the heap by definition is garbage.

_bxg1 7y ago
https://en.m.wikipedia.org/wiki/Tracing_garbage_collection https://en.m.wikipedia.org/wiki/Tracing_garbage_collection > tracing garbage collection is a form of automatic memory management that consists of determining which objects should be deallocated ("garbage collected") by tracing which objects are reachable by a chain of references from certain "root" objects, and considering the rest as "garbage" and collecting them So it starts at the root and, in a sense, "iterates" down through the reference tree to see which allocations are reachable, and then the inverse of that is freed. In the OP case, by contrast, "which allocations to free" is known at "collection" time, but there's still an extra step of actually doing the collection.
- DmitryOlshansky 7y ago
  The point is that tracing GC searches for things to keep and assumes the rest is free. 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.
  - _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.
UncleMeat 7y ago
Tracing gc works this way. But reference counting gc exists, even if it isn’t widely used in gced languages. Ref counting finds garbage directly.

_bxg1 7y ago

https://en.m.wikipedia.org/wiki/Tracing_garbage_collection https://en.m.wikipedia.org/wiki/Tracing_garbage_collection > tracing garbage collection is a form of automatic memory management that consists of determining which objects should be deallocated ("garbage collected") by tracing which objects are reachable by a chain of references from certain "root" objects, and considering the rest as "garbage" and collecting them So it starts at the root and, in a sense, "iterates" down through the reference tree to see which allocations are reachable, and then the inverse of that is freed. In the OP case, by contrast, "which allocations to free" is known at "collection" time, but there's still an extra step of actually doing the collection.

DmitryOlshansky 7y ago
The point is that tracing GC searches for things to keep and assumes the rest is free. 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.
- _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.

UncleMeat 7y ago

Tracing gc works this way. But reference counting gc exists, even if it isn’t widely used in gced languages. Ref counting finds garbage directly.