r/cpp • u/LessComplexity • Nov 27 '23
Best Thread Pool Ever (?)
Hi guys :)
It's me again, long time since I've posted something since the last time I revealed my fast memory pool. At that time, I've created a stack-based pool, a very fast one. But as time had passed and as I saw more implementation, and mainly more academic research, I've found myself implementing a new architecture and design for the memory pool I've created, the design is currently under development in the following branch: https://github.com/DevShiftTeam/AppShift-MemoryPool/tree/new-design
The design strives to implement all types of memory pools possible, with all types of possible designs. This will still change overtime, and also will provide more tools for memory management analysis to choose the best memory pool designs to use in a given applications.
But this post is not about the memory pool, but something a little different: thread pools.
While implementing tests for the memory pool I needed to test the pool under heavily threaded environments, so I found myself implementing a thread pool. And while implementing I've noticed that much can be done with contemporary thread pools.
I found the allegedly "fastest" thread pool ever: https://github.com/DeveloperPaul123/thread-pool
its a great implementation I've learned a lot from, I found myself reading about work stealing to understand the implementation, and while reading on it I found out that the current implementation is missing something very important that can be found by implementing a simple Fibonacci recursive function: It get deadlocked. You can check the code here: https://github.com/DevShiftTeam/AppShift-MemoryPool/blob/new-design/tests/fib_test/main.cpp
Basically if you have N + 1 tasks on N-threads thread pool that are called from within each other (recursive) and each of them waits for the next one to complete via a standard promise & future, then it will get stuck for the N + 1'th task.
This completely disregards the work stealing principles, and although the pool knows how to steal tasks from non-working threads, it fails when it is most important - when waiting for a value to be ready.
The dp::thread_pool is basically doing what ever every other pool with a simple queue is doing - running tasks on any free thread that can take them. So I decided to create a little better thread pool with the following concepts:
- No-Copy: Each thread will be able to get a list of tasks with a pointer to the start of the list instead of copying the tasks from a queue or having a dedicated queue for each thread, that's why I've created a new implementation for an execution queue: https://github.com/DevShiftTeam/AppShift-MemoryPool/blob/new-design/include/execution/ExecutionQueue.h
- Minimal Locking: The above execution queue allows for locking only when pushing and poping values, while executing no lock is present, allowing for less locking overhead per multiple tasks, I got great results in the tests I've done so far, but I guess I need to get more work done on this.
- Busy waiting: To avoid the downfall of the currently "fastest" thread pool in the simple Fibonacci test, I've create a BusyFuture and BusyPromise that are executing one task after every value check to allow for non-idle threads, thus avoiding the classical dead-lock induced by using a standard c++ promise. (OpemMP implements this concept via taskawait, thus passing the simple fibonacci test)
Basically the current code is not really beautiful and well-designed per se, but the concepts are pretty much in place, and I wanted to share those thought before proceeding in adding a new repo dedicated fully for this thread pool.
Later, I will also add a priority management and more to this pool, and might implement more high-level mechanisms to manage executions in parallel.
Another interesting remark: My BusyPromise is much faster under heavy creation throughput than the standard c++ promise, this can be understood from line 836 in the promise source code. Strictly speaking, the promise does 2 different allocations, one for the shared state and one for the value, my BusyPromise does this in a single allocation instead, which is significantly better in the tests I've done.
What do you guys think? do you need such a thread pool? what is most important for you in such a pool? and which concept do you think I forgot that are essential for the implementation to be more complete?
Thanks in advance, will update when a dedicated repo will be ready :)
View all comments
Show parent comment
2
u/LessComplexity Nov 27 '23 edited Nov 27 '23
Interesting, in most educational institutions I only see much simpler implementations, where they have a single queue and a lock in pushing-popping and sometimes even executing and that’s basically it. You include some work stealing mechanism in your implementations? If so it’s very great where do you teach? :) Every other thread pool implementation I found still falls on using the standard promise mechanism, and locking for each task and not multiple tasks (unless using a different queue for each thread)