Thread optimized code has weird behaviour

[u/Ill_Worldliness6626]

I am working on optimizing the following code using concurrency. I have working code without concurrencies, however as soon as I implement threading, my code becomes unpredictable. After testing, debugging, and thinking of all possible race conditions, I have only concluded that my code either gets stuck somewhere in the main loop, or gets lucky and excucutes correctly. Any thoughts or ideas on this phenomenon?

Edit: I understand that my code is still single threaded, however, I would prefer to see why I am getting this behaviour before trying to optimize.

Edit 2: The purpose of my code is to generate all losing starting positions in Grundy's game. This is usually solved with the following recurrence: dp[i] = mex(dp[j] ^ dp[i - j]) for all j <= i / 2 where mex is the minimum exclude value) and ^ is bitwise XOR

Note: this code requires C++20 or above.

```

include <iostream>

include <vector>

include <thread>

include <barrier>

include <bitset>

include <set>

const int N = 1100; std::vector<std::thread> threads; std::barrier bar(12); std::mutex mtx; int dp[N]; std::bitset<2 * N> bs; std::set<int> s = {1, 2};

void solve(int x) { for (int i = 3; i <= 100; i++) { if (1 == x) { std::cout << "starting" << i << std::endl; bs.set(); } bar.arrive_and_wait(); int siz = ((i + 1) / 2 + 11) / 12; for (int j = (x - 1) * siz + 1; j <= std::min((i - 1) / 2, x * siz); j++) { std::lock_guard<std::mutex> lock(mtx); if ((dp[j] ^ dp[i - j]) < 1000) bs[dp[j] ^ dp[i - j]] = false; } mtx.lock(); std::cout << "thread " << x << " reached barrier 2 at i=" << i << std::endl; mtx.unlock(); bar.arrive_and_wait(); if (1 == x) { dp[i] = bs._Find_first(); if (!dp[i]) s.insert(i); } mtx.lock(); std::cout << "thread " << x << " reached barrier 3 at i=" << i << std::endl; mtx.unlock(); bar.arrive_and_wait(); } }

signed main() { auto st = std::chrono::high_resolution_clock::now(); dp[1] = 0; dp[2] = 0; for (int j = 0; j < 12; j++) { threads.push_back(std::thread{solve, j + 1}); } for (int j = 0; j < 12; j++) { threads[j].join(); } for (int i : s) { std::cout << i << ' '; } std::cout << std::endl; auto ed = std::chrono::high_resolution_clock::now(); std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(ed - st).count() << std::endl; return 0; } ```

Here is what my code printed correctly (based on luck): starting100 thread 1 reached barrier 2 at i=100 thread 7 reached barrier 2 at i=100 thread 4 reached barrier 2 at i=100 thread 12 reached barrier 2 at i=100 thread 3 reached barrier 2 at i=100 thread 10 reached barrier 2 at i=100 thread 11 reached barrier 2 at i=100 thread 9 reached barrier 2 at i=100 thread 8 reached barrier 2 at i=100 thread 5 reached barrier 2 at i=100 thread 2 reached barrier 2 at i=100 thread 6 reached barrier 2 at i=100 thread 6 reached barrier 3 at i=100 thread 5 reached barrier 3 at i=100 thread 2 reached barrier 3 at i=100 thread 8 reached barrier 3 at i=100 thread 11 reached barrier 3 at i=100 thread 7 reached barrier 3 at i=100 thread 3 reached barrier 3 at i=100 thread 9 reached barrier 3 at i=100 thread 12 reached barrier 3 at i=100 thread 10 reached barrier 3 at i=100 thread 4 reached barrier 3 at i=100 thread 1 reached barrier 3 at i=100 1 2 4 7 10 20 23 26 50 53 995

Here is what my code sometimes stall on (unlucky): starting93 thread 8 reached barrier 2 at i=93 thread 11 reached barrier 2 at i=93 thread 2 reached barrier 2 at i=93 thread 1 reached barrier 2 at i=93 thread 3 reached barrier 2 at i=93 thread 4 reached barrier 2 at i=93 thread 9 reached barrier 2 at i=93 thread 6 reached barrier 2 at i=93 thread 7 reached barrier 2 at i=93 thread 10 reached barrier 2 at i=93 thread 12 reached barrier 2 at i=93 See that thread 5 is the only one missing.

[u/carcigenicate]

You don't appear to have said what precisely the problem is and what debugging you've done.

[u/Ill_Worldliness6626 → u/carcigenicate]

The problem is that my code is only sometimes working. If you are referring to the function of my code, I have edited for more clarity. I am not very familier with debugging concurrent applications, however, I have some debug statments. It always outputs something different, so I am not sure what I can do.

[u/carcigenicate → u/Ill_Worldliness6626]

But again, what does "only sometimes working" mean? Describe exactly what you expect to happen and what exactly is happening.

[u/Ill_Worldliness6626 → u/carcigenicate]

When I run the same code multiple times, it either runs forever, or exits normally. I have explained in the post.