#10980: Deriving Read instance from datatype with N fields leads to N^2 code size growth -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: deriving-perf 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: | -------------------------------------+------------------------------------- Comment (by rwbarton): Here's a simple example of the quadratic code size I was talking about in comment:7, not specific to Read or Applicative or Monad. {{{#!hs f a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 = a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 }}} At the Core and STG stages the size of `f` is linear in the number of arguments. But the Cmm for `f` builds a thunk for the first argument `a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9` and then calls `+`. In order to build that thunk it has to copy `a1` through `a9` into the thunk, as they are its free variables. Then the code for that thunk is going to build another thunk for `a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8`, which requires copying `a1` through `a8` again, and so on. The total code size, work done and allocations are all quadratic in the number of arguments. In this particular case it would clearly be better to do all the thunk construction up front in `f`, like (pseudo-STG) {{{#!hs f a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 = let t2 = a1 + a2 t3 = t2 + a3 t4 = t3 + a4 ... t9 = t8 + a9 in t9 + a10 }}} which would be linear code size, work and allocations in the number of arguments. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10980#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler