News for hackers. Stuff that matters.
Re:A Comparison of Arenas in Rust by theusus on Sunday August 25, 2024 @01:58PM (#41349541)
Does anyone know about a sound and lock free arena algorithm?
Re:A Comparison of Arenas in Rust by lor_louis on Sunday August 25, 2024 @02:19PM (#41349752)
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.
Re:A Comparison of Arenas in Rust by theusus on Sunday August 25, 2024 @02:23PM (#41349810)
References for both?
Re:A Comparison of Arenas in Rust by eigenspace on Sunday August 25, 2024 @04:32PM (#41351122)
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

Re:A Comparison of Arenas in Rust by MathMonkeyMan on Sunday August 25, 2024 @04:38PM (#41351181)
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...