Opened 3 years ago

Last modified 5 months ago

#9198 new bug

large performance regression in type checker speed in 7.8

Reported by: carter Owned by:
Priority: high Milestone: 8.4.1
Component: Compiler (Type checker) Version: 7.8.2
Keywords: Cc: lelf, RyanGlScott
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by bgamari)

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 (11)

comment:1 Changed 3 years 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 3 years 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 3 years ago by thoughtpolice

Milestone: 7.10.1

Moving to 7.10.1.

comment:4 Changed 3 years 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 2 years ago by thoughtpolice

Milestone: 7.10.17.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 :)

comment:6 Changed 23 months ago by lelf

Cc: lelf added

comment:7 Changed 21 months ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:8 Changed 17 months ago by bgamari

Description: modified (diff)
Milestone: 8.0.18.2.1

This won't be fixed for 8.0.1.

comment:9 Changed 17 months ago by simonpj

The trouble here is that we don't have even a partial solution in mind. Ideas welcome.

comment:10 Changed 8 months ago by RyanGlScott

Cc: RyanGlScott added

comment:11 Changed 5 months ago by bgamari

Milestone: 8.2.18.4.1

There is no solution on the horizon for this. Bumping to 8.4 at the earliest.

Note: See TracTickets for help on using tickets.