Efficent lens operation for Data.Map et al.

[Roman Cheplyaka]

* roconnor at theorem.ca <roconnor at theorem.ca> [2012-01-18 16:35:52-0500]
> On Wed, 18 Jan 2012, Johan Tibell wrote:
> 
> >IIRC you just replace the current functions with yours and run make in
> >the benchmarks/ directory to compile the benchmark binaries (which use
> >Criterion). Then simply run them.
> 
> I got an error trying to build the benchmarks:

Worked for me with GHC 7.0.4.

The results are attached.

In short, your version is indeed typically slower, up to a factor of 5
(for lookup).

-- 
Roman I. Cheplyaka :: http://ro-che.info/
-------------- next part --------------
warming up
estimating clock resolution...
mean is 12.07426 us (80001 iterations)
found 33433 outliers among 79999 samples (41.8%)
  19370 (24.2%) low severe
  14063 (17.6%) high severe
estimating cost of a clock call...
mean is 142.0234 ns (88 iterations)
found 3 outliers among 88 samples (3.4%)
  3 (3.4%) high mild

benchmarking lookup
mean: 1.416598 ms, lb 1.415843 ms, ub 1.418148 ms, ci 0.950
std dev: 5.322005 us, lb 3.138803 us, ub 10.09858 us, ci 0.950

benchmarking insert
mean: 966.2893 us, lb 965.5557 us, ub 967.8407 us, ci 0.950
std dev: 5.217048 us, lb 2.933248 us, ub 9.867330 us, ci 0.950

benchmarking map
mean: 342.3310 us, lb 341.2740 us, ub 343.6296 us, ci 0.950
std dev: 5.978326 us, lb 4.866551 us, ub 9.036037 us, ci 0.950
found 1 outliers among 100 samples (1.0%)
  1 (1.0%) high severe
variance introduced by outliers: 10.380%
variance is moderately inflated by outliers

benchmarking mapWithKey
mean: 344.4226 us, lb 343.3877 us, ub 345.4086 us, ci 0.950
std dev: 5.142366 us, lb 4.680959 us, ub 5.675438 us, ci 0.950
variance introduced by outliers: 7.551%
variance is slightly inflated by outliers

benchmarking foldlWithKey
mean: 2.490770 ms, lb 2.487691 ms, ub 2.497595 ms, ci 0.950
std dev: 22.42300 us, lb 12.60156 us, ub 44.34108 us, ci 0.950

benchmarking delete
mean: 1.194906 ms, lb 1.189457 ms, ub 1.214295 ms, ci 0.950
std dev: 47.07701 us, lb 12.26002 us, ub 107.6022 us, ci 0.950
found 7 outliers among 100 samples (7.0%)
  6 (6.0%) high severe
variance introduced by outliers: 36.546%
variance is moderately inflated by outliers

benchmarking update
mean: 2.445310 ms, lb 2.443551 ms, ub 2.448788 ms, ci 0.950
std dev: 12.16175 us, lb 7.567424 us, ub 22.37774 us, ci 0.950

benchmarking updateLookupWithKey
mean: 2.691886 ms, lb 2.685137 ms, ub 2.717787 ms, ci 0.950
std dev: 60.47195 us, lb 13.17799 us, ub 141.0781 us, ci 0.950
found 5 outliers among 100 samples (5.0%)
  3 (3.0%) high mild
  2 (2.0%) high severe
variance introduced by outliers: 16.105%
variance is moderately inflated by outliers

benchmarking alter
mean: 2.447551 ms, lb 2.445249 ms, ub 2.451752 ms, ci 0.950
std dev: 15.45131 us, lb 8.907326 us, ub 24.89683 us, ci 0.950

benchmarking mapMaybe
mean: 315.7964 us, lb 314.9744 us, ub 316.6161 us, ci 0.950
std dev: 4.199592 us, lb 3.732571 us, ub 4.781435 us, ci 0.950
variance introduced by outliers: 6.567%
variance is slightly inflated by outliers
-------------- next part --------------
warming up
estimating clock resolution...
mean is 11.93087 us (80001 iterations)
found 1730 outliers among 79999 samples (2.2%)
  1373 (1.7%) high severe
estimating cost of a clock call...
mean is 141.3864 ns (89 iterations)
found 14 outliers among 89 samples (15.7%)
  12 (13.5%) high mild
  2 (2.2%) high severe

benchmarking lookup
mean: 267.4041 us, lb 267.2755 us, ub 267.6014 us, ci 0.950
std dev: 806.6436 ns, lb 606.4914 ns, ub 1.234920 us, ci 0.950

benchmarking insert
mean: 596.6775 us, lb 591.6880 us, ub 602.0942 us, ci 0.950
std dev: 26.54710 us, lb 23.32294 us, ub 31.43878 us, ci 0.950
found 1 outliers among 100 samples (1.0%)
variance introduced by outliers: 42.472%
variance is moderately inflated by outliers

benchmarking map
mean: 349.9705 us, lb 348.9970 us, ub 351.0159 us, ci 0.950
std dev: 5.161718 us, lb 4.564701 us, ub 6.041488 us, ci 0.950
found 1 outliers among 100 samples (1.0%)
variance introduced by outliers: 7.540%
variance is slightly inflated by outliers

benchmarking mapWithKey
mean: 340.4314 us, lb 339.4232 us, ub 341.4504 us, ci 0.950
std dev: 5.177331 us, lb 4.725543 us, ub 5.882216 us, ci 0.950
variance introduced by outliers: 8.453%
variance is slightly inflated by outliers

benchmarking foldlWithKey
mean: 1.468329 ms, lb 1.459881 ms, ub 1.475352 ms, ci 0.950
std dev: 39.45324 us, lb 33.59771 us, ub 44.96820 us, ci 0.950
found 21 outliers among 100 samples (21.0%)
  17 (17.0%) low severe
  3 (3.0%) low mild
variance introduced by outliers: 20.953%
variance is moderately inflated by outliers

benchmarking delete
mean: 476.7795 us, lb 476.4021 us, ub 477.5763 us, ci 0.950
std dev: 2.680520 us, lb 1.564961 us, ub 5.005106 us, ci 0.950

benchmarking update
mean: 1.590619 ms, lb 1.583124 ms, ub 1.598866 ms, ci 0.950
std dev: 40.38600 us, lb 36.89724 us, ub 43.41719 us, ci 0.950
variance introduced by outliers: 19.030%
variance is moderately inflated by outliers

benchmarking updateLookupWithKey
mean: 2.726739 ms, lb 2.723728 ms, ub 2.730547 ms, ci 0.950
std dev: 17.24291 us, lb 13.97092 us, ub 23.29574 us, ci 0.950

benchmarking alter
mean: 1.601741 ms, lb 1.590689 ms, ub 1.619180 ms, ci 0.950
std dev: 70.26172 us, lb 50.44474 us, ub 110.0122 us, ci 0.950
found 4 outliers among 100 samples (4.0%)
  3 (3.0%) high mild
  1 (1.0%) high severe
variance introduced by outliers: 41.499%
variance is moderately inflated by outliers

benchmarking mapMaybe
mean: 286.6122 us, lb 285.7398 us, ub 287.5180 us, ci 0.950
std dev: 4.536349 us, lb 3.974031 us, ub 5.278899 us, ci 0.950
found 2 outliers among 100 samples (2.0%)
  2 (2.0%) high mild
variance introduced by outliers: 8.495%
variance is slightly inflated by outliers