GHC: Ticket #149: missed CSE opportunity
http://ghc.haskell.org/trac/ghc/ticket/149
<p>
Don't know if this is a bug, but it was at least
_surprising_ to find that
</p>
<pre class="wiki">playerMostOccur [a] = a
playerMostOccur (x:xs)
| numOccur x (x:xs) > numOccur (playerMostOccur xs) xs = x
| otherwise = playerMostOccur xs
</pre><p>
was exponentially slower when compiled with ghc-5.04.2
-O than:
</p>
<pre class="wiki">playerMostOccur [a] = a
playerMostOccur (x:xs)
| numOccur x (x:xs) > numOccur pmo xs = x
| otherwise = pmo
where pmo = playerMostOccur xs
</pre><p>
Although the student responsible for the code couldn't
spot the
obvious optimisation, I was expecting that GHC's
optimiser would. :)
If it's not a bug, could you explain it to me?
</p>
<p>
-Greg(gregm.at.cs.uwa.edu.au)
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/149
Trac 1.0.1simonmarFri, 17 Dec 2004 09:46:55 GMT
http://ghc.haskell.org/trac/ghc/ticket/149#comment:1
http://ghc.haskell.org/trac/ghc/ticket/149#comment:1
<pre class="wiki">Logged In: YES
user_id=48280
Looks like a case where GHC's CSE isn't spotting the common
subexpression. The CSE in GHC is pretty cheap & cheerful,
there are plenty of ways it could be improved, or even
replaced by a completely new one.
</pre>
TicketsimonmarFri, 17 Dec 2004 09:47:21 GMTsummary changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:2
http://ghc.haskell.org/trac/ghc/ticket/149#comment:2
<ul>
<li><strong>summary</strong>
changed from <em>strange non-optimising</em> to <em>missed CSE opportunity</em>
</li>
</ul>
TicketiglooThu, 12 Oct 2006 18:48:16 GMTdescription changed; difficulty, architecture, milestone, keywords, os set
http://ghc.haskell.org/trac/ghc/ticket/149#comment:3
http://ghc.haskell.org/trac/ghc/ticket/149#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/trac/ghc/ticket/149?action=diff&version=3">diff</a>)
</li>
<li><strong>difficulty</strong>
set to <em>Unknown</em>
</li>
<li><strong>architecture</strong>
set to <em>Unknown</em>
</li>
<li><strong>milestone</strong>
set to <em>_|_</em>
</li>
<li><strong>keywords</strong>
<em>optimisations</em> added
</li>
<li><strong>os</strong>
set to <em>Unknown</em>
</li>
</ul>
TicketiglooThu, 12 Oct 2006 20:10:30 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:4
http://ghc.haskell.org/trac/ghc/ticket/149#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>_|_</em> to <em>6.8</em>
</li>
</ul>
<p>
This seems to work in 6.4.1, but not in the HEAD as of a few days ago, so it's probably worth at least looking to see what's going on. I've added a test (simplrun006) to the testsuite.
</p>
TicketiglooTue, 17 Oct 2006 00:39:16 GMTtestcase set
http://ghc.haskell.org/trac/ghc/ticket/149#comment:5
http://ghc.haskell.org/trac/ghc/ticket/149#comment:5
<ul>
<li><strong>testcase</strong>
set to <em>simplrun006</em>
</li>
</ul>
TicketsimonmarTue, 13 Nov 2007 15:08:52 GMTstatus, milestone changed; owner deleted
http://ghc.haskell.org/trac/ghc/ticket/149#comment:6
http://ghc.haskell.org/trac/ghc/ticket/149#comment:6
<ul>
<li><strong>owner</strong>
<em>nobody</em> deleted
</li>
<li><strong>status</strong>
changed from <em>assigned</em> to <em>new</em>
</li>
<li><strong>milestone</strong>
changed from <em>6.8 branch</em> to <em>6.8.3</em>
</li>
</ul>
<p>
look into for 6.8.3
</p>
TicketiglooTue, 18 Dec 2007 19:47:37 GMTpriority changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:7
http://ghc.haskell.org/trac/ghc/ticket/149#comment:7
<ul>
<li><strong>priority</strong>
changed from <em>low</em> to <em>high</em>
</li>
</ul>
<p>
This is a (possibly long-standing) regression.
</p>
TicketsimonmarMon, 07 Jan 2008 10:43:43 GMTtype changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:8
http://ghc.haskell.org/trac/ghc/ticket/149#comment:8
<ul>
<li><strong>type</strong>
changed from <em>bug</em> to <em>run-time performance bug</em>
</li>
</ul>
TicketsimonmarMon, 18 Feb 2008 10:50:14 GMTpriority, difficulty, description, severity, milestone changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:9
http://ghc.haskell.org/trac/ghc/ticket/149#comment:9
<ul>
<li><strong>priority</strong>
changed from <em>high</em> to <em>normal</em>
</li>
<li><strong>difficulty</strong>
changed from <em>Unknown</em> to <em>Moderate (1 day)</em>
</li>
<li><strong>description</strong>
modified (<a href="/trac/ghc/ticket/149?action=diff&version=9">diff</a>)
</li>
<li><strong>severity</strong>
changed from <em>normal</em> to <em>minor</em>
</li>
<li><strong>milestone</strong>
changed from <em>6.8.3</em> to <em>6.8 branch</em>
</li>
</ul>
<p>
The problem seems to be that Float Out isn't floating out the let expression in the guard, whereas presumably it used to. The let can't be floated out past a lambda, but nevertheless floating it would reveal an opportunity for CSE.
</p>
<p>
Plan: try floating out <em>all</em> lets, even if they can't move past a lambda, and measure the difference on nofib.
</p>
<p>
Not urgent enough for 6.8.3.
</p>
TicketiglooFri, 20 Jun 2008 22:13:05 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:10
http://ghc.haskell.org/trac/ghc/ticket/149#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>6.8 branch</em> to <em>6.10.1</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:37:13 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:11
http://ghc.haskell.org/trac/ghc/ticket/149#comment:11
<ul>
<li><strong>architecture</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:50:57 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:12
http://ghc.haskell.org/trac/ghc/ticket/149#comment:12
<ul>
<li><strong>os</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketiglooSat, 04 Oct 2008 11:50:56 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:13
http://ghc.haskell.org/trac/ghc/ticket/149#comment:13
<ul>
<li><strong>milestone</strong>
changed from <em>6.10.1</em> to <em>6.10.2</em>
</li>
</ul>
TicketsimonpjMon, 01 Dec 2008 13:11:25 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:14
http://ghc.haskell.org/trac/ghc/ticket/149#comment:14
<ul>
<li><strong>milestone</strong>
changed from <em>6.10.2</em> to <em>_|_</em>
</li>
</ul>
<p>
GHC currently does not do full-blown CSE, partly because it's a bit harder than what is done now, and partly because doing so can introduce space leaks. There is scope for experimentation here, but we're removing it from the immediate milestone.
</p>
<p>
Simon
</p>
TicketsimonmarMon, 16 Nov 2009 13:11:41 GMTdifficulty changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:15
http://ghc.haskell.org/trac/ghc/ticket/149#comment:15
<ul>
<li><strong>difficulty</strong>
changed from <em>Moderate (1 day)</em> to <em>Moderate (less than a day)</em>
</li>
</ul>
TicketsimonmarMon, 16 Nov 2009 13:28:34 GMTfailure set
http://ghc.haskell.org/trac/ghc/ticket/149#comment:16
http://ghc.haskell.org/trac/ghc/ticket/149#comment:16
<ul>
<li><strong>failure</strong>
set to <em>Runtime performance bug</em>
</li>
</ul>
TicketrizsottoMon, 16 Nov 2009 21:37:22 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/149
http://ghc.haskell.org/trac/ghc/ticket/149
<ul>
<li><strong>attachment</strong>
set to <em>CriterionBench.hs</em>
</li>
</ul>
<p>
criterion benchmark for the problem
</p>
TicketnominoloWed, 21 Apr 2010 17:00:54 GMTpatch set
http://ghc.haskell.org/trac/ghc/ticket/149#comment:17
http://ghc.haskell.org/trac/ghc/ticket/149#comment:17
<ul>
<li><strong>patch</strong>
set to <em>0</em>
</li>
</ul>
<p>
I ran the criterion benchmark on OS X 10.5 (32 bits) with GHC 6.12.1 using the default optimisation level and the runtimes are identical (163ns +/- 2ns).
</p>
TicketsimonmarThu, 22 Apr 2010 08:24:31 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/149
http://ghc.haskell.org/trac/ghc/ticket/149
<ul>
<li><strong>attachment</strong>
set to <em>CriterionBenchFixed.hs</em>
</li>
</ul>
<p>
fixed bug in CriterionBench (not using whnf)
</p>
TicketsimonmarThu, 22 Apr 2010 08:25:20 GMT
http://ghc.haskell.org/trac/ghc/ticket/149#comment:18
http://ghc.haskell.org/trac/ghc/ticket/149#comment:18
<p>
The version of the benchmark I just attached demonstrates the problem.
</p>
TicketmichaltTue, 22 Mar 2011 21:21:04 GMTcc set
http://ghc.haskell.org/trac/ghc/ticket/149#comment:19
http://ghc.haskell.org/trac/ghc/ticket/149#comment:19
<ul>
<li><strong>cc</strong>
<em>michal.terepeta@…</em> added
</li>
</ul>
<p>
I've run the fixed benchhmark on GHC 7.0.2 and the differences are quite small:
</p>
<pre class="wiki">warming up
estimating clock resolution...
mean is 5.608272 us (160001 iterations)
found 2835 outliers among 159999 samples (1.8%)
2620 (1.6%) high severe
estimating cost of a clock call...
mean is 41.08527 ns (43 iterations)
found 4 outliers among 43 samples (9.3%)
2 (4.7%) high mild
2 (4.7%) high severe
benchmarking playerMostOccur
collecting 100 samples, 1 iterations each, in estimated 635.0040 ms
bootstrapping with 100000 resamples
mean: 3.506386 ms, lb 3.463573 ms, ub 3.627819 ms, ci 0.950
std dev: 335.3037 us, lb 107.8520 us, ub 701.8364 us, ci 0.950
found 3 outliers among 100 samples (3.0%)
2 (2.0%) high severe
variance introduced by outliers: 1.000%
variance is unaffected by outliers
benchmarking playerMostOccur'
collecting 100 samples, 2 iterations each, in estimated 720.7155 ms
bootstrapping with 100000 resamples
mean: 3.606333 ms, lb 3.600894 ms, ub 3.616024 ms, ci 0.950
std dev: 36.14909 us, lb 22.68614 us, ub 52.87152 us, ci 0.950
found 10 outliers among 100 samples (10.0%)
9 (9.0%) high severe
variance introduced by outliers: 0.990%
variance is unaffected by outliers
benchmarking playerMostOccur
collecting 100 samples, 67 iterations each, in estimated 561.6000 ms
bootstrapping with 100000 resamples
mean: 84.15780 us, lb 84.03386 us, ub 84.47981 us, ci 0.950
std dev: 953.0503 ns, lb 438.4662 ns, ub 1.977162 us, ci 0.950
found 7 outliers among 100 samples (7.0%)
3 (3.0%) high mild
4 (4.0%) high severe
variance introduced by outliers: 0.990%
variance is unaffected by outliers
benchmarking playerMostOccur'
collecting 100 samples, 70 iterations each, in estimated 566.6148 ms
bootstrapping with 100000 resamples
mean: 81.52763 us, lb 81.32001 us, ub 81.96656 us, ci 0.950
std dev: 1.476358 us, lb 803.8508 ns, ub 2.630875 us, ci 0.950
found 11 outliers among 100 samples (11.0%)
4 (4.0%) high mild
7 (7.0%) high severe
variance introduced by outliers: 0.995%
variance is unaffected by outliers
benchmarking playerMostOccur
collecting 100 samples, 1 iterations each, in estimated 923.5859 ms
bootstrapping with 100000 resamples
mean: 7.817296 ms, lb 7.790770 ms, ub 7.877817 ms, ci 0.950
std dev: 193.8747 us, lb 70.80833 us, ub 338.0659 us, ci 0.950
found 4 outliers among 100 samples (4.0%)
3 (3.0%) high severe
variance introduced by outliers: 0.997%
variance is unaffected by outliers
benchmarking playerMostOccur'
collecting 100 samples, 1 iterations each, in estimated 757.6227 ms
bootstrapping with 100000 resamples
mean: 7.514011 ms, lb 7.495620 ms, ub 7.552087 ms, ci 0.950
std dev: 130.1032 us, lb 72.61251 us, ub 236.9545 us, ci 0.950
found 6 outliers among 100 samples (6.0%)
4 (4.0%) high mild
2 (2.0%) high severe
variance introduced by outliers: 0.995%
variance is unaffected by outliers
benchmarking playerMostOccur
collecting 100 samples, 1 iterations each, in estimated 82.58250 s
bootstrapping with 100000 resamples
mean: 777.5068 ms, lb 776.6123 ms, ub 778.8386 ms, ci 0.950
std dev: 5.512690 ms, lb 4.044142 ms, ub 7.447603 ms, ci 0.950
found 10 outliers among 100 samples (10.0%)
4 (4.0%) high mild
6 (6.0%) high severe
variance introduced by outliers: 0.990%
variance is unaffected by outliers
benchmarking playerMostOccur'
collecting 100 samples, 1 iterations each, in estimated 76.42000 s
bootstrapping with 100000 resamples
mean: 748.9900 ms, lb 747.7942 ms, ub 750.6694 ms, ci 0.950
std dev: 7.211566 ms, lb 5.591098 ms, ub 9.302462 ms, ci 0.950
found 9 outliers among 100 samples (9.0%)
3 (3.0%) high mild
6 (6.0%) high severe
variance introduced by outliers: 0.990%
variance is unaffected by outliers
</pre><p>
It's interesting that the times are not the same. On the other hand, it seems
that the original issue has been fixed.
</p>
TicketiglooFri, 25 Mar 2011 00:55:56 GMTpriority, milestone changed; owner set
http://ghc.haskell.org/trac/ghc/ticket/149#comment:20
http://ghc.haskell.org/trac/ghc/ticket/149#comment:20
<ul>
<li><strong>owner</strong>
set to <em>igloo</em>
</li>
<li><strong>priority</strong>
changed from <em>normal</em> to <em>high</em>
</li>
<li><strong>milestone</strong>
changed from <em>_|_</em> to <em>7.2.1</em>
</li>
</ul>
<p>
Thanks for looking into it. If it's fixed, let's add a regression test and close it.
</p>
TicketsimonmarFri, 25 Mar 2011 09:34:45 GMT
http://ghc.haskell.org/trac/ghc/ticket/149#comment:21
http://ghc.haskell.org/trac/ghc/ticket/149#comment:21
<p>
I'm fairly sure the bug in general is not fixed, but this particular instance of it might be.
</p>
TicketiglooSun, 17 Apr 2011 17:20:59 GMTpriority, testcase, milestone changed; owner deleted
http://ghc.haskell.org/trac/ghc/ticket/149#comment:22
http://ghc.haskell.org/trac/ghc/ticket/149#comment:22
<ul>
<li><strong>owner</strong>
<em>igloo</em> deleted
</li>
<li><strong>priority</strong>
changed from <em>high</em> to <em>normal</em>
</li>
<li><strong>testcase</strong>
changed from <em>simplrun006</em> to <em>T149</em>
</li>
<li><strong>milestone</strong>
changed from <em>7.2.1</em> to <em>_|_</em>
</li>
</ul>
<p>
Doesn't look fixed to me. I've changed the test to be less fragile.
</p>
TicketliyangMon, 25 Mar 2013 11:29:44 GMTcc changed
http://ghc.haskell.org/trac/ghc/ticket/149#comment:23
http://ghc.haskell.org/trac/ghc/ticket/149#comment:23
<ul>
<li><strong>cc</strong>
<em>hackage.haskell.org@…</em> added
</li>
</ul>
TicketnfrisbyThu, 02 May 2013 15:49:01 GMT
http://ghc.haskell.org/trac/ghc/ticket/149#comment:24
http://ghc.haskell.org/trac/ghc/ticket/149#comment:24
<p>
As of my fix for <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/7796" title="bug: improve dead code elimination in CorePrep (closed: fixed)">#7796</a>, commit hash <a class="changeset" href="http://ghc.haskell.org/trac/ghc/changeset/c7d80c6524390551b64e9c1d651e1a03ed3c7617/ghc" title="improve dead code elimination in CorePrep (fixes #7796)">c7d80c6524390551b64e9c1d651e1a03ed3c7617</a>, this test is passing again. I made no changes to CSE, though. So it needs to be further robustified. It's on my todo list, but not near the top.
</p>
TicketIan Lynagh <igloo@…>Sun, 12 Jan 2014 12:00:47 GMT
http://ghc.haskell.org/trac/ghc/ticket/149#comment:25
http://ghc.haskell.org/trac/ghc/ticket/149#comment:25
<p>
In <a class="changeset" href="http://ghc.haskell.org/trac/ghc/changeset/ee40de9386961639e9520dee372688183b26aa5e/ghc" title="Test for #149 (missed CSE opportunity)">ee40de9386961639e9520dee372688183b26aa5e/ghc</a>:
</p>
<pre class="message">Test for #149 (missed CSE opportunity)</pre>
TicketIan Lynagh <igloo@…>Sun, 12 Jan 2014 12:01:19 GMT
http://ghc.haskell.org/trac/ghc/ticket/149#comment:26
http://ghc.haskell.org/trac/ghc/ticket/149#comment:26
<p>
In <a class="changeset" href="http://ghc.haskell.org/trac/ghc/changeset/c4068e4df8b23e7f51605bd8db9754fee28b6ff0/ghc" title="simplrun006 is broken: trac #149">c4068e4df8b23e7f51605bd8db9754fee28b6ff0/ghc</a>:
</p>
<pre class="message">simplrun006 is broken: trac #149</pre>
TicketJoachim Breitner <mail@…>Mon, 10 Feb 2014 13:53:01 GMT
http://ghc.haskell.org/trac/ghc/ticket/149#comment:27
http://ghc.haskell.org/trac/ghc/ticket/149#comment:27
<p>
In <a class="changeset" href="http://ghc.haskell.org/trac/ghc/changeset/393ea739567206d848f53e9ca75f532a49218694/ghc" title="Update test cases due to call arity
Some nice improvements on already ...">393ea739567206d848f53e9ca75f532a49218694/ghc</a>:
</p>
<pre class="message">Update test cases due to call arity
Some nice improvements on already succeeding test cases (#876, #7954
and #4267)
Test #149 needed a little change, lest call arity causes a allocation
change that we do not want to test here.</pre>
Ticket