]> git.lizzy.rs Git - rust.git/commit - src/tools/miri
Auto merge of #88448 - xu-cheng:btree-blk-build, r=Mark-Simulacrum
authorbors <bors@rust-lang.org>
Tue, 7 Sep 2021 02:24:11 +0000 (02:24 +0000)
committerbors <bors@rust-lang.org>
Tue, 7 Sep 2021 02:24:11 +0000 (02:24 +0000)
commitffaf857045f4f4d8bb563e0a5077f9b065f42916
treec4ddda3dc84bfd079a01e805fe3b865a04698cab
parent11bbb5231349a0a144d86d5c0c21061a06d1969d
parenta03287bbf765ce7ac0e2ae9e64d8ade168ece301
Auto merge of #88448 - xu-cheng:btree-blk-build, r=Mark-Simulacrum

BTreeMap/BTreeSet::from_iter: use bulk building to improve the performance

Bulk building is a common technique to increase the performance of building a fresh btree map. Instead of inserting items one-by-one, we sort all the items beforehand then create the BtreeMap in bulk.

Benchmark
```
./x.py bench library/alloc --test-args btree::map::from_iter
```

* Before
```
test btree::map::from_iter_rand_100                      ... bench:       3,694 ns/iter (+/- 840)
test btree::map::from_iter_rand_10_000                   ... bench:   1,033,446 ns/iter (+/- 192,950)
test btree::map::from_iter_seq_100                       ... bench:       5,689 ns/iter (+/- 1,259)
test btree::map::from_iter_seq_10_000                    ... bench:     861,033 ns/iter (+/- 118,815)
```

* After
```
test btree::map::from_iter_rand_100                      ... bench:       3,033 ns/iter (+/- 707)
test btree::map::from_iter_rand_10_000                   ... bench:     775,958 ns/iter (+/- 105,152)
test btree::map::from_iter_seq_100                       ... bench:       2,969 ns/iter (+/- 336)
test btree::map::from_iter_seq_10_000                    ... bench:     258,292 ns/iter (+/- 29,364)
```
library/alloc/src/collections/btree/map.rs
library/alloc/src/collections/btree/set.rs