4 ms·
> 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 aren
by 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!
- winstonewert 6y agoYes. We are violently agreeing
- 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.