unique identifiers as a separate library
isaacdupree at charter.net
Tue Dec 23 11:30:38 EST 2008
Iavor Diatchki wrote:
> - It uses unsafeDupableInterleaveIO to avoid double locking,
> gen r = unsafeDupableInterleaveIO
> $ do v <- unsafeDupableInterleaveIO (genSym r)
> ls <- gen r
> rs <- gen r
> return (Node v ls rs)
where is the double locking? We want referential
e.g. suppose you use newNumSupply to create a thunk for a
Gen; when evaluated, it will run unsafeDupableInterleaveIO.
You send that thunk off to two different other threads.
Then those threads decide to evaluate it (say, enough to get
the first genSym'd value) and happen to make a race
condition, so it becomes two separate IO computations.
Therefore one of them runs atomicModifyIORef, and the other
one runs atomicModifyIORef, and so they get two different
Node 0 (...) (...)
Node 1 (...) (...)
when it's suppose to be the very same Gen data structure.
so, am I right or wrong about what the perils of
I could see changing (unsafe[Dupable]InterleaveIO (genSym
r)) to (genSym r), to halve the number of
unsafeInterleaveIOs needed if we assume that most of the
time a node is evaluated in order to get a value... but it's
hard to see a good way to make *fewer* InterleaveIOs than
there are genSym'd values. (possible, but hard, and really
depends on the relative expenses/risks of locking, of
computing the next number, and of using up the "address
space" of all possible Ints for example). Maybe the outer
InterleaveIO could "strictly" make a few levels of Nodes
(with lazy genSym'd values this time) before "interleaving"
again, to reduce the amount of interleaving from the
More information about the Glasgow-haskell-users