| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
Remove trait LengthAtMost32
This is a continuation of https://github.com/rust-lang/rust/pull/74026 preserving the original burrbull's commit.
I talked to @burrbull, he suggested me to finish his PR.
|
|
Remove needless unsafety from BTreeMap::drain_filter
Remove one piece of unsafe code in the iteration over the iterator returned by BTreeMap::drain_filter.
- Changes an explicitly unspecified part of the API: when the user-supplied predicate (or some of BTreeMap's code) panicked, and the caller tries to use the iterator again, we no longer offer the same key/value pair to the predicate again but pretend the iterator has finished. Note that Miri does not find UB in the test case added here with the unsafe code (or without).
- Makes the code a little easier on the eyes.
- Makes the code a little harder on the CPU:
```
benchcmp c0 c2 --threshold 3
name c0 ns/iter c2 ns/iter diff ns/iter diff % speedup
btree::set::clone_100_and_drain_all 2,794 2,900 106 3.79% x 0.96
btree::set::clone_100_and_drain_half 2,604 2,964 360 13.82% x 0.88
btree::set::clone_10k_and_drain_half 287,770 322,755 34,985 12.16% x 0.89
```
r? @Amanieu
|
|
|
|
Use italics for O notation
In documentation, I think it makes sense to italicize O notation (*O(n)*) as opposed to using back-ticks (`O(n)`). Visually, back-ticks focus the reader on the literal characters being used, making them ideal for representing code. Using italics, as far I can tell, more closely follows typographic conventions in mathematics and computer science.
Just a suggestion, of course! 😇
|
|
Co-authored-by: Guillaume Gomez <guillaume1.gomez@gmail.com>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This patch adds `VecDeque::range` and `VecDeque::range_mut` to provide
iterators over a sub-range of a `VecDeque`. This behavior can be
emulated with `skip` and `take`, but directly providing a `Range` is
more ergonomic. This also partially makes up for `VecDeque`'s lack of
`SliceIndex` support.
|
|
|
|
|
|
Update BTreeMap::new() doc
Updates the documentation according to [this comment](https://github.com/rust-lang/rust/pull/72876/files/0c5c644c91edf6ed949cfa5ffc524f43369df604#r433232581) on #72876
|
|
Remove unused crate imports in 2018 edition crates
Closes #73570
|
|
Mention that BTreeMap::new() doesn't allocate
I think it would be nice to mention this, so you don't have to dig through the src to look at the definition of new().
|
|
|
|
|
|
|
|
I think it would be nice to mention this, so you don't have to dig through the src to look at the definition of new().
|
|
This adds new optional methods on `Extend`: `extend_one` add a single
element to the collection, and `extend_reserve` pre-allocates space for
the predicted number of incoming elements. These are used in `Iterator`
for `partition` and `unzip` as they shuffle elements one-at-a-time into
their respective collections.
|
|
Use min_specialization in liballoc
- Remove a type parameter from `[A]RcFromIter`.
- Remove an implementation of `[A]RcFromIter` that didn't actually
specialize anything.
- Remove unused implementation of `IsZero` for `Option<&mut T>`.
- Change specializations of `[A]RcEqIdent` to use a marker trait version
of `Eq`.
- Remove `BTreeClone`. I couldn't find a way to make this work with
`min_specialization`.
- Add `rustc_unsafe_specialization_marker` to `Copy` and `TrustedLen`.
After this only libcore is the only standard library crate using `feature(specialization)`.
cc #31844
|
|
r=Amanieu
Make `RawVec::grow` mostly non-generic.
`cargo-llvm-lines` shows that, in various benchmarks, `RawVec::grow` is
instantiated 10s or 100s of times and accounts for 1-8% of lines of
generated LLVM IR.
This commit moves most of `RawVec::grow` into a separate function that
isn't parameterized by `T`, which means it doesn't need to be
instantiated many times. This reduces compile time significantly.
r? @ghost
|
|
Miri: run liballoc tests with threads
Miri now supports threads, so we can run these tests. :)
|
|
It's only used once, for `VecDeque`, and can easily be replaced by
something else. The commit changes `grow_if_necessary` to `grow` to
avoid some small regressions caused by changed inlining.
The commit also removes `Strategy::Double`, and streamlines the
remaining variants of `Strategy`.
It's a compile time win on some benchmarks because the many
instantations of `RawVec::grow` are a little smaller.
|
|
Make BTreeMap::new and BTreeSet::new const
|
|
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
|
|
r=jonas-schievink
Update btree_map::VacantEntry::insert docs to actually call insert
It looks like they were copied from the `or_insert` docs. This change
makes the example more like the hash_map::VacantEntry::insert docs.
|
|
It looks like they were copied from the `or_insert` docs. This change
makes the example more like the hash_map::VacantEntry::insert docs.
|
|
|
|
The `remove_current` method only returns the inner `T` and deallocates the list node. This is unnecessary for move operations, where the element is going to be linked back into this (or even a different) `LinkedList`. The `remove_current_as_list` method avoids this by returning the unlinked list node as a new single-element `LinkedList` structure .
|
|
|
|
|
|
remove Unique::from for shared pointer types
r? @SimonSapin
|
|
|
|
- Remove a type parameter from `[A]RcFromIter`.
- Remove an implementation of `[A]RcFromIter` that didn't actually
specialize anything.
- Remove unused implementation of `IsZero` for `Option<&mut T>`.
- Change specializations of `[A]RcEqIdent` to use a marker trait version
of `Eq`.
- Remove `BTreeClone`. I couldn't find a way to make this work with
`min_specialization`.
- Add `rustc_unsafe_specialization_marker` to `Copy` and `TrustedLen`.
|
|
Fix stable(since) attribute for BTreeMap::remove_entry
Stabilized in #70712.
Maybe checking that the since attributes are added correctly should be automated through tidy? This is the third PR I'm opening that fixes a stable(since) attribute for something meant to be stabilized in 1.43 / 1.44 initially but then only stabilized in 1.45. (the other two are #71571, #71574)
|
|
|
|
clippy::{redundant_pattern_matching, clone_on_copy, iter_cloned_collect, option_as_ref_deref, match_ref_pats}
|
|
Add missing Send and Sync impls for linked list Cursor and CursorMut.
Someone pointed out these to me, and i think it's indeed reasonable to add those impl.
r? @Amanieu
|
|
Deprecate `{Box,Rc,Arc}::into_raw_non_null`
Per ongoing FCP at https://github.com/rust-lang/rust/issues/47336#issuecomment-586589016
See also https://github.com/rust-lang/rust/issues/47336#issuecomment-614054164
|
|
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
|
|
Co-Authored-By: Amanieu d'Antras <amanieu@gmail.com>
|
|
Take a single root node in range_search
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.
cc @ssomers
r? @Amanieu
|
|
|
|
Add BinaryHeap::retain as suggested in #42849
This PR implements retain for BinaryHeap as suggested in #42849.
This is my first PR for Rust, so please let me know if I should be doing anything differently, thanks!
|
