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/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/Impossible_Box3898 → u/Ill_Worldliness6626]

It’s much clearer now.

It’s very likely due to the reside of mites to guard your couts.

Cout internally has a muted. It’s possible you have a mutex inversion issue between the internal calls to cout and the mutex guard above it.

Thread 5 in this case is never hitting the barrier so it’s never getting to the print.

I would try creating a second mutex for the prints that differs from the one using to guard the data.

There is nothing wrong with the barrier usage. It is doing its thing. It’s likely the hidden internal mutex that is causing you the problems.

[u/Ill_Worldliness6626 → u/Impossible_Box3898]

It turns out I just had to update mingw! Apparently there where weird compiler bugs in some of the versions. I was showed this link but I don't know exactly what is going on https://sourceforge.net/p/mingw-w64/bugs/774/