DsExpr: Don't build/foldr huge lists
authorBen Gamari <bgamari.foss@gmail.com>
Sun, 20 Mar 2016 16:49:58 +0000 (17:49 +0100)
committerBen Gamari <ben@smart-cactus.org>
Sun, 20 Mar 2016 21:00:37 +0000 (22:00 +0100)
Desugaring long lists with build trades large static data for large
code, which is likely a poor trade-off. See #11707.

Test Plan: Validate, nofib

Reviewers: simonpj, austin

Reviewed By: austin

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2007

GHC Trac Issues: #11707

compiler/deSugar/DsExpr.hs
testsuite/tests/perf/compiler/all.T

index 59c8c4d..8a64a68 100644 (file)
@@ -788,6 +788,12 @@ allocation in some nofib programs. Specifically
 Of course, if rules aren't turned on then there is pretty much no
 point doing this fancy stuff, and it may even be harmful.
 
+Moreover, for large lists (with a dynamic prefix longer than maxBuildLength) we
+choose not to perform this optimization as it will trade large static data for
+large code, which is generally a poor trade-off. See #11707 and the
+documentation for maxBuildLength.
+
+
 =======>  Note by SLPJ Dec 08.
 
 I'm unconvinced that we should *ever* generate a build for an explicit
@@ -803,10 +809,29 @@ We do not want to generate a build invocation on the LHS of this RULE!
 We fix this by disabling rules in rule LHSs, and testing that
 flag here; see Note [Desugaring RULE left hand sides] in Desugar
 
-To test this I've added a (static) flag -fsimple-list-literals, which
+To test this I've added a flag -fsimple-list-literals, which
 makes all list literals be generated via the simple route.
 -}
 
+{- | The longest list length which we will desugar using @build@.
+
+This is essentially a magic number and its setting is unfortunate rather
+arbitrary. The idea here, as mentioned in Note [Desugaring explicit lists],
+is to avoid deforesting large static data into large(r) code. 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 impossible to
+set generally correctly.
+
+The effect of reducing this number will be that 'build' fusion is applied
+less often. From a runtime performance perspective, applying 'build' more
+liberally on "moderately" sized lists should rarely hurt and will often it can
+only expose further optimization opportunities; if no fusion is possible it will
+eventually get rule-rewritten back to a list). We do, however, pay in compile
+time.
+-}
+maxBuildLength :: Int
+maxBuildLength = 32
+
 dsExplicitList :: Type -> Maybe (SyntaxExpr Id) -> [LHsExpr Id]
                -> DsM CoreExpr
 -- See Note [Desugaring explicit lists]
@@ -815,6 +840,8 @@ dsExplicitList elt_ty Nothing xs
        ; xs' <- mapM dsLExpr xs
        ; let (dynamic_prefix, static_suffix) = spanTail is_static xs'
        ; if gopt Opt_SimpleListLiterals dflags        -- -fsimple-list-literals
+         || length dynamic_prefix > maxBuildLength
+                -- Don't generate builds if the list is very long.
          || not (gopt Opt_EnableRewriteRules dflags)  -- Rewrite rules off
                 -- Don't generate a build if there are no rules to eliminate it!
                 -- See Note [Desugaring RULE left hand sides] in Desugar
index c19d51d..a1ebe11 100644 (file)
@@ -722,12 +722,13 @@ test('T9872d',
 test('T9961',
      [ only_ways(['normal']),
        compiler_stats_num_field('bytes allocated',
-          [(wordsize(64), 745044392, 5),
+          [(wordsize(64), 519436672, 5),
           # 2015-01-12    807117816   Initally created
           # 2015-spring   772510192   Got better
           # 2015-05-22    663978160   Fix for #10370 improves it more
           # 2015-10-28    708680480   x86_64/Linux   Emit Typeable at definition site
           # 2015-12-17    745044392   x86_64/Darwin  Creep upwards
+          # 2016-03-20    519436672   x64_64/Linux   Don't use build desugaring for large lists (D2007)
            (wordsize(32), 375647160, 5)
           ]),
       ],