Re: [GHC] #10980: Deriving Read instance from datatype with N fields leads to N^2 code size growth

16 Oct 2015

      #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:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by slyfox):

 Derived instance looks reasonably well (i've picked a data type with 282
 fields):

 {{{#!hs
 {-
 $ ghc -O1 -fforce-recomp -ddump-deriv M.hs
 [1 of 1] Compiling M                ( M.hs, M.o )

 ==================== Derived instances ====================
 Derived instances:
 -}
   instance GHC.Read.Read M.D where
     GHC.Read.readPrec
       = GHC.Read.parens
           (Text.ParserCombinators.ReadPrec.prec
              11
              (do { GHC.Read.expectP (Text.Read.Lex.Ident "D");
                    GHC.Read.expectP (Text.Read.Lex.Punc "{");
                    GHC.Read.expectP (Text.Read.Lex.Ident "a0");
                    GHC.Read.expectP (Text.Read.Lex.Punc "=");
                    a1_a1ns <- Text.ParserCombinators.ReadPrec.reset
 GHC.Read.readPrec;
                    GHC.Read.expectP (Text.Read.Lex.Punc ",");
                    GHC.Read.expectP (Text.Read.Lex.Ident "a1");
                    GHC.Read.expectP (Text.Read.Lex.Punc "=");
                    a2_a1nt <- Text.ParserCombinators.ReadPrec.reset
 GHC.Read.readPrec;
                    GHC.Read.expectP (Text.Read.Lex.Punc ",");
                    GHC.Read.expectP (Text.Read.Lex.Ident "a2");
                    GHC.Read.expectP (Text.Read.Lex.Punc "=");
                    a3_a1nu <- Text.ParserCombinators.ReadPrec.reset
 GHC.Read.readPrec;
 -- ...
                    GHC.Read.expectP (Text.Read.Lex.Punc ",");
                    GHC.Read.expectP (Text.Read.Lex.Ident "a280");
                    GHC.Read.expectP (Text.Read.Lex.Punc "=");
                    a281_a1rY <- Text.ParserCombinators.ReadPrec.reset
                                   GHC.Read.readPrec;
                    GHC.Read.expectP (Text.Read.Lex.Punc ",");
                    GHC.Read.expectP (Text.Read.Lex.Ident "a281");
                    GHC.Read.expectP (Text.Read.Lex.Punc "=");
                    a282_a1rZ <- Text.ParserCombinators.ReadPrec.reset
                                   GHC.Read.readPrec;
                    GHC.Read.expectP (Text.Read.Lex.Punc "}");
                    GHC.Base.return
                      (M.D
                         a1_a1ns
                         a2_a1nt
                         a3_a1nu
                         a4_a1nv
                         a5_a1nw
 -- ...
                         a280_a1rX
                         a281_a1rY
                         a282_a1rZ) }))
     GHC.Read.readList = GHC.Read.readListDefault
     GHC.Read.readListPrec = GHC.Read.readListPrecDefault
 }}}

 Generated assembly is full of stack rearrangements which seems to be a
 main source of code inflation and compilation slowdown.

 Some thoughts:

 - Could GHC do a CSE for code sequences of '''expetP (Punc ); expetP
 (Ident ); expetP (Punc );'''?
 - If all fields were strict could GHC optimise stack layout better?

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10980#comment:1
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler