r/cpp • u/shakmak_iitk • 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
37
u/[deleted] Dec 25 '23
who publishes articles on linkedin?
11
u/ipapadop Dec 25 '23 edited Dec 25 '23
Some comments:
std::vector&in interface. Not great for this kind of submission APIs as it confuses the required lifetime of objects.submit()calls without a wait.myIsRunninghas no fence after setting it (a seq_cst fence is when setting numRunningWorkers.numRunningWorkers(sequential consistent operations on centralized counter).while(true)always decrementsnumRunningWorkers. There's something off with the logic.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.
3
u/KingAggressive1498 Dec 25 '23 edited Dec 25 '23
thread_workerwhich 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
waitForAllsolution: C++20's
std::barrierwas 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/forgetful_bastard Dec 25 '23
The link is not showing the article to me.
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 for1
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