Opened 9 years ago

Last modified 7 months ago

#2642 new bug

Improve SpecConstr for join points

Reported by: simonpj Owned by:
Priority: lowest Milestone:
Component: Compiler Version: 6.8.3
Keywords: SpecConstr Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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?

Change History (16)

comment:1 Changed 9 years ago by igloo

Milestone: 6.10 branch

comment:2 Changed 9 years ago by igloo

Milestone: 6.10 branch6.12 branch

comment:3 Changed 8 years ago by simonmar

Type of failure: Runtime performance bug

comment:4 Changed 7 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:5 Changed 7 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:6 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:7 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:8 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:9 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lowlowest

comment:10 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:11 Changed 3 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:12 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:13 Changed 3 years ago by thoughtpolice

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:14 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:15 Changed 21 months ago by thomie

Milestone: 8.0.1

comment:16 Changed 7 months ago by simonpj

Keywords: SpecConstr added
Note: See TracTickets for help on using tickets.