| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Tiny Vecs are dumb.
Currently, if you repeatedly push to an empty vector, the capacity
growth sequence is 0, 1, 2, 4, 8, 16, etc. This commit changes the
relevant code (the "amortized" growth strategy) to skip 1 and 2, instead
using 0, 4, 8, 16, etc. (You can still get a capacity of 1 or 2 using
the "exact" growth strategy, e.g. via `reserve_exact()`.)
This idea (along with the phrase "tiny Vecs are dumb") comes from the
"doubling" growth strategy that was removed from `RawVec` in #72013.
That strategy was barely ever used -- only when a `VecDeque` was grown,
oddly enough -- which is why it was removed in #72013.
(Fun fact: until just a few days ago, I thought the "doubling" strategy
was used for repeated push case. In other words, this commit makes
`Vec`s behave the way I always thought they behaved.)
This change reduces the number of allocations done by rustc itself by
10% or more. It speeds up rustc, and will also speed up any other Rust
program that uses `Vec`s a lot.
In theory, the change could increase memory usage, but in practice it
doesn't. It would be an unusual program where very small `Vec`s having a
capacity of 4 rather than 1 or 2 would make a difference. You'd need a
*lot* of very small `Vec`s, and/or some very small `Vec`s with very
large elements.
r? @Amanieu
|
|
impl From<Cow> for Box, Rc, and Arc
These forward `Borrowed`/`Owned` values to existing `From` impls.
- `Box<T>` is a fundamental type, so it would be a breaking change to add a blanket impl. Therefore, `From<Cow>` is only implemented for `[T]`, `str`, `CStr`, `OsStr`, and `Path`.
- For `Rc<T>` and `Arc<T>`, `From<Cow>` is implemented for everything that implements `From` the borrowed and owned types separately.
|
|
Currently, if you repeatedly push to an empty vector, the capacity
growth sequence is 0, 1, 2, 4, 8, 16, etc. This commit changes the
relevant code (the "amortized" growth strategy) to skip 1 and 2 in most
cases, instead using 0, 4, 8, 16, etc. (You can still get a capacity of
1 or 2 using the "exact" growth strategy, e.g. via `reserve_exact()`.)
This idea (along with the phrase "tiny Vecs are dumb") comes from the
"doubling" growth strategy that was removed from `RawVec` in #72013.
That strategy was barely ever used -- only when a `VecDeque` was grown,
oddly enough -- which is why it was removed in #72013.
(Fun fact: until just a few days ago, I thought the "doubling" strategy
was used for repeated push case. In other words, this commit makes
`Vec`s behave the way I always thought they behaved.)
This change reduces the number of allocations done by rustc itself by
10% or more. It speeds up rustc, and will also speed up any other Rust
program that uses `Vec`s a lot.
|
|
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!
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Don't import integer and float modules, use assoc consts
Stop importing the standard library integer and float modules to reach the `MIN`, `MAX` and other constants. They are available directly on the primitive types now.
This PR is a follow up of #69860 which made sure we use the new constants in documentation.
This type of change touches a lot of files, and previously all my assoc int consts PRs had collisions and were accepted only after a long delay. So I'd prefer to do it in smaller steps now. Just removing these imports seem like a good next step.
r? @dtolnay
|
|
Fix some aliasing issues in Vec
`Vec::extend` and `Vec::truncate` invalidated references into the vector even without reallocation, because they (implicitly) created a mutable reference covering the *entire* initialized part of the vector.
Fixes https://github.com/rust-lang/rust/issues/70301
I verified the fix by adding some new tests here that I ran in Miri.
|
|
|
|
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
|
|
BTreeMap/BTreeSet: implement drain_filter
Provide an implementation of drain_filter for BTreeMap and BTreeSet. Should be optimal when the predicate picks only elements in leaf nodes with at least MIN_LEN remaining elements, which is a common case, at least when draining only a fraction of the map/set, and also when the predicate picks elements stored in internal nodes where the right subtree can easily let go of a replacement element.
The first commit adds benchmarks with an external, naive implementation. to compare how much this claimed optimality-in-some-cases is actually worth.
|
|
|
|
also add smoke test to detect relocation even in rustc runs
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#70194
|
|
|
|
Fix & test leak of some BTreeMap nodes on panic during `into_iter`
Fixes #69769
|
|
|
|
|
|
Remove `usable_size` APIs
This removes the usable size APIs:
- remove `usable_size` (obv)
- change return type of allocating methods to include the allocated size
- remove `_excess` API
r? @Amanieu
closes rust-lang/wg-allocators#17
|
|
|
|
Audit liballoc for leaks in `Drop` impls when user destructor panics
Inspired by https://github.com/rust-lang/rust/pull/67243 and https://github.com/rust-lang/rust/pull/67235, this audits and hopefully fixes the remaining `Drop` impls in liballoc for resource leaks in the presence of panics in destructors called by the affected `Drop` impl.
This does not touch `Hash{Map,Set}` since they live in hashbrown. They have similar issues though.
r? @KodrAus
|
|
Implement split_inclusive for slice and str
# Overview
* Implement `split_inclusive` for `slice` and `str` and `split_inclusive_mut` for `slice`
* `split_inclusive` is a substring/subslice splitting iterator that includes the matched part in the iterated substrings as a terminator.
* EDIT: The behaviour has now changed, as per @KodrAus 's input, to the same semantics with the `split_terminator` function. I updated the examples below.
* Two examples below:
```Rust
let data = "\nMäry häd ä little lämb\nLittle lämb\n";
let split: Vec<&str> = data.split_inclusive('\n').collect();
assert_eq!(split, ["\n", "Märy häd ä little lämb\n", "Little lämb\n"]);
```
```Rust
let uppercase_separated = "SheePSharKTurtlECaT";
let mut first_char = true;
let split: Vec<&str> = uppercase_separated.split_inclusive(|c: char| {
let split = !first_char && c.is_uppercase();
first_char = split;
split
}).collect();
assert_eq!(split, ["SheeP", "SharK", "TurtlE", "CaT"]);
```
# Justification for the API
* I was surprised to find that stdlib currently only has splitting iterators that leave out the matched part. In my experience, wanting to leave a substring terminator as a part of the substring is a pretty common usecase.
* This API is strictly more expressive than the standard `split` API: it's easy to get the behaviour of `split` by mapping a subslicing operation that drops the terminator. On the other hand it's impossible to derive this behaviour from `split` without using hacky and brittle `unsafe` code. The normal way to achieve this functionality would be implementing the iterator yourself.
* Especially when dealing with mutable slices, the only way currently is to use `split_at_mut`. This API provides an ergonomic alternative that plays to the strengths of the iterating capabilities of Rust. (Using `split_at_mut` iteratively used to be a real pain before NLL, fortunately the situation is a bit better now.)
# Discussion items
* <s>Does it make sense to mimic `split_terminator` in that the final empty slice would be left off in case of the string/slice ending with a terminator? It might do, as this use case is naturally geared towards considering the matching part as a terminator instead of a separator.</s>
* EDIT: The behaviour was changed to mimic `split_terminator`.
* Does it make sense to have `split_inclusive_mut` for `&mut str`?
|
|
|
|
Derive Clone + Eq for std::string::FromUtf8Error
Implement `Clone` and `Eq` for `std::string::FromUtf8Error`.
Both the inner `Vec<u8>` and `std::str::Utf8Error` are also `Clone + Eq`, so I don't see why we shouldn't derive them on `FromUtf8Error` as well.
(impl are insta-stable, requiring FCP from T-libs.)
|
|
reverse iteration.
|
|
includes the matched part in the iterated substrings as a terminator.
|
|
pop_first, pop_last
|
|
|
|
Implement clone_from for BTreeMap and BTreeSet
See #28481. This results in up to 90% speedups on simple data types when `self` and `other` are the same size, and is generally comparable or faster. Some concerns:
1. This implementation requires an `Ord` bound on the `Clone` implementation for `BTreeMap` and `BTreeSet`. Since these structs can only be created externally for keys with `Ord` implemented, this should be fine? If not, there's certainly a less safe way to do this.
2. Changing `next_unchecked` on `RangeMut` to return mutable key references allows for replacing the entire overlapping portion of both maps without changing the external interface in any way. However, if `clone_from` fails it can leave the `BTreeMap` in an invalid state, which might be unacceptable.
~This probably needs an FCP since it changes a trait bound, but (as far as I know?) that change cannot break any external code.~
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
