about summary refs log tree commit diff
path: root/src/liballoc/collections/btree
AgeCommit message (Collapse)AuthorLines
2020-05-06Rollup merge of #71510 - ssomers:btreemap_iter_intertwined, r=Mark-SimulacrumDylan DPC-29/+47
Btreemap iter intertwined 3 commits: 1. Introduced benchmarks for `BTreeMap::iter()`. Benchmarks named `iter_20` were of the whole iteration process, so I renamed them. Also the benchmarks of `range` that I wrote earlier weren't very good. I included an (awkwardly named) one that compares `iter()` to `range(..)` on the same set, because the contrast is surprising: ``` name ns/iter btree::map::range_unbounded_unbounded 28,176 btree::map::range_unbounded_vs_iter 89,369 ``` Both dig up the same pair of leaf edges. `range(..)` also checks that some keys are correctly ordered, the only thing `iter()` does more is to copy the map's length. 2. Slightly refactoring the code to what I find more readable (not in chronological order of discovery), boosts performance: ``` >cargo-benchcmp.exe benchcmp a1 a2 --threshold 5 name a1 ns/iter a2 ns/iter diff ns/iter diff % speedup btree::map::find_rand_100 18 17 -1 -5.56% x 1.06 btree::map::first_and_last_10k 64 71 7 10.94% x 0.90 btree::map::iter_0 2,939 2,209 -730 -24.84% x 1.33 btree::map::iter_1 6,845 2,696 -4,149 -60.61% x 2.54 btree::map::iter_100 8,556 3,672 -4,884 -57.08% x 2.33 btree::map::iter_10k 9,292 5,884 -3,408 -36.68% x 1.58 btree::map::iter_1m 10,268 6,510 -3,758 -36.60% x 1.58 btree::map::iteration_mut_100000 478,575 453,050 -25,525 -5.33% x 1.06 btree::map::range_unbounded_unbounded 28,176 36,169 7,993 28.37% x 0.78 btree::map::range_unbounded_vs_iter 89,369 38,290 -51,079 -57.16% x 2.33 btree::set::clone_100_and_remove_all 4,801 4,245 -556 -11.58% x 1.13 btree::set::clone_10k_and_remove_all 529,450 496,030 -33,420 -6.31% x 1.07 ``` But you can tell from the `range_unbounded_*` lines that, despite an unwarranted, vengeful attack on the range_unbounded_unbounded benchmark, this change still doesn't allow `iter()` to catch up with `range(..)`. 3. I guess that `range(..)` copes so well because it intertwines the leftmost and rightmost descend towards leaf edges, doing the two root node accesses close together, perhaps exploiting a CPU's internal pipelining? So the third commit distils a version of `range_search` (which we can't use directly because of the `Ord` bound), and we get another boost: ``` cargo-benchcmp.exe benchcmp a2 a3 --threshold 5 name a2 ns/iter a3 ns/iter diff ns/iter diff % speedup btree::map::first_and_last_100 40 43 3 7.50% x 0.93 btree::map::first_and_last_10k 71 64 -7 -9.86% x 1.11 btree::map::iter_0 2,209 1,719 -490 -22.18% x 1.29 btree::map::iter_1 2,696 2,205 -491 -18.21% x 1.22 btree::map::iter_100 3,672 2,943 -729 -19.85% x 1.25 btree::map::iter_10k 5,884 3,929 -1,955 -33.23% x 1.50 btree::map::iter_1m 6,510 5,532 -978 -15.02% x 1.18 btree::map::iteration_mut_100000 453,050 476,667 23,617 5.21% x 0.95 btree::map::range_included_excluded 405,075 371,297 -33,778 -8.34% x 1.09 btree::map::range_included_included 427,577 397,440 -30,137 -7.05% x 1.08 btree::map::range_unbounded_unbounded 36,169 28,175 -7,994 -22.10% x 1.28 btree::map::range_unbounded_vs_iter 38,290 30,838 -7,452 -19.46% x 1.24 ``` But I think this is just fake news from the microbenchmarking media. `iter()` is still trying to catch up with `range(..)`. And we can sure do without another function. So I would skip this 3rd commit. r? @Mark-Simulacrum
2020-05-04Update btree_map::VacantEntry::insert docs to actually call insertCarol (Nichols || Goulding)-6/+5
It looks like they were copied from the `or_insert` docs. This change makes the example more like the hash_map::VacantEntry::insert docs.
2020-04-27Rollup merge of #71589 - RalfJung:unique-no-shr, r=SimonSapinDylan DPC-1/+1
remove Unique::from for shared pointer types r? @SimonSapin
2020-04-26remove Unique::from for shared pointer typesRalf Jung-1/+1
2020-04-26Fix stable(since) attribute for BTreeMap::remove_entryJonas Platte-1/+1
2020-04-25Rollup merge of #70712 - :stabilize-remove-entry, r=AmanieuDylan DPC-2/+1
stabilize BTreeMap::remove_entry This PR stabilizes `BTreeMap::remove_entry` as implemented in https://github.com/rust-lang/rust/pull/68378. Closes https://github.com/rust-lang/rust/issues/66714
2020-04-25Speed up BTreeMap iteration by intertwined descend to the initial leaf edgesStein Somers-29/+47
2020-04-24Take a single root node in range_searchMark Rousskov-10/+7
The unsafe code can be justified within range_search, as it makes sure to not overlap the returned references, but from the callers perspective it's an entirely safe algorithm and there's no need for the caller to know about the duplication.
2020-04-17Rollup merge of #71167 - RalfJung:big-o, r=shepmasterDylan DPC-1/+1
big-O notation: parenthesis for function calls, explicit multiplication I saw `O(n m log n)` in the docs and found that really hard to parse. In particular, I don't think we should use blank space as syntax for *both* multiplication and function calls, that is just confusing. This PR makes both multiplication and function calls explicit using Rust-like syntax. If you prefer, I can also leave one of them implicit, but I believe explicit is better here. While I was at it I also added backticks consistently.
2020-04-16Dogfood or_patterns in the standard libraryJosh Stone-6/+1
2020-04-15don't specify log base in big-ORalf Jung-1/+1
2020-04-15big-O notation: parenthesis, multiplication and backticksRalf Jung-1/+1
2020-04-11Rollup merge of #70996 - ChaiTRex:master, r=AmanieuDylan DPC-0/+28
Add or_insert_with_key to Entry of HashMap/BTreeMap Going along with `or_insert_with`, `or_insert_with_key` provides the `Entry`'s key to the lambda, avoiding the need to either clone the key or the need to reimplement this body of this method from scratch each time. This is useful when the initial value for a map entry is derived from the key. For example, the introductory Rust book has an example Cacher struct that takes an expensive-to-compute lambda and then can, given an argument to the lambda, produce either the cached result or execute the lambda. --- I'm fairly new to Rust, so any optimizations, corrections to types, better names, better documentation, or whatever else would be appreciated. I'd like to thank Arnavion on freenode for helping me to implement a very similar method when I found that `or_insert_with_key` was unavailable. As a somewhat-related note, this implements https://github.com/rust-lang/rfcs/issues/1202 from 2015, so if this pull request is accepted, that should be closed.
2020-04-11Change issue number to point to tracking issueChai T. Rex-1/+1
2020-04-10Fixed doc tests for added methodsChai T. Rex-0/+1
2020-04-10Add or_insert_with_key to Entry of HashMap/BTreeMapChai T. Rex-0/+27
Going along with or_insert_with, or_insert_with_key provides the Entry's key to the lambda, avoiding the need to either clone the key or the need to reimplement this body of this method from scratch each time. This is useful when the initial value for a map entry is derived from the key. For example, the introductory Rust book has an example Cacher struct that takes an expensive-to-compute lambda and then can, given an argument to the lambda, produce either the cached result or execute the lambda.
2020-04-10Rollup merge of #70981 - ssomers:btreemap_into_into_iter, r=Mark-SimulacrumMazdak Farrokhzad-13/+13
Rearrange BTreeMap::into_iter to match range_mut. r? @Mark-Simulacrum I wondered why you catered for the optional root differently in `into_iter` than in `range_mut`.
2020-04-10Rollup merge of #70979 - ssomers:btreemap_the_alice_merton_variations, r=AmanieuMazdak Farrokhzad-4/+2
Follow up on BTreeMap comments r? @Amanieu (for the first commit)
2020-04-10Rollup merge of #70843 - ssomers:btree_drain_filter_epilogue, r=AmanieuMazdak Farrokhzad-45/+21
Remove the Ord bound that was plaguing drain_filter Now that #70795 made it superfluous. Also removes superfluous lifetime specifiers (at least I think they are).
2020-04-10Rearrange BTreeMap::into_iter to match range_mut.Stein Somers-13/+13
2020-04-09Respect the comment: no root unless the borrow type is `Mut`Stein Somers-2/+2
2020-04-09Kill comment left behind by a last minute change in #70795Stein Somers-2/+0
2020-04-06BTreeMap first/last: add pop methodsStein Somers-0/+48
2020-04-06BTreeMap first/last: make examples more to the pointStein Somers-10/+12
2020-04-06BTreeMap first/last: simplify implementationsStein Somers-38/+16
2020-04-06Remove the Ord bound that was plaguing drain_filter, and superfluous lifetimesStein Somers-45/+21
2020-04-05Rollup merge of #70795 - Amanieu:btree_remove_tracking, r=Mark-SimulacrumDylan DPC-49/+64
Keep track of position when deleting from a BTreeMap This improves the performance of drain_filter and is needed for future Cursor support for BTreeMap. cc @ssomers r? @Mark-Simulacrum
2020-04-05Apply review feedbackAmanieu d'Antras-15/+10
2020-04-05Keep track of position when deleting from a BTreeMapAmanieu d'Antras-39/+59
This improves the performance of drain_filter and is needed for future Cursor support for BTreeMap.
2020-04-04use ManuallyDrop instead of forget inside collectionsTrevor Spiteri-8/+8
This commit changes some usage of mem::forget into mem::ManuallyDrop in some Vec, VecDeque, BTreeMap and Box methods. Before the commit, the generated IR for some of the methods was longer, and even after optimization, some unwinding artifacts were still present.
2020-04-02stabilize BTreeMap::remove_entryDutchGhost-2/+1
2020-04-02Auto merge of #70362 - TimDiekmann:alloc-overhaul, r=Amanieubors-4/+5
Overhaul of the `AllocRef` trait to match allocator-wg's latest consens; Take 2 GitHub won't let me reopen #69889 so I make a new PR. In addition to #69889 this fixes the unsoundness of `RawVec::into_box` when using allocators supporting overallocating. Also it uses `MemoryBlock` in `AllocRef` to unify `_in_place` methods by passing `&mut MemoryBlock`. Additionally, `RawVec` now checks for `size_of::<T>()` again and ignore every ZST. The internal capacity of `RawVec` isn't used by ZSTs anymore, as `into_box` now requires a length to be specified. r? @Amanieu fixes rust-lang/wg-allocators#38 fixes rust-lang/wg-allocators#41 fixes rust-lang/wg-allocators#44 fixes rust-lang/wg-allocators#51
2020-03-29BTreeMap/BTreeSet: implement and test drain_filterStein Somers-13/+298
2020-03-26Remove alignment from `MemoryBlock`Tim Diekmann-8/+4
2020-03-26Fix issues from review and unsoundness of `RawVec::into_box`Tim Diekmann-7/+12
2020-03-22remove redundant closures (clippy::redundant_closure)Matthias Krüger-2/+2
2020-03-20Simplify ensure_root_is_owned callersMark Rousskov-15/+13
This makes ensure_root_is_owned return a reference to the (now guaranteed to exist) root, allowing callers to operate on it without going through another unwrap. Unfortunately this is only rarely useful as it's frequently the case that both the length and the root need to be accessed and field-level borrows in methods don't yet exist.
2020-03-20Drop NodeHeader type from BTree codeMark Rousskov-41/+5
We no longer have a separate header because the shared root is gone; all code can work solely with leafs now.
2020-03-20Make functions dependent only on shared root avoidance safeMark Rousskov-58/+58
2020-03-20Remove shared root code and assertions from BTree nodesMark Rousskov-59/+8
2020-03-20Replace shared root with optional rootMark Rousskov-77/+112
This simplifies the node manipulation, as we can (in later commits) always know when traversing nodes that we are not in a shared root.
2020-03-08Rollup merge of #69668 - ssomers:btreemap_even_more_comments, r=Mark-SimulacrumMazdak Farrokhzad-14/+19
More documentation and simplification of BTreeMap's internals Salvage the documentation and simplification from #67980, without changing the type locked down by debuginfo. r? @rkruppe
2020-03-08Rollup merge of #69776 - ssomers:fix69769, r=Mark-SimulacrumMazdak Farrokhzad-1/+10
Fix & test leak of some BTreeMap nodes on panic during `into_iter` Fixes #69769
2020-03-06fix various typosMatthias Krüger-1/+1
2020-03-06Fix & test leak of some BTreeMap nodes on panic during `into_iter`Stein Somers-1/+10
2020-03-04Documentation and slight simplification of BTreeMap's internalsStein Somers-14/+19
2020-03-03Simplify conditions like x + 1 <= y to x < yMatthias Krüger-1/+1
2020-02-28Auto merge of #68827 - ssomers:btree_navigation_revisited, r=Mark-Simulacrumbors-150/+148
BTreeMap navigation done safer & faster It turns out that there was a faster way to do the tree navigation code bundled in #67073, by moving from edge to KV and from KV to next edge separately. It extracts most of the code as safe functions, and contains the duplication of handles within the short wrapper functions. This somehow hits a sweet spot in the compiler because it reports boosts all over the board: ``` >cargo benchcmp pre3.txt posz4.txt --threshold 5 name pre3.txt ns/iter posz4.txt ns/iter diff ns/iter diff % speedup btree::map::first_and_last_0 40 37 -3 -7.50% x 1.08 btree::map::first_and_last_100 58 44 -14 -24.14% x 1.32 btree::map::iter_1000 8,920 3,419 -5,501 -61.67% x 2.61 btree::map::iter_100000 1,069,290 411,615 -657,675 -61.51% x 2.60 btree::map::iter_20 169 58 -111 -65.68% x 2.91 btree::map::iter_mut_1000 8,701 3,303 -5,398 -62.04% x 2.63 btree::map::iter_mut_100000 1,034,560 405,975 -628,585 -60.76% x 2.55 btree::map::iter_mut_20 165 58 -107 -64.85% x 2.84 btree::set::clone_100 1,831 1,562 -269 -14.69% x 1.17 btree::set::clone_100_and_clear 1,831 1,565 -266 -14.53% x 1.17 btree::set::clone_100_and_into_iter 1,917 1,541 -376 -19.61% x 1.24 btree::set::clone_100_and_pop_all 2,609 2,441 -168 -6.44% x 1.07 btree::set::clone_100_and_remove_all 4,598 3,927 -671 -14.59% x 1.17 btree::set::clone_100_and_remove_half 2,765 2,551 -214 -7.74% x 1.08 btree::set::clone_10k 191,610 164,616 -26,994 -14.09% x 1.16 btree::set::clone_10k_and_clear 192,003 164,616 -27,387 -14.26% x 1.17 btree::set::clone_10k_and_into_iter 200,037 163,010 -37,027 -18.51% x 1.23 btree::set::clone_10k_and_pop_all 267,023 250,913 -16,110 -6.03% x 1.06 btree::set::clone_10k_and_remove_all 536,230 464,100 -72,130 -13.45% x 1.16 btree::set::clone_10k_and_remove_half 453,350 430,545 -22,805 -5.03% x 1.05 btree::set::difference_random_100_vs_100 1,787 801 -986 -55.18% x 2.23 btree::set::difference_random_100_vs_10k 2,978 2,696 -282 -9.47% x 1.10 btree::set::difference_random_10k_vs_100 111,075 54,734 -56,341 -50.72% x 2.03 btree::set::difference_random_10k_vs_10k 246,380 175,980 -70,400 -28.57% x 1.40 btree::set::difference_staggered_100_vs_100 1,789 951 -838 -46.84% x 1.88 btree::set::difference_staggered_100_vs_10k 2,798 2,606 -192 -6.86% x 1.07 btree::set::difference_staggered_10k_vs_10k 176,452 97,401 -79,051 -44.80% x 1.81 btree::set::intersection_100_neg_vs_10k_pos 34 32 -2 -5.88% x 1.06 btree::set::intersection_100_pos_vs_100_neg 30 27 -3 -10.00% x 1.11 btree::set::intersection_random_100_vs_100 1,537 613 -924 -60.12% x 2.51 btree::set::intersection_random_100_vs_10k 2,793 2,649 -144 -5.16% x 1.05 btree::set::intersection_random_10k_vs_10k 222,127 147,166 -74,961 -33.75% x 1.51 btree::set::intersection_staggered_100_vs_100 1,447 622 -825 -57.01% x 2.33 btree::set::intersection_staggered_100_vs_10k 2,606 2,382 -224 -8.60% x 1.09 btree::set::intersection_staggered_10k_vs_10k 143,620 58,790 -84,830 -59.07% x 2.44 btree::set::is_subset_100_vs_100 1,349 488 -861 -63.83% x 2.76 btree::set::is_subset_100_vs_10k 1,720 1,428 -292 -16.98% x 1.20 btree::set::is_subset_10k_vs_10k 135,984 48,527 -87,457 -64.31% x 2.80 ``` The `first_and_last` ones are noise (they don't do iteration), the others seem genuine. As always, approved by Miri. Also, a separate commit with some more benchmarks of mutable behaviour (which also benefit). r? @cuviper
2020-02-28Make implementation of navigation simpler, safer and fasterStein Somers-150/+148
2020-02-28Fix and test implementation of BTreeMap's first_entry, last_entry, ↵Stein Somers-10/+14
pop_first, pop_last
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-26 12:42:42 +0000