| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Implement ordered/sorted iterators on BinaryHeap as per #59278
I've implemented the ordered version of iterator on BinaryHeap as per #59278.
# Added methods:
* `.into_iter_sorted()`
* like `.into_iter()`; but returns elements in heap order
* `.drain_sorted()`
* like `.drain()`; but returns elements in heap order
* It's a bit _lazy_; elements are removed on drop. (Edit: it’s similar to vec::Drain)
For `DrainSorted` struct, I implemented `Drop` trait following @scottmcm 's [suggestion](https://github.com/rust-lang/rust/issues/59278#issuecomment-537306925)
# ~TODO~ DONE
* ~I think I need to add more tests other than doctest.~
# **Notes:**
* we renamed `_ordered` to `_sorted`, because the latter is more common in rust libs. (as suggested by @KodrAus )
|
|
* `.drain_sorted()` doc change suggested by @KodrAus
|
|
|
|
Fix zero-size uninitialized boxes
Requesting a zero-size allocation is not allowed, return a dangling pointer instead.
CC https://github.com/rust-lang/rust/issues/63291#issuecomment-538692745
|
|
|
|
|
|
|
|
rustbuild
Remove some random unnecessary lint `allow`s
|
|
|
|
|
|
|
|
|
|
|
|
FCP: https://github.com/rust-lang/rust/issues/27791#issuecomment-376864727
|
|
|
|
|
|
This commit deletes the `alloc_system` crate from the standard
distribution. This unstable crate is no longer needed in the modern
stable global allocator world, but rather its functionality is folded
directly into the standard library. The standard library was already the
only stable location to access this crate, and as a result this should
not affect any stable code.
|
|
* Also update the bootstrap compiler
* Update cargo to 1.32.0
* Clean out stage0 annotations
|
|
Fixes #55177
|
|
Fixes #47115
|
|
These work exactly like the normal chunks iterators but start creating
chunks from the end of the slice.
See #55177 for the tracking issue
|
|
|
|
|
|
See https://github.com/rust-lang/rust/issues/47115#issuecomment-403090815
and https://github.com/rust-lang/rust/issues/47115#issuecomment-424053547
|
|
|
|
|
|
|
|
|
|
Incorporate a stray test
`liballoc/repeat-generic-slice.rs` doesn't seem to be tested (I think it was intended to be placed in `run-pass`). This PR incorporates the test into `liballoc/tests`.
|
|
|
|
|
|
|
|
Fixes #27741
|
|
|
|
Added new()/start()/end() methods to RangeInclusive.
Changed the lowering of `..=` to use RangeInclusive::new().
|
|
|
|
|
|
This permits easier iteration without having to worry about warnings
being denied.
Fixes #49517
|
|
Holy cow that's a lot of `cfg(stage0)` removed and a lot of new stable language
features!
|
|
Closes #22181, #27779
|
|
Add slice::sort_by_cached_key as a memoised sort_by_key
At present, `slice::sort_by_key` calls its key function twice for each comparison that is made. When the key function is expensive (which can often be the case when `sort_by_key` is chosen over `sort_by`), this can lead to very suboptimal behaviour.
To address this, I've introduced a new slice method, `sort_by_cached_key`, which has identical semantic behaviour to `sort_by_key`, except that it guarantees the key function will only be called once per element.
Where there are `n` elements and the key function is `O(m)`:
- `slice::sort_by_cached_key` time complexity is `O(m n log m n)`, compared to `slice::sort_by_key`'s `O(m n + n log n)`.
- `slice::sort_by_cached_key` space complexity remains at `O(n + m)`. (Technically, it now reserves a slice of size `n`, whereas before it reserved a slice of size `n/2`.)
`slice::sort_unstable_by_key` has not been given an analogue, as it is important that unstable sorts are in-place, which is not a property that is guaranteed here. However, this also means that `slice::sort_unstable_by_key` is likely to be slower than `slice::sort_by_cached_key` when the key function does not have negligible complexity. We might want to explore this trade-off further in the future.
Benchmarks (for a vector of 100 `i32`s):
```
# Lexicographic: `|x| x.to_string()`
test bench_sort_by_key ... bench: 112,638 ns/iter (+/- 19,563)
test bench_sort_by_cached_key ... bench: 15,038 ns/iter (+/- 4,814)
# Identity: `|x| *x`
test bench_sort_by_key ... bench: 1,346 ns/iter (+/- 238)
test bench_sort_by_cached_key ... bench: 1,839 ns/iter (+/- 765)
# Power: `|x| x.pow(31)`
test bench_sort_by_key ... bench: 3,624 ns/iter (+/- 738)
test bench_sort_by_cached_key ... bench: 1,997 ns/iter (+/- 311)
# Abs: `|x| x.abs()`
test bench_sort_by_key ... bench: 1,546 ns/iter (+/- 174)
test bench_sort_by_cached_key ... bench: 1,668 ns/iter (+/- 790)
```
(So it seems functions that are single operations do perform slightly worse with this method, but for pretty much any more complex key, you're better off with this optimisation.)
I've definitely found myself using expensive keys in the past and wishing this optimisation was made (e.g. for https://github.com/rust-lang/rust/pull/47415). This feels like both desirable and expected behaviour, at the small cost of slightly more stack allocation and minute degradation in performance for extremely trivial keys.
Resolves #34447.
|
|
|
|
Stabilize inclusive range (`..=`)
Stabilize the followings:
* `inclusive_range` — The `std::ops::RangeInclusive` and `std::ops::RangeInclusiveTo` types, except its fields (tracked by #49022 separately).
* `inclusive_range_syntax` — The `a..=b` and `..=b` expression syntax
* `dotdoteq_in_patterns` — Using `a..=b` in a pattern
cc #28237
r? @rust-lang/lang
|
|
|
|
Stabilize the syntax `a..=b` and `..=b`.
|
|
|
|
https://github.com/rust-lang/rust/issues/41891
|
|
|
|
These are basically modified copies of the chunks/chunks_mut tests.
|
|
The GNU C library (glibc) is documented to always allocate with an alignment
of at least 8 or 16 bytes, on 32-bit or 64-bit platforms:
https://www.gnu.org/software/libc/manual/html_node/Aligned-Memory-Blocks.html
This matches our use of `MIN_ALIGN` before this commit.
However, even when libc is glibc, the program might be linked
with another allocator that redefines the `malloc` symbol and friends.
(The `alloc_jemalloc` crate does, in some cases.)
So `alloc_system` doesn’t know which allocator it calls,
and needs to be conservative in assumptions it makes.
The C standard says:
https://port70.net/%7Ensz/c/c11/n1570.html#7.22.3
> The pointer returned if the allocation succeeds is suitably aligned
> so that it may be assigned to a pointer to any type of object
> with a fundamental alignment requirement
https://port70.net/~nsz/c/c11/n1570.html#6.2.8p2
> A fundamental alignment is represented by an alignment less than
> or equal to the greatest alignment supported by the implementation
> in all contexts, which is equal to `_Alignof (max_align_t)`.
`_Alignof (max_align_t)` depends on the ABI and doesn’t seem to have
a clear definition, but it seems to match our `MIN_ALIGN` in practice.
However, the size of objects is rounded up to the next multiple
of their alignment (since that size is also the stride used in arrays).
Conversely, the alignment of a non-zero-size object is at most its size.
So for example it seems ot be legal for `malloc(8)` to return a pointer
that’s only 8-bytes-aligned, even if `_Alignof (max_align_t)` is 16.
|
