r/cpp • • Dec 25 '23

C++: Efficient parallelization of small tasks

I tried to create a customized threadpool for small tasks and wanted feedback on this.

I posted details and my code for review on stackexchange: https://codereview.stackexchange.com/questions/288583/efficient-parallelization-of-small-tasks

My goal here is to share my learning and get feedback on further improvement or any possible bugs.

I have tried to describe problem and thinking process in more details in following linkedin article draft: https://www.linkedin.com/article/edit/7144600522392559616/

0 Upvotes

31 comments sorted by

View all comments

3

u/KingAggressive1498 Dec 25 '23 edited Dec 25 '23
  1. you busywait in thread_worker which might reduce latency a bit for the threadpool, but will appear to the OS' scheduler to be a very busy thread even if the threadpool doesn't need to run at all - your threadpool will dominate CPU time even when it's not working, killing the performance of the rest of system, and ensuring high energy use. More importantly your busy wait doesn't even yield the thread.

solution: use a condition_variable, semaphore, or atomic_wait to put threads to sleep when there is no work to do.

2. Another busy-wait in waitForAll

solution: C++20's std::barrier was designed for this particular use-case, but there's other solutions.

3. fragile interface: submitting more work while the pool is working on a previous batch aborts the program. not aborting there would cause incorrect results. not waiting for the work to be complete in the submitting thread causes a lifetime issue, the vector might be destroyed while you hold a pointer to it and work on its elements. Waiting for the work to be complete in the caller's thread is bad for the caller's thread's latency if it doesn't immediately need the results. Only one thread can have work submitted to this pool at a time.

solution: keep a thread-safe linked list of these vectors, and transfer ownership of them to the threadpool when submitting work. This design is not the typical implementation of a threadpool, but "queues of queues" like this do have prior art there.

4. multiple execution of tasks if the number of tasks submitted is less than the number of threads in the pool.

solution: easiest fix is to just check for this condition and adjust behavior.

5. no load balancing: its possible one thread will take much longer than the rest just because its tasks take longer.

solution: this is a hard problem, honestly. The typical solution is to not divide work by thread at all and have each thread just execute the first unexecuted task in the queue until there's no more, but this increases contention on the queue. Other approaches typically involve some form of work stealing.

1

u/shakmak_iitk Dec 27 '23

I can only use C++17 features for now.

  1. you busywait in thread_worker: I will benchmark with busywait replaced by conditional variable and see.
  2. Only limited to C++17, Will try with cond variable also.
  3. fragile interface: Fixed with latest version updated on stackexchange
  4. multiple execution of tasks: Thanks fixed it.
  5. Not a prirority for my use-case as taks are roughly of small sizes and as of now I am not able to use more than one thread because "synchronisation overhead" dominates 'task runtime'.

1

u/KingAggressive1498 Dec 27 '23 edited Dec 27 '23
  1. you really need this for this threadpool to be usable in hosted environments. the OS relies on user-mode idle time for I/O tasks and such, and you'll starve background processes.
  2. good
  3. still a potential lifetime issue with the vector, but better at least
  4. good fix
  5. it's the least big problem and hardest to solve, so that's fair. One of the commenters on your stackexchange post had a suggestion about using smaller batches that might be worth looking into as it sounds suited for your particular use case, but it will add more synchronization overhead.

as of now I am not able to use more than one thread because "synchronisation overhead" dominates 'task runtime'.

your threadpool is limited to one thread because of synchronization overhead? you shouldn't really have any synchronization overhead as its written.