Proposal: Make intersperse lazier

[Christian Maeder]

Am 24.09.2010 17:55, schrieb Christian Maeder:
> I consider it useful, because the "natural" implementation:
> 
>   prependToAll s = foldr (\ x r -> s : x : r) []
> 
> seems to leak without optimization.

"leak" is wrong. My Benchmarks fail without optimization.
(see attached log.txt)

Christian

Bench.hs:

import Criterion.Main

testCase f = print . length . f ','

main = do
  let s = replicate 100000000 'A'
  print $ length s
  defaultMain [ bench "prepend" $ testCase prepend s
              , bench "prependToAll" $ testCase prependToAll s ]

prependToAll :: a -> [a] -> [a]
prependToAll s = foldr (\ x r -> s : x : r) []

prepend :: a -> [a] -> [a]
prepend s l = case l of
  [] -> []
  x : r -> s : x : prepend s r
-------------- next part --------------
maeder at leibniz:~/haskell/examples> ghc --make -fforce-recomp -O0 Bench.hs
[1 of 1] Compiling Main             ( Bench.hs, Bench.o )
Linking Bench ...
maeder at leibniz:~/haskell/examples> ./Bench -s 10
100000000
warming up
estimating clock resolution...
mean is 17.53661 us (40001 iterations)
found 1866 outliers among 39999 samples (4.7%)
  1370 (3.4%) high severe
estimating cost of a clock call...
mean is 1.366620 us (70 iterations)
found 3 outliers among 70 samples (4.3%)
  1 (1.4%) high mild
  2 (2.9%) high severe

benchmarking prepend
200000000
collecting 10 samples, 1 iterations each, in estimated 20.89278 s
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
bootstrapping with 100000 resamples
mean: 10.24436 us, lb 9.791369 us, ub 10.84041 us, ci 0.950
std dev: 878.1661 ns, lb 615.5941 ns, ub 1.108069 us, ci 0.950
variance introduced by outliers: 9.787%
variance is slightly inflated by outliers

benchmarking prependToAll
200000000
collecting 10 samples, 1 iterations each, in estimated 24.10117 s
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
bootstrapping with 100000 resamples
mean: 10.38742 us, lb 9.910578 us, ub 11.57951 us, ci 0.950
std dev: 1.231445 us, lb 408.3389 ns, ub 2.033791 us, ci 0.950
found 1 outliers among 10 samples (10.0%)
  1 (10.0%) high severe
variance introduced by outliers: 9.889%
variance is slightly inflated by outliers
maeder at leibniz:~/haskell/examples> ghc --make -fforce-recomp -O2 Bench.hs
[1 of 1] Compiling Main             ( Bench.hs, Bench.o )
Linking Bench ...
maeder at leibniz:~/haskell/examples> ./Bench -s 10
100000000
warming up
estimating clock resolution...
mean is 17.19073 us (40001 iterations)
found 1624 outliers among 39999 samples (4.1%)
  568 (1.4%) high mild
  1056 (2.6%) high severe
estimating cost of a clock call...
mean is 1.372403 us (62 iterations)
found 3 outliers among 62 samples (4.8%)
  3 (4.8%) high mild

benchmarking prepend
200000000
collecting 10 samples, 1 iterations each, in estimated 21.06879 s
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
bootstrapping with 100000 resamples
mean: 2.037685 s, lb 2.035850 s, ub 2.039932 s, ci 0.950
std dev: 3.441953 ms, lb 2.379356 ms, ub 4.579715 ms, ci 0.950
variance introduced by outliers: 9.000%
variance is slightly inflated by outliers

benchmarking prependToAll
200000000
collecting 10 samples, 1 iterations each, in estimated 21.60974 s
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
200000000
bootstrapping with 100000 resamples
mean: 2.149744 s, lb 2.132435 s, ub 2.170067 s, ci 0.950
std dev: 31.60195 ms, lb 27.30131 ms, ub 37.08768 ms, ci 0.950
variance introduced by outliers: 9.000%
variance is slightly inflated by outliers