Opened 5 months ago

Last modified 5 months 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:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Difficulty: Unknown
Test Case: Blocked By:
Blocking: Related Tickets:


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 5 months ago.
no equality constraints tuple code
Tuple.hs (33.3 KB) - added by carter 5 months ago.
equality constraints variant 1
NeighborTuple.hs (32.4 KB) - added by carter 5 months ago.
another equality constraint variant

Download all attachments as: .zip

Change History (6)

Changed 5 months ago by carter

no equality constraints tuple code

Changed 5 months ago by carter

equality constraints variant 1

Changed 5 months ago by carter

another equality constraint variant

comment:1 Changed 5 months 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 5 months ago by dreixel

Perhaps related to #5642?

comment:3 Changed 5 months 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.


Note: See TracTickets for help on using tickets.