Cardinality analysis and other small fixes
Simon Peyton-Jones
simonpj at microsoft.com
Thu Jun 6 16:59:42 CEST 2013
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
More information about the ghc-devs
mailing list