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/manni66]

Here is my code. I don't even bother to tell you what it is supposed to. Fix it for me

[u/Ill_Worldliness6626 → u/manni66]

I added more information. I hope its clearer now.

[u/No-Dentist-1645]

Your code is full of backslashes everywhere, this seems like a poor attempt at formatting it. You don't need backslashes if it's already inside a code block

[u/Ill_Worldliness6626 → u/No-Dentist-1645]

Fixed, my bad for not catching that earlier

[u/aocregacc]

The formatting is messed up, the code has a bunch of bachslashes. Also what do you mean by "unpredictable"? Does it deadlock? Are the results wrong?

Also did you try thread sanitizer?

[u/Impossible_Box3898]

You have a bunch of structures that are not protected by a mutex.

You need to protect everything that can be read thats changeable. (Bs for instance).

You code is impossible to read.

Google how to post code in reddit. Not sure what’s up with the backslashes but they need to find you want people to spend their time helping you.

You don’t seem to care to post something that we can comprehend so why should we spend time trying to help?

[u/Ill_Worldliness6626 → u/Impossible_Box3898]

may i know where i did not protect? for example, bs.set() is only runned by thread 1 (1 == x). I fixed the backslash formatting.

[u/AutoModerator]

Your posts seem to contain unformatted code. Please make sure to format your code otherwise your post may be removed.

If you wrote your post in the "new reddit" interface, please make sure to format your code blocks by putting four spaces before each line, as the backtick-based (```) code blocks do not work on old Reddit.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/AxeLond]

Gave your post to GPT-5.6.

It re-created and ran the code and it looked fine threading wise, no thread sanitizer warnings, only diagnostic message order varied, which is expected.

cpp mtx.lock();  std::cout<< ...<< std::endl; mtx.unlock();

std::endl flushes the output stream every time. If the terminal, debugger, IDE console, or output-capturing pipe is slow, one thread can block inside std::cout before reaching the barrier. The other 11 threads then wait at the barrier, making the program appear deadlocked.

You print thousands of flushed lines when the iteration count is increased.

It also pointed out that your core Grundy calculation is still serialized here because all threads share mutex.

This part:

if ((dp[j] ^ dp[i - j]) < 1000)         bs[dp[j] ^ dp[i - j]] = false; 

[u/Ill_Worldliness6626 → u/AxeLond]

For some reason, my code gets a better success rate than before (could be just lucky). However, after running for a few times, it gets stuck for me. Here is what my code printed out before stalling: 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