Hacker News new | past | comments | ask | show | jobs | submit login
A Comparison of Arenas in Rust (donsz.nl)
87 points by PaulHoule 5 months ago | hide | past | favorite | 9 comments



I'm the author of slotmap. I don't know why slotmap is listed as not having ABA protection, when it absolutely does.

EDIT: I've emailed the author.


Seeing these things come from teachers at TU Delft makes me excited to do my master's there. Sadly school already starts soon and I haven't done my pre yet.


What kind of pre is it?


> “Deref Key” documents whether ...

But it doesn't. The autor uses the cryptic words “Deref Key” and a checkbox but never says which side of the decision it actually refers to. So much work to produce a useless "documentation". Pro tip: Documenting stuff means you have to spell it out.


Does anyone know about a sound and lock free arena algorithm?


Not totally sure what you're looking for, but what I did when I made a package for arena allocators in Julia, I made the arena task-local rather than global.

That means that if you spawn a concurrent task and then request the arena to allocate something to, you'll be writing to a completely separate chunk of memory than the memory used by the arena in the parent task.

Users can still cause race conditions by explicitly passing an existing arena across task boundaries, but if they use the function to fetch the currently-active task-local allocator, it's naturally threadsafe without any slow locks or atomics required.

Ref: https://github.com/MasonProtter/Bumper.jl


I don't, and I also haven't learned Rust.

My experience with arena allocators comes from Bloomberg's C++ libraries[1]. For example, here's the documentation[2] for a thread safe heterogeneous allocator and header[3] for the underlying thread safe pool.

It uses a mutex, but at a glance only when it needs to consult the fallback allocator (which could involve a system call). If you knew that the fallback allocator were a pre-allocated arena, maybe you could do with atomics only. The free list is already lock-free, and so too could be the block list.

[1]: https://github.com/bloomberg/bde/wiki/BDE-Allocator-model

[2]: https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr...

[3]: https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr...


A bump allocator can be implemented using atomics, but it does not support freeing individuals elements. I have seen some CAS heaps (linked list like) but I never had to implement them.


References for both?




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: