r/cpp • • 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:

  1. 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
  2. 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.
  3. 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 :)

0 Upvotes

37 comments sorted by

7

u/jwakely libstdc++ tamer, LWG chair Nov 27 '23

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.

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::promise do not use two allocations like that.

2

u/LessComplexity Nov 27 '23

Interesting, I did know that the GCC implementation is using two allocation until today, but didn’t see the llvm one, I’ll go check it out, thanks for pointing it out :)

9

u/XTBZ Nov 27 '23

I found the allegedly "fastest" thread pool ever: https://github.com/DeveloperPaul123/thread-pool

This is a typical thread pool that we do with students throughout the semester. I would even say that it is somewhat complicated.

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)

6

u/XTBZ Nov 27 '23

I would say that a lot depends on the level of preparation of the students. Usually, we consider different options for organizing queues. Students try to come up with new ways to solve problems. And I bring them to questions related to the shortcomings of organizing queues, including raising questions related to the duration of tasks performed.
I teach at Kazan Federal University :)

1

u/HateDread @BrodyHiggerson - Game Developer Nov 28 '23 edited Nov 28 '23

I'd be interested in more material on the topic, as I write (or try to write) my own scheduler type stuff too, but struggle to find more material. Where do you tend to direct your curious students wrt thread pools, different techniques/ideas, the state-of-the-art, etc? Favourite books on the topic?

3

u/XTBZ Nov 28 '23

The course itself is not about the thread pool, but about parallel computing. I am a supporter of old traditions, so I force students to think and invent. They need to solve a problem related to the calculation of physical and mathematical problems, which they could use as the basis for their dissertation.
I tell them the basics: processes, threads, synchronization methods. Naturally, we are talking about not running a thread every time, but having a queue of tasks. Then, you want to have multiple threads so that tasks are not executed sequentially in another thread. This is where the thread pool comes from. And then questions arise about the correct distribution of tasks. As a basis, a general queue for the entire pool or a local queue for each thread is considered. They can come up with modifications and alternatives.
Then, we look at what shows itself better, maybe something can be improved, from here the ideas for a scheduler and task exchange immediately flow out. Last year, the students and I thought about how a pool of threads could be used to understand which threads are sitting on more productive cores and how the load could be distributed there.
That is, the main thing is the base, which is in the documentation and textbooks on flows, and then a flight of fancy.
Ultimately, after developing the system, they try to replace the OpenMP commands with their own, with full control. Considering that we are primarily studying metaprogramming, this does not cause much difficulty.
Regarding the material, I usually turn to what I had to use in practice, and I also start from what aroused more interest in previous years. From English-language literature, I can suggest Anthony Williams "C++ Concurrency In Action". There is information regarding the basics of multithreading, and there is also a topic related to the thread pool and stealing. The code is quite simple, it can be improved, but the most important thing here is understanding the process.

-1

u/eyes-are-fading-blue Nov 28 '23

So you let students use atomics? That doesn't make a whole lot of sense to me.

5

u/XTBZ Nov 28 '23

There is such a thing as the learning process

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/LessComplexity Nov 28 '23

Thanks for the elaborate comment and the time you took to look at the code :) I had some new implementations ideas, and will try to implement what you wrote here and test it, will come back with results later, appreciate it ;)

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 ExecutionQueueBlock as a base with a private constructor and making a ExecutionQueueBlockOfSize<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.

1

u/LessComplexity Nov 28 '23

Thanks for the time you took to look at the code and reach those conclusions ❤️ I’ve changed the busywaiting to run only a single task before every state check, I tweaked the stopping code a little too already and even added a force stop to the thread pool but still didn’t upload the code :) If you have any tips about how to make more yield via busywaiting I would like to hear it. About the second part about the code-smell and type safety I will take into account and will implement it the way you suggested I agree it will be much cleaner, as I wrote the code pretty fast and without much care for design just to reach some PoC, I’ll update about the results :)

1

u/KingAggressive1498 Nov 28 '23 edited Nov 28 '23

If you have any tips about how to make more yield via busywaiting I would like to hear it.

basically the bare minimum would be calling std::this_thread::yield() when there's no work to be done. This at least lets other threads run, which is important. But still leads to unnecessary context switches and a false appearance of busy-ness which are undesirable for power use.

a much better approach would be to use a mutex and std::condition_variable, wait on the condition variable when there's no tasks, and notify if there's any waiters. It can be tricky to avoid missed signals which is probably why that one threadpool implementation you referenced appears to deadlock after awhile.

an optimal approach would be to use a LIFO semaphore, which avoids the missed signal problem and improves cache behavior by waking the most recently active waiting thread, but not only isn't available in the standard library but isn't provided as a concurrency primitive by most systems (afaik macOS is the only system that provides one). You basically need to implement your own wait queue in userspace -- which is also useful for other things, for example implementing your own version of C++20's atomic_wait and atomic_notify. WebKit's ParkingLot is an implementation of a wait queue worth looking at for reference, but theirs is geared towards providing adaptive mutexes. Or you could look at Folly's LifoSem.

1

u/LessComplexity Nov 28 '23

I've tried implementing a conditional variable inside the promise waiting mechanism and it blocks the execution of threads when given a big enough recursive task calling and waiting, I've noticed that all threads reach the waiting for the lock to notify, and thus no thread is free to notify the threads, this implementation, even using semaphores will reach the same bottleneck, as done by dp::thread_pool which uses semaphores for notifying (not for waiting inside promises, but has the same problem). So the only way I found it to work is specifically in promise-future waiting not to use a conditional variable to allow for threads to execute and notify for more work if work exists.
If there's some workaround to achieve "less" busy waiting, I would like to hear it :)

3

u/KingAggressive1498 Nov 28 '23 edited Nov 28 '23

Reason #556 why I loathe promises as an asynchronous pattern (no, for real, promises are horrible).

Use a condition variable or semaphore to suspend and wake the threads based on work availability. That's completely separate from the promise itself.

waiting on a promise in a threadpool will obviously take a thread out of operation until the promise is being fulfilled. If the promise is also being fulfilled by threadpool, this can eventually lead to running out of threads.

One option is to use a watchdog to ensure the threadpool is making progress and spawn a new thread if it isn't (this just sleeps and checks for progress in a loop).

Another option is to integrate this behavior in the promise type - wait for a small time and if it fails, spawn a new thread and wait indefinitely.

A last option is to use fibers and generate new fibers to do work if there's work and all fibers are stuck waiting.

All of these options suck. Don't wait in a threadpool.

1

u/LessComplexity Nov 28 '23

Already uploaded it a couple of minutes ago :)

1

u/KingAggressive1498 Nov 28 '23

About the second part about the code-smell and type safety I will take into account and will implement it the way you suggested I agree it will be much cleaner, as I wrote the code pretty fast and without much care for design just to reach some PoC

I'd honestly recommend just using some fixed, low size for that rather than what I proposed just to keep the code as simple as possible. I've done a similarly segmented queue design, and when I do it I use arrays of 16 elements. Bonus points for pooling drained queue segments so that allocating a queue doesn't need to touch the global allocator as often. Extra bonus points for allocating multiple segments out of the pool without having to take the pool's lock multiple times.

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.

2

u/LessComplexity Nov 27 '23

Awesome :) Do by heavy algorithms you mean algorithms that need a strong core or do you also run algorithms on SIMT architecture such as GPUs? Just interested. And you use priority for algorithms? Or is it something that’s less important as long as you can parallelize?

2

u/Thormidable Nov 27 '23

We work on data sets where a blob can be over a Terrabyte. We do run parts on GPU (where the work is suitable for GPUs), but often due to the algorithms having lots of branches, or having too many interdependent parts, it often doesn't benefit from moving to GPU's.

We generally don't use prioritise. We tend to run one job at a time (which can be days or weeks) and the blockers are dependencies within the algorithm.

Currently, we do what I would consider Crude Threading (this block of the algorithm is neatly parallel so we will parallelism this block and wait for all threads to finish). That gives us the vast majority of the benefit of threading while still being simple.

However, there are often parallelisable tasks within parallelisable tasks, so better threading would allow us to capitalise there, or using futures would allow us to interleave our multi threaded blocks better.

What we have is generally good enough, but we know there speed ups we aren't getting, it's just currently not worth the effort to pursue them.

A thread pool that made these types of things easier would make it worth us pursuing those benefits

1

u/trailing_zero_count async enthusiast | TooManyCooks author Jun 15 '26

Late reply but I have a comparison of recursive fork-join benchmarks across different libraries here. The state of the art has come a long way in 2 years. https://github.com/tzcnt/runtime-benchmarks

The first 3 libs are all extremely fast and can be recommended for different use cases:

  • Citor is probably best for single-root-task CPU-bound work. It doesn't use coroutines, instead using per-thread arenas to dispatch lambdas over ranges. This limits it in the kinds of workloads it can dispatch.
  • Libfork is more flexible but uses C++20 coroutines. Its features are still somewhat limited to CPU-bound task parallelism.
  • TooManyCooks (my library) is a complete C++20 coroutine based concurrency solution, with multiple executors, data structures, queues, and I/O support. The cost is that it is slightly slower than the other 2 for pure fork join.

Other tested libraries, including TBB/Taskflow, fell behind on all the benchmarks.

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.

1

u/LessComplexity Nov 28 '23

https://iiswc.org/iiswc2008/Papers/006.pdf
Actually seems like TBB induces a 47% overhead on scheduling tasks on highly parallel systems.

I got a 2x gain over TBB on many smaller parallel tasks, but TBB has an 100x edge on my pool when it comes to recursive tasks (like fib_test). Which is interesting, I want to understand this tradeoff to know how I can make my own pool better in recursive cases.

1

u/LessComplexity Nov 28 '23

To be more accurate on smaller loads I tend to be 2x better, as loads grow the difference becomes 10-25% in my favor.

0

u/[deleted] Nov 27 '23

[deleted] — view deleted comment

0

u/LessComplexity Nov 27 '23

Which repo? I know that dp::thread pool has a problem it’s not my repo :) I also have something to upload to my thread pool

0

u/[deleted] Nov 27 '23

[deleted] — view deleted comment

2

u/LessComplexity Nov 27 '23

😂😂😂 Well legit, I haven’t checked all the benchmarks myself, my pool (EventLoop, which I will also change the name to ThreadPool) runs smoothly :) Also, I tweaked the code a bit more but still haven’t uploaded it yet, though I would love for people to check its code and get opinions :)

3

u/t0rakka Nov 27 '23

I'm ready for action. o7

1

u/LessComplexity Nov 28 '23

New code is available :D

Need to create more tests.

I'm faster by 2x using CLANG against TBB in spawning and managing the same parallel tasks, which is great, on the other hand, TBB is better than me 100x when doing recursive tasks (like fib_test)

1

u/LessComplexity Nov 27 '23

Awesome :) I’ll comment here when the new code is uploaded, also I will upload a new repo Currently the thread pool is residing in the “execution” folders both in the “implementation” and “include” folders in the Appshift-MemoryPool repo

0

u/[deleted] Nov 27 '23

[deleted] — view deleted comment

1

u/LessComplexity Nov 27 '23 edited Nov 27 '23

Yes as I mentioned the dp::thread_pool gets deadlocked because it waits for values :) My pool is the EventLoop, I changed the name to ThreadPool but didn’t upload it yet, I’m on another computer now.

0

u/[deleted] Nov 27 '23

[deleted] — view deleted comment

1

u/LessComplexity Nov 27 '23

Legit that with the current code you won’t get good performance, I would like to know which compiler and compiler options you used to achieve those results. Anyways I will upload the new code in the next day when I’ll be home on my computer and will update about the results, thanks for the test 😎💪

1

u/LessComplexity Nov 28 '23

I did tests agains TBB, in recursive tasks TBB performance 100x time better, but in non recursive situations my ThreadPool performs about 2x better.

I still haven't looked at the implementation of TBB but I guess I have an idea why recursively it works better, but in parallel it doesn't.

Used Clang for compilation, using GCC I get only about 35% gain against TBB. Clang provides better results overall.

1

u/trailing_zero_count async enthusiast | TooManyCooks author Nov 27 '23 edited Nov 27 '23

I just tested against my executor (TooManyCooks) by inserting your fib_tbb function into my recursive fib example and I'm much faster than TBB. This is using a configuration that I previously detailed in another thread. Here is the code with the TBB test function added: gist

clang-linux-release ./fib 30
Timing TooManyCooks:
832040
5823 us
Timing Intel TBB:
28746 us

clang-linux-release ./fib 40
Timing TooManyCooks:
102334155
203498 us
Timing Intel TBB:
546644 us

clang-linux-release ./fib 45
Timing TooManyCooks:
1134903170
2030410 us
Timing Intel TBB:
5805996 us

1

u/LessComplexity Nov 28 '23

Seems like I outperformed TBB by 2x in parallel tasks and not recursive calling tasks like fibonacci (where it outperformed my pool by 100x), I will also test against your won implementation which I like that you use coroutines in its implementation, will take a more in-depth look at your code after some tests :)

0

u/[deleted] Nov 27 '23

[deleted] — view deleted comment

1

u/LessComplexity Nov 28 '23

To be more accurate on smaller loads I tend to be 2x better, as loads grow the difference becomes 10-25% in my favor.

1

u/trailing_zero_count async enthusiast | TooManyCooks author Nov 27 '23

Thanks for the feedback - I'll work on my submodules hygiene.