| Age | Commit message (Collapse) | Author | Lines |
|---|
|
This change moves:
1. `libcoretest` into `libcore/tests`
2. `libcollectionstest` into `libcollections/tests`
This is a follow-up to #39561.
|
|
Test sort algorithms using a random cmp function
This ensures that sorting using a broken comparison function doesn't panic nor fail in some other way (especially not segfault).
r? @alexcrichton
|
|
|
|
It's fairly common to expose an API which takes an `IntoIterator` and
immediately collects that into a vector. It's also common to buffer
a bunch of items into a vector and then pass that into one of these
APIs. If the iterator hasn't been advanced, we can make this `from_iter`
simply reassemble the original `Vec` with no actual iteration or
reallocation.
|
|
|
|
|
|
Their relationship is:
* `resume_from = error_len.map(|l| l + valid_up_to)`
* error_len is always one of None, Some(1), Some(2), or Some(3).
When I started using resume_from I almost always ended up subtracting
valid_up_to to obtain error_len.
Therefore the latter is what should be provided in the first place.
|
|
Without this, code outside of the standard library needs to reimplement
most of the logic `from_utf8` to interpret the bytes after `valid_up_to()`.
|
|
|
|
It was only accessible through the `#[unstable]` crate std_unicode.
It has never been used in the compiler or standard library
since 47e7a05a28c9662159af2d2e0f2b7efc13fa09cb added it in 2012
“for OS API interop”.
It can be replaced with a one-liner:
```rust
fn is_utf16(slice: &[u16]) -> bool {
std::char::decode_utf16(s.iter().cloned()).all(|r| r.is_ok())
}
```
|
|
|
|
|
|
|
|
|
|
And libcore/benches
|
|
Before, the `count` would be copied into the closure and could
potentially be optimized way. This change ensures it's borrowed by
closure and finally consumed by `test::black_box`.
|
|
Fixes https://github.com/rust-lang/rust/issues/38625.
|
|
This commit applies the stabilization/deprecations of the 1.16.0 release, as
tracked by the rust-lang/rust issue tracker and the final-comment-period tag.
The following APIs were stabilized:
* `VecDeque::truncate`
* `VecDeque::resize`
* `String::insert_str`
* `Duration::checked_{add,sub,div,mul}`
* `str::replacen`
* `SocketAddr::is_ipv{4,6}`
* `IpAddr::is_ipv{4,6}`
* `str::repeat`
* `Vec::dedup_by`
* `Vec::dedup_by_key`
* `Result::unwrap_or_default`
* `<*const T>::wrapping_offset`
* `<*mut T>::wrapping_offset`
* `CommandExt::creation_flags` (on Windows)
* `File::set_permissions`
* `String::split_off`
The following APIs were deprecated
* `EnumSet` - replaced with other ecosystem abstractions, long since unstable
Closes #27788
Closes #35553
Closes #35774
Closes #36436
Closes #36949
Closes #37079
Closes #37087
Closes #37516
Closes #37827
Closes #37916
Closes #37966
Closes #38080
|
|
Implement placement-in protocol for `BinaryHeap`
Related to #30172, and loosley based on #38551.
At the moment, this PR is in a pretty rough state, but I wanted to get some feedback to see if I'm going in the right direction.
I hope the Mentor label of #30172 is still applicable, even though it's a year old 😄
|
|
|
|
|
|
|
|
|
|
|
|
Add PeekMut::pop
A fairly common workflow is to put a bunch of stuff into a binary heap
and then mutate the top value until its empty. This both makes that a
bit more convenient (no need to save a boolean off and pop after to
avoid borrowck issues), and a bit more efficient since you only shift
once.
r? @alexcrichton
cc @rust-lang/libs
|
|
Implement placement-in protocol for `Vec`
Follow-up of #32366 per comment at https://github.com/rust-lang/rust/issues/30172#issuecomment-268099009, updating to latest rust, leaving @apasel422 as author and putting myself as committer.
I've removed the implementation of `push` in terms of place to make this PR more conservative.
|
|
Use more specific panic message for &str slicing errors
Separate out of bounds errors from character boundary errors, and print
more details for character boundary errors.
It reports the first error it finds in:
1. begin out of bounds
2. end out of bounds
3. begin <= end violated
3. begin not char boundary
5. end not char boundary.
Example:
&"abcαβγ"[..4]
thread 'str::test_slice_fail_boundary_1' panicked at 'byte index 4 is not
a char boundary; it is inside 'α' (bytes 3..5) of `abcαβγ`'
Fixes #38052
|
|
A fairly common workflow is to put a bunch of stuff into a binary heap
and then mutate the top value until its empty. This both makes that a
bit more convenient (no need to save a boolean off and pop after to
avoid borrowck issues), and a bit more efficient since you only shift
once.
|
|
|
|
|
|
Rename 'librustc_unicode' crate to 'libstd_unicode'.
Fixes https://github.com/rust-lang/rust/issues/26554.
|
|
Implement a faster sort algorithm
Hi everyone, this is my first PR.
I've made some changes to the standard sort algorithm, starting out with a few tweaks here and there, but in the end this endeavour became a complete rewrite of it.
#### Summary
Changes:
* Improved performance, especially on partially sorted inputs.
* Performs less comparisons on both random and partially sorted inputs.
* Decreased the size of temporary memory: the new sort allocates 4x less.
Benchmark:
```
name out1 ns/iter out2 ns/iter diff ns/iter diff %
slice::bench::sort_large_ascending 85,323 (937 MB/s) 8,970 (8918 MB/s) -76,353 -89.49%
slice::bench::sort_large_big_ascending 2,135,297 (599 MB/s) 355,955 (3595 MB/s) -1,779,342 -83.33%
slice::bench::sort_large_big_descending 2,266,402 (564 MB/s) 416,479 (3073 MB/s) -1,849,923 -81.62%
slice::bench::sort_large_big_random 3,053,031 (419 MB/s) 1,921,389 (666 MB/s) -1,131,642 -37.07%
slice::bench::sort_large_descending 313,181 (255 MB/s) 14,725 (5432 MB/s) -298,456 -95.30%
slice::bench::sort_large_mostly_ascending 287,706 (278 MB/s) 243,204 (328 MB/s) -44,502 -15.47%
slice::bench::sort_large_mostly_descending 415,078 (192 MB/s) 271,028 (295 MB/s) -144,050 -34.70%
slice::bench::sort_large_random 545,872 (146 MB/s) 521,559 (153 MB/s) -24,313 -4.45%
slice::bench::sort_large_random_expensive 30,321,770 (2 MB/s) 23,533,735 (3 MB/s) -6,788,035 -22.39%
slice::bench::sort_medium_ascending 616 (1298 MB/s) 155 (5161 MB/s) -461 -74.84%
slice::bench::sort_medium_descending 1,952 (409 MB/s) 202 (3960 MB/s) -1,750 -89.65%
slice::bench::sort_medium_random 3,646 (219 MB/s) 3,421 (233 MB/s) -225 -6.17%
slice::bench::sort_small_ascending 39 (2051 MB/s) 34 (2352 MB/s) -5 -12.82%
slice::bench::sort_small_big_ascending 96 (13333 MB/s) 96 (13333 MB/s) 0 0.00%
slice::bench::sort_small_big_descending 248 (5161 MB/s) 243 (5267 MB/s) -5 -2.02%
slice::bench::sort_small_big_random 501 (2554 MB/s) 490 (2612 MB/s) -11 -2.20%
slice::bench::sort_small_descending 95 (842 MB/s) 63 (1269 MB/s) -32 -33.68%
slice::bench::sort_small_random 372 (215 MB/s) 354 (225 MB/s) -18 -4.84%
```
#### Background
First, let me just do a quick brain dump to discuss what I learned along the way.
The official documentation says that the standard sort in Rust is a stable sort. This constraint is thus set in stone and immediately rules out many popular sorting algorithms. Essentially, the only algorithms we might even take into consideration are:
1. [Merge sort](https://en.wikipedia.org/wiki/Merge_sort)
2. [Block sort](https://en.wikipedia.org/wiki/Block_sort) (famous implementations are [WikiSort](https://github.com/BonzaiThePenguin/WikiSort) and [GrailSort](https://github.com/Mrrl/GrailSort))
3. [TimSort](https://en.wikipedia.org/wiki/Timsort)
Actually, all of those are just merge sort flavors. :) The current standard sort in Rust is a simple iterative merge sort. It has three problems. First, it's slow on partially sorted inputs (even though #29675 helped quite a bit). Second, it always makes around `log(n)` iterations copying the entire array between buffers, no matter what. Third, it allocates huge amounts of temporary memory (a buffer of size `2*n`, where `n` is the size of input).
The problem of auxilliary memory allocation is a tough one. Ideally, it would be best for our sort to allocate `O(1)` additional memory. This is what block sort (and it's variants) does. However, it's often very complicated (look at [this](https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.cpp)) and even then performs rather poorly. The author of WikiSort claims good performance, but that must be taken with a grain of salt. It performs well in comparison to `std::stable_sort` in C++. It can even beat `std::sort` on partially sorted inputs, but on random inputs it's always far worse. My rule of thumb is: high performance, low memory overhead, stability - choose two.
TimSort is another option. It allocates a buffer of size `n/2`, which is not great, but acceptable. Performs extremelly well on partially sorted inputs. However, it seems pretty much all implementations suck on random inputs. I benchmarked implementations in [Rust](https://github.com/notriddle/rust-timsort), [C++](https://github.com/gfx/cpp-TimSort), and [D](https://github.com/dlang/phobos/blob/fd518eb310a9494cccf28c54892542b052c49669/std/algorithm/sorting.d#L2062). The results were a bit disappointing. It seems bad performance is due to complex galloping procedures in hot loops. Galloping noticeably improves performance on partially sorted inputs, but worsens it on random ones.
#### The new algorithm
Choosing the best algorithm is not easy. Plain merge sort is bad on partially sorted inputs. TimSort is bad on random inputs and block sort is even worse. However, if we take the main ideas from TimSort (intelligent merging strategy of sorted runs) and drop galloping, then we'll have great performance on random inputs and it won't be bad on partially sorted inputs either.
That is exactly what this new algorithm does. I can't call it TimSort, since it steals just a few of it's ideas. Complete TimSort would be a much more complex and elaborate implementation. In case we in the future figure out how to incorporate more of it's ideas into this implementation without crippling performance on random inputs, it's going to be very easy to extend. I also did several other minor improvements, like reworked insertion sort to make it faster.
There are also new, more thorough benchmarks and panic safety tests.
The final code is not terribly complex and has less unsafe code than I anticipated, but there's still plenty of it that should be carefully reviewed. I did my best at documenting non-obvious code.
I'd like to notify several people of this PR, since they might be interested and have useful insights:
1. @huonw because he wrote the [original merge sort](https://github.com/rust-lang/rust/pull/11064).
2. @alexcrichton because he was involved in multiple discussions of it.
3. @veddan because he wrote [introsort](https://github.com/veddan/rust-introsort) in Rust.
4. @notriddle because he wrote [TimSort](https://github.com/notriddle/rust-timsort) in Rust.
5. @bluss because he had an attempt at writing WikiSort in Rust.
6. @gnzlbg, @rkruppe, and @mark-i-m because they were involved in discussion #36318.
**P.S.** [quickersort](https://github.com/notriddle/quickersort) describes itself as being universally [faster](https://github.com/notriddle/quickersort/blob/master/perf.txt) than the standard sort, which is true. However, if this PR gets merged, things might [change](https://gist.github.com/stjepang/b9f0c3eaa0e1f1280b61b963dae19a30) a bit. ;)
|
|
This is a complete rewrite of the standard sort algorithm. The new algorithm
is a simplified variant of TimSort. In summary, the changes are:
* Improved performance, especially on partially sorted inputs.
* Performs less comparisons on both random and partially sorted inputs.
* Decreased the size of temporary memory: the new sort allocates 4x less.
|
|
Improve is_empty on the VecDeque and its iterators by just comparing
tail and head; this saves a few instructions (to be able to remove the
`& (size - 1)` computation, it would have to know that size is a power of two).
|
|
|
|
Separate out of bounds errors from character boundary errors, and print
more details for character boundary errors.
Example:
&"abcαβγ"[..4]
thread 'str::test_slice_fail_boundary_1' panicked at 'byte index 4 is not
a char boundary; it is inside `α` (bytes 3..5) of `abcαβγ`'
|
|
Fixes #26554.
|
|
Implement better .is_empty() for slice and vec iterators
These iterators can use a pointer comparison instead of computing the length.
|
|
These iterators can use a pointer comparison instead of computing the length.
|
|
Improve .chars().count()
Use a simpler loop to count the `char` of a string: count the
number of non-continuation bytes. Use `count += <conditional>` which the
compiler understands well and can apply loop optimizations to.
benchmark descriptions and results for two configurations:
- ascii: ascii text
- cy: cyrillic text
- jp: japanese text
- words ascii: counting each split_whitespace item from the ascii text
- words jp: counting each split_whitespace item from the jp text
```
x86-64 rustc -Copt-level=3
name orig_ ns/iter cmov_ ns/iter diff ns/iter diff %
count_ascii 1,453 (1755 MB/s) 1,398 (1824 MB/s) -55 -3.79%
count_cy 5,990 (856 MB/s) 2,545 (2016 MB/s) -3,445 -57.51%
count_jp 3,075 (1169 MB/s) 1,772 (2029 MB/s) -1,303 -42.37%
count_words_ascii 4,157 (521 MB/s) 1,797 (1205 MB/s) -2,360 -56.77%
count_words_jp 3,337 (1071 MB/s) 1,772 (2018 MB/s) -1,565 -46.90%
x86-64 rustc -Ctarget-feature=+avx -Copt-level=3
name orig_ ns/iter cmov_ ns/iter diff ns/iter diff %
count_ascii 1,444 (1766 MB/s) 763 (3343 MB/s) -681 -47.16%
count_cy 5,871 (874 MB/s) 1,527 (3360 MB/s) -4,344 -73.99%
count_jp 2,874 (1251 MB/s) 1,073 (3351 MB/s) -1,801 -62.67%
count_words_ascii 4,131 (524 MB/s) 1,871 (1157 MB/s) -2,260 -54.71%
count_words_jp 3,253 (1099 MB/s) 1,331 (2686 MB/s) -1,922 -59.08%
```
I briefly explored a more involved blocked algorithm (looking at 8 or more bytes at a time),
but the code in this PR was always winning `count_words_ascii` in particular (counting
many small strings); this solution is an improvement without tradeoffs.
|
|
The default implementation of last() goes through the entire iterator
but that's not needed here.
|
|
Use a simpler loop to count the `char` of a string: count the
number of non-continuation bytes. Use `count += <conditional>` which the
compiler understands well and can apply loop optimizations to.
|
|
The default implementation of last() goes through the entire iterator
but that's not needed here.
|
|
* Correct the stability attributes.
* Make Add and AddAssign actually behave the same.
* Use String::with_capacity when allocating a new string.
* Fix the tests.
|
|
run rustfmt on libcollectionstest
|
|
|
|
Motivation: the `selectors` crate is generic over a string type,
in order to support all of `String`, `string_cache::Atom`, and
`gecko_string_cache::Atom`. Multiple trait bounds are used
for the various operations done with these strings.
One of these operations is creating a string (as efficiently as possible,
re-using an existing memory allocation if possible) from `Cow<str>`.
The `std::convert::From` trait seems natural for this, but
the relevant implementation was missing before this PR.
To work around this I’ve added a `FromCowStr` trait in `selectors`,
but with trait coherence that means one of `selectors` or `string_cache`
needs to depend on the other to implement this trait.
Using a trait from `std` would solve this.
The `Vec<T>` implementation is just added for consistency.
I also tried a more general
`impl<'a, O, B: ?Sized + ToOwned<Owned=O>> From<Cow<'a, B>> for O`,
but (the compiler thinks?) it conflicts with `From<T> for T` the impl
(after moving all of `collections::borrow` into `core::borrow`
to work around trait coherence).
|
|
Lint against lowercase static mut
Closes #37145.
Lint for non mut statics was added in https://github.com/rust-lang/rust/pull/7523, and it explicitly did not cover mut statics. I am not sure why.
|
|
|
|
Add Vec::dedup_by and Vec::dedup_by_key
|
