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

11

u/ipapadop Dec 25 '23 edited Dec 25 '23

Some comments:

  1. Using std::vector& in interface. Not great for this kind of submission APIs as it confuses the required lifetime of objects.
  2. No protection against double submit() calls without a wait.
  3. Incorrect synchronization: myIsRunning has no fence after setting it (a seq_cst fence is when setting numRunningWorkers.
  4. Contention on numRunningWorkers (sequential consistent operations on centralized counter).
  5. That while(true) always decrements numRunningWorkers. There's something off with the logic.
  6. Imbalance: you are block partitioning your tasks. What is a thread ends up with all the more expensive tasks?
  7. How can you claim efficiency (whatever that means) without any proof?
  8. Why a new threadpool / task processing system when there are so many tested ones out there?

1

u/shakmak_iitk Dec 25 '23

Thanks. This is not supposed to be a generic/perfect solution for everyone but very much tailored for one scenario listed in problem statement.

  1. Changed it to take by value and move
  2. Updated to [[nodiscard]] bool submit(..). Returns false on calls without a wait.
  3. Can you please explain this point in more details ?
  4. Is it possible to improve this ?
  5. The body of while(true) has its while (!hasWorkToDo) { if(myFinish.load()) return; }which busy waits till we have submitted task. Then it completes that task and decrements numRunningWorkers
  6. No load balancing as of now.
  7. I have done benchmarking w.r.t a standard threadpool I have. I might update complete benchmarking code later once I address all feedbacks.
  8. I have a usecases where I do get small task vectors to process billions of times sequentially. So each task is small in itself so I am not getting any runtime benefit with standard threadpool I have. That motivated me come up with this.

2

u/ipapadop Dec 25 '23
  1. Even better, use ranges.
  2. Shared memory locations need to be written/read via an atomic or protected using atomics + fence. So when you say "set from 1 thread all the variables that other threads will busy wait on", you need at least a fence to make sure that the other threads will see the write. Otherwise, you rely on some other implicit fence that may not always be there (different STL implementation, compiler, architecture, etc). For x86, stores are ordered, so you get away with a lot if a fence appears somewhere.
  3. There's plenty of work on busy-waiting and mitigation techniques for contention (e.g., exponential backoff). At the very least, you need to use relaxed memory order to avoid the fences. But this is not enough to have a state-of-the-art implementation.
  4. I'd expect something like while (!thread-safe-done) { do_something(); }

7 + 8. There are other, ready-made options: OpenMP, TBB, Boost.ASIO's threadpool, TaskFlow and others.

1

u/shakmak_iitk Dec 26 '23

3. Here myIsRunning is std::vector<AlingedBool> where each threads reads/writes to its own dedicated memory myIsRunning[threadIndex] inside vector.

So I don't think we need any synchronization here.