#2642: Improve SpecConstr for join points
-----------------------------------------+----------------------------------
Reporter: simonpj | Owner:
Type: run-time performance bug | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 6.8.3
Severity: normal | Keywords:
Difficulty: Unknown | Testcase:
Architecture: Unknown/Multiple | Os: Unknown/Multiple
-----------------------------------------+----------------------------------
This is another `SpecConstr` improvement suggestion. See also #2598,
#2255.
Roman writes: Yes, this is turning into a major problem, in fact. This is
the simplest example I could find:
{{{
foo :: Int -> Int :*: (Int :*: Int) -> Int
foo 0 p = p `seq` 0
foo i (m :*: (n1 :*: n2)) =
case (case even (i-n1-n2) of
True -> (i `div` 2, (n1-1) :*: (n2-1))
False -> (i-1, (n1+1) :*: (n2+1))) of
(j, p) -> foo (if even i then i-m else i+m) ((m-1) :*: p)
}}}
The pattern here seems to be
{{{
let j x = ....
in ...(j (C a b)).... (j (C p q)) ...
}}}
So a C value is built every time j is called. Simon Marlow also saw
something very similar in some STM code he was optimising recently.
Here's a possible solution:
* extend `SpecConstr` to work on *non-recursive* functions too.
* look for the call pattern not in j's RHS (as we do for recursive fns)
but in the body of the let
A possible restriction is to do all this only for local, non-recursive fns
that are themselves defined in the RHS of a recursive function. The
motivation would be do it only when we're in a loop, and being in the body
of a recursive function is a big clue.
Do you think that would address the cases you've encountered? It would
be a bit like making join-points eager to inline (specialisation is a bit
like partial inlining) except that
* we'd get sharing when there were two calls applied to the same
constructor
* it'd only happen if that argument was taken apart in the join point
Roman comments: No, the last restriction is not good: we often have
{{{
foo p = let j x' = ... foo (x',c) ...
in ... j (C a) ... j (C b) ...
}}}
Here, the join point doesn't take apart the argument. In fact, this
probably makes it a bit trickier: we want to specialise the join point and
*then* specialise foo, getting
{{{
foo p = let j x' = ... foo (x',c) ...
{-# RULES j (C z) = j' z #-}
j' z = ... foo (C z,c) ...
in ... j' a ... j' b ...
{-# RULES foo (C x,y) = foo' x y #-}
foo' x y = ...
}}}
A problem is that for `SpecConstr` to specialise `foo`, `j` must be
specialised
and *simplified* first to expose the structure of the argument in the
recursive call. Can this be done without running SpecConstr twice? Or is
running `pecConstr/Simplify` repeatedly (until it produces no more
specialisations) acceptable?
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2642>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
