[GHC] #5642: Deriving Generic of a big type takes a long time and lots of space

[GHC]

#5642: Deriving Generic of a big type takes a long time and lots of space
-------------------------------------+-------------------------------------
        Reporter:  basvandijk        |                Owner:  bgamari
            Type:  bug               |               Status:  merge
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.3
      Resolution:                    |             Keywords:  deriving-
                                     |  perf, Generics
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:  T5642
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D2304
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by RyanGlScott):

 Replying to [comment:43 gidyn]:
 > Gen_v3 not going in?

 At least, not for now. In Phab:D2304, SPJ
 [https://phabricator.haskell.org/D2304#67443 also asked to repeat the same
 experiment] in comment:39, but with a four-constructor datatype:

 {{{#!hs
 data Bigsum = C0 | C1 | C2 | C3 -- Perhaps not the best name in
 hindsight...
 }}}

 As above, here are
 [https://gist.github.com/RyanGlScott/8341acaaf38b7fbd6e08c2ffc77aa7bd
 #file-gen_v1-hs Gen_v1.hs],
 [https://gist.github.com/RyanGlScott/8341acaaf38b7fbd6e08c2ffc77aa7bd
 #file-gen_v2-hs Gen_v2.hs], and
 [https://gist.github.com/RyanGlScott/8341acaaf38b7fbd6e08c2ffc77aa7bd
 #file-gen_v13-hs Gen_v3.hs], and here are their logs:


 * [https://gist.github.com/RyanGlScott/8341acaaf38b7fbd6e08c2ffc77aa7bd
 #file-gen_v1-txt Gen_v1.txt]
   * `{terms: 143, types: 562, coercions: 239}`
   * `94,739,056 bytes allocated in the heap`
   * `Total   time    0.201s  (  0.191s elapsed)`
 * [https://gist.github.com/RyanGlScott/8341acaaf38b7fbd6e08c2ffc77aa7bd
 #file-gen_v2-txt Gen_v2.txt]
   * `{terms: 148, types: 638, coercions: 174}`
   * `93,979,880 bytes allocated in the heap`
   * `Total   time    0.196s  (  0.187s elapsed)`
 * [https://gist.github.com/RyanGlScott/8341acaaf38b7fbd6e08c2ffc77aa7bd
 #file-gen_v3-txt Gen_v3.txt]
   * `{terms: 148, types: 638, coercions: 174}`
   * `94,281,768 bytes allocated in the heap`
   * `Total   time    0.203s  (  0.192s elapsed)`

 Curiously, in this example, `v3` fares //worse// than `v2`. Again, I'm not
 sure what's going on here, and with a sample size of two, it's difficult
 to conclude if the strategy in `v3` is always better than `v2`. I suspect
 it's asymptotically better, since we go from an O(//n//) number of
 `L1`s/`R1`s to an O(log //n//) number, but I'd need more evidence to
 support that claim.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/5642#comment:44>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler