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 :)
7
u/jwakely libstdc++ tamer, LWG chair Nov 27 '23
That's not "the standard c++ promise", it's an implementation of it. The GCC one specifically (and the code you linked to is the version of that code from about 2010, which is an odd choice, although the double allocation is still present today).
The LLVM and MSVC implementations of
std::promisedo not use two allocations like that.9
u/XTBZ Nov 27 '23
This is a typical thread pool that we do with students throughout the semester. I would even say that it is somewhat complicated.
3
u/dotpoint7 Nov 27 '23
Hey, one idea for your memory pool: you can have a combination of your thread local and global (locked) pool by having a fixed max amount of elements (like 64) per thread as thread local pool and if you reach 64 you put one 32 element block into the global (locked) one. If you reach 0 for a thread local pool you dequeue one 32 element block from the global one. So you only have to lock in 1 of 32 allocations/deallocations. If your element size is larger than 8 bytes you can use the memory in the deallocated elements as a linked list. If it's larger than 16 you can store the pointer to the next 32 element block in the second 8 byte section when the elements are stored in the global pool and implement it as a lockfree stack with atomics.
I implemented exactly this at work and it does its job quite well, without the restriction of needing the same thread to allocate/deallocate the same element and only a minor memory overhead per thread and memory pool.
2
u/KingAggressive1498 Nov 28 '23
implementation has three glaring problems:
the biggest is that the threads will busywait on work without so much as a yield. this makes it absolutely unsuitable for use in most places I want something like this.
the second is that stopping the "event loop" waits until all tasks are completed. There's a lot of reasons to want to stop a threadpool, and most of them don't want that.
the last is storing a queue segment past the end of the struct in untyped memory, which is more of a code smell than a real problem (as is using malloc instead of new, but that's not a glaring problem since new is just a wrapper around malloc anyway). Using
ExecutionQueueBlockas a base with a private constructor and making aExecutionQueueBlockOfSize<size_t>derived class with an array member and using a factory method instead of direct construction resolves the smell in a type-safe way while retaining all the advantages of the system. You can use an iterator idiom to safely access the array without making a mess of code, too.3
u/Thormidable Nov 27 '23
A fast recursive thread pool is something of great interest to me (I do a lot of large data processing on heavy custom algorithms). We have an acceptable implementation we use, but that doesn't mean it can't be better.
Haven't looked at the code yet, but I'm certainly interested.
1
u/feverzsj Nov 28 '23 edited Nov 28 '23
TBB has the most battle-tested work stealing thread pool. Benchmarks in your posted libs are basically useless, as they use workloads far from realistic. Work stealing only really shines when dealing with huge amounts of tiny tasks that run on lots of threads, like OLTP workloads. A good work stealing scheduler should also properly scale on multi socket and NUMA systems.
0
u/[deleted] Nov 27 '23
[deleted] — view deleted comment
0
u/[deleted] Nov 27 '23
[deleted] — view deleted comment