missed CSE opportunity

[nobody]

Don't know if this is a bug, but it was at least _surprising_ to find that

playerMostOccur [a] = a
playerMostOccur (x:xs)
 | numOccur x (x:xs) > numOccur (playerMostOccur xs) xs = x
 | otherwise = playerMostOccur xs

was exponentially slower when compiled with ghc-5.04.2 -O than:

playerMostOccur [a] = a
playerMostOccur (x:xs)
 | numOccur x (x:xs) > numOccur pmo xs = x
 | otherwise = pmo
 where pmo = playerMostOccur xs

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?

-Greg(gregm.at.cs.uwa.edu.au)

[simonmar]

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.

[igloo]

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.

[simonmar]

look into for 6.8.3

[igloo]

This is a (possibly long-standing) regression.

[simonmar]

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.

Plan: try floating out all lets, even if they can't move past a lambda, and measure the difference on nofib.

Not urgent enough for 6.8.3.

[simonpj]

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.

Simon

[rizsotto]

criterion benchmark for the problem

[nominolo]

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).

[simonmar]

fixed bug in CriterionBench? (not using whnf)

[simonmar]

The version of the benchmark I just attached demonstrates the problem.

[michalt]

I've run the fixed benchhmark on GHC 7.0.2 and the differences are quite small:

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

It's interesting that the times are not the same. On the other hand, it seems that the original issue has been fixed.

[igloo]

Thanks for looking into it. If it's fixed, let's add a regression test and close it.

[simonmar]

I'm fairly sure the bug in general is not fixed, but this particular instance of it might be.

[igloo]

Doesn't look fixed to me. I've changed the test to be less fragile.

[nfrisby]

As of my fix for #7796, commit hash c7d80c6524390551b64e9c1d651e1a03ed3c7617, 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.