3 ms·

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

lor_louis 2y ago
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.
- theusus 2y ago
  References for both?
eigenspace 2y ago
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 https://github.com/MasonProtter/Bumper.jl
MathMonkeyMan 2y ago
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 https://github.com/bloomberg/bde/wiki/BDE-Allocator-model [2]: https://bloomberg.github.io/bde-resources/doxygen/bde_api_prod/group__bdlma__concurrentmultipool.html https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr... [3]: https://bloomberg.github.io/bde-resources/doxygen/bde_api_prod/bdlma__concurrentpool_8h_source.html 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.

theusus 2y ago
References for both?

eigenspace 2y ago

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 https://github.com/MasonProtter/Bumper.jl

MathMonkeyMan 2y ago

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 https://github.com/bloomberg/bde/wiki/BDE-Allocator-model [2]: https://bloomberg.github.io/bde-resources/doxygen/bde_api_prod/group__bdlma__concurrentmultipool.html https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr... [3]: https://bloomberg.github.io/bde-resources/doxygen/bde_api_prod/bdlma__concurrentpool_8h_source.html https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr...