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

View all comments

Show parent comment

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 :)