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

[Jake McArthur]

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