Typedarena for Rc<T>?

Is there something like typed-arena for Rc<T> ?

The main difference is this: when the ref count of the Rc<T> goes to 0, we want to call the drop handler in the arena. Then we want to mark the space as FREE in the arena -- and possibly re-use it later on.

I.e. is there something like typed-arena for fast allocation, but instead of deallocating everything at once, we add it to the free list, to be used in the future.

I.e. is there something built for handling lots of Rc<T> ?

In this case you don't need any of the borrow-friendliness of typed-arena โ€” you just need a custom allocator, i.e. Rc<T, KeepsAFreeList>. Unfortunately, custom per-data-structure allocators aren't currently stable. I don't know if there's a crate that offers a variant Rc that has this feature.

It might not necessarily be worthwhile, though โ€” I've experimented with hanging on to allocations for later reuse and the results are often equal to or slower than the naive approach.

I might be naive here -- isn't there a huge benefit of not fragmenting main memory? I.e. instead of having 10k Rc<T> sized holes in main memory, instead it's just a few Vec's with all theRc<T> packed together.

Ah, good point โ€” I was thinking about the free-list angle and not compactness. Though note that (if I understand processor/memory architecture correctly) compactness mostly helps only if:

  • your access is sequential so that the processor can predict and prefetch upcoming accesses (but this isn't guaranteed by a free-list) or
  • the Ts are small enough that several of them fit in a single cache-line.

If neither of these conditions is met then the memory addresses being nearby doesn't help.

Modern allocators are smart, and pool similar-sized small allocations. You pooling a bunch of 32-byte allocations is hard to do substantially better than the allocator will. Especially as modern allocators also do smart things like per-thread allocations with cross-thread stealing and such as needed.

What's the overhead you actually see, with a good non-system allocator (maybe tikv-jemallocator โ€” Rust memory management library // Lib.rs or MiMalloc โ€” Rust memory management library // Lib.rs) and LTO?

Never benchmarked this. Got curious after studying typed-arena.

rc_arena/src/lib.rs at master ยท ebfull/rc_arena ยท GitHub -- apparently from 9 years ago, might be similar to what I need.

That crate reference counts the whole arena, and merely serves to eliminate the need for a lifetime. It doesn't ever drop individual items early.

1 Like

Good call. I believe I need the arena to store

#[repr(C)]
struct RcBox<T: ?Sized> {
    strong: Cell<usize>,
    weak: Cell<usize>,
    value: T,
}

If you're implementing the ref counting yourself, you could use a slotmap to manage the free space. When your RcBox is dropped, it could remove the entry from the slotmap. You would use slotmap keys instead of references.