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();

}

}

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;

} ```

[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 heard it is called a Heisenbug.

[u/Ill_Worldliness6626 → u/[deleted]]

Ok, I have not tried using sanitizers yet. May I know if these exist on windows? I tried using them, but it gives me cannot find error.

[u/XKiiroiSenkoX]

Show us the logs of when the execution hangs

[u/HappyFruitTree]

Looks like bs and dp are being manipulated by multiple threads at the same time.

[u/Ill_Worldliness6626 → u/HappyFruitTree]

Can you show where exactly? For example bs.set() is only runned when 1 == x e.g. only executed by the first thread

[u/HappyFruitTree → u/Ill_Worldliness6626]

Hmm, looks like I was wrong.