HN Explorer

22 comments

[ 4.0 ms ] story [ 48.3 ms ] thread
oconnore 

    import Control.Concurrent.STM
    import Control.Monad
    import Data.Vector

    type VecInts = Vector (TVar Int)

    newVecInts :: Int -> STM (VecInts)
    newVecInts s = generateM s (\_ -> newTVar 0)

    modifyVI :: VecInts -> Int -> Int -> STM ()
    modifyVI vi pos val = do
      writeTVar (vi ! pos) val

    waitUntilEqual :: VecInts -> Int -> Int -> STM ()
    waitUntilEqual vi p1 p2 = do
      a <- readTVar (vi ! p1)
      b <- readTVar (vi ! p2)
      when (a /= b) retry
Strilanc
I'm not familiar with the semantics of software transactional memory, but doesn't this violate the "don't busy-loop" requirement? Is the retrying logic smart enough to set up some kind of watch on the values, or does it just run continuously until satisfied?
oconnore
> Is the retrying logic smart enough to set up some kind of watch on the values

Yes. It only retries when one of the referenced values is updated.

This does violate the rule "only use mutexes and condition variables", and perhaps the rule added at the end "you can't read the values" (comparing memory without reading from memory seems like quite a trick!).

Strilanc
The "you can't read the values" note is referring to the API exposed to callers, not internal restrictions on the implementation.
JadeNB
Are you sure? That doesn't seem to match with the wording:

> There's no way to read the values from the array, only to set them and compare them for equality

(emphasis mine). That seems to me to mean literally what it says; that you can query two values for equality, but, either way, have no information about what the values are.

EDIT: From the horse's mouth (https://news.ycombinator.com/item?id=9801189), I'm wrong.

davidtgoldblatt
My bad; Strilanc's interpretation is correct. I updated the wording to hopefully be a little clearer.
JadeNB
Thanks! While you're here, is oconnore (https://news.ycombinator.com/item?id=9800705 )'s solution legal according to your rules?

EDIT: Also, the wording

> There's no way to read the values from the array, only to set them and compare them for equality

seems unchanged.

re
The preceding sentence was changed to be more explicit that the bullet points are about the "user-facing API" being unrealistic. They're not implementation rules/constraints.
davidtgoldblatt
I think his solution is a little bit tongue in cheek - it shows how much easier it is to solve using transactional memory compared to low-level concurrency primitives. So it cheats by using very powerful techniques instead of the very weak ones that the post says to use. You couldn't use his solution in C++ for instance, because C++ doesn't come with garbage collection or transactional memory.
JadeNB
I see; I don't know enough about concurrency to recognise the tongue-in-cheek-ness (or whatever). Thanks for explaining!
JadeNB
I think the rule is that you can only compare the values for equality, not find out what they actually are. (How one would stumble upon such a restriction is a different matter, but at least it's not a paradoxical setup.)

EDIT: From the horse's mouth (https://news.ycombinator.com/item?id=9801189), I'm wrong.

brlewis
This is an example of why I see node.js having more value in its single-threaded async architecture than in its capacity to use the same programming language on client and server.

More generally, when you discover a tricky problem that would make a good interview question, oftentimes there's an architectural decision that would eliminate the problem.

oconnore 

    var a = [0, 0, 0];

    // Accept input from user
    function modify(i, v) {
      a[i] = v;
      // ...
    }

    // Trigger an event when two values are equal
    function waitUntil(i, j) {
      return new Promise(function(res, rej) {
        // ?
      });
    }
brlewis 

  var EventEmitter = require('events').EventEmitter;
  var Promise = require('promise');

  function Answer() {
    var values = [];
    var emitters = [];

    this.modify = function(index, value) {
        values[index] = value;
        if (emitters[index]) {
            emitters[index].emit('modified');
        }
    };

    this.waitUntilEqual = function(index1, index2) {
        return new Promise(function(resolve) {
            if (!emitters[index1]) {
                emitters[index1] = new EventEmitter();
            }
            if (!emitters[index2]) {
                emitters[index2] = new EventEmitter();
            }
            function compare() {
                if (values[index1] === values[index2]) {
                    resolve();
                }
            }
            emitters[index1].on('modified', compare);
            emitters[index2].on('modified', compare);
        });
    };
  }

  var check = new Answer();
  check.waitUntilEqual(0, 1).then(function () {   console.log('equal'); });
  check.modify(0, 'x');
  check.modify(1, 'x');
oconnore
Nice job! But I thought you said this problem would be eliminated by the architecture of Node.js? This appears to be longer and more complex than the fully parallel and concurrent Haskell solution.
brlewis
It eliminates having to think about race conditions. It doesn't automatically mean concise code.
[deleted]
(comment deleted)
[dead] ddustin
I believe the problem is simple enough to solve assuming I have the requirements correct. Essentially you need these types:

    map<int, map<int, int>> equalityIndices;
    map<int, pair<mutex, condition_variable> pendingWaits;
    mutex writeLock;
When a call to wait occurs you do:

    writeLock.lock();
    
    mutex *m;
    condition_variable *cv;
    
    if(pendingWaits.count(index1)) {
        m = &pendingWaits[index1].first;
        cv = &pendingWaits[index1].second;
    }
    else {
        m = &pendingWaits[index2].first;
        cv = &pendingWaits[index2].second;
    }
    
    equalityIndices[index1][index2]++;
    equalityIndices[index2][index1]++;
    
    writeLock.unlock();
    
    unique_lock lk(*m);
    
    do {
        cv->wait(lk);
    } while(array[index1] != array[index2]);
    
    writeLock.lock();
    
    if(--equalityIndices[index1][index2] == 0) {
        equalityIndices[index1].erase(index2);
        if(equalityIndices[index1].empty()) {
            equalityIndices.erase(index1);
            pendingWaits.erase(index1);
        }
    }
    
    if(--equalityIndices[index2][index1] == 0) {
        equalityIndices[index2].erase(index1);
        if(equalityIndices[index2].empty()) {
            equalityIndices.erase(index2);
            pendingWaits.erase(index2);
        }
    }
    
    writeLock.unlock();
Then in the update value function you do

    array[index] = value;
    
    if(equalityIndices.count(index)) {
        pendingWaits[index].second.notify_all();
        try {
            for(const auto itr : equalityIndices.at(index))
                if(array[index] == array[*itr])
                    pendingWaits[*itr].second.notify_all();
        }
        catch(out_of_range e) {
            (void)e;
        }
    }
This gives you a typical write overhead of O(log k) where k is your number of unique index equality monitors.

The wait until equal method will have a few O(log k) overheads.

sdab
My c++ solution: 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
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

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
Ah, yep I see the race. Here is a fix: 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.

[dead] ddustin
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.