Graph.Tree vs Graph.PatriciaTree

[Thomas Bereknyei]

After trying to install criterion for hours, i finally got it to work:

Criterion result:

warming up
estimating clock resolution...
mean is 44.18596 us (20001 iterations)
found 1333 outliers among 19999 samples (6.7%)
  1221 (6.1%) high severe
estimating cost of a clock call...
mean is 2.035546 us (25 iterations)
found 5 outliers among 25 samples (20.0%)
  1 (4.0%) high mild
  4 (16.0%) high severe

benchmarking nn/with Patricia Tree
collecting 100 samples, 1 iterations each, in estimated 13.04941 s
bootstrapping with 100000 resamples
mean: 137.3505 ms, lb 128.3973 ms, ub 165.4278 ms, ci 0.950
std dev: 73.17724 ms, lb 20.02270 ms, ub 160.0066 ms, ci 0.950
found 8 outliers among 100 samples (8.0%)
  5 (5.0%) high mild
  3 (3.0%) high severe
variance introduced by outliers: 4.000%
variance is slightly inflated by outliers

benchmarking nn/with Tree
collecting 100 samples, 1 iterations each, in estimated 52.40080 s
bootstrapping with 100000 resamples
mean: 253.7902 ms, lb 244.2605 ms, ub 266.0068 ms, ci 0.950
std dev: 55.37706 ms, lb 45.28436 ms, ub 69.20759 ms, ci 0.950
found 5 outliers among 100 samples (5.0%)
  4 (4.0%) high mild
  1 (1.0%) high severe
variance introduced by outliers: 2.000%
variance is slightly inflated by outliers

The numbers pretty much tell the same story that doing it by hand did
(I reduced the iterations from 10,000 to 1000).  All of this was done
with just the O2 flag, not the -H256m)

-Thomas