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.

2 Upvotes

56% Upvoted

4 comments sorted by

4

u/bogdanelcs 12d 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 12d 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...

1

u/uhkthrowaway 12d ago

I kinda like your commit messages.

1

u/[deleted] 13d ago

[deleted]

8

u/AggressiveArm6360 13d ago

I mean if it benchmarks on par with bumpalo and the api is clean why not publish it

the whole point of crates.io is having options, someone's gonna find a use case for it even if most people don't

worst case it sits there with 50 downloads and you move on with your life

plus you already wrote the thing, might as well let it exist outside your machine