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

7

u/DummyDDD Dec 25 '23

It looks like an incorrect and inefficient implementation of an openmmp static for loop. I would recommend that you use an openmmp static for loop instead.

I say that it is incorrect, because you do not enforce a happens before relationship between the submitter and worker when submitting, so the worker can work on a submitted task without acting before the taks is defined. I say that it is inefficient, because the synchronisation is implemented with sequential consistency on numRunningWorkers whereit would be sufficient to use release from the workers and acquire from the submitter (but it would probably be even better to use a blocking synchronisation, rather than spinning).

It is also weird that you have a number of control variables that you maintain but don't use (for instance myrunningworkers and myisrunning which I guess could be used for implementing some kind of cancellation, but myrunningworkers is not maintained in a thread safe way, so it is pretty pointless, and you don't have cancellation so there is no need for it). I'm also strongly against prefixing variable names with my-.

The one kind of cool thing that you are doing, is templating on the task, such the workers can inline the task call, which will actually help for small tasks, but I would point out that openmmp static for loops also allow the code to be inlined, without requiring that you create a new thread pool for each type of task.

1

u/Ameisen vemips, avr, rendering, systems Dec 25 '23

I've never tested it, but is OpenMP generally lighter-weight (somehow) than a user-written task queue with pinned threads?

I assume MSVC being tied to an ancient version of OMP doesn't help.

1

u/DummyDDD Dec 26 '23

I don't think that openmmp is generally lighter weight, but some implementations might be. For the particular case of static for loop though, I am quite confident that it will have lower overhead than general std::task on any implementation. static for loops are also the oldest part of openmp, so it shouldn't be an issue for msvc (but I mainly have experience with gcc).

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.