Opened 12 months ago

Last modified 3 months ago

#9198 new bug

large performance regression in type checker speed in 7.8

Reported by: carter Owned by:
Priority: high Milestone: 7.12.1
Component: Compiler (Type checker) Version: 7.8.2
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description (last modified by thomie)

it was recently demonstrated on the haskell-cafe mailing list that the following code takes measurably longer to type check in GHC 7.8.2 than in GHC 7.6.

http://www.haskell.org/pipermail/haskell-cafe/2014-June/114562.html

the program example is as follows

begin :: Monad m => (m () -> t) -> t
begin cont = cont (return ())
 
a :: IO a -> (IO () -> t) -> t
a m cont = cont (m >> putStrLn "a")
 
end :: t -> t
end m = m
 
main = begin a a a a a a a a a a a a a a a a a a end

takes about a second to type check in ghc 7.8, and is "instant" in 7.6 ()

each additional a doubles the time to type check the program

main = begin a a a a a a a a a a a a a a a a a a a a a a a a end

takes longer than I have the patience to wait :) (so more than 5 seconds)

the author of the email notes that a related program

  main = id id id id id id id id id id id
         id id id id id id id id id id id (return ())

has the exponential complexity in both 7.8.2 and 7.6.2

This It could very well be that some of the type checker changes between 7.8 and 7.6 enlarged the space of programs that trip up exponential worst case behavior, but one way or another understanding *why* this happened

Change History (5)

comment:1 Changed 12 months ago by goldfire

With typos removed and types added, this looks like

begin :: Monad m => (m () -> t) -> t
begin cont = cont (return ())

a :: IO a -> (IO () -> t) -> t
a m cont = cont (m >> putStrLn "a")

end :: t -> t
end m = m

main = begin a a a a a a a a a a a a a a a a a a a a end

Including the type signatures does not improve performance.

Great example case -- this does indeed need to be fixed.

comment:2 Changed 12 months ago by simonpj

The types really do get twice as large each time you add an a, I think. Are you certain that 7.6 is really fast? It got slow for me, just as 7.8 does, and not surprisingly so.

These "big type" examples are pretty rare in practice, but even basic old Hindley-Milner type inference is worst-case exponential in program size.

That said, GHC makes it worse by dragging these large type right through the compiler pipeline; it's a price we pay for a properly typed intermediate language. See Scrap your type applications for a way to improve these bad cases -- at a cost in compiler code complexity.

Simon

comment:3 Changed 11 months ago by thoughtpolice

  • Milestone set to 7.10.1

Moving to 7.10.1.

comment:4 Changed 7 months ago by thomie

  • Description modified (diff)

For what it's worth: crude timing results for the example from the description with 18 a's:

GHC Time
7.4.2 2.2s
7.6.3 2.2s
7.8.3 3.4s
7.9.20141113 3.8s

Command: time ghc -c -fforce-recomp test.hs

comment:5 Changed 3 months ago by thoughtpolice

  • Milestone changed from 7.10.1 to 7.12.1

Moving to the 7.12.1 milestone, as these tickets won't be fixed in time for the 7.10.1 release (unless you, the reader, help write a patch :)

Note: See TracTickets for help on using tickets.