7 ms·

This is the standard problem with tracing data structures to free them. You frequently run into it with systems based on malloc/free or reference counting. The

This is the standard problem with tracing data structures to free them. You frequently run into it with systems based on malloc/free or reference counting. The underlying problem is that freeing the structure takes time proportional to the number of pointers in the structure it has to chase. Generational/compacting GC has the opposite problem. Garbage collection takes time proportional to the live set, and the amount of memory collected is unimportant. It's actually a lot to be said for rust that the ownership system lets you transfer freeing responsibility off-thread safely and cheaply in order to not have it block the critical path. But overall, there's nothing really unexpected here, if you're familiar with memory management.

loufe 6y ago
I've not worked with any language thus far without automatic garbage collecting, so this was definitely a neat read for me. It sounds rather elegant.
- burpsnard 6y ago
  It's worth popping the hood and getting your fingers dirty. C was written in an era where memory was a scarce and precious resource to be grudgingly used if absolutely necessary
  - tsimionescu 6y ago
    Please note that C is quite a few years older than the first GC languages. LISP1.5, ALGOL-68 and APL all had garbage collectors before C even existed. Not to say that it's not worth it to learn manual memory management as well, but it is important not to think that GCs are a fancy modern tool, and that greybeards would never touch one. There were greybeards using punch cards and programming in a GC language, with output printed out on paper.
Reelin 6y ago
> the ownership system lets you transfer freeing responsibility off-thread safely and cheaply in order to not have it block the critical path This can also trivially be done in other languages. Atomically append your pointer to a queue of "large things that need to be freed" and move on as though you had actually called free. Within a particularly time sensitive loop you can even opt to place pointers into a preallocated array locally. Then once per loop iteration swap that array with the thread handling the deallocations for you. It eats up a bit of CPU time but can significantly reduce latency.
- jacobparker 6y ago
  OP said safely; what you're describing isn't safe in, say, C++ in the same sense that it is in Rust.
  - Reelin 6y ago
    Isn't that essentially a tautology? Manual memory management and threading in such languages lacks safety guarantees to begin with.
- im3w1l 6y ago
  A lot of C++ code depends on deallocation order for correctness. Like a destructor may want to say bye-bye to a pointed-to-object, and if you reverse order of deallocation, that pointer may be dangling. Consider this code { Window a; ClickHandler* b = new ClickHandler(&a); delete b; } Let's say b tries to deregister itself when it's deleted. This code will work as written. But if you defer the deletion of b, then stack allocated Window a may already be gone.
  - Reelin 6y ago
    I never meant to imply that you could use such tricks without considering the lifetimes of references. Manual memory management already requires being mindful of those though so it's nothing unique to the described situation. Yes Rust offers an advantage here, but it's the same one it offers everywhere else so it doesn't seem relevant to me. That being said, it seems like most cases where such an approach is worthwhile involve large nested data structures that involve lots of pointer chasing to traverse. All cases I've encountered so far were bulk stores that didn't involve actively interacting with external objects.
  - im3w1l 6y ago
    Replying to myself: I guess you could run the destructors in order, but keep the memory around a bit longer.
arcticbull 6y ago
> This is the standard problem with tracing data structures to free them. You frequently run into it with systems based on malloc/free or reference counting. The underlying problem is that freeing the structure takes time proportional to the number of pointers in the structure it has to chase. That doesn't seem to make intuitive sense. A GC has the same problem. A garbage collector has to traverse the data structure in a similar way to determine whether it (and it's embedded keys and values) are part of the live set or not, and to invoke finalizers. You're beginning your comparison after the mark step, which isn't a fair assessment since what Rust is doing is akin both both the mark and sweep phases. The only way to drop an extensively nested structure like this any faster than traversing it would be an arena allocator, and forgetting about the entire arena. The difference between a GC and this kind of memory management is that the GC does the traversal later, at some point, non-deterministically. Rust allows you to decide between deallocating it in place, immediately, or deferring it to a different thread.
- saagarjha 6y ago
  Usually in a background thread ;)
  - arcticbull 6y ago
    Indeed. The difference is this is happening deterministically, in place (with an optional deferral). A garbage collector has all sorts of different trade-offs.
- Reelin 6y ago
  > The only way to drop an extensively nested structure like this any faster than traversing it would be an arena allocator, and forgetting about the entire arena. Isn't that incompatible with RAII though?
  - arcticbull 6y ago
    You can handle this in Rust pretty neatly with lifetimes. There's a bunch of crates that do this. [1] [1] https://crates.io/crates/typed-arena https://crates.io/crates/typed-arena
Jasper_ 6y ago
One of my favorite papers by Bacon et al expands on this intuition that garbage collection and reference counting are opposite tradeoffs in many respects, and gives a formal theory for it. My views on gc/rc haven't been the same since. http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon04Unified.pdf http://researcher.watson.ibm.com/researcher/files/us-bacon/B...
- pron 6y ago
  That's a great paper, but one important thing to point out is that some production-grade tracing GCs are on the sophisticated end of that paper, while almost all reference counting GCs are on the rather primitive end. Given the same amount of effort, it's easier to get a reasonable result with reference-counting, but there are industrial-strength tracing GCs out there that have had a lot of effort put into them.
jeffdavis 6y ago
"Generational/compacting GC has the opposite problem. Garbage collection takes time proportional to the live set, and the amount of memory collected is unimportant." Takes time proportional the live set times the number of GC runs that happen while the objects are alive. In other words, the longer the objects live, the more GC runs have to scan that object (assuming there is enough activity to trigger the GC), and the worse GC looks.
- titzer 6y ago
  This is most decidedly not true for generational GCs, and for concurrent GCs, the tracing work happens asynchronously and in parallel, on other cores, not taking time on the main thread.
  - tsimionescu 6y ago
    It's still true for generational GC, but the costs are more complicated. Even objects in the oldest generation are periodically scanned in most implementations (though there are some, like Clozure CL's GC, that never scan the old generation automatically). But generational GCs do improve massively on this problem.
  - jeffdavis 6y ago
    You still have to scan the oldest generation at some point; otherwise (assuming some activity) you'll be leaking memory there over time. Moving the work to another core doesn't really change my statement. Aside: I wonder if it's feasible to switch to reference counting for the oldest generation? That would move the problem back to deallocation. I'm not sure if that's a good trade-off, but it would be interesting.

loufe 6y ago

I've not worked with any language thus far without automatic garbage collecting, so this was definitely a neat read for me. It sounds rather elegant.

burpsnard 6y ago
It's worth popping the hood and getting your fingers dirty. C was written in an era where memory was a scarce and precious resource to be grudgingly used if absolutely necessary
- tsimionescu 6y ago
  Please note that C is quite a few years older than the first GC languages. LISP1.5, ALGOL-68 and APL all had garbage collectors before C even existed. Not to say that it's not worth it to learn manual memory management as well, but it is important not to think that GCs are a fancy modern tool, and that greybeards would never touch one. There were greybeards using punch cards and programming in a GC language, with output printed out on paper.

Reelin 6y ago

> the ownership system lets you transfer freeing responsibility off-thread safely and cheaply in order to not have it block the critical path This can also trivially be done in other languages. Atomically append your pointer to a queue of "large things that need to be freed" and move on as though you had actually called free. Within a particularly time sensitive loop you can even opt to place pointers into a preallocated array locally. Then once per loop iteration swap that array with the thread handling the deallocations for you. It eats up a bit of CPU time but can significantly reduce latency.

jacobparker 6y ago
OP said safely; what you're describing isn't safe in, say, C++ in the same sense that it is in Rust.
- Reelin 6y ago
  Isn't that essentially a tautology? Manual memory management and threading in such languages lacks safety guarantees to begin with.
im3w1l 6y ago
A lot of C++ code depends on deallocation order for correctness. Like a destructor may want to say bye-bye to a pointed-to-object, and if you reverse order of deallocation, that pointer may be dangling. Consider this code { Window a; ClickHandler* b = new ClickHandler(&a); delete b; } Let's say b tries to deregister itself when it's deleted. This code will work as written. But if you defer the deletion of b, then stack allocated Window a may already be gone.
- Reelin 6y ago
  I never meant to imply that you could use such tricks without considering the lifetimes of references. Manual memory management already requires being mindful of those though so it's nothing unique to the described situation. Yes Rust offers an advantage here, but it's the same one it offers everywhere else so it doesn't seem relevant to me. That being said, it seems like most cases where such an approach is worthwhile involve large nested data structures that involve lots of pointer chasing to traverse. All cases I've encountered so far were bulk stores that didn't involve actively interacting with external objects.
- im3w1l 6y ago
  Replying to myself: I guess you could run the destructors in order, but keep the memory around a bit longer.

arcticbull 6y ago

> This is the standard problem with tracing data structures to free them. You frequently run into it with systems based on malloc/free or reference counting. The underlying problem is that freeing the structure takes time proportional to the number of pointers in the structure it has to chase. That doesn't seem to make intuitive sense. A GC has the same problem. A garbage collector has to traverse the data structure in a similar way to determine whether it (and it's embedded keys and values) are part of the live set or not, and to invoke finalizers. You're beginning your comparison after the mark step, which isn't a fair assessment since what Rust is doing is akin both both the mark and sweep phases. The only way to drop an extensively nested structure like this any faster than traversing it would be an arena allocator, and forgetting about the entire arena. The difference between a GC and this kind of memory management is that the GC does the traversal later, at some point, non-deterministically. Rust allows you to decide between deallocating it in place, immediately, or deferring it to a different thread.

saagarjha 6y ago
Usually in a background thread ;)
- arcticbull 6y ago
  Indeed. The difference is this is happening deterministically, in place (with an optional deferral). A garbage collector has all sorts of different trade-offs.
Reelin 6y ago
> The only way to drop an extensively nested structure like this any faster than traversing it would be an arena allocator, and forgetting about the entire arena. Isn't that incompatible with RAII though?
- arcticbull 6y ago
  You can handle this in Rust pretty neatly with lifetimes. There's a bunch of crates that do this. [1] [1] https://crates.io/crates/typed-arena https://crates.io/crates/typed-arena

Jasper_ 6y ago

One of my favorite papers by Bacon et al expands on this intuition that garbage collection and reference counting are opposite tradeoffs in many respects, and gives a formal theory for it. My views on gc/rc haven't been the same since. http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon04Unified.pdf http://researcher.watson.ibm.com/researcher/files/us-bacon/B...

pron 6y ago
That's a great paper, but one important thing to point out is that some production-grade tracing GCs are on the sophisticated end of that paper, while almost all reference counting GCs are on the rather primitive end. Given the same amount of effort, it's easier to get a reasonable result with reference-counting, but there are industrial-strength tracing GCs out there that have had a lot of effort put into them.

jeffdavis 6y ago

"Generational/compacting GC has the opposite problem. Garbage collection takes time proportional to the live set, and the amount of memory collected is unimportant." Takes time proportional the live set times the number of GC runs that happen while the objects are alive. In other words, the longer the objects live, the more GC runs have to scan that object (assuming there is enough activity to trigger the GC), and the worse GC looks.

titzer 6y ago
This is most decidedly not true for generational GCs, and for concurrent GCs, the tracing work happens asynchronously and in parallel, on other cores, not taking time on the main thread.
- tsimionescu 6y ago
  It's still true for generational GC, but the costs are more complicated. Even objects in the oldest generation are periodically scanned in most implementations (though there are some, like Clozure CL's GC, that never scan the old generation automatically). But generational GCs do improve massively on this problem.
- jeffdavis 6y ago
  You still have to scan the oldest generation at some point; otherwise (assuming some activity) you'll be leaking memory there over time. Moving the work to another core doesn't really change my statement. Aside: I wonder if it's feasible to switch to reference counting for the oldest generation? That would move the problem back to deallocation. I'm not sure if that's a good trade-off, but it would be interesting.