#11707: Don't desugar large lists with build -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): There is currently a GHC flag which controls whether `build` desugaring is used at all, `-fsimple-list-literals`. To roughly characterize the effect of `build` on allocation, I did a nofib against 3f60ce8751c860a2bd0ddbe87429136a9d97449b run with and without `-fsimple- list-literals`. The major allocation changes were, {{{ -------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed TotalMem -------------------------------------------------------------------------------- ansi +0.0% +10.8% 0.000 0.004 0.0% bspt +0.1% +2.7% 0.004 0.004 0.0% cacheprof +0.1% +3.3% 0.181 0.181 0.0% eliza -0.2% +0.8% 0.000 0.000 0.0% fluid -0.1% +0.7% 0.004 0.004 0.0% fulsom +0.0% +0.7% 0.125 0.125 -21.4% integrate +0.0% +152.6% 0.081 0.081 +7.4% lift +0.0% +4.5% 0.000 0.000 0.0% nucleic2 -0.3% +2.4% 0.024 0.024 0.0% parser -0.4% +0.6% 0.011 0.012 0.0% reptile -0.0% +0.1% 0.004 0.004 0.0% rewrite +0.1% +96.7% 0.007 0.012 0.0% (those tests with no change in allocations omitted) -------------------------------------------------------------------------------- Min -0.4% -0.2% -1.0% -2.0% -21.4% Max +0.1% +152.6% +0.3% +0.6% +7.4% Geometric Mean -0.0% +1.9% -0.2% -0.2% -0.2% }}} There are a few things to note here: * Allocations, if they change at all, increase without `build` fusion, as we would expect * A `fulsom` had its total memory usage dramatically reduced without `build` fusion; this may be worth further investigation. * Runtime didn't appreciably change in any case * Binary sizes don't change On the other hand, if I compile `T9961` with `-fsimple-list-literals`, I see a dramatic reduction in compiler allocations (from 745044392 to 518841472, about 30%). Unfortunately it's not easy to measure the runtime cost of list construction with this test. I'll try to write up a simple `Criterion` benchmark to do this. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11707#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11707: Don't desugar large lists with build -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Why do `integrate` and `rewrite` regress so much? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11707#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11707: Don't desugar large lists with build -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): I'm not as certain in the case of `rewrite`, which is a much larger program. This is one possibility, {{{#!hs group_rules = map parse_eqn [ "(a * b) * c = a * (b * c)", "E * x = x", "I(x) * x = E" ] }}} Perhaps the more likely culprit is, {{{#!hs p_term = seQ q_func [p_ident, look_for '(', list_of p_expr ',', look_for ')'] ## p_prim }}} where, `seQ` involves `foldr` on its list argument and was clearly designed expecting fusion. There are also a number of singleton lists, although -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11707#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11707: Don't desugar large lists with build -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): I've pushed a simple approach to avoid `build`-based list desugaring for large lists to Phab:D2007. Here we simply threshold on the list length. I have a few concerns about this approach, * This threshold introduces a "performance cliff", where users will suddenly see drastically different performance characteristics as their literal lists grow. * There isn't really a good way to choose this size. Ideally we'd want a smaller threshold with larger consumers and vice-versa, but we have no way of knowing what will be consuming our list in the desugaring. From a runtime performance perspective, applying `build` more liberally should rarely hurt (it can only expose further optimization opportunities; if no fusion is possible it will eventually get rule-rewritten back to a list) Consequently, the threshold we introduce here is a bit concerning since we are limiting contexts in which we'll use `build`, potentially hiding optimizations. Regardless, `nofib` shows no change in allocations after this change, so it at very least doesn't hurt any of the cases there. Moreover, it shows a 30% reduction in compiler allocations in `T9961` (from 745044392 to 745044392 bytes). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11707#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11707: Don't desugar large lists with build -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2007 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): See #11710; I think we should abandon the "static tail" idea described in `Note [Desugaring explicit lists]` entirely. Then, to avoid code bloat on very long lists, let's have the patch in this ticket, which ensures that if the list is long we revert to cons-list for. The goal here is just to eliminate mega-code-bloat in extreme cases. (Hence no real need for a flag to control `maxBuildLength`. I don't really like it; but I don't want BOTH hacks. One is enough! Not worth burning much midnight oil on this one. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11707#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11707: Don't desugar large lists with build -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: merge Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2007 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => merge * milestone: => 8.0.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11707#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11707: Don't desugar large lists with build -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: merge Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2007 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Ah: see Phab:D2023 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11707#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11707: Don't desugar large lists with build -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2007, Wiki Page: | Phab:D2023 -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11707#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler