Opened 6 years ago

Last modified 3 years ago

#8523 new bug

blowup in space/time for type checking and object size for high arity tuples

Reported by: carter Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.6.3
Keywords: Cc: 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:


Eric Mertens found a compilation performance issue in how GHC handles type class instance methods with many equality constraints and large arity tuples.

basically using equality constraints to force 62 variables equal, instead of using the same variable for all the tuple slots, make the type checking time go from 0.9 seconds and very little memory to ~20 seconds and ~ 700mb of ram, along with going from ~ 7,000 coercions to 700,000-400,000 coercions, and object file size of 143kb to an object file size of 2.8mb-3.1mb

I'm attaching 2 variants Tuple.hs and NeighborTuple.hs that exhibit the blowup behavior, and MonoTuple.hs (better named PolyTuple.hs but thats a side detail) that doesn't exhibit the blow up behavior.

Attachments (3)

MonoTuple.hs (32.4 KB) - added by carter 6 years ago.
no equality constraints tuple code
Tuple.hs (33.3 KB) - added by carter 6 years ago.
equality constraints variant 1
NeighborTuple.hs (32.4 KB) - added by carter 6 years ago.
another equality constraint variant

Download all attachments as: .zip

Change History (7)

Changed 6 years ago by carter

Attachment: MonoTuple.hs added

no equality constraints tuple code

Changed 6 years ago by carter

Attachment: Tuple.hs added

equality constraints variant 1

Changed 6 years ago by carter

Attachment: NeighborTuple.hs added

another equality constraint variant

comment:1 Changed 6 years ago by carter

I think it'd be a good idea to understand this blowup. What I think is specially concerning is the increase in object code size, though that will require some exploration.

I'd also like to understand why the equality constraints blow up the compile time. Do we need a better / more robust algorithm for handling the constraints. In some sense its a possible denial of service issue hypothetically.

comment:2 Changed 6 years ago by dreixel

Perhaps related to #5642?

comment:3 Changed 6 years ago by simonpj

I have not investigated yet (busy), but my nose tells me that it is indeed similar to #5642, and in particular is a symptom of Section 2.3 of Scrap your type applications. Bit I could be wrong.


comment:4 Changed 3 years ago by RyanGlScott

Cc: RyanGlScott added
Note: See TracTickets for help on using tickets.