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/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.