I am trying to optimize a C++20 program by splitting work across 12 threads. The single-threaded version works, but after adding threads and several std::barrier synchronization points, the program sometimes produces different output and occasionally appears to get stuck in the main loop. I have tried adding diagnostic output, but the order and results vary between runs, making the problem difficult to isolate.
The program computes Grundy values using dp[i] = mex(dp[j] ^ dp[i-j]) for j <= i/2. Each thread handles part of the j range for a given i. A shared bitset is reset for each iteration, updated by the workers, and then read by the first thread to calculate dp[i]. The dp array is then used by later iterations. The program requires C++20 because it uses std::barrier. What synchronization or data-sharing mistake could explain this behavior, and how should I debug it?
3 Answers
The shared state is very difficult to reason about because the worker threads update the same bitset and the first thread reads it afterward. The mutex protects individual bit assignments, but it does not make the overall algorithm simpler or faster: every update is serialized, so most of the intended parallelism disappears. Make the ownership explicit instead. Give each thread its own local bitset, let it process its assigned j range without a mutex, then combine the local results after a barrier. Also keep all accesses to bs, dp, and s consistently synchronized; relying on the barrier ordering makes the code fragile when it is changed.
The first thing to establish is whether the program is actually hanging or simply producing nondeterministic diagnostic output. Thread scheduling is not deterministic, so the order of the messages will naturally change from run to run. Add logging around every barrier, including the thread ID and iteration, and verify that all 12 threads arrive at each barrier for every iteration. A barrier deadlocks if even one participating thread exits early, throws, or reaches a different control path.
That makes sense for the output order, but some runs also stop making progress. I will log entry and exit around each barrier to find which phase is missing a participant.
Use a thread sanitizer if your compiler supports it, and run the program under a debugger when it stops. On Windows, support depends on the compiler and toolchain; Visual Studio's concurrency tools and compiler warnings can help, while Clang-based builds may provide ThreadSanitizer support in suitable environments. Also replace manual mtx.lock()/mtx.unlock() pairs with std::lock_guard or std::scoped_lock so an exception cannot leave the mutex locked. The barrier itself is not a general substitute for protecting every shared object, so check each read and write against the phase in which it occurs.
The barriers do establish ordering between phases, but a local bitset per worker would remove the per-element locking and make it much easier to check that no data race exists.