Skip to content

Collapse branches containing only leaves #47

Closed
tibbe opened this Issue Oct 10, 2012 · 3 comments

2 participants

@tibbe
Owner
tibbe commented Oct 10, 2012

In e.g. delete remove a BitmapIndexed or Full node if it has size one and its only element is a Leaf or Collisions.

@michalt michalt added a commit to michalt/unordered-containers that referenced this issue Oct 18, 2012
@michalt michalt Collapse BitmapIndexed with one Leaf/Collision child (issue #47) af3dc99
@michalt michalt added a commit to michalt/unordered-containers that referenced this issue Oct 18, 2012
@michalt michalt Collapse branches with one Leaf/Collision child (issue #47) ae8fb73
@michalt michalt added a commit to michalt/unordered-containers that referenced this issue Oct 18, 2012
@michalt michalt Collapse nodes with one Leaf/Collision child (issue #47) ac6c6d6
@tibbe
Owner
tibbe commented Oct 18, 2012

Things actually get a bit faster with this patch!

Before:

benchmarking HashMap/delete/Int
mean: 1.661201 ms, lb 1.505994 ms, ub 1.905580 ms, ci 0.950
std dev: 978.6935 us, lb 688.4066 us, ub 1.346056 ms, ci 0.950
found 16 outliers among 100 samples (16.0%)
  15 (15.0%) high severe
variance introduced by outliers: 98.956%
variance is severely inflated by outliers

benchmarking HashMap/filterWithKey
mean: 165.4743 us, lb 153.4823 us, ub 189.6089 us, ci 0.950
std dev: 84.31756 us, lb 49.62413 us, ub 140.8524 us, ci 0.950
found 17 outliers among 100 samples (17.0%)
  6 (6.0%) high mild
  11 (11.0%) high severe
variance introduced by outliers: 98.941%
variance is severely inflated by outliers

After:

benchmarking HashMap/delete/Int
mean: 1.084834 ms, lb 1.075059 ms, ub 1.109935 ms, ci 0.950
std dev: 75.45808 us, lb 35.29258 us, ub 156.8446 us, 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: 64.593%
variance is severely inflated by outliers

benchmarking HashMap/filterWithKey
mean: 140.3548 us, lb 139.7206 us, ub 140.9828 us, ci 0.950
std dev: 3.239092 us, lb 2.981030 us, ub 3.550451 us, ci 0.950
variance introduced by outliers: 16.152%
variance is moderately inflated by outliers
@tibbe
Owner
tibbe commented Oct 18, 2012

Fixed by ac6c6d6.

@tibbe tibbe closed this Oct 18, 2012
@michalt
michalt commented Oct 19, 2012

Great! :D I didn't really expect measurable performance changes.

Btw thanks for help and discussions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.