[DISARMED] RE: Better calling conventions for strict functions (bang patterns)?

[Andrew Farmer]

Simon,

I really enjoyed reading this paper... I was wondering if you could comment
on the implementation of Strict Core? Was it ever implemented in GHC (even
as a proof-of-concept)? If not, was it just due to a lack of time or some
fundamental limitation or problem discovered after the paper? If it was
implemented, was any benefit actually measured? Can you speculate on
whether some of the more recent changes/additions to Core (such as
coercions and roles) might fit into this? (I don't see any obvious reason
they couldn't, but that is me.)

Thanks!
Andrew

On Fri, Oct 23, 2015 at 7:11 AM, Simon Peyton Jones <simonpj at microsoft.com>
wrote:

> It’s absolutely the case that bang patterns etc tell the caller what to
> do, but the function CANNOT ASSUME that its argument is evaluated.  Reason:
> higher order functions.
>
>
>
> I think that the way to allow functions that can assume their arg is
> evaluated is through types: see Type are calling conventions
> <http://research.microsoft.com/~simonpj/papers/strict-core/tacc-hs09.pdf>.
> But it’d be a fairly big deal to implement.
>
>
>
> Simon
>
>
>
>
>
> *From:* ghc-devs [mailto:ghc-devs-bounces at haskell.org] *On Behalf Of *Ryan
> Newton
> *Sent:* 23 October 2015 14:54
> *To:* ghc-devs at haskell.org; Ömer Sinan Ağacan; Ryan Scott; Chao-Hong
> Chen; Johan Tibell
> *Subject:* Better calling conventions for strict functions (bang
> patterns)?
>
>
>
> Hi all,
>
>
>
> With module-level Strict and StrictData pragmas coming soon, one obvious
> question is what kind of the code quality GHC can achieve for strict
> programs.
>
>
>
> When it came up in discussion in our research group we realized we didn't
> actually know whether the bang patterns, `f !x`, on function arguments were
> enforced by caller or callee.
>
>
>
> Here's a Gist that shows the compilation of a trivial function:
>
> foo :: Maybe Int -> Int
>
> foo !x =
>
>   case x of
>
>    Just y -> y
>
>
>
>    *MailScanner has detected a possible fraud attempt from
> "na01.safelinks.protection.outlook.com" claiming to be*
> https://gist.github.com/rrnewton/1ac722189c65f26fe9ac
> <https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fgist.github.com%2frrnewton%2f1ac722189c65f26fe9ac&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7cb006dcdbfe834ebb6c1e08d2dbb16c03%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=qxrT8r1VSP97xQUF2qqkLlxEtSGi9VOzfmORl25W%2fWY%3d>
>
>
>
> If that function is compiled to *assume* its input is in WHNF, it should
> be just as efficient as the isomorphic MLton/OCaml code, right?  It only
> needs to branch on the tag, do a field dereference, and return.
>
>
>
> But as you can see from the STG and CMM generated, foo *does indeed*
> enter the thunk, adding an extra indirect jump.  Here's the body:
>
>       c3aY:
>
>           if ((Sp + -8) < SpLim) goto c3aZ; else goto c3b0;
>
>       c3aZ:
>
>           // nop
>
>           R1 = PicBaseReg + foo_closure;
>
>           call (I64[BaseReg - 8])(R2, R1) args: 8, res: 0, upd: 8;
>
>       c3b0:
>
>           I64[Sp - 8] = PicBaseReg + block_c3aO_info;
>
>           R1 = R2;
>
>           Sp = Sp - 8;
>
>           if (R1 & 7 != 0) goto c3aO; else goto c3aP;
>
>       c3aP:
>
>           call (I64[R1])(R1) returns to c3aO, args: 8, res: 8, upd: 8;
>
>       c3aO:
>
>           if (R1 & 7 >= 2) goto c3aW; else goto c3aX;
>
>       c3aW:
>
>           R1 = P64[R1 + 6] & (-8);
>
>           Sp = Sp + 8;
>
>           call (I64[R1])(R1) args: 8, res: 0, upd: 8;
>
>       c3aX:
>
>           R1 = PicBaseReg + lvl_r39S_closure;
>
>           Sp = Sp + 8;
>
>           call (I64[R1])(R1) args: 8, res: 0, upd: 8;
>
>
>
>
>
> The call inside c3aP is entering "x" as a thunk, which also incurs all of
> the stack limit check code.  I believe that IF the input could be assumed
> to be in WHNF, everything above the label "c3aO" could be omitted.
>
>
>
> So... if GHC is going to be a fabulous pure *and* imperative language,
> and a fabulous lazy *and* strict compiler/runtime.. is there some work we
> can do here to improve this situation? Would the following make sense:
>
>    - Put together a benchmark suite of all-strict programs with
>    Strict/StrictData (compare a few benchmark's generated code to MLton, if
>    time allows)
>    - Modify GHC to change calling conventions for bang patterns -- caller
>    enforces WHNF rather than callee.  Existing strictness/demand/cardinality
>    analysis would stay the same.
>
> Unless there's something I'm really missing here, the result should be
> that you can have a whole chain of strict function calls, each of which
> knows its arguments and the arguments it passes to its callees are all in
> WHNF, without ever generating thunk-entry sequences.
>
>
>
> Thanks for your time,
>
>   -Ryan
>
>
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20151026/f4f76dd1/attachment-0001.html>