IVars (write-once variables) can be useful for various purposes. In Haskell, they can be implemented using MVars. But MVars are not the lightest things in the world. I'm wondering if it might pay to implement something much lighter primitively. Here's a sketch of some things I'll tentatively call QVars. A QVar has two fields: a value (possibly null) and a stack (no need for a queue) of waiting threads. newEmptyQVar: Create a QVar with a null value and an empty queue. tryReadQVar: Just look at the value. readQVar: Check if the value is null (simple memory read). If not, use it. If so, push yourself onto the waiting stack (CAS loop). The code that will run when you're awakened will try to awaken the next thread if there is one (CAS loop). putQVar: Install a new value and get the old one (exchange). If the old value was null, mark the QVar dirty. Awaken the first thread if there is one (CAS loop). Return the old value if it was non-null (this can be used in library code to make duplicate writes, or non-equal duplicate writes, an error). I think we'd probably also want atomic modification operations, but I haven't figured out which ones yet. Implementation differences from MVars: * We have two fields instead of three (because we can get away with a stack instead of a queue). * We never need to lock the QVar closure. MVars do: they can change freely between empty and full, so it's necessary to coordinate between value and queue modifications.
I have wanted something like that! Also similiar STM TQVar would be nice to have. For example `async` uses TMVar where the value is written only once. if once filled the QVar cannot be empty is useful property. For STM variant, I'd actually like to have putTQVar' :: QTVar a -> a -> STM (TVar a) i.e. giving me back a `TVar a`, for which I now the value is already there (i.e. reading won't block). Not sure what the would be such for IO, IORef doesn't feel right. - Oleg On 29.06.2018 08:28, David Feuer wrote:
IVars (write-once variables) can be useful for various purposes. In Haskell, they can be implemented using MVars. But MVars are not the lightest things in the world. I'm wondering if it might pay to implement something much lighter primitively. Here's a sketch of some things I'll tentatively call QVars.
A QVar has two fields: a value (possibly null) and a stack (no need for a queue) of waiting threads.
newEmptyQVar: Create a QVar with a null value and an empty queue.
tryReadQVar: Just look at the value.
readQVar: Check if the value is null (simple memory read). If not, use it. If so, push yourself onto the waiting stack (CAS loop). The code that will run when you're awakened will try to awaken the next thread if there is one (CAS loop).
putQVar: Install a new value and get the old one (exchange). If the old value was null, mark the QVar dirty. Awaken the first thread if there is one (CAS loop). Return the old value if it was non-null (this can be used in library code to make duplicate writes, or non-equal duplicate writes, an error).
I think we'd probably also want atomic modification operations, but I haven't figured out which ones yet.
Implementation differences from MVars:
* We have two fields instead of three (because we can get away with a stack instead of a queue).
* We never need to lock the QVar closure. MVars do: they can change freely between empty and full, so it's necessary to coordinate between value and queue modifications. _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
This would make MonadFix's implementation much nicer, I think :)
On Fri, Jun 29, 2018 at 9:14 AM, Oleg Grenrus
I have wanted something like that! Also similiar STM TQVar would be nice to have. For example `async` uses TMVar where the value is written only once. if once filled the QVar cannot be empty is useful property.
For STM variant, I'd actually like to have
putTQVar' :: QTVar a -> a -> STM (TVar a)
i.e. giving me back a `TVar a`, for which I now the value is already there (i.e. reading won't block). Not sure what the would be such for IO, IORef doesn't feel right.
- Oleg
IVars (write-once variables) can be useful for various purposes. In Haskell, they can be implemented using MVars. But MVars are not the
On 29.06.2018 08:28, David Feuer wrote: lightest things in the world. I'm wondering if it might pay to implement something much lighter primitively. Here's a sketch of some things I'll tentatively call QVars.
A QVar has two fields: a value (possibly null) and a stack (no need for
a queue) of waiting threads.
newEmptyQVar: Create a QVar with a null value and an empty queue.
tryReadQVar: Just look at the value.
readQVar: Check if the value is null (simple memory read). If not, use
it. If so, push yourself onto the waiting stack (CAS loop). The code that will run when you're awakened will try to awaken the next thread if there is one (CAS loop).
putQVar: Install a new value and get the old one (exchange). If the old
value was null, mark the QVar dirty. Awaken the first thread if there is one (CAS loop). Return the old value if it was non-null (this can be used in library code to make duplicate writes, or non-equal duplicate writes, an error).
I think we'd probably also want atomic modification operations, but I
haven't figured out which ones yet.
Implementation differences from MVars:
* We have two fields instead of three (because we can get away with a
stack instead of a queue).
* We never need to lock the QVar closure. MVars do: they can change
freely between empty and full, so it's necessary to coordinate between value and queue modifications.
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Hi, when reading the subject I was expecting something like this: -- | Creates an empty IVar newIVar :: IO (IVar a) -- | pure! but blocks until the IVar is written readIVar :: IVar a -> a -- | tries to write to an IVar. -- Succeeds if it is empty (returning True) -- Does nothing if it has been written to (returning False) writeIVar :: IVar a -> a -> IO Bool Alternatively: -- | all in one newIVar :: IO (a, a -> IO Bool) Essentially a thunk, but with explicit control over filling it. In fact, people have implemented something like this using C-- hacks before: https://github.com/twanvl/unsafe-sequence
This would make MonadFix's implementation much nicer, I think :)
This would suffice for MonadFix, right? Sorry for derailing the thread :-) Cheers, Joachim -- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/
i'm a little confused, whats the order of reads here?
Mvars have write wins, whats the order here? last writer runs first, first
writer runs last? (wouldn't there be starvation issues?)
On Fri, Jun 29, 2018 at 11:51 AM Joachim Breitner
Hi,
when reading the subject I was expecting something like this:
-- | Creates an empty IVar newIVar :: IO (IVar a)
-- | pure! but blocks until the IVar is written readIVar :: IVar a -> a
-- | tries to write to an IVar. -- Succeeds if it is empty (returning True) -- Does nothing if it has been written to (returning False) writeIVar :: IVar a -> a -> IO Bool
Alternatively:
-- | all in one newIVar :: IO (a, a -> IO Bool)
Essentially a thunk, but with explicit control over filling it. In fact, people have implemented something like this using C-- hacks before: https://github.com/twanvl/unsafe-sequence
This would make MonadFix's implementation much nicer, I think :)
This would suffice for MonadFix, right?
Sorry for derailing the thread :-)
Cheers, Joachim
-- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/ _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
*first write first On Fri, Jun 29, 2018 at 12:19 PM Carter Schonwald < carter.schonwald@gmail.com> wrote:
i'm a little confused, whats the order of reads here? Mvars have write wins, whats the order here? last writer runs first, first writer runs last? (wouldn't there be starvation issues?)
On Fri, Jun 29, 2018 at 11:51 AM Joachim Breitner < mail@joachim-breitner.de> wrote:
Hi,
when reading the subject I was expecting something like this:
-- | Creates an empty IVar newIVar :: IO (IVar a)
-- | pure! but blocks until the IVar is written readIVar :: IVar a -> a
-- | tries to write to an IVar. -- Succeeds if it is empty (returning True) -- Does nothing if it has been written to (returning False) writeIVar :: IVar a -> a -> IO Bool
Alternatively:
-- | all in one newIVar :: IO (a, a -> IO Bool)
Essentially a thunk, but with explicit control over filling it. In fact, people have implemented something like this using C-- hacks before: https://github.com/twanvl/unsafe-sequence
This would make MonadFix's implementation much nicer, I think :)
This would suffice for MonadFix, right?
Sorry for derailing the thread :-)
Cheers, Joachim
-- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/ _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
On Friday, June 29, 2018 12:19:53 PM EDT Carter Schonwald wrote:
i'm a little confused, whats the order of reads here? Mvars have write wins, whats the order here? last writer runs first, first writer runs last? (wouldn't there be starvation issues?)
Writes would occur in no particular order (very much like atomicWriteIORef). Blocked reads would occur from last to first, and I think that's okay. If you think about this as being primarily intended to implement IVars, but with a little extra flexibility, you should get the right intuition.
On Friday, June 29, 2018 11:51:07 AM EDT Joachim Breitner wrote:
when reading the subject I was expecting something like this:
-- | pure! but blocks until the IVar is written readIVar :: IVar a -> a
-- | tries to write to an IVar. -- Succeeds if it is empty (returning True) -- Does nothing if it has been written to (returning False) writeIVar :: IVar a -> a -> IO Bool
It really depends. Are there useful (compile-time or run-time) optimization for IVars (write-once) that don't apply to QVars (fill-once)? If so, we might indeed want to offer writeIVar as you suggest, and
readIVar :: IVar a -> (# a #)
The unboxed tuple allows the value to be extracted from the IVar without being forced. If, however, we want QVars, we can always simulate that using accursedUnutterablePerformIO:
readIVarPure (IVar var) = case readIVar# var realWorld# of (# _, a #) -> (# a #)
I don't know if there are useful IVar optimizations or not. If so, we should take them; if not, we should take the extra flexibility.
Alternatively:
-- | all in one newIVar :: IO (a, a -> IO Bool)
Does this have some advantage as a primop?
In fact, people have implemented something like this using C-- hacks before: https://github.com/twanvl/unsafe-sequence
I'll have to take a look.
This would make MonadFix's implementation much nicer, I think :)
This would suffice for MonadFix, right?
It should indeed. Side note: my implementation sketch for readQVar was missing one piece: after a reader pushes itself on the stack, it must check the QVar status a second time in case the QVar was filled between the read and the enstackment. If it's been filled, it needs to awaken the first thread the way writeQVar would. Indeed, it might as well check the QVar status on every trip through the CAS loop.
On Friday, June 29, 2018 12:54:23 PM EDT David Feuer wrote:
The unboxed tuple allows the value to be extracted from the IVar without being forced. If, however, we want QVars, we can always simulate that using accursedUnutterablePerformIO:
Actually, this might be silly, depending on implementation details. Twan's technique (which may or may not be directly relevant) overwrites a closure with its final value, which is a pretty good match for your approach. We still need to be able to implement tryRead[IQ]Var; I'm not sure what limitations that imposes.
Hi, Am Freitag, den 29.06.2018, 12:54 -0400 schrieb David Feuer:
On Friday, June 29, 2018 11:51:07 AM EDT Joachim Breitner wrote:
when reading the subject I was expecting something like this:
-- | pure! but blocks until the IVar is written readIVar :: IVar a -> a
-- | tries to write to an IVar. -- Succeeds if it is empty (returning True) -- Does nothing if it has been written to (returning False) writeIVar :: IVar a -> a -> IO Bool
It really depends. Are there useful (compile-time or run-time) optimization for IVars (write-once) that don't apply to QVars (fill- once)? If so, we might indeed want to offer writeIVar as you suggest, and
I don’t know! Maybe the GC can treat a filled IVar differently (because it is no longer mutable?) But really, I don't know :-) Cheers, Joachim -- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/
On Friday, June 29, 2018 2:13:39 PM EDT Joachim Breitner wrote:
I don’t know! Maybe the GC can treat a filled IVar differently (because it is no longer mutable?) But really, I don't know :-)
That's a very good point. If we turn the IVar into a pure value, then it loses its "dirty" bit and the GC no longer has to check whether it's pointing to a newer generation. But this is getting into territory that's pretty murky to me.
Thinking this through some more, I see real trade-offs between the two approaches. The names I've assigned them are for reference only, and not intended to claim or assign any credit. Approach 1 (Feuer style) The IVar is pretty much just a stripped-down MVar. Features: * Should be pretty simple to implement. * We get object identity (equality, stable names, weak pointers) without any fuss. * We can have mutation if we want it (i.e., QVar rather than true IVar). * We can unsafeCoerce our way into sticking a QVar# directly into a QVar# if that's useful. Downside: * An IVar is always an indirection. Approach 2 (Breitner/Van Laarhoven style) Writing to an IVar turns it into an indirection to its value. Feature: * Long-lived filled IVars are compacted, removing indirections. Downsides: * Mutation isn't an option at all. * Object identity looks quite tricky. Options: - Don't have object identity for IVars. - Require values to be forced to WHNF before being written to IVars and pull some trickery. - Make thunks noDuplicate# when they're written to IVars and pull some trickery. * We'll have to make sure the garbage collector doesn't goof things up. In particular, if a value has been written to an IVar, but the waiting threads haven't been woken up yet, we need to be sure not to lose the threads. Do we already have some similar logic for threads waiting on blackholes? * We can't ever stick an IVar# directly inside an IVar#, because there's then no way for tryReadIVar to tell whether it's at the right nesting depth. I doubt this is the biggest deal, but I figured I should mention it. All in all, I'm leaning toward proposing the Feuer style because of its relative simplicity. Someone familiar enough with GHC internals could probably implement it in a day or two, while the Breitner/Van Laarhoven approach would take much more serious thinking. But perhaps the indirection-removal is worth the price; I dunno.
participants (5)
-
Carter Schonwald -
David Feuer -
Joachim Breitner -
Oleg Grenrus -
Ryan Trinkle