Should we have primitive fill-once variables?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Should we have primitive fill-once variables?

David Feuer-2
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

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

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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

Ryan Trinkle-3
This would make MonadFix's implementation much nicer, I think :)

On Fri, Jun 29, 2018 at 9:14 AM, Oleg Grenrus <[hidden email]> wrote:
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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

Joachim Breitner-2
In reply to this post by David Feuer-2
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
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

Carter Schonwald
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 <[hidden email]> 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
  [hidden email]
  http://www.joachim-breitner.de/
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

Carter Schonwald
*first write first

On Fri, Jun 29, 2018 at 12:19 PM Carter Schonwald <[hidden email]> 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 <[hidden email]> 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
  [hidden email]
  http://www.joachim-breitner.de/
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

David Feuer-2
In reply to this post by Joachim Breitner-2
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.
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

David Feuer-2
In reply to this post by Carter Schonwald
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.
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

David Feuer-2
In reply to this post by David Feuer-2
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.
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

Joachim Breitner-2
In reply to this post by David Feuer-2
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
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

David Feuer-2
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.
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Should we have primitive fill-once variables?

David Feuer-2
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.
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs