| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
|
|
|
|
`Float` still needs to be public for libcore unit tests.
|
|
|
|
Fixes #45803
|
|
|
|
|
|
Bonus: might make code than uses `.len()` on slice iterators faster
|
|
Stabilize std::ops::RangeInclusive and std::ops::RangeInclusiveTo.
|
|
Stabilize FusedIterator
FusedIterator is a marker trait that promises that the implementing
iterator continues to return `None` from `.next()` once it has returned
`None` once (and/or `.next_back()`, if implemented).
The effects of FusedIterator are already widely available through
`.fuse()`, but with stable `FusedIterator`, stable Rust users can
implement this trait for their iterators when appropriate.
Closes #35602
|
|
Backport LLVM fixes for a JumpThreading / assume intrinsic bug
This fixes the original cause of #48116 and restores the assume intrinsic that was removed as a workaround.
r? @alexcrichton
|
|
|
|
FusedIterator is a marker trait that promises that the implementing
iterator continues to return `None` from `.next()` once it has returned
`None` once (and/or `.next_back()`, if implemented).
The effects of FusedIterator are already widely available through
`.fuse()`, but with stable `FusedIterator`, stable Rust users can
implement this trait for their iterators when appropriate.
|
|
|
|
https://github.com/rust-lang/rust/issues/41891
|
|
Removed the `assume()` which we assumed is the cause of misoptimization in
issue #48116.
|
|
Use the slice length to hint the optimizer about iter.position result
Using the len of the iterator doesn't give the same result.
That's also why we can't generalize it to all TrustedLen iterators.
Problem demo: https://godbolt.org/g/MXg2ae
Fix demo: https://godbolt.org/g/P8q5aZ
Second attempt of #47333
Third attempt of #45501
Fixes #45964
|
|
Using the len of the iterator doesn't give the same result.
That's also why we can't generalize it to all TrustedLen iterators.
|
|
Standardize on "re-export" rather than "reexport"
While working on the book with our editors, it was brought to our attention that we're not consistent with when we use "re-export" versus "reexport". For the book, we've decided (with our editors) to go with "re-export"; in prose, I think that looks better. In code, I'm fine with "reexport".
However, the rustdoc generated section is currently "Reexports", so when we have a screenshot of generated documentation with the prose where we use "re-export", it's inconsistent.
It's too late to fix this for the book because we're using 1.21.0 for the output in the book, and it's really only one spot so it's not a huge deal, but I'd like to advocate for changing the documentation header so that a future edition of the book can be consistent.
The first commit here only changes the documentation section heading text and rustdoc documentation that references it. This is the commit that's most important to me.
The second commit changes error messages and associated tests to also be consistent with the use of re-export. This is the next most important commit to me, but I could be argued out of this one because then it won't match code like the `macro_reexports` feature name, which ostensibly should change to `macro_re_exports` to be most consistent but I didn't want to change code.
The last commit changes re-export anywhere else in prose: either in documentation comments or regular comments. This is least important as most of them aren't user-visible. Instances like these will likely sneak back in over time. I'm totally fine dropping this commit if anyone wants, but [the hobgoblins made me do it](http://www.bartleby.com/100/420.47.html) and it sets a good example.
r? @steveklabnik
|
|
Optimize slice.{r}position result bounds check
Second attempt of https://github.com/rust-lang/rust/pull/45501
Fixes https://github.com/rust-lang/rust/issues/45964
Demo: https://godbolt.org/g/N4mBHp
|
|
|
|
Add slice::ExactChunks and ::ExactChunksMut iterators
These guarantee that always the requested slice size will be returned
and any leftoever elements at the end will be ignored. It allows llvm to
get rid of bounds checks in the code using the iterator.
This is inspired by the same iterators provided by ndarray.
Fixes https://github.com/rust-lang/rust/issues/47115
I'll add unit tests for all this if the general idea and behaviour makes sense for everybody.
Also see https://github.com/rust-lang/rust/issues/47115#issuecomment-354715511 for an example what this improves.
|
|
|
|
|
|
- Simplify nth() by making use of the fact that the slice is evenly
divisible by the chunk size, and calling next() instead of
duplicating it
- Call next_back() in last(), they are equivalent
- Implement ExactSizeIterator::is_empty()
|
|
These guarantee that always the requested slice size will be returned
and any leftoever elements at the end will be ignored. It allows llvm to
get rid of bounds checks in the code using the iterator.
This is inspired by the same iterators provided by ndarray.
See https://github.com/rust-lang/rust/issues/47115
|
|
|
|
Deprecate [T]::rotate in favor of [T]::rotate_{left,right}.
Background
==========
Slices currently have an **unstable** [`rotate`] method which rotates
elements in the slice to the _left_ N positions. [Here][tracking] is the
tracking issue for this unstable feature.
```rust
let mut a = ['a', 'b' ,'c', 'd', 'e', 'f'];
a.rotate(2);
assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
```
Proposal
========
Deprecate the [`rotate`] method and introduce `rotate_left` and
`rotate_right` methods.
```rust
let mut a = ['a', 'b' ,'c', 'd', 'e', 'f'];
a.rotate_left(2);
assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
```
```rust
let mut a = ['a', 'b' ,'c', 'd', 'e', 'f'];
a.rotate_right(2);
assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
```
Justification
=============
I used this method today for my first time and (probably because I’m a
naive westerner who reads LTR) was surprised when the docs mentioned that
elements get rotated in a left-ward direction. I was in a situation
where I needed to shift elements in a right-ward direction and had to
context switch from the main problem I was working on and think how much
to rotate left in order to accomplish the right-ward rotation I needed.
Ruby’s `Array.rotate` shifts left-ward, Python’s `deque.rotate` shifts
right-ward. Both of their implementations allow passing negative numbers
to shift in the opposite direction respectively. The current `rotate`
implementation takes an unsigned integer argument which doesn't allow
the negative number behavior.
Introducing `rotate_left` and `rotate_right` would:
- remove ambiguity about direction (alleviating need to read docs 😉)
- make it easier for people who need to rotate right
[`rotate`]: https://doc.rust-lang.org/std/primitive.slice.html#method.rotate
[tracking]: https://github.com/rust-lang/rust/issues/41891
|
|
|
|
https://github.com/rust-lang/rust/pull/47113 renamed the private size
field to chunk_size for consistency.
|
|
|
|
memchr: fix variable name in docstrings
upstream BurntSushi/rust-memchr#24
r=BurntSushi
|
|
|
|
Previously Chunks used size and ChunksMut used chunk_size
|
|
|
|
Use memchr to speed up [u8]::contains 3x
None
|
|
|
|
Background
==========
Slices currently have an unstable [`rotate`] method which rotates
elements in the slice to the _left_ N positions. [Here][tracking] is the
tracking issue for this unstable feature.
```rust
let mut a = ['a', 'b' ,'c', 'd', 'e', 'f'];
a.rotate(2);
assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
```
Proposal
========
Deprecate the [`rotate`] method and introduce `rotate_left` and
`rotate_right` methods.
```rust
let mut a = ['a', 'b' ,'c', 'd', 'e', 'f'];
a.rotate_left(2);
assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
```
```rust
let mut a = ['a', 'b' ,'c', 'd', 'e', 'f'];
a.rotate_right(2);
assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
```
Justification
=============
I used this method today for my first time and (probably because I’m a
naive westerner who reads LTR) was surprised when the docs mentioned that
elements get rotated in a left-ward direction. I was in a situation
where I needed to shift elements in a right-ward direction and had to
context switch from the main problem I was working on and think how much
to rotate left in order to accomplish the right-ward rotation I needed.
Ruby’s `Array.rotate` shifts left-ward, Python’s `deque.rotate` shifts
right-ward. Both of their implementations allow passing negative numbers
to shift in the opposite direction respectively.
Introducing `rotate_left` and `rotate_right` would:
- remove ambiguity about direction (alleviating need to read docs 😉)
- make it easier for people who need to rotate right
[`rotate`]: https://doc.rust-lang.org/std/primitive.slice.html#method.rotate
[tracking]: https://github.com/rust-lang/rust/issues/41891
|
|
|
|
|
|
|
|
|
|
Short-circuiting internal iteration with Iterator::try_fold & try_rfold
These are the core methods in terms of which the other methods (`fold`, `all`, `any`, `find`, `position`, `nth`, ...) can be implemented, allowing Iterator implementors to get the full goodness of internal iteration by only overriding one method (per direction).
Based off the `Try` trait, so works with both `Result` and `Option` (:tada: https://github.com/rust-lang/rust/pull/42526). The `try_fold` rustdoc examples use `Option` and the `try_rfold` ones use `Result`.
AKA continuing in the vein of PRs https://github.com/rust-lang/rust/pull/44682 & https://github.com/rust-lang/rust/pull/44856 for more of `Iterator`.
New bench following the pattern from the latter of those:
```
test iter::bench_take_while_chain_ref_sum ... bench: 1,130,843 ns/iter (+/- 25,110)
test iter::bench_take_while_chain_sum ... bench: 362,530 ns/iter (+/- 391)
```
I also ran the benches without the `fold` & `rfold` overrides to test their new default impls, with basically no change. I left them there, though, to take advantage of existing overrides and because `AlwaysOk` has some sub-optimality due to https://github.com/rust-lang/rust/issues/43278 (which 45225 should fix).
If you're wondering why there are three type parameters, see issue https://github.com/rust-lang/rust/issues/45462
Thanks for @bluss for the [original IRLO thread](https://internals.rust-lang.org/t/pre-rfc-fold-ok-is-composable-internal-iteration/4434) and the rfold PR and to @cuviper for adding so many folds, [encouraging me](https://github.com/rust-lang/rust/pull/45379#issuecomment-339424670) to make this PR, and finding a catastrophic bug in a pre-review.
|
|
Improve SliceExt::binary_search performance
Improve the performance of binary_search by reducing the number of unpredictable conditional branches in the loop. In addition improve the benchmarks to test performance in l1, l2 and l3 caches on sorted arrays with or without dups.
Before:
```
test slice::binary_search_l1 ... bench: 48 ns/iter (+/- 1)
test slice::binary_search_l2 ... bench: 63 ns/iter (+/- 0)
test slice::binary_search_l3 ... bench: 152 ns/iter (+/- 12)
test slice::binary_search_l1_with_dups ... bench: 36 ns/iter (+/- 0)
test slice::binary_search_l2_with_dups ... bench: 64 ns/iter (+/- 1)
test slice::binary_search_l3_with_dups ... bench: 153 ns/iter (+/- 6)
```
After:
```
test slice::binary_search_l1 ... bench: 15 ns/iter (+/- 0)
test slice::binary_search_l2 ... bench: 23 ns/iter (+/- 0)
test slice::binary_search_l3 ... bench: 100 ns/iter (+/- 17)
test slice::binary_search_l1_with_dups ... bench: 15 ns/iter (+/- 0)
test slice::binary_search_l2_with_dups ... bench: 23 ns/iter (+/- 0)
test slice::binary_search_l3_with_dups ... bench: 98 ns/iter (+/- 14)
```
|
|
unpredictable conditional branches in the loop. In addition improve the
benchmarks to test performance in l1, l2 and l3 caches on sorted arrays
with or without dups.
Before:
```
test slice::binary_search_l1 ... bench: 48 ns/iter (+/- 1)
test slice::binary_search_l2 ... bench: 63 ns/iter (+/- 0)
test slice::binary_search_l3 ... bench: 152 ns/iter (+/- 12)
test slice::binary_search_l1_with_dups ... bench: 36 ns/iter (+/- 0)
test slice::binary_search_l2_with_dups ... bench: 64 ns/iter (+/- 1)
test slice::binary_search_l3_with_dups ... bench: 153 ns/iter (+/- 6)
```
After:
```
test slice::binary_search_l1 ... bench: 15 ns/iter (+/- 0)
test slice::binary_search_l2 ... bench: 23 ns/iter (+/- 0)
test slice::binary_search_l3 ... bench: 100 ns/iter (+/- 17)
test slice::binary_search_l1_with_dups ... bench: 15 ns/iter (+/- 0)
test slice::binary_search_l2_with_dups ... bench: 23 ns/iter (+/- 0)
test slice::binary_search_l3_with_dups ... bench: 98 ns/iter (+/- 14)
```
|
|
|
|
|
|
This is the core method in terms of which the other methods (fold, all, any, find, position, nth, ...) can be implemented, allowing Iterator implementors to get the full goodness of internal iteration by only overriding one method (per direction).
|
|
These functions were deprecated and removed in 1.5, but such simple
functionality shouldn't require using unsafe code, and it isn't
cluttering libstd too much.
|
