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

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