roc-toolkit
roc-toolkit copied to clipboard
roc-streaming
Make core::Pool lock-free
All our threads communicate via lock-free task and packet queues (see pipeline::TaskPipeline, netio::NetworkLoop, ctl::ControlLoop).
However, these threads also use shared memory pools (core::Pool), which is basically a simple slab allocator with a mutex.
The good properties of core::Pool are: amortized O(1) allocation, O(1) deallocation, and that most recently deallocated memory is re-used first, to increase chances that it's still present in CPU caches.
The bad property is that it's not lock-free and thus potentially can be a point of contention and source of unwanted delays in the real-time path.
Our goal is to make the pool wait-free or at least lock-free, while preserving it's good properties.
We already have an implementation of a lock-free unbounded intrusive FIFO (core::MpscQueue). However, it's not ideal for core::Pool:
- it's FIFO, while for core::Pool a LIFO would be more appropriate
- it's single-consumer
- its push is wait-free, but pop is only lock-free and not wait-free
The most preferable option would be to employ a wait-free intrusive unbounded node-based multi-producer multi-consumer LIFO (stack, free-list), if such an algorithm exists.
Another option is to employ a combination of a bounded wait-free LIFO (again, if it exists) and an unbounded wait-free FIFO. In this case, we can use the bounded LIFO for "hot" (recently deallocated) objects and FIFO for the rest, "cold" ones.
If neither bounded nor unbounded wait-free multi-producer multi-consumer LIFO exists, we can at least use a lock-free one. They exist, though usually perform worse under contention.
Feel free to suggest other ideas!
Should we implement the algorithms by ourselves or use a library? It depends. Again, here are some thoughts:
-
If we can find an algorithm which can have a compact and portable implementation, it's better to avoid adding new external dependencies.
-
Otherwise, if there is a library which implements the whole pool with all desired properties, and which fulfills our requirements to external libraries, we can just use it.
-
Otherwise, if there is a library which implements some data structures that we can use, and which fulfills our requirements to external libraries, we can also use it.
We have some requirements to an external library:
-
it should be portable across operating systems and compilers, including various embedded systems;
-
it should allow to provide a custom allocator; core::Pool works on top of core::IAllocator, and we should preserve this logic;
-
its license should not be strict; it should be a permissive license or at least something like LGPL;
-
it should be well-maintained.
As a compromise, we can choose a library that is not portable across all platforms, but at least supports major platforms, and use non-lock-free fallback on the platforms which it doesn't support.
