#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): However, the quadratic behavior exhibited by the Read instance is more similar to this example {{{#!hs f :: (Int -> a) -> a f k = k 0 {-# NOINLINE f #-} v :: (Int,Int,Int,Int,Int,Int,Int,Int,Int,Int) v = f (\a1 -> f (\a2 -> f (\a3 -> f (\a4 -> f (\a5 -> f (\a6 -> f (\a7 -> f (\a8 -> f (\a9 -> f (\a10 -> (a1,a2,a3,a4,a5,a6,a7,a8,a9,a10))))))))))) }}} `v` is supposed to correspond to the desugaring of the long `do` blocks in slyfox's attachments. Here the quadratic blowup at the Cmm stage is caused by the fact that the free variables of the nth lambda are all the preceding `a1`, ..., `an`. We have to copy `a1` through `an` into the (n+1)st lambda that we provide as an argument to the next `f`. This is the blowup that I said I didn't know how to solve in the code generator in comment:7. However, (I claimed that) in this case we can avoid generating such nested lambdas in the first place by changing the desugaring to use Applicative methods rather than Monad ones. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10980#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler