Changes between Version 3 and Version 4 of OneShot


Ignore:
Timestamp:
Nov 6, 2014 12:22:33 PM (5 years ago)
Author:
nomeata
Comment:

Post-Implementation-Cleanup

Legend:

Unmodified
Added
Removed
Modified
  • OneShot

    v3 v4  
    33== Synopsis ==
    44
    5 This proposal proposes to add a function
     5This documents the magic function
    66
    77{{{
     
    99}}}
    1010
    11 to the library. Semantically, it is the identity, but in addition it tell the compiler to assume that `oneShot f` is called at most once, which allows it to optimize the code more aggressively.
     11Semantically, it is the identity, but in addition it tell the compiler to assume that `oneShot f` is called at most once, which allows it to optimize the code more aggressively.
    1212
    1313== Motivation ==
     
    2323Later, David Feuer creatd more good consumers that would rely on such eta-expansion to produce good code, such as `scanl`. Using `oneShot` in these would make this transformation more reliable, in particular when CallArity fails.
    2424
    25 <del>Nofib shows (only) one case where – in the presence of Call Arity – this definition yields better results: `fft2` improves allocations by 1.5%.</del>
    26 
    27 After fixing the inlining of `iterateFB`, nofib does not exhibit any case where adding `oneShot` improves performance over Call Arity. But there is still a good chance that such cases occur out there.
     25Nofib itself does not exhibit any case where adding `oneShot` improves performance over Call Arity. But there is still a good chance that such cases occur out there.
    2826
    2927== Implementation ==
    3028
    31 GHC already supports one-shot lambdas, see `setOneShotLambda` in `Id.lhs`. We propose to implement `oneShot` as a built in function, similar to `lazy` etc. The branch `wip/oneShot` contains a first prototype: source:ghc/compiler/basicTypes/MkId.lhs?rev=wip/oneShot#L1124
     29GHC already supports one-shot lambdas, see `setOneShotLambda` in `Id.lhs`. We implemented `oneShot` as a built in function, similar to `lazy` etc. The crucial bit is to apply `setOneShotLambda` on the lambda’s binder in the unfolding, and to inline `oneShot` aggressively. This is [c271e32eac65ee95ba1aacc72ed1b24b58ef17ad]
    3230
    33 The crucial bit is to apply `setOneShotLambda` on the lambda’s binder in the unfolding, and to inline `oneShot` aggressively.
     31Also, we need the `oneShot` information needs to prevail in unfoldings and across interfaces. For that, `IfaceExpr` was extended with a boolean flag on lambda binders in [c001bde73e38904ed161b0b61b240f99a3b6f48d].
     32
     33Finally, `oneShot` is actually used in the libraries. This is [072259c78f77d6fe7c36755ebe0123e813c34457].
    3434
    3535== Challenges ==
     
    5454but now the `OneShot` flag is not true any more. So likely it should be reset. OTOH, this might contradict the user’s intentions. Should CSE be aware of this and avoid CSE’ing these function? Or maybe leave the `OneShot` in place, even if incorrect at first glance, on the grounds that the only effect an incorrect `OneShot` annotation has will be to un-do the CSE?
    5555
    56 Observed placed where the flag may be lost:
    57  * Unconditionally in `CoreTidy`, easily fixed.
    58  * ''anything else?''
    59 
    60 The good things is that this can be tackled incrementally. Unless we give hard guarantees about the effect of `oneShot` (which we don’t), resetting it does not make programs go wrong, and not slower than if there is no `oneShot` annotation at all. So we improve over the previous state, and can keep improving as we make the transformation pay closer attention to this flag.
    61 
    62 === Preservation of `setOneShotLambda` across module boundaries ===
    63 
    64 For the motivational cause to work the `oneShot` information needs to prevail in unfoldings and across interfaces.
    65 
    66 The cleanest solution is to serialize the `OneShot` bit in interface files. To that end, the constructor
    67 {{{
    68 IfaceLam :: IfaceBndr -> IfaceExpr -> IfaceExpr
    69 }}}
    70 needs to be changed to
    71 {{{
    72 IfaceLam :: IfaceOneShot -> IfaceBndr -> IfaceExpr -> IfaceExpr
    73 }}}
    74 with
    75 {{{
    76 data IfaceOneShot = IfaceNoOneShot | IfaceOneShot
    77 }}}
    78 
    79 The current `wip/oneShot` branch uses a different solution (avoiding inlining `oneShot` in unfoldings and rules), but this is not nice and fragile.
     56So far, this is a hypothetical challenge: It seems that the `oneShotInfo` is preserved rather well. We’ll see if something else comes up.
    8057
    8158== Wild, unverified ideas ==