3 ms·

My c++ solution: https://gist.github.com/anonymous/7e6cc8f58e9cde1b6fda https://gist.github.com/anonymous/7e6cc8f58e9cde1b6fda I believe it follows all of the

by sdab 11y ago

My c++ solution: https://gist.github.com/anonymous/7e6cc8f58e9cde1b6fda https://gist.github.com/anonymous/7e6cc8f58e9cde1b6fda I believe it follows all of the requirements. There is one glaring flaw which is that it uses a condition variable per 'wait_until_equal' call, though it uses only N mutexes. So this doesn't fall under the N^2 primitives (in the case of many waits), though its unclear to me if thats an official rule. Im happy to listen to feedback or if someone sees an error.

davidtgoldblatt 11y ago
Looks good to me; that's essentially the solution I had in mind (though, I think you have a race on NintBucket::waiters in modify and append_cv). Using a custom two-mutex lock class and condition_variable_any is particularly clever, I hadn't thought of that. I just published my solution, which uses a similar strategy: http://dgoldblatt.com/a-threading-riddle-solution.html http://dgoldblatt.com/a-threading-riddle-solution.html I don't think of this as violating the N^2 primitives rule; the solution is still linear in the size of the problem its facing (it only uses K condition variables for K threads, so even if K is bigger than N^2, it's still morally in the scope of the problem).
- sdab 11y ago
  Ah, yep I see the race. Here is a fix: https://gist.github.com/sdab/d7ba036b2b7f4b5626cd https://gist.github.com/sdab/d7ba036b2b7f4b5626cd Thanks for the puzzle, its hard to find good concurrency problems. Edit: Looked through your solution. You are right, we thought of similar things. I started out by wanting a multi condition variable, but didnt want to implement it :). I ended up getting something similar in a roundabout way.
ddustin 11y ago
The problem is vector<condition_variable_any*> waiters; Can realloc at any moment, making the following code unsafe: vector<condition_variable_any*>::iterator it; for (it = m_array[index].waiters.begin(); it != m_array[index].waiters.end(); ++it) { (*it)->notify_one(); } If a realloc occurs between the calls to begin() and end() than the loop can become infinite.

by sdab 11y ago

davidtgoldblatt 11y ago

Looks good to me; that's essentially the solution I had in mind (though, I think you have a race on NintBucket::waiters in modify and append_cv). Using a custom two-mutex lock class and condition_variable_any is particularly clever, I hadn't thought of that. I just published my solution, which uses a similar strategy: http://dgoldblatt.com/a-threading-riddle-solution.html http://dgoldblatt.com/a-threading-riddle-solution.html I don't think of this as violating the N^2 primitives rule; the solution is still linear in the size of the problem its facing (it only uses K condition variables for K threads, so even if K is bigger than N^2, it's still morally in the scope of the problem).

sdab 11y ago
Ah, yep I see the race. Here is a fix: https://gist.github.com/sdab/d7ba036b2b7f4b5626cd https://gist.github.com/sdab/d7ba036b2b7f4b5626cd Thanks for the puzzle, its hard to find good concurrency problems. Edit: Looked through your solution. You are right, we thought of similar things. I started out by wanting a multi condition variable, but didnt want to implement it :). I ended up getting something similar in a roundabout way.

ddustin 11y ago

The problem is vector<condition_variable_any*> waiters; Can realloc at any moment, making the following code unsafe: vector<condition_variable_any*>::iterator it; for (it = m_array[index].waiters.begin(); it != m_array[index].waiters.end(); ++it) { (*it)->notify_one(); } If a realloc occurs between the calls to begin() and end() than the loop can become infinite.