Nailing down what we expect IO to do and not do - and why
I'm writing a book, I'd like to get this nailed down and to get it right. If anyone on here that's familiar with the various ways in which IO/State#/realWorld# work in GHC and you have time to reply, anything at all would be welcome. Any pointers, links, references, details, anecdotes, or faint memories of GHC bugs will be greatly appreciated! Getting this written up (possibly for addition to Michael Snoyman's wiki article?) would make me, and I imagine others, a lot happier with trying to understand how the different bits and bobs fit together. I will be dumping my notes as I don't want to get linked to stuff that can be googled because I've already lost 10-15 hours to just that in the past 3-4 days. Digging it up in the compiler is hard because compiler behavior that influences how IO actions are treated don't necessarily have "IO" or "realWorld" mentioned in the relevant parts of the compiler, optimizations, etc. What I'm hoping for is answers on what specifically preserves the listed properties we want from IO in the compiler, prims, or structure of how we write IO actions. What we expect IO to do: - Disable sharing of results, even when it's not a lambda and is evaluated multiple times by the same name. ie, getCurrentTime :: IO UTCTime should get evaluated more than once. - Not reorder sequential IO actions, such as in a do-block. Called "linearity" below - Not duplicate the effects of IO actions. Effects shouldn't be spuriously duplicated during optimization passes. - Effects should not be discarded separately of the value returned by an IO action, merged, or elided. # Sharing A friend suggested that perhaps one-shot semantics via the state hack for State# in the IO type is responsible for disabling sharing, I don't believe so, but here are my notes.
-fno-state-hack Turn off the "state hack" whereby any lambda with a State# token as argument is considered to be single-entry, hence it is considered OK to inline things inside it. This can improve performance of IO and ST monad code, but it runs the risk of reducing sharing.
A one shot lambda State hack, makes the lambda over State# assume it's one-shot universally by default. one-shot/state hack is an anti-inlining heuristic, suggesting that inlining is costly.
Can the IO state hack be avoided if oneShot is used in the right places in
Also I found this on Trac, does anyone know the answer to this? Is the summary above accurate? library code, e.g. in IO’s definition of >>=? This seems related how the state token works, for differentiating which IO action is which and how many times an IO action should run, when it should run, etc.
From the prims:
data State# s
State# is the primitive, unlifted type of states. It has one type parameter, thus State# RealWorld, or State# s, where s is a type variable. The only purpose of the type parameter is to keep different state threads separate. It is represented by nothing at all.
data RealWorld
RealWorld is deeply magical. It is primitive, but it is not unlifted (hence ptrArg). We never manipulate values of type RealWorld; it's only used in the type system, to parameterise State#.
# Linearity Is this from the nesting of lambdas? It doesn't seem like that's enough based on the various examples using State/State# in GHC Trac bug tickets. The RealWorld token seems to be what's driving this but precisely how that works hasn't been easy to find. # Discarding, not inlining effects I believe these are addressed by has_side_effects in the prim ops. I could very well be wrong. can_fail has_side_effects Discard NO NO Float in YES YES Float out NO NO Duplicate YES NO * Duplication. You cannot duplicate a has_side_effect primop. You might wonder how this can occur given the state token threading, but just look at Control.Monad.ST.Lazy.Imp.strictToLazy! We get something like this p = case readMutVar# s v of (# s', r #) -> (S# s', r) s' = case p of (s', r) -> s' r = case p of (s', r) -> r I believe duplication addresses inlining IO actions more generally but I could be wrong. Here's a note I found regarding elision/merging: * Use the compiler flag @-fno-cse@ to prevent common sub-expression elimination being performed on the module, which might combine two side effects that were meant to be separate. A good example is using multiple global variables (like @test@ in the example below). Any help or pointers for nailing down and documenting this would be greatly appreciated. Also if there's a more detailed explanation of what behavior is expected out of each unsafe function, that would help as well. There are bits and pieces I've been able to aggregate from the GHC trac tickets. References used (not exhaustive): - Referential Transparency; Haskell Wiki https://wiki.haskell.org/Referential_transparency - IO Inside; Haskell Wiki https://wiki.haskell.org/IO_inside - Unraveling the mystery of the IO Monad; Edward Z. Yang http://blog.ezyang.com/2011/05/unraveling-the-mystery-of-the-io-monad/ - Evaluation order and state tokens; Michael Snoyman https://wiki.haskell.org/Evaluation_order_and_state_tokens - Haskell GHC Illustrated; Takenobu Tani - Tackling the Awkward Squad; Simon Peyton Jones http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/m... - Note [IO hack in the demand analyser]; GHC source code - Monadic I/O in Haskell 1.3; Andrew D. Gordon and Kevin Hammond - Haskell Report 1.2 http://haskell.cs.yale.edu/wp-content/uploads/2011/01/haskell-report-1.2.pdf Thank you for your time, Chris
If you are thinking about the compiler internals, then knowing about State# etc is necessary. “Digging it up in the compiler is hard” Indeed, and you should not have to do that. If you are think about programmers, and how they reason about their programs, then my working hypothesis is that all that stuff should be irrelevant, and indeed confusing. State# etc is just an implementation technique. Just use the semantics in “Tackling the awkward squad”. Simon From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of Christopher Allen Sent: 31 January 2016 01:57 To: ghc-devs@haskell.org Subject: Nailing down what we expect IO to do and not do - and why I'm writing a book, I'd like to get this nailed down and to get it right. If anyone on here that's familiar with the various ways in which IO/State#/realWorld# work in GHC and you have time to reply, anything at all would be welcome. Any pointers, links, references, details, anecdotes, or faint memories of GHC bugs will be greatly appreciated! Getting this written up (possibly for addition to Michael Snoyman's wiki article?) would make me, and I imagine others, a lot happier with trying to understand how the different bits and bobs fit together. I will be dumping my notes as I don't want to get linked to stuff that can be googled because I've already lost 10-15 hours to just that in the past 3-4 days. Digging it up in the compiler is hard because compiler behavior that influences how IO actions are treated don't necessarily have "IO" or "realWorld" mentioned in the relevant parts of the compiler, optimizations, etc. What I'm hoping for is answers on what specifically preserves the listed properties we want from IO in the compiler, prims, or structure of how we write IO actions. What we expect IO to do: - Disable sharing of results, even when it's not a lambda and is evaluated multiple times by the same name. ie, getCurrentTime :: IO UTCTime should get evaluated more than once. - Not reorder sequential IO actions, such as in a do-block. Called "linearity" below - Not duplicate the effects of IO actions. Effects shouldn't be spuriously duplicated during optimization passes. - Effects should not be discarded separately of the value returned by an IO action, merged, or elided. # Sharing A friend suggested that perhaps one-shot semantics via the state hack for State# in the IO type is responsible for disabling sharing, I don't believe so, but here are my notes.
-fno-state-hack Turn off the "state hack" whereby any lambda with a State# token as argument is considered to be single-entry, hence it is considered OK to inline things inside it. This can improve performance of IO and ST monad code, but it runs the risk of reducing sharing.
A one shot lambda State hack, makes the lambda over State# assume it's one-shot universally by default. one-shot/state hack is an anti-inlining heuristic, suggesting that inlining is costly.
Also I found this on Trac, does anyone know the answer to this? Is the summary above accurate?
Can the IO state hack be avoided if oneShot is used in the right places in library code, e.g. in IO’s definition of >>=?
This seems related how the state token works, for differentiating which IO action is which and how many times an IO action should run, when it should run, etc. From the prims:
data State# s
State# is the primitive, unlifted type of states. It has one type parameter, thus State# RealWorld, or State# s, where s is a type variable. The only purpose of the type parameter is to keep different state threads separate. It is represented by nothing at all.
data RealWorld
RealWorld is deeply magical. It is primitive, but it is not unlifted (hence ptrArg). We never manipulate values of type RealWorld; it's only used in the type system, to parameterise State#.
# Linearity Is this from the nesting of lambdas? It doesn't seem like that's enough based on the various examples using State/State# in GHC Trac bug tickets. The RealWorld token seems to be what's driving this but precisely how that works hasn't been easy to find. # Discarding, not inlining effects I believe these are addressed by has_side_effects in the prim ops. I could very well be wrong. can_fail has_side_effects Discard NO NO Float in YES YES Float out NO NO Duplicate YES NO * Duplication. You cannot duplicate a has_side_effect primop. You might wonder how this can occur given the state token threading, but just look at Control.Monad.ST.Lazy.Imp.strictToLazy! We get something like this p = case readMutVar# s v of (# s', r #) -> (S# s', r) s' = case p of (s', r) -> s' r = case p of (s', r) -> r I believe duplication addresses inlining IO actions more generally but I could be wrong. Here's a note I found regarding elision/merging: * Use the compiler flag @-fno-cse@ to prevent common sub-expression elimination being performed on the module, which might combine two side effects that were meant to be separate. A good example is using multiple global variables (like @test@ in the example below). Any help or pointers for nailing down and documenting this would be greatly appreciated. Also if there's a more detailed explanation of what behavior is expected out of each unsafe function, that would help as well. There are bits and pieces I've been able to aggregate from the GHC trac tickets. References used (not exhaustive): - Referential Transparency; Haskell Wiki https://wiki.haskell.org/Referential_transparencyhttps://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fwiki.haskell.org%2fReferential_transparency&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=ecpPX5Ru1ov20MumzpjiSHEX5uR12Xyk1CaHQ0Vizcw%3d - IO Inside; Haskell Wiki https://wiki.haskell.org/IO_insidehttps://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fwiki.haskell.org%2fIO_inside&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=fk7unq7EtFReU81Td%2bvhAYAFE71hzTLcoCuM4SJz90s%3d - Unraveling the mystery of the IO Monad; Edward Z. Yang http://blog.ezyang.com/2011/05/unraveling-the-mystery-of-the-io-monad/https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fblog.ezyang.com%2f2011%2f05%2funraveling-the-mystery-of-the-io-monad%2f&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=sUe0aq9yaMNqNzhlEOporHOLgBkDWF3t27HOhrq7MmQ%3d - Evaluation order and state tokens; Michael Snoyman https://wiki.haskell.org/Evaluation_order_and_state_tokenshttps://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fwiki.haskell.org%2fEvaluation_order_and_state_tokens&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=SO1OefBi8YlTWj3vDq8pbwupW3LFGMsf2hGyXwPQ6O0%3d - Haskell GHC Illustrated; Takenobu Tani - Tackling the Awkward Squad; Simon Peyton Jones http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/m...https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fresearch.microsoft.com%2fen-us%2fum%2fpeople%2fsimonpj%2fpapers%2fmarktoberdorf%2fmark.pdf&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=0V9ZswJSVeZfZR1i0Qn7wORO8f7Qd1geUJap0e8hCKQ%3d - Note [IO hack in the demand analyser]; GHC source code - Monadic I/O in Haskell 1.3; Andrew D. Gordon and Kevin Hammond - Haskell Report 1.2 http://haskell.cs.yale.edu/wp-content/uploads/2011/01/haskell-report-1.2.pdfhttps://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fhaskell.cs.yale.edu%2fwp-content%2fuploads%2f2011%2f01%2fhaskell-report-1.2.pdf&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=SrvFhhQkvW%2f%2f1PFcpV8VKSaEeqrfm53JfUFJdUnXeWA%3d Thank you for your time, Chris
Right, I'm seeking to understand the internals more generally, but
specifically I'd like to know the answers to my questions in my original
email.
I'd really appreciate some pointers and information on this.
On Mon, Feb 1, 2016 at 2:57 AM, Simon Peyton Jones
If you are thinking about the compiler internals, then knowing about State# etc is necessary. “Digging it up in the compiler is hard” Indeed, and you should not have to do that.
If you are think about *programmers*, and how they *reason about their programs*, then my working hypothesis is that all that stuff should be irrelevant, and indeed confusing. State# etc is just an implementation technique. Just use the semantics in “Tackling the awkward squad”.
Simon
*From:* ghc-devs [mailto:ghc-devs-bounces@haskell.org] *On Behalf Of *Christopher Allen *Sent:* 31 January 2016 01:57 *To:* ghc-devs@haskell.org *Subject:* Nailing down what we expect IO to do and not do - and why
I'm writing a book, I'd like to get this nailed down and to get it right. If anyone on here that's familiar with the various ways in which IO/State#/realWorld# work in GHC and you have time to reply, anything at all would be welcome. Any pointers, links, references, details, anecdotes, or faint memories of GHC bugs will be greatly appreciated! Getting this written up (possibly for addition to Michael Snoyman's wiki article?) would make me, and I imagine others, a lot happier with trying to understand how the different bits and bobs fit together.
I will be dumping my notes as I don't want to get linked to stuff that can be googled because I've already lost 10-15 hours to just that in the past 3-4 days. Digging it up in the compiler is hard because compiler behavior that influences how IO actions are treated don't necessarily have "IO" or "realWorld" mentioned in the relevant parts of the compiler, optimizations, etc.
What I'm hoping for is answers on what specifically preserves the listed properties we want from IO in the compiler, prims, or structure of how we write IO actions.
What we expect IO to do:
- Disable sharing of results, even when it's not a lambda and is evaluated multiple times by the same name. ie, getCurrentTime :: IO UTCTime should get evaluated more than once.
- Not reorder sequential IO actions, such as in a do-block. Called "linearity" below
- Not duplicate the effects of IO actions. Effects shouldn't be spuriously duplicated during optimization passes.
- Effects should not be discarded separately of the value returned by an IO action, merged, or elided.
# Sharing
A friend suggested that perhaps one-shot semantics via the state hack for State# in the IO type is responsible for disabling sharing, I don't believe so, but here are my notes.
-fno-state-hack
Turn off the "state hack" whereby any lambda with a State# token as argument is considered to be single-entry, hence it is considered OK to inline things inside it. This can improve performance of IO and ST monad code, but it runs the risk of reducing sharing.
A one shot lambda
State hack, makes the lambda over State# assume it's one-shot universally by default.
one-shot/state hack is an anti-inlining heuristic, suggesting that inlining is costly.
Also I found this on Trac, does anyone know the answer to this? Is the summary above accurate?
Can the IO state hack be avoided if oneShot is used in the right places in library code, e.g. in IO’s definition of >>=?
This seems related how the state token works, for differentiating which IO action is which and how many times an IO action should run, when it should run, etc.
From the prims:
data State# s
State# is the primitive, unlifted type of states. It has one type parameter, thus State# RealWorld, or State# s, where s is a type variable. The only purpose of the type parameter is to keep different state threads separate. It is represented by nothing at all.
data RealWorld
RealWorld is deeply magical. It is primitive, but it is not unlifted (hence ptrArg). We never manipulate values of type RealWorld; it's only used in the type system, to parameterise State#.
# Linearity
Is this from the nesting of lambdas? It doesn't seem like that's enough based on the various examples using State/State# in GHC Trac bug tickets. The RealWorld token seems to be what's driving this but precisely how that works hasn't been easy to find.
# Discarding, not inlining effects
I believe these are addressed by has_side_effects in the prim ops. I could very well be wrong.
can_fail has_side_effects
Discard NO NO
Float in YES YES
Float out NO NO
Duplicate YES NO
* Duplication. You cannot duplicate a has_side_effect primop. You
might wonder how this can occur given the state token threading, but
just look at Control.Monad.ST.Lazy.Imp.strictToLazy! We get
something like this
p = case readMutVar# s v of
(# s', r #) -> (S# s', r)
s' = case p of (s', r) -> s'
r = case p of (s', r) -> r
I believe duplication addresses inlining IO actions more generally but I could be wrong. Here's a note I found regarding elision/merging:
* Use the compiler flag @-fno-cse@ to prevent common sub-expression
elimination being performed on the module, which might combine
two side effects that were meant to be separate. A good example
is using multiple global variables (like @test@ in the example below).
Any help or pointers for nailing down and documenting this would be greatly appreciated. Also if there's a more detailed explanation of what behavior is expected out of each unsafe function, that would help as well. There are bits and pieces I've been able to aggregate from the GHC trac tickets.
References used (not exhaustive):
- Referential Transparency; Haskell Wiki
https://wiki.haskell.org/Referential_transparency https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fwiki.haskell.org%2fReferential_transparency&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=ecpPX5Ru1ov20MumzpjiSHEX5uR12Xyk1CaHQ0Vizcw%3d
- IO Inside; Haskell Wiki
https://wiki.haskell.org/IO_inside https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fwiki.haskell.org%2fIO_inside&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=fk7unq7EtFReU81Td%2bvhAYAFE71hzTLcoCuM4SJz90s%3d
- Unraveling the mystery of the IO Monad; Edward Z. Yang
http://blog.ezyang.com/2011/05/unraveling-the-mystery-of-the-io-monad/ https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fblog.ezyang.com%2f2011%2f05%2funraveling-the-mystery-of-the-io-monad%2f&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=sUe0aq9yaMNqNzhlEOporHOLgBkDWF3t27HOhrq7MmQ%3d
- Evaluation order and state tokens; Michael Snoyman
https://wiki.haskell.org/Evaluation_order_and_state_tokens https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fwiki.haskell.org%2fEvaluation_order_and_state_tokens&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=SO1OefBi8YlTWj3vDq8pbwupW3LFGMsf2hGyXwPQ6O0%3d
- Haskell GHC Illustrated; Takenobu Tani
- Tackling the Awkward Squad; Simon Peyton Jones
http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/m... https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fresearch.microsoft.com%2fen-us%2fum%2fpeople%2fsimonpj%2fpapers%2fmarktoberdorf%2fmark.pdf&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=0V9ZswJSVeZfZR1i0Qn7wORO8f7Qd1geUJap0e8hCKQ%3d
- Note [IO hack in the demand analyser]; GHC source code
- Monadic I/O in Haskell 1.3; Andrew D. Gordon and Kevin Hammond
- Haskell Report 1.2
http://haskell.cs.yale.edu/wp-content/uploads/2011/01/haskell-report-1.2.pdf https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fhaskell.cs.yale.edu%2fwp-content%2fuploads%2f2011%2f01%2fhaskell-report-1.2.pdf&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c8f855b4f9a8b425f1e3d08d329e1d18d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=SrvFhhQkvW%2f%2f1PFcpV8VKSaEeqrfm53JfUFJdUnXeWA%3d
Thank you for your time,
Chris
-- Chris Allen Currently working on http://haskellbook.com
participants (2)
-
Christopher Allen -
Simon Peyton Jones