Cardinality analysis and other small fixes

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Cardinality analysis and other small fixes

Simon Peyton Jones
As you'll see I've just pushed a wave of commits, of which cardinality analysis is the big one.  Some of the others are performance tweaks that I discovered when benchmarking.  Before pushing the wave I did a full nofib run against today's HEAD; here are the results.

Pretty modest reductions, but zero big outliers in the wrong direction.

A couple of compiler perf tests are worse, which I should look into.

Thanks to Ilya for doing a lot of the cardinality work.

Simon

--------------------------------------------------------------------------------
        Program           Size    Allocs   Runtime   Elapsed  TotalMem
--------------------------------------------------------------------------------
           anna          -1.3%     -0.5%      0.18      0.18     +0.0%
           ansi          -2.5%     -0.8%      0.00      0.00     +0.0%
           atom          -2.3%     -0.0%     -1.3%     -1.3%     +0.0%
         awards          -2.4%     -0.1%      0.00      0.00     +0.0%
         banner          -2.8%     -0.2%      0.00      0.00     +0.0%
     bernouilli          -2.5%     -0.0%     +0.0%     +0.0%     +0.0%
   binary-trees          -2.6%     -0.2%     -1.1%     -1.1%     +7.4%
          boyer          -2.4%     -0.0%      0.07      0.07     +0.0%
         boyer2          -2.6%     -0.4%      0.01      0.01     +0.0%
           bspt          -2.1%     -0.0%      0.02      0.02     +0.0%
      cacheprof          -2.0%     -0.4%     -3.6%     -2.7%     -5.7%
       calendar          -2.5%     +0.2%      0.00      0.00     +0.0%
       cichelli          -2.6%     -0.0%      0.16      0.16     +0.0%
        circsim          -2.3%     -0.0%     -2.0%     -1.9%    +11.5%
       clausify          -2.5%     -0.0%      0.06      0.06     +0.0%
  comp_lab_zift          -2.4%     -0.0%     -3.0%     -3.0%    +14.3%
       compress          -2.3%     -0.0%     +0.0%     +0.0%    -33.3%
      compress2          -2.7%     -0.0%     -8.1%     -8.1%    -14.3%
    constraints          -2.7%     -1.9%     -3.5%     -3.5%     +0.0%
   cryptarithm1          -2.9%     -0.0%     -8.8%     -8.8%    -50.0%
   cryptarithm2          -2.5%     -0.0%      0.01      0.01     +0.0%
            cse          -2.5%     -0.1%      0.00      0.00     +0.0%
          eliza          -2.7%     -0.1%      0.00      0.00     +0.0%
          event          -2.5%     -0.0%     +0.0%     +0.0%     +0.0%
         exp3_8          -2.5%     -0.0%     +0.0%     +0.0%     +0.0%
         expert          -2.7%     -0.2%      0.00      0.00     +0.0%
 fannkuch-redux          -2.5%     -0.0%     -0.9%     -0.9%     +0.0%
          fasta          -3.3%     -0.0%     -0.2%     -0.4%     +0.0%
            fem          -2.4%     -0.0%      0.03      0.03     +0.0%
            fft          -2.4%     -0.0%      0.06      0.06     +0.0%
           fft2          -2.2%     -0.0%      0.09      0.09     +0.0%
       fibheaps          -2.5%     -0.0%      0.05      0.05     +0.0%
           fish          -2.8%     -0.0%      0.02      0.02    -50.0%
          fluid          -1.7%     -0.0%      0.01      0.01     +0.0%
         fulsom          -2.0%     -0.0%     +0.4%     +0.4%    +33.3%
         gamteb          -2.3%     +0.5%      0.06      0.06     +0.0%
            gcd          -2.5%     -0.0%      0.05      0.05     +0.0%
    gen_regexps          -2.9%     -0.1%      0.00      0.00     +0.0%
         genfft          -2.5%     -0.0%      0.05      0.05     +0.0%
             gg          -2.3%     -0.0%      0.02      0.02     +0.0%
           grep          -2.6%     -0.4%      0.00      0.00     +0.0%
         hidden          -2.1%     -0.0%     -0.5%     -0.3%     +0.0%
            hpg          -2.2%     -1.0%     +1.7%     +1.7%     +0.0%
            ida          -2.4%     -0.0%      0.13      0.12     +0.0%
          infer          -2.2%     +0.0%      0.10      0.10     +0.0%
        integer          -2.4%     +0.0%     -2.7%     -2.7%     +0.0%
      integrate          -2.4%     -0.0%     +1.2%     +1.2%     +0.0%
   k-nucleotide          -6.3%     -0.0%     +1.1%     +1.1%     +0.0%
          kahan          -2.5%     -0.0%     +0.0%     +0.0%     +0.0%
        knights          -2.5%     -1.6%      0.01      0.01     +0.0%
           lcss          -2.5%     +0.0%     +0.0%     +0.0%     +0.0%
           life          -2.7%     -0.0%     -2.8%     -2.8%     +0.0%
           lift          -2.5%     -0.0%      0.00      0.00     +0.0%
      listcompr          -2.8%     -0.0%      0.14      0.14     +0.0%
       listcopy          -2.8%     -0.0%      0.14      0.14     +0.0%
       maillist          -2.9%     -0.2%      0.07      0.09    +11.2%
         mandel          -2.4%     -0.0%      0.11      0.11     +0.0%
        mandel2          -2.8%     -0.0%      0.00      0.00     +0.0%
        minimax          -2.7%     -0.0%      0.00      0.00     +0.0%
        mkhprog          -2.8%     +0.1%      0.00      0.00     +0.0%
     multiplier          -2.5%     -0.0%     -4.5%     -4.5%     +0.0%
         n-body          -3.7%     -0.0%     +1.2%     +1.1%     +0.0%
       nucleic2          -2.3%    -10.9%      0.10      0.10     +0.0%
           para          -2.6%     -0.0%     +0.0%     +0.0%     +0.0%
      paraffins          -2.5%     -0.0%      0.20      0.20     +0.0%
         parser          -1.9%     -0.2%      0.05      0.05    -20.0%
        parstof          -2.2%     -0.0%      0.00      0.00     +0.0%
            pic          -2.4%     -0.0%      0.00      0.00     +0.0%
       pidigits          -2.5%     -0.0%     -0.3%     -1.0%     +0.0%
          power          -2.2%     -0.0%     -1.4%     -1.4%     +0.0%
         pretty          -2.7%     -0.2%      0.00      0.00     +0.0%
         primes          -2.6%     -0.0%      0.11      0.11     +0.0%
      primetest          -2.5%     -0.0%      0.14      0.14     +0.0%
         prolog          -2.4%     -0.3%      0.00      0.00     +0.0%
         puzzle          -2.8%     -0.0%     -8.0%     -8.0%     +0.0%
         queens          -2.5%     -0.0%      0.02      0.02     +0.0%
        reptile          -2.2%     -0.0%      0.02      0.02     +0.0%
reverse-complem          -3.3%     -0.1%     +4.5%     +4.5%     +0.0%
        rewrite          -2.6%     -0.1%      0.02      0.02     +0.0%
           rfib          -2.4%     -0.1%      0.03      0.03     +0.0%
            rsa          -2.6%     -0.0%      0.03      0.03     +0.0%
            scc          -2.8%     -0.4%      0.00      0.00     +0.0%
          sched          -2.5%     -0.0%      0.03      0.03     +0.0%
            scs          -1.9%     +0.0%     +0.2%     +0.2%     +0.0%
         simple          -1.9%     -0.0%     -2.1%     -2.1%     +0.0%
          solid          -2.3%     -0.0%     +0.0%     +0.0%     +0.0%
        sorting          -2.8%     -0.0%      0.00      0.00     +0.0%
  spectral-norm          -2.6%     -0.1%     +0.0%     +0.0%     +0.0%
         sphere          -2.3%     -1.5%      0.08      0.08     +0.0%
         symalg          -1.7%     -0.0%      0.01      0.01     +0.0%
            tak          -2.5%     -0.0%      0.02      0.02     +0.0%
      transform          -2.2%     -0.0%     -1.8%     -1.8%     +0.0%
       treejoin          -2.9%     -0.0%     +0.0%     +0.0%     +0.0%
      typecheck          -2.4%     -0.0%     -4.4%     -4.4%     +0.0%
        veritas          -1.1%     -0.0%      0.00      0.00     +0.0%
           wang          -2.4%     -0.0%     +0.0%     +0.0%     +0.0%
      wave4main          -2.4%     +0.5%     +0.0%     +0.0%     +0.0%
   wheel-sieve1          -2.5%     -0.0%     +0.0%     +0.0%     +0.0%
   wheel-sieve2          -2.5%     -0.0%     +0.0%     +0.0%     +0.0%
           x2n1          -2.5%     -0.0%      0.00      0.00     +0.0%
--------------------------------------------------------------------------------
            Min          -6.3%    -10.9%     -8.8%     -8.8%    -50.0%
            Max          -1.1%     +0.5%     +4.5%     +4.5%    +33.3%
 Geometric Mean          -2.5%     -0.2%     -1.3%     -1.3%     -1.5%

| -----Original Message-----
| From: ghc-commits-bounces at haskell.org [mailto:ghc-commits-
| bounces at haskell.org] On Behalf Of Simon Peyton Jones
| Sent: 06 June 2013 14:30
| To: ghc-commits at haskell.org
| Subject: [commit: ghc] master: Implement cardinality analysis (99d4e5b)
|
| Repository : http://darcs.haskell.org/ghc.git/
|
| On branch  : master
|
| https://github.com/ghc/ghc/commit/99d4e5b4a0bd32813ff8c74e91d2dcf6b355
| 5176
|
| >---------------------------------------------------------------
|
| commit 99d4e5b4a0bd32813ff8c74e91d2dcf6b3555176
| Author: Simon Peyton Jones <simonpj at microsoft.com>
| Date:   Fri May 3 14:50:58 2013 +0100
|
|     Implement cardinality analysis
|
|     This major patch implements the cardinality analysis described
|     in our paper "Higher order cardinality analysis". It is joint
|     work with Ilya Sergey and Dimitrios Vytiniotis.
|
|     The basic is augment the absence-analysis part of the demand
|     analyser so that it can tell when something is used
|     never
|     at most once
|       some other way
|
|     The "at most once" information is used
|         a) to enable transformations, and
|            in particular to identify one-shot lambdas
|         b) to allow updates on thunks to be omitted.
|
|     There are two new flags, mainly there so you can do performance
|     comparisons:
|         -fkill-absence   stops GHC doing absence analysis at all
|         -fkill-one-shot  stops GHC spotting one-shot lambdas
|                          and single-entry thunks
|
|     The big changes are:
|
|     * The Demand type is substantially refactored.  In particular
|       the UseDmd is factored as follows
|           data UseDmd
|             = UCall Count UseDmd
|             | UProd [MaybeUsed]
|             | UHead
|             | Used
|
|           data MaybeUsed = Abs | Use Count UseDmd
|
|           data Count = One | Many
|
|       Notice that UCall recurses straight to UseDmd, whereas
|       UProd goes via MaybeUsed.
|
|       The "Count" embodies the "at most once" or "many" idea.
|
|     * The demand analyser itself was refactored a lot
|
|     * The previously ad-hoc stuff in the occurrence analyser for foldr and
|       build goes away entirely.  Before if we had build (\cn -> ...x... )
|       then the "\cn" was hackily made one-shot (by spotting 'build' as
|       special.  That's essential to allow x to be inlined.  Now the
|       occurrence analyser propagates info gotten from 'build's stricness
|       signature (so build isn't special); and that strictness sig is
|       in turn derived entirely automatically.  Much nicer!
|
|     * The ticky stuff is improved to count single-entry thunks separately.
|
|     One shortcoming is that there is no DEBUG way to spot if an
|     allegedly-single-entry thunk is acually entered more than once.  It
|     would not be hard to generate a bit of code to check for this, and it
|     would be reassuring.  But it's fiddly and I have not done it.
|
|     Despite all this fuss, the performance numbers are rather under-whelming.
|     See the paper for more discussion.
|
|            nucleic2          -0.8%    -10.9%      0.10      0.10     +0.0%
|              sphere          -0.7%     -1.5%      0.08      0.08     +0.0%
|     --------------------------------------------------------------------------------
|                 Min          -4.7%    -10.9%     -9.3%     -9.3%    -50.0%
|                 Max          -0.4%     +0.5%     +2.2%     +2.3%     +7.4%
|      Geometric Mean          -0.8%     -0.2%     -1.3%     -1.3%     -1.8%
|
|     I don't quite know how much credence to place in the runtime changes,
|     but movement seems generally in the right direction.
|
|  compiler/basicTypes/Demand.lhs   | 1034 ++++++++++++++++++++++++++------
| ------
|  compiler/basicTypes/MkId.lhs     |    4 +-
|  compiler/basicTypes/OccName.lhs  |    7 +-
|  compiler/cmm/CmmParse.y          |    3 +-
|  compiler/codeGen/StgCmmBind.hs   |   44 +-
|  compiler/codeGen/StgCmmTicky.hs  |   25 +-
|  compiler/coreSyn/CorePrep.lhs    |   57 ++-
|  compiler/main/DynFlags.hs        |    6 +-
|  compiler/simplCore/OccurAnal.lhs |  208 ++++----
|  compiler/stgSyn/CoreToStg.lhs    |   30 +-
|  compiler/stranal/DmdAnal.lhs     |  582 ++++++++++++---------
|  docs/storage-mgt/ldv.tex         |    6 +-
|  includes/stg/Ticky.h             |    7 +-
|  rts/Linker.c                     |    8 +-
|  rts/Ticky.c                      |   15 +-
|  15 files changed, 1302 insertions(+), 734 deletions(-)
|
|
| Diff suppressed because of size. To see it, use:
|
|     git show 99d4e5b4a0bd32813ff8c74e91d2dcf6b3555176
|
| _______________________________________________
| ghc-commits mailing list
| ghc-commits at haskell.org
| http://www.haskell.org/mailman/listinfo/ghc-commits