]> git.lizzy.rs Git - rust.git/commit
Auto merge of #75105 - ssomers:btree_respect_min_len_hard, r=Mark-Simulacrum
authorbors <bors@rust-lang.org>
Thu, 13 Aug 2020 21:36:02 +0000 (21:36 +0000)
committerbors <bors@rust-lang.org>
Thu, 13 Aug 2020 21:36:02 +0000 (21:36 +0000)
commit81dc88f88f92ba8ad7465f9cba10c12d3a7b70f1
treea9ef432b92933100f46efe74c1f07900582ada9f
parent5e3f1b148db5bfa27fee52464ae1f5d34c49d77b
parent17ab457f21700caad62c3f3fcfeff48f21d2393b
Auto merge of #75105 - ssomers:btree_respect_min_len_hard, r=Mark-Simulacrum

Hard way to respect BTreeMap's minimum node length

Resolves #74834 the hard way (though not the hardest imaginable).

Benchmarks (which are all biased/realistic, inserting keys in ascending order) say:
```
benchcmp r0 r1 --threshold 10
 name                                        r0 ns/iter  r1 ns/iter  diff ns/iter   diff %  speedup
 btree::map::clone_slim_100_and_clear        2,183       2,723                540   24.74%   x 0.80
 btree::map::clone_slim_100_and_drain_all    3,652       4,173                521   14.27%   x 0.88
 btree::map::clone_slim_100_and_drain_half   3,320       3,940                620   18.67%   x 0.84
 btree::map::clone_slim_100_and_into_iter    2,154       2,717                563   26.14%   x 0.79
 btree::map::clone_slim_100_and_pop_all      3,372       3,870                498   14.77%   x 0.87
 btree::map::clone_slim_100_and_remove_all   5,111       5,647                536   10.49%   x 0.91
 btree::map::clone_slim_100_and_remove_half  3,259       3,821                562   17.24%   x 0.85
 btree::map::iter_0                          1,733       1,509               -224  -12.93%   x 1.15
 btree::map::iter_100                        2,714       3,739              1,025   37.77%   x 0.73
 btree::map::iter_10k                        3,728       4,269                541   14.51%   x 0.87
 btree::map::range_unbounded_unbounded       28,426      36,631             8,205   28.86%   x 0.78
 btree::map::range_unbounded_vs_iter         28,808      34,056             5,248   18.22%   x 0.85
```
This difference is not caused by the `debug_assert`-related code in the function `splitpoint`, it's the same without.