Opened 2 years ago

Last modified 6 months ago

#9198 new bug

large performance regression in type checker speed in 7.8

Reported by: carter Owned by:
Priority: high Milestone: 8.2.1
Component: Compiler (Type checker) Version: 7.8.2
Keywords: Cc: lelf
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.

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

comment:1 Changed 2 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 2 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.


comment:3 Changed 2 years ago by thoughtpolice

  • Milestone set to 7.10.1

Moving to 7.10.1.

comment:4 Changed 21 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 17 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 :)

comment:6 Changed 12 months ago by lelf

  • Cc lelf added

comment:7 Changed 11 months ago by thoughtpolice

  • Milestone changed from 7.12.1 to 8.0.1

Milestone renamed

comment:8 Changed 7 months ago by bgamari

  • Description modified (diff)
  • Milestone changed from 8.0.1 to 8.2.1

This won't be fixed for 8.0.1.

comment:9 Changed 6 months ago by simonpj

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

Note: See TracTickets for help on using tickets.