I am trying to parallelize a C++20 program that computes Grundy values for Grundy's game. The sequential version works, but after adding twelve worker threads and several std::barrier synchronization points, the program sometimes produces different results and sometimes appears to get stuck in the main loop. The workers divide the inner-loop range among themselves, update a shared bitset under a mutex, and thread 1 computes dp[i] after the other threads finish their work for that iteration. I have checked the obvious race conditions, but I am still unsure whether the barriers and shared state are being used correctly. What could explain this behavior, and how should I debug or restructure it?
3 Answers
Use a thread sanitizer and a debugger that can inspect all threads at the hang. Also avoid relying on _Find_first(): it is an implementation-specific, nonstandard member of some library implementations. Scan the bitset with a normal loop or use a documented alternative. Keep the synchronization explicit and protect every shared object consistently. The barriers should establish the ordering for dp, but logging and a sanitizer are still the quickest way to confirm whether the hang is a barrier wait or an actual data race.
The code is not getting much benefit from concurrency here. Every update to bs takes the mutex, so the most important part of the computation is serialized. The barriers also force all workers to stop several times per iteration. A simpler and safer design would give each worker its own local bitset, let it process its assigned range without locking, and then combine the local results after all workers finish. Alternatively, this inner loop is small enough that a sequential implementation may be faster once thread and barrier overhead are included.
The first thing to verify is where the program stops. A barrier is a collective operation: every one of the twelve participants must call arrive_and_wait() once for every phase. If even one worker returns early, throws an exception, or takes a different control path, all the others will wait forever. Add logging immediately before and after each barrier, including the thread number and iteration. Also check that every worker really executes exactly the same number of loop iterations.
A thread that throws during solve() can also make the process terminate rather than simply leave a useful diagnostic. Wrapping the worker body in a try/catch while debugging can make failures much easier to identify.
On Windows, compiler support for ThreadSanitizer is more limited than on Linux. You can still use Visual Studio’s debugger and concurrency tools, or run the code under a Linux environment such as WSL with a sanitizer-enabled compiler.