[Haskell-cafe] vector stream fusion, inlining and compilation time

[Conal Elliott]

Hi Max.  Thanks much for passing on this info.  Very encouraging news!  -
Conal

On Wed, Mar 10, 2010 at 8:41 AM, Max Bolingbroke <batterseapower at hotmail.com
> wrote:

> This is my understanding:
>
> Old story (GHC 6.12.1 (?) and below):
> 1) Function bodies are only optimised if they are not marked INLINE.
> The assumption is that INLINE bodies will be inlined and then
> optimised at the point where they are inlined.
> 2) Unfoldings are exported in .hi files for functions if they are
> nonrecursive and "small enough" or marked INLINE
>
> New story (GHC HEAD):
> 1) Function bodies are optimised regardless of whether they are marked
> INLINE or not.
> 2) Unfoldings are exported in .hi files for functions if they are
> nonrecursive and "small enough" or marked INLINE, but the unfolding
> that is exported is the _unoptimised_ version!
>  - It is important to export the unoptimised version because the
> optimisation may destroy information we would have relied upon in rule
> matching. E.g. the optimised version of a list producer will not use
> "build", but we need to be able to spot the "build" in rules to do
> foldr/build fusion.
>
> The new story is much more robust - adding INLINE pragmas should be a
> much safer thing to do now, because even if the function is not
> inlined you will still get an optimised definition for that function.
>
> Other relevant points:
> a) There is a new flag, -fexpose-all-unfoldings, in GHC HEAD. This
> does what you want - compile vector-space with this flag on and
> unfoldings for everything will show up in the .hi file, with no INLINE
> annotations necessary. This was intended for supercompilers (such as
> the one I'm working on :-) but you can probably use for this as well.
> b) GHC already treats RULES differently for the purposes of inlining.
> It is very eager to inline into the arguments of a function you have
> RULES for, because doing so may let it spot extra chances for the rule
> to fire.
>
> Hope that helps,
> Max
>
> On 10 March 2010 16:23, Jake McArthur <jake.mcarthur at gmail.com> wrote:
> > Here's a transcript from a conversation I had with Conal on IRC.
> >
> > tl;dr: <conal> cross-module inlining is only possible because ghc
> > stashes a definition in a .hi, iuuc.  i'm suggesting that the stashed
> > definition either (a) never include further inlinings, or (b) be
> > augmented by such a definition.
> >
> > Full transcript:
> >
> > 11:23:10 <conal> jmcarthur: i'm wondering what to do about INLINE
> > pragmas for vector-space and other libraries.  i love optimizability
> > and clean/elegant/terse code.  and i don't know how to resolve that
> > tension.
> > 11:23:21 <jmcarthur> conal: yeah, me either. it's annoying
> > 11:23:41 <jmcarthur> conal: a compiler feature to do it more
> > succinctly would be nice, if we can come up with one
> > 11:23:52 <conal> jmcarthur: i'm thinking exactly the same
> > 11:24:04 <conal> jmcarthur: a ghc flag that does what you did manually
> > 11:24:41 <jmcarthur> conal: yeah, but we still need to do better than
> > inlining *all* functions. we need to be able to tell it we want it to
> > inline all functions satisfying some predicate or something
> > 11:25:07 <jmcarthur> like, there's no point in forcing to inline
> > functions having absolutely nothing to do with vector, for example
> > 11:25:18 <conal> jmcarthur: i wonder.  ghc already has some
> > heuristics.  do we really want anything different/unusual?
> > 11:25:26 <jmcarthur> then again, combinators that don't inline and get
> > used in a vector function later might still be annoying
> > 11:26:08 <conal> jmcarthur: maybe some kind of demand-driven mechanism
> > 11:26:21 <jmcarthur> conal: that's what i was thinking would be best
> > 11:26:28 <conal> jmcarthur: ie pull inlining rather than push them.
> > or some combo.
> > 11:27:21 <conal> jmcarthur: i don't think this issue is specific to
> > either vector fusion or to the vector-space package.
> > 11:27:28 <jmcarthur> conal: actually, this is about rewrite rules more
> > than inlining
> > 11:27:40 <jmcarthur> conal: maybe if we focus on the rewrite rules we
> > can think of something nicer
> > 11:27:46 <conal> jmcarthur: ah, yeah.
> > 11:28:32 <conal> jmcarthur: have you talked with they ghc guys about
> > this issue?  i wonder what practice they'd advise for use with the
> > current ghc
> > 11:28:54 <jmcarthur> i have not
> > 11:29:47 <conal> jmcarthur: how did the inlining/rewriting concern
> > arise for vector fusion and the vector-space package?
> > 11:30:16 <jmcarthur> conal: i assume you read the email i linked to?
> > 11:30:27 <jmcarthur> this one:
> > http://www.haskell.org/pipermail/haskell-cafe/2010-March/074153.html
> > 11:30:34 <conal> jmcarthur: yes.  i'l reread now.
> > 11:31:03 <jmcarthur> conal: "in general, you have to add INLINE
> > pragmas in such cases if you want to be sure your code fuses. A
> > general-purpose mechanism for handling situations like this
> > automatically would be great but we haven't found a good one so far."
> > 11:31:14 <jmcarthur> i think the most relevant line
> > 11:31:49 <conal> jmcarthur: thx.  and the difficulty (with current
> > ghc) is specifically cross-module, right?
> > 11:32:00 <jmcarthur> conal: that is my understanding
> > 11:32:10 <jmcarthur> but perhaps it is more complex
> > 11:32:49 <conal> jmcarthur: if so, i wonder if ghc could be fixed to
> > inline between modules according to the same heuristics as within a
> > module.
> > 11:34:36 <jmcarthur> conal: maybe.
> > 11:35:34 <conal> jmcarthur: part of my discomfort is that i don't know
> > whether the INLINE directives are more helpful or more harmful under
> > all uses.  if they were generally helpful, i imagine ghc would do it.
> > 11:56:56 <jmcarthur> me too
> > 11:57:46 <conal> jmcarthur: i just found that haskell-cafe thread and
> > added a reply.
> > 11:58:31 <conal> jmcarthur: hoping that don, roman, etc will have some
> > ideas in addressing that discomfort.
> > 12:09:58 <jmcarthur> conal: apparently the real trick is that GHC will
> > not inline functions in a function that is annotated INLINE, meaning
> > that rewrite rules can fire on the outermost rule before firing on
> > inner ones
> > 12:10:30 <jmcarthur> conal: i think it would be nice if we could come
> > up with a way for rewrite rules to affect GHC's inliner
> > 12:10:44 <conal> jmcarthur: yeah.  maybe INLINE ought to be decomposed
> > into two sub-meanings.
> > 12:10:45 <jmcarthur> then it would only happen when necessary
> > 12:11:17 <jmcarthur> well, the fact that it forces that function to be
> > inlined is also good though
> > 12:11:33 <jmcarthur> which is apparently important across module
> boundaries
> > 12:11:45 <conal> jmcarthur: maybe ghc could *never* inline functions
> > into an inline body.  and then do some caching to avoid redundant
> > work.
> > 12:12:00 <jmcarthur> perhaps. still leaves the cross-module inlining
> > issue though
> > 12:12:32 <jmcarthur> i suspect this is also architectural
> > 12:12:44 <jmcarthur> ghc doesn't know if it will inline a function
> > across a module boundary in advance
> > 12:12:52 <jmcarthur> therefore it goes ahead and inlines into it
> > 12:13:04 <jmcarthur> *inlines other functions into it
> > 12:13:31 <conal> jmcarthur: i don't understand how module boundaries
> > come into play
> > 12:14:40 <jmcarthur> conal: my suspicion is that because ghc builds
> > modules separately it can't know whether a function will be inlined in
> > another module, so if it's not marked INLINE it feels free to inline
> > other functions into it as it pleases
> > 12:15:17 <jmcarthur> conal: but a function marked INLINE is clearly
> > going to be inlined everywhere it's used, so ghc can go ahead and
> > avoid inlining into it
> > 12:17:07 <jmcarthur> conal: perhaps a way around it would be to avoid
> > making inlining decisions about exported functions at all until link
> > time
> > 12:17:20 <jmcarthur> but that would stink a little
> > 12:17:24 <conal> jmcarthur: maybe so.  sounds like a place for
> > improving ghc.  it makes an invalid assumption: that a def not marked
> > INLINE won't be inlined.
> > 12:17:25 <conal> jmcarthur: instead, it could be prepared to inline
> elsewhere.
> > 12:17:25 <conal> jmcarthur: i'm confused though.  ghc *is* prepared to
> > inline elsewhere.
> > 12:18:23 <jmcarthur> conal: well, it's not that ghc makes an invalid
> > assumption, i think. it just doesn't take certain steps unless you
> > tell it to explicitly
> > 12:18:58 <conal> jmcarthur: the invalid assumption i mean is that it's
> > not worth saving an inline-and-optimze-friendly def.
> > 12:19:43 <conal> jmcarthur: cross-module inlining is only possible
> > because ghc stashes a definition in a .hi, iuuc.  i'm suggesting that
> > the stashed definition either (a) never include further inlinings, or
> > (b) be augmented by such a definition.
> > 12:20:07 <jmcarthur> conal: i agree with that suggestion, if our
> > understanding of how it works is correct
> > 12:20:54 <conal> jmcarthur: okay.  let's take this understanding into
> > the haskell-cafe discussion and see what evolves.  okay?
> >
> > - Jake
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100310/8286adc6/attachment.html