Thread optimized code has weird behaviour
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();
}
}
int 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;
}