[GHC] #8523: blowup in space/time for type checking and object size for high arity tuples

11 Nov 2013

      #8523: blowup in space/time for type checking and object size for high arity
tuples
-------------------------+-------------------------------------------------
       Reporter:         |             Owner:
  carter                 |            Status:  new
           Type:  bug    |         Milestone:
       Priority:         |           Version:  7.6.3
  normal                 |  Operating System:  Unknown/Multiple
      Component:         |   Type of failure:  Compile-time performance bug
  Compiler               |         Test Case:
       Keywords:         |          Blocking:
   Architecture:         |
  Unknown/Multiple       |
     Difficulty:         |
  Unknown                |
     Blocked By:         |
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.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8523
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler