diff options
| author | Simon Peyton Jones <simonpj@microsoft.com> | 2016-12-02 13:59:11 +0000 |
|---|---|---|
| committer | Simon Peyton Jones <simonpj@microsoft.com> | 2016-12-05 17:40:00 +0000 |
| commit | 517d03e41b4f5c144d1ad684539340421be2be2a (patch) | |
| tree | 4aceeedb0ab669b02a6371be7b119ffa6caede01 /testsuite/tests/typecheck/should_compile | |
| parent | 90c5af4778c8ed1c33991c4f28bbbe8958f1e60f (diff) | |
| download | haskell-517d03e41b4f5c144d1ad684539340421be2be2a.tar.gz | |
Fix an asymptotic bug in the occurrence analyser
Trac #12425 and #12234 showed up a major and long-standing
bug in the occurrence analyser, whereby it could generate
explonentially large program!
There's a lot of commentary on #12425; and it's all described
in Note [Loop breakers, node scoring, and stability]
I did quite a lot of refactoring to make the code comprehensibe
again (its structure had bit-rotted rather), so the patch
looks bigger than it really is.
Hurrah!
I did a nofib run to check that I hadn't inadertently ruined
anything:
--------------------------------------------------------------------------------
Program Size Allocs Runtime Elapsed TotalMem
--------------------------------------------------------------------------------
fluid -0.3% -1.5% 0.01 0.01 +0.0%
parser -0.9% +0.6% 0.04 0.04 +0.0%
prolog -0.1% +1.2% 0.00 0.00 +0.0%
--------------------------------------------------------------------------------
Min -0.9% -1.5% -8.6% -8.7% +0.0%
Max +0.1% +1.2% +7.7% +7.8% +2.4%
Geometric Mean -0.2% -0.0% -0.2% -0.3% +0.0%
I checked what happened in 'prolog'. It seems that we have a
recursive data structure something like this
f :: [blah]
f x = build (\cn. ...g... )
g :: [blah2]
g y = ....(foldr k z (f y))....
If we inline 'f' into 'g' we get better fusion than the other
way round, but we don't have any way to spot that at the moment.
(I wonder if we could do worker/wrapper for functions returning
a 'build'?) It was happening before by a fluke.
Anyway I decided to accept this; it's relatively rare I think.
Diffstat (limited to 'testsuite/tests/typecheck/should_compile')
| -rw-r--r-- | testsuite/tests/typecheck/should_compile/all.T | 1 |
1 files changed, 1 insertions, 0 deletions
diff --git a/testsuite/tests/typecheck/should_compile/all.T b/testsuite/tests/typecheck/should_compile/all.T index 98e4ece08c..de7f147383 100644 --- a/testsuite/tests/typecheck/should_compile/all.T +++ b/testsuite/tests/typecheck/should_compile/all.T @@ -555,3 +555,4 @@ test('T12734', normal, compile, ['']) test('T12734a', normal, compile_fail, ['']) test('T12763', normal, compile, ['']) test('T12797', normal, compile, ['']) + |