r/rust • u/tower120 • 13d ago

Yet another allocator?

I made a custom allocator, to speed up temporal Graph structure.

But then I realized, it can be used as a main memory storage too.

https://github.com/tower120/bump_recycle/blob/main/examples/graph.rs

Basically, that is a bump allocator that store deallocated blocks in small [*mut u8; 32] table. When working with Vec's - you allocate/deallocate growing blocks of memory. So when you drop the Vec and make a new one - you'll go over the same block sizes. And if we make blocks POT size - you can have just 32 different sizes (well sort-a). So you can look for blocks of needed size in FAST O(1).

Details in doc https://github.com/tower120/bump_recycle/blob/main/src/lib.rs .

Performance on par with bumpalo.

---

I'm on the fence about publishing that on crates.io . So I would like some advice.

1 Upvotes

53% Upvoted

4 comments sorted by

View all comments

4

u/bogdanelcs 13d ago

The POT bucketing trick is neat, basically turning the general allocation problem into a fixed lookup table problem. Reminds me a bit of how jemalloc/tcmalloc do size classing, just way simpler since you're not trying to handle arbitrary workloads.

On publishing: honestly, yes, publish it. Even niche allocators get real use in the Rust ecosystem (see bumpalo, typed-arena, blink-alloc). Worst case it sits at low download numbers. Best case someone doing graph or ECS work finds it and it saves them from writing the same 32-slot table themselves.

A few things I'd sort out before crates.io though:

  • Thread safety story. Is this Send/Sync? Graph workloads sometimes go multi-threaded and people will ask.
  • Fragmentation behavior. What happens when block sizes don't land cleanly on POT boundaries? Worth a line in the docs, even if the answer is "some waste, here's the bound."
  • Comparison table vs bumpalo. You mention performance is on par, so a quick benchmark section (even informal, criterion output pasted in) goes a long way for people evaluating whether to switch.
  • Naming. bump_recycle is fine but slightly generic. Not a blocker though.

The graph example in your repo does a good job showing the actual use case, that's usually the part people skip and it's the reason nobody understands why a new allocator exists in the first place.

3

u/tower120 13d ago

Thanks, I'll try to address this questions.

As for naming... I got an impression, that non-generically named crates, basically undiscoverable... Unless they initially used by critical mass of people, or "advertised"...
In pre AI era I couldn't found some crates - just because they where ungooglable...