search

kyren / gc-arena

Incremental garbage collection from safe Rust
Creative Commons Zero v1.0 Universal
436 stars 36 forks source link

Rework `DynamicRootSet` to amortize allocation. #101

Closed kyren closed 6 days ago

kyren commented 1 week ago

Downsides:

1) Stashed values must be Gc<'gc, T>, which is less flexible. 2) DynamicRoot types are larger, 2 pointers and a usize instead of 1 pointer.

Upsides:

1) Amortized allocation. Dropping and recreating a DynamicRoot does not allocate. Previously, always allocated an Rc and pushed to an internal Vec, now only pushes to an internal Vec. 2) Single allocation block. All reference counts and root pointers kept in a single Vec. 3) No double indirection during DynamicRootSet::fetch. DynamicRootSet::fetch now checks one pointer field for equality (the slots field) and returns another pointer field (the root field) without dereferencing anything. 4) Not really any more complicated, and handling the allocation metrics is much simpler.

kyren commented 1 week ago

d559a3ac859b8deb7b3154996f5cd565e0fea6e1 was a drive-by change because I was manually testing allocation metrics and noticed it.

If we all think it's stupid I can drop it.

kyren commented 6 days ago

There are ways in the future that we might be able to reduce the size of DynamicRoot so that it's only two or one machine words again, but they're not free either, and 3 machine words is not that big.

Especially with the change to use an embedded free list, I think this is a strict improvement. The only way the old way is potentially better is in the case where most of what you're doing is cloning (rather than creating, destroying, or accessing) DynamicRoot handles, which seems unlikely.