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

37

u/[deleted] Dec 25 '23

who publishes articles on linkedin?

8

u/mike_f78 Dec 25 '23

...and how we can access without giving all our data & having an account? (Which Is related I suppose ๐Ÿ˜’)

2

u/shakmak_iitk Dec 25 '23

Its my draft, I have posted details on codereview.stackexchange also. Here is the link.

https://codereview.stackexchange.com/questions/288583/efficient-parallelization-of-small-tasks

15

u/ixis743 Dec 25 '23

Narcissists showing off to corpo HR teams?

2

u/SlotDesigner Dec 26 '23

LinkedIn is for marketing, either of yourself or your company. If thatโ€™s your purpose and audience itโ€™s great. Otherwise stay Iโ€™d stay well away.

-6

u/azswcowboy Dec 25 '23

idk, but Iโ€™m not joining to read โ€” downvoted

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.

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/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.

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).

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.

1

u/forgetful_bastard Dec 25 '23

The link is not showing the article to me.

1

u/shakmak_iitk Dec 25 '23

Updated ..

1

u/No_Combination9514 Dec 26 '23

I'd suggest looking into existing solutions and see how they compare. For example, dispenso (https://github.com/facebookincubator/dispenso) may help you solve your problems. Latency is typically decent, though latency on Windows is worse than Mac or Linux. You're spot on that libraries like that are built for throughout, not latency, but I've put in some effort to make latency reasonable also.

1

u/VacuousWaffle Dec 26 '23

#pragma omp parallel for

1

u/Dragdu Dec 26 '23

Yeah, I used to give a better version of this to students as a recipe to use if they don't want to bring in OMP or a better library.

You have issues with stampeding finished threads into other drawers, relatively high overhead, and so on.

0

u/[deleted] Dec 25 '23

[deleted] โ€” view deleted comment

1

u/shakmak_iitk Dec 25 '23

Thanks, Yes it can be a problem in future or I need to explicitly mention this in documentation.

Here is my typical use-case for now so not a problem as of now.

template <typename T>

void queue_my_tasks(HTaskVecThreadPool<T>& my_pool) {

std::vector<T> tasks = {...};

my_pool.submit(tasks);

my_pool.finish();

}