cons/build and making rules look boring

[David Feuer]

The rule to make scanl fuse looks like this:

"scanl" [~1] forall f a bs . scanl f a bs =
  build (\c n -> a `c` foldr (scanlFB f c) (constScanl n) bs a)

I initially tried reversing it with something like this rule (I'm not sure
it was exactly like this, but it was similar):

"scanlList" [1] forall f a bs . a : foldr (scanlFB f (:)) (constScanl [])
bs a)
  = scanl f a bs

What I found was that this implementation led to poor performance on a
couple nofib benchmarks (I don't remember which off the top of my head).
When I dug down into them to see how they were using scanl, I found that
they *weren't*, either directly or indirectly. When I compared core2core
and dump-inlinings, I saw that the core looked pretty much the same for a
while, but the inliner was saying different things about how it was making
judgements about what to inline. Eventually, I realized that it was looking
at (:) differently *in general*, and giving it an inlining bonus, because
it appeared as the outermost name in the "scanlList" rule. In at least one
case, that changed its decision about whether to inline something. I only
know this is bad because the benchmarks said so—I don't know the precise
reasons.
On Sep 1, 2014 4:49 AM, "Simon Peyton Jones" <simonpj at microsoft.com> wrote:

> | makes (:) look "interesting" to the inliner. Unfortunately, as I
> | discovered after much extreme puzzlement about why rules relating to
> | scanl were affecting things that had nothing to do with scanl, it
> | turns out that making (:) look interesting is really quite bad, and
> | something that we probably never want to happen.
>
> Can you give a concrete, reproducible example of the problem you
> articulate here?  (In general, a concrete example brings tremendous focus
> to discussions, giving readers something specific to bite on.)
>
> Simon
>
> | -----Original Message-----
> | From: ghc-devs [mailto:ghc-devs-bounces at haskell.org] On Behalf Of David
> | Feuer
> | Sent: 30 August 2014 23:05
> | To: ghc-devs
> | Subject: cons/build and making rules look boring
> |
> | I think I may have figured out at least part of the reason that
> | cons/build gives bad results. I actually ran into a clue when working
> | on scanl. It seems at least part of the problem is that a rule like
> |
> | x : build g = build (\c n -> c x (g c n))
> |
> | makes (:) look "interesting" to the inliner. Unfortunately, as I
> | discovered after much extreme puzzlement about why rules relating to
> | scanl were affecting things that had nothing to do with scanl, it
> | turns out that making (:) look interesting is really quite bad, and
> | something that we probably never want to happen.
> |
> | As a result, the only ways I see to try to make rules like that work
> | properly are
> |
> | 1. If constructors are *always* best treated as boring, and the
> | inliner knows when's a constructor, make it treat them all as boring.
> |
> | 2. Offer a BORINGRULE annotation to indicate that the rule should not
> | make its LHS "interesting", or
> |
> | 3. (I don't like this option much) Make a special case forcing (:) in
> | particular to be boring.
> |
> | David
> | _______________________________________________
> | ghc-devs mailing list
> | ghc-devs at haskell.org
> | http://www.haskell.org/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140901/545f35b7/attachment.html>