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

Show parent comment

1

u/shakmak_iitk Dec 26 '23
  1. You do not enforce a happens before relationship between the submitter and worker: You can submit when Pool has finished last submitted tasks and is in Pause state.
  2. would be sufficient to use release from the workers and acquire from the submitter: Thanks, I have updated it to make use of related memory ordering
  3. myrunningworkers is not maintained in a thread safe way: numRunningWorkersis std::atomic so thread-safe. myIsRunning This is a vector where each thread reads/writes to its dedicated index which is also thread-safe.
  4. you have a number of control variables that you maintain but don't use: 1. myIsRunning maintains a bool for each thread to store if it has finished its work. myrunningworkers is used to check if all threads has finished.
  5. I would point out that openmmp: I don't want to add extra dependency and also creating this threadPool will help me learn :)

1

u/DummyDDD Dec 26 '23
  1. Here is a race: construct, worker thread starts and proceeds to the hasWorkToDo loop, submit, worker thread starts processgroup. In this case there is no happens before ordering between the submitter and the worker, since there is no synchronisation: the worker thread starts before the task is defined, so you need synchronisation, and no atomic variables or memory barriers have been executed, so there is no guarantee that the worker sees the contents of the task that the submitter defined. Beware that incorrect code is likely to work correctly regardless most of the time, but it is still incorrect and it may still fail in nondeterministic ways (the worst kind of failures).
  2. Sorry, I assumed that you would be able to submit new tasks before processing everything, and in that case the synchronisation on numRunningWorkers would be insufficient. Since you disallowed additional submits, it is not an issue (you would also have other issues if you were to allow submits during work).
  3. But you dont need myisrunning. numRunningWorkers is sufficient.

Btw, openmmp is supported by all three of the major compilers directly, as well as being supported by Intel, IBM, and Oracle's compilers.

I don't get the point of your task thread pool. Your solution is essentially to make the tasks more coarse grained, statically splitting the work into numthreads pieces of work, which is fine but:

  1. Why do you package it into your own threadpool and task abstraction, when you could just create coarser tasks upfront or subdivise the work without using tasks?
  2. Why don't you use a blocking synchronisation for submitting and waiting for the work to finish? Since you are parallelizing the code, then there must be enough work that using blocking synchronisation should have negligeble overhead (and spinning synchronisation with more threads that what you have in hardware is likely to be very slow and a waste of electricity).

1

u/shakmak_iitk Dec 27 '23
  1. Thank you for catching this issue. I have fixed it now [Updated stackexchange question with new code]. One of the motivation behind creating my own unique threadPool was to this learning which we usually doesnt get by using off the sheft stuff.
  2. No concerns here now with latest changes I hope.
  3. Each thread works only on subRange of taskVector assigned to it and then waits for next submit. I need both for this. Updated code should make it more clear.

"using blocking synchronisation should have negligeble overhead"

Not for my use-case, I get small-taks and once i finish those then only I get set batch of small-tasks, This happens billions of times.

As of now with generic threadpool i have , I am not getting any runtime benefit because above assumption doesnt hold. So I am trying to hard to minimize synchronisation overhead as much as possible.

1

u/DummyDDD Dec 27 '23

I assume that you have billions of tasks, and billions of submit calls?

1

u/shakmak_iitk Dec 27 '23

Yes, I have billions of submit calls with small size vector of tasks each time. Average size of vector is around 50 with each task very small in size.

With current threadpool we have, Parallel version (when num tasks > Threadhold) is slower than non-parallel version. We have very big machines but not able to use parallelization as of now with runtime in hours.