A threading riddle

Re:A threading riddle by oconnore on Monday June 29, 2015 @04:20PM (#9800705)

    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

[ Parent | on HN ]

Re:A threading riddle by Strilanc on Monday June 29, 2015 @04:41PM (#9800875)

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?

[ Parent | on HN ]

Re:A threading riddle by oconnore on Monday June 29, 2015 @04:45PM (#9800911)

> 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!).

[ Parent | on HN ]

Re:A threading riddle by Strilanc on Monday June 29, 2015 @04:59PM (#9801025)

The "you can't read the values" note is referring to the API exposed to callers, not internal restrictions on the implementation.

[ Parent | on HN ]

Re:A threading riddle by JadeNB on Monday June 29, 2015 @05:14PM (#9801138)

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.

[ Parent | on HN ]

Re:A threading riddle by davidtgoldblatt on Monday June 29, 2015 @05:20PM (#9801189)

My bad; Strilanc's interpretation is correct. I updated the wording to hopefully be a little clearer.

[ Parent | on HN ]

Re:A threading riddle by JadeNB on Monday June 29, 2015 @06:12PM (#9801510)

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.

[ Parent | on HN ]

Re:A threading riddle by re on Monday June 29, 2015 @06:19PM (#9801551)

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.

[ Parent | on HN ]

Re:A threading riddle by davidtgoldblatt on Monday June 29, 2015 @07:07PM (#9801778)

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.

[ Parent | on HN ]

Re:A threading riddle by JadeNB on Monday June 29, 2015 @07:49PM (#9801960)

I see; I don't know enough about concurrency to recognise the tongue-in-cheek-ness (or whatever). Thanks for explaining!

[ Parent | on HN ]

Re:A threading riddle by JadeNB on Monday June 29, 2015 @05:12PM (#9801125)

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.

[ Parent | on HN ]