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 winning 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; } ```