I’ve been toying with the freelist header file, seeing how to present two ideas I’ve had for a long time.
First is to add support for single-threaded use. This means you can flip the freelist into singlethreaded mode, from which point onwards only the thread which made the flip can use the freelist, until that thread flips it back to multithreaded mode, and then everyone else can join in again.
Singlethreaded mode is at least an order of magnitude faster than multithreaded mode used by a single thread; if you’re doing performance work, you simply cannot use a lock-free freelist in a single thread – it’s insane – but currently you’d have to, because if you did build up a single-threaded freelist, how would you get those elements into the lock-free freelist? (think also about stacks, queues, etc)
It also means the freelist can *in general* be used as a single-threaded freelist, which is often required. It also then provides support for scenarios like one thread building up a freelist and then throwing it over to a set of other threads (okay – not something you’d do so much with a freelist, but imagine a stack, or queue, etc, all of which should get the same treatment).
Providing a fully single-threaded mode provides the necessary functionality for the benchmark programme’s benchmark for the unbounded single/single queue.
Second is being able to form freelist elements up into a chain of freelist elements, and then pushing the chain to the freelist, where that push regardless of the chain length occurs as a single atomic operation. So we’re offering write combining in the API.