about summary refs log tree commit diff
path: root/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp
diff options
context:
space:
mode:
authorbors <bors@rust-lang.org>2021-09-07 02:24:11 +0000
committerbors <bors@rust-lang.org>2021-09-07 02:24:11 +0000
commitffaf857045f4f4d8bb563e0a5077f9b065f42916 (patch)
treec4ddda3dc84bfd079a01e805fe3b865a04698cab /compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp
parent11bbb5231349a0a144d86d5c0c21061a06d1969d (diff)
parenta03287bbf765ce7ac0e2ae9e64d8ade168ece301 (diff)
downloadrust-ffaf857045f4f4d8bb563e0a5077f9b065f42916.tar.gz
rust-ffaf857045f4f4d8bb563e0a5077f9b065f42916.zip
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)
```
Diffstat (limited to 'compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp')
0 files changed, 0 insertions, 0 deletions