Should we have primitive fill-once variables?
david at well-typed.com
Fri Jun 29 05:28:02 UTC 2018
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.
More information about the ghc-devs