[GHC] #8523: blowup in space/time for type checking and object size for high arity tuples
#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
#8523: blowup in space/time for type checking and object size for high arity tuples -------------------------------------------------+------------------------- Reporter: carter | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time performance bug | Unknown/Multiple Test Case: | Difficulty: Blocking: | Unknown | Blocked By: | Related Tickets: -------------------------------------------------+------------------------- Comment (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. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8523#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8523: blowup in space/time for type checking and object size for high arity tuples -------------------------------------------------+------------------------- Reporter: carter | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time performance bug | Unknown/Multiple Test Case: | Difficulty: Blocking: | Unknown | Blocked By: | Related Tickets: -------------------------------------------------+------------------------- Comment (by dreixel): Perhaps related to #5642? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8523#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8523: blowup in space/time for type checking and object size for high arity tuples -------------------------------------------------+------------------------- Reporter: carter | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time performance bug | Unknown/Multiple Test Case: | Difficulty: Blocking: | Unknown | Blocked By: | Related Tickets: -------------------------------------------------+------------------------- Comment (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 [http://research.microsoft.com/en- us/um/people/simonpj/papers/variant-f/index.htm Scrap your type applications]. Bit I could be wrong. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8523#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8523: blowup in space/time for type checking and object size for high arity tuples -------------------------------------+------------------------------------- Reporter: carter | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8523#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC