5 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. Th
by 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 agoUsually in a background thread ;)
- arcticbull 6y agoIndeed. 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 agoYou 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
- Reelin 6y agoThat's a neat library but as far as I can tell it doesn't avoid any traversal or cleanup code. It appears to delay the cleanup so it all happens at once. That's certainly useful, but if you have RAII the traversal still has to happen at some point.
- winstonewert 6y agoIt avoids it if your type has no-op drop implementation. So if you use typed-arena for objects which don't own resources, they all get dropped in one massive deallocation and don't have to be traversed. EDIT: and then I noticed that you mentioned RAII... Right, if the object own some sort of resources that doesn't apply.
- Reelin 6y agoNo worries. And to clarify, in context the point is that traversal fundamentally can't be avoided in the case of RAII. This defeats (what I see as) the primary use case of an arena allocator - deallocating an arbitrarily large chunk of contiguous memory in O(1) time regardless of object count. Of course this is all somewhat tangential to the original topic of generational GCs, where the RAII idiom also has significant negative impacts. The performance characteristics would otherwise be O(n) based on the live set and thus similar to an arena allocator in terms of the ability to dispose of an arbitrarily large number of objects efficiently.
- winstonewert 6y agoI'm not sure its fair to say it defeats that use case. It only defeats that use case if you need RAII. Furthermore, in my experience, an arena is most useful when you allocate lots of small objects which is the least likely to case to need RAII.
- Reelin 6y agoI think we're violently agreeing? RAII is the only use case I was speaking of there. Way back up thread the original post I responded to was talking about arena allocators in comparison to a generational GC and finalizers. The point is that a generational GC doesn't handle finalizers well, but neither does an arena allocator!
- all-fakes 6y agoYes. Some libraries, like typed-arena (and Rust's built-in Vec), will traverse the structure and call the drop implementations, and others, like bumpalo, will just leak the resources.
- chowells 6y agoI said generational/compacting collector. You're talking about a mark and sweep collector. A generational/compacting collector traverses pointers from the live roots, and copies everything it finds to the start of its memory space, and then declares the rest unused. If there is 1GB of unused memory, it's irrelevant. Only the things that can be reached are even examined. As I said, this has the opposite problem. When the live set becomes huge, this can drag performance. When the live set is small, it doesn't matter how much garbage it produces, performance is fast.
- arcticbull 6y agoHow are finalizers invoked if the structure isn't traversed? Would it just be optimized away none of the objects have finalizers? Hence my suggestion about the area allocators being a better point of comparison.
- Reelin 6y agoMy understanding is that finalizers are special cased for a generational GC, have a tendency to introduce significant overhead, and (as with any GC scheme) generally run at unpredictable times. My impression is that RAII idioms are strongly discouraged in conjunction with most GC ecosystems.
- tsimionescu 6y agoActually, RAII idioms are generally encouraged, but finalizers are not. For the rare few classes that hold resources in GC languages, the Resource is usually Acquired at Initialization as well, and released in a special method (IDisposable.Dispose() in C#, AutoCloseable.Close() in Java). There is also usually some special syntax for automatically calling this syntax when the object exits some scope, though that scope usually has to be declared by the user (using(), try-with-resources, with() in Python etc.). The biggest difference I know of is that the 'holds-resources' property does not propagate automatically like it does in C++. It's not that hard to always remember to call using(file = new File()) [...]. However, it's much easier to forget that you have a File field in your class which you initialize in the constructor, and so your class must itself be declared IDisposable/AutoCloseable etc.
- pron 6y ago> 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 Yes, but in practice tracing in a tracing GC is done concurrently and with the help of GC barriers that don't require synchronization and so are generally cheaper than the common mechanisms for reference-counting GC. > and to invoke finalizers As others have said, finalizers are very uncommon and, in fact, have been deprecated in Java.
- tsimionescu 6y agoNo, they are actually fundamentally wrong. GCs never scan garbage - they only scan objects that are referenced from a GC root. Note that the problem appears in a different place: if your large structure is actually not garbage, then every GC pass will have to scan it to see what other objects it is keeping alive.
- pron 6y agoNot every GC pass. Some modern GCs (like OpenJDK's default GC, G1) track mutation and maintain "remembered sets." They only need to scan objects that have changed since the last scan (they're actually even more efficient than that, but this is a simplification). In addition, when this scanning is required, it is performed concurrently to the application, so the technique of moving the work to a separate thread is done automatically.
- mcguire 6y agoFinalizers/destructors do not work well in garbage collected languages, for that very reason.
- tsimionescu 6y ago> 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. All garbage collectors start from live objects and only scan those. Then, whatever objects they have not scanned get collected. In copying collectors (like most generational ones), this means that garbage is never touched. In the mark-and-sweep algorithms, the mark phase still never touches the unreachable objects. However, the sweep phase does need to return those objects to the free list, so it will have to walk them. It will still not do it the same way as malloc/free, as it can walk the heap in order and free unmarked objects as it encounters them, no need to follow pointers, so it may still have better cache performance. Finalizers introduce extra difficulty, but still the behavior is fundamentally different. What usually happens is that objects which have finalizers are usually remembered in a special list which acts as a GC root itself. When they are only reachable from that list, they get marked so that the finalize will run (usually on a special Finalizer thread). When the Finalizer is finished, and assuming the object was not resurrected, they get removed from the Finalizer list, and now they are not reachable from anywhere at all, so the next GC will finally clean them up. Usually, there is also some API for user code to mark a Finalizable object as 'finalized', which essentially removed it from the Finalizer list early and allows it to be collected as normal, without going through the above process. And yes, having a large number of finalizable objects in your memory is usually considered a very bad idea. Generally, they are only recommended as a fail-safe measure: you are supposed to do explicit cleaning, but as a fail-safe, to avoid your program crashing in production if a connection or file leak was missed, you also have the Finalizer to throw buckets of water out of your boat (but you should really notice that it is happening and plug that leak, rather then relying on the bucketeer).