summary refs log tree commit diff
path: root/library/alloc/src
AgeCommit message (Collapse)AuthorLines
2022-07-27Auto merge of #98553 - the8472:next_chunk_opt, r=Mark-Simulacrumbors-2/+43
Optimized vec::IntoIter::next_chunk impl ``` x86_64v1, default test vec::bench_next_chunk ... bench: 696 ns/iter (+/- 22) x86_64v1, pr test vec::bench_next_chunk ... bench: 309 ns/iter (+/- 4) znver2, default test vec::bench_next_chunk ... bench: 17,272 ns/iter (+/- 117) znver2, pr test vec::bench_next_chunk ... bench: 211 ns/iter (+/- 3) ``` On znver2 the default impl seems to be slow due to different inlining decisions. It goes through `core::array::iter_next_chunk` which has a deep call tree.
2022-07-26Auto merge of #99574 - durin42:allocator-patch-redux, r=nikicbors-1/+4
codegen: use new {re,de,}allocator annotations in llvm This obviates the patch that teaches LLVM internals about _rust_{re,de}alloc functions by putting annotations directly in the IR for the optimizer. The sole test change is required to anchor FileCheck to the body of the `box_uninitialized` method, so it doesn't see the `allocalign` on `__rust_alloc` and get mad about the string `alloca` showing up. Since I was there anyway, I added some checks on the attributes to prove the right attributes got set. r? `@nikic`
2022-07-26Optimized vec::IntoIter::next_chunk implThe 8472-2/+43
``` test vec::bench_next_chunk ... bench: 696 ns/iter (+/- 22) x86_64v1, pr test vec::bench_next_chunk ... bench: 309 ns/iter (+/- 4) znver2, default test vec::bench_next_chunk ... bench: 17,272 ns/iter (+/- 117) znver2, pr test vec::bench_next_chunk ... bench: 211 ns/iter (+/- 3) ``` The znver2 default impl seems to be slow due to inlining decisions. It goes through `core::array::iter_next_chunk` which has a deeper call tree.
2022-07-26codegen: use new {re,de,}allocator annotations in llvmAugie Fackler-1/+4
This obviates the patch that teaches LLVM internals about _rust_{re,de}alloc functions by putting annotations directly in the IR for the optimizer. The sole test change is required to anchor FileCheck to the body of the `box_uninitialized` method, so it doesn't see the `allocalign` on `__rust_alloc` and get mad about the string `alloca` showing up. Since I was there anyway, I added some checks on the attributes to prove the right attributes got set. While we're here, we also emit allocator attributes on __rust_alloc_zeroed. This should allow LLVM to perform more optimizations for zeroed blocks, and probably fixes #90032. [This comment](https://github.com/rust-lang/rust/issues/24194#issuecomment-308791157) mentions "weird UB-like behaviour with bitvec iterators in rustc_data_structures" so we may need to back this change out if things go wrong. The new test cases require LLVM 15, so we copy them into LLVM 14-supporting versions, which we can delete when we drop LLVM 14.
2022-07-26Rollup merge of #98710 - mojave2:string, r=JohnTitorYuki Okushi-5/+5
correct the output of a `capacity` method example The output of this example in std::alloc is different from which shown in the comment. I have tested it on both Linux and Windows.
2022-07-24Support vec zero-alloc optimization for tuples and byte arraysAngelicosPhosphoros-17/+46
* Implement IsZero trait for tuples up to 8 IsZero elements; * Implement IsZero for u8/i8, leading to implementation of it for arrays of them too; * Add more codegen tests for this optimization. * Lower size of array for IsZero trait because it fails to inline checks
2022-07-21Rollup merge of #99413 - steffahn:btree_dropck, r=m-ou-seMatthias Krüger-4/+26
Add `PhantomData` marker for dropck to `BTreeMap` closes #99408
2022-07-18Rollup merge of #99198 - RalfJung:alloc-null-ptr, r=JohnTitorDylan DPC-1/+4
add missing null ptr check in alloc example `alloc` can return null on OOM, if I understood correctly. So we should never just deref a pointer we get from `alloc`.
2022-07-18Add `PhantomData` marker for dropck to `BTreeMap`Frank Steffahn-4/+26
closes #99408
2022-07-16Rollup merge of #99317 - yanchith:borrow-vec-ta-as-slice-t, r=Mark-SimulacrumMatthias Krüger-2/+2
Borrow Vec<T, A> as [T] Hello all, When `Vec` was parametrized with `A`, the `Borrow` impls were omitted and currently `Vec<T, A>` can't be borrowed as `[T]`. This PR fixes that. This was probably missed, because the `Borrow` impls are in a different file - `src/alloc/slice.rs`. We briefly discussed this here: https://github.com/rust-lang/wg-allocators/issues/96 and I was told to go ahead and make a PR :) I tested this by building the toolchain and building my code that needed the `Borrow` impl against it, but let me know if I should add any tests to this PR.
2022-07-16Borrow Vec<T, A> as [T]yanchith-2/+2
2022-07-16Rollup merge of #99277 - joshtriplett:stabilize-core-cstr-alloc-cstring, ↵Yuki Okushi-9/+7
r=Mark-Simulacrum Stabilize `core::ffi::CStr`, `alloc::ffi::CString`, and friends Stabilize the `core_c_str` and `alloc_c_string` feature gates. Change `std::ffi` to re-export these types rather than creating type aliases, since they now have matching stability.
2022-07-16Rollup merge of #99270 - rhysd:issue-99269, r=Mark-SimulacrumYuki Okushi-0/+1
Add `#[must_use]` to `Box::from_raw` Fixes #99269
2022-07-15Stabilize `core::ffi::CStr`, `alloc::ffi::CString`, and friendsJosh Triplett-9/+7
Stabilize the `core_c_str` and `alloc_c_string` feature gates. Change `std::ffi` to re-export these types rather than creating type aliases, since they now have matching stability.
2022-07-15add `#[must_use]` to `Box::from_raw`rhysd-0/+1
2022-07-15Rollup merge of #99113 - WaffleLapkin:arc_simplify, r=Mark-SimulacrumDylan DPC-12/+11
Simplify [a]rc code a little Nothing interesting, just make [a]rc code a little nicer by using `byte_sub` and `let`-`else`.
2022-07-14add missing null ptr check in alloc exampleRalf Jung-1/+4
2022-07-14Rollup merge of #98315 - joshtriplett:stabilize-core-ffi-c, r=Mark-SimulacrumDylan DPC-1/+0
Stabilize `core::ffi:c_*` and rexport in `std::ffi` This only stabilizes the base types, not the non-zero variants, since those have their own separate tracking issue and have not gone through FCP to stabilize.
2022-07-13Stabilize `core::ffi:c_*` and rexport in `std::ffi`Josh Triplett-1/+0
This only stabilizes the base types, not the non-zero variants, since those have their own separate tracking issue and have not gone through FCP to stabilize.
2022-07-10Use `byte_sub` in [a]rc implMaybe Waffle-12/+11
2022-07-08Intra-doc-link-ify reference to Clone::clone_fromest31-1/+1
2022-07-03Auto merge of #98755 - nnethercote:faster-vec-insert, r=cuviperbors-6/+9
Optimize `Vec::insert` for the case where `index == len`. By skipping the call to `copy` with a zero length. This makes it closer to `push`. I did this recently for `SmallVec` (https://github.com/servo/rust-smallvec/pull/282) and it was a big perf win in one case. Although I don't have a specific use case in mind, it seems worth doing it for `Vec` as well. Things to note: - In the `index < len` case, the number of conditions checked is unchanged. - In the `index == len` case, the number of conditions checked increases by one, but the more expensive zero-length copy is avoided. - In the `index > len` case the code now reserves space for the extra element before panicking. This seems like an unimportant change. r? `@cuviper`
2022-07-03Auto merge of #98673 - pietroalbini:pa-bootstrap-update, r=Mark-Simulacrumbors-42/+6
Bump bootstrap compiler r? `@Mark-Simulacrum`
2022-07-01Rollup merge of #98585 - cuviper:covariant-thinbox, r=thomccDylan DPC-6/+27
Make `ThinBox<T>` covariant in `T` Just like `Box<T>`, we want `ThinBox<T>` to be covariant in `T`, but the projection in `WithHeader<<T as Pointee>::Metadata>` was making it invariant. This is now hidden as `WithOpaqueHeader`, which we type-cast whenever the real `WithHeader<H>` type is needed. Fixes the problem noted in <https://github.com/rust-lang/rust/issues/92791#issuecomment-1104636249>.
2022-07-01update cfg(bootstrap)sPietro Albini-42/+6
2022-07-01Optimize `Vec::insert` for the case where `index == len`.Nicholas Nethercote-6/+9
By skipping the call to `copy` with a zero length. This makes it closer to `push`. I did this recently for `SmallVec` (https://github.com/servo/rust-smallvec/pull/282) and it was a big perf win in one case. Although I don't have a specific use case in mind, it seems worth doing it for `Vec` as well. Things to note: - In the `index < len` case, the number of conditions checked is unchanged. - In the `index == len` case, the number of conditions checked increases by one, but the more expensive zero-length copy is avoided. - In the `index > len` case the code now reserves space for the extra element before panicking. This seems like an unimportant change.
2022-06-30correct the output of a `capacity` method examplemojave2-5/+5
2022-06-29alloc: fix `no_global_oom_handling` warningsMiguel Ojeda-3/+8
Rust 1.62.0 introduced a couple new `unused_imports` warnings in `no_global_oom_handling` builds, making a total of 5 warnings: ```txt warning: unused import: `Unsize` --> library/alloc/src/boxed/thin.rs:6:33 | 6 | use core::marker::{PhantomData, Unsize}; | ^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `from_fn` --> library/alloc/src/string.rs:51:18 | 51 | use core::iter::{from_fn, FusedIterator}; | ^^^^^^^ warning: unused import: `core::ops::Deref` --> library/alloc/src/vec/into_iter.rs:12:5 | 12 | use core::ops::Deref; | ^^^^^^^^^^^^^^^^ warning: associated function `shrink` is never used --> library/alloc/src/raw_vec.rs:424:8 | 424 | fn shrink(&mut self, cap: usize) -> Result<(), TryReserveError> { | ^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: associated function `forget_remaining_elements` is never used --> library/alloc/src/vec/into_iter.rs:126:19 | 126 | pub(crate) fn forget_remaining_elements(&mut self) { | ^^^^^^^^^^^^^^^^^^^^^^^^^ ``` This patch cleans them so that projects compiling `alloc` without infallible allocations do not see the warnings. It also enables the use of `-Dwarnings`. The couple `dead_code` ones may be reverted when some fallible allocation support starts using them. Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
2022-06-27Implement `Send` and `Sync` for `ThinBox<T>`Josh Stone-0/+8
Just like `Box<T>`, `ThinBox<T>` owns its data on the heap, so it should implement `Send` and `Sync` when `T` does.
2022-06-27Make `ThinBox<T>` covariant in `T`Josh Stone-6/+27
Just like `Box<T>`, we want `ThinBox<T>` to be covariant in `T`, but the projection in `WithHeader<<T as Pointee>::Metadata>` was making it invariant. This is now hidden as `WithOpaqueHeader`, which we type-cast whenever the real `WithHeader<H>` type is needed.
2022-06-24Rollup merge of #98039 - tnballo:master, r=thomccYuki Okushi-13/+117
Fix `panic` message for `BTreeSet`'s `range` API and document `panic` cases Currently, the `panic` cases for [`BTreeSet`'s `range` API](https://doc.rust-lang.org/std/collections/struct.BTreeSet.html#method.range) are undocumented and produce a slightly wrong `panic` message (says `BTreeMap` instead of `BTreeSet`). Panic case 1 code: ```rust use std::collections::BTreeSet; use std::ops::Bound::Excluded; fn main() { let mut set = BTreeSet::new(); set.insert(3); set.insert(5); set.insert(8); for &elem in set.range((Excluded(&3), Excluded(&3))) { println!("{elem}"); } } ``` Panic case 1 message: ``` thread 'main' panicked at 'range start and end are equal and excluded in BTreeMap', /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/alloc/src/collections/btree/search.rs:105:17 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ``` Panic case 2 code: ```rust use std::collections::BTreeSet; use std::ops::Bound::Included; fn main() { let mut set = BTreeSet::new(); set.insert(3); set.insert(5); set.insert(8); for &elem in set.range((Included(&8), Included(&3))) { println!("{elem}"); } } ``` Panic case 2: ``` thread 'main' panicked at 'range start is greater than range end in BTreeMap', /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/alloc/src/collections/btree/search.rs:110:17 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ``` This PR fixes the output messages to say `BTreeSet`, adds the relevant unit tests, and updates the documentation for the API.
2022-06-23Fix BTreeSet's range API panic message, documenttnballo-13/+117
2022-06-23Rollup merge of #98364 - RalfJung:arc-clone, r=Mark-SimulacrumMichael Goulet-8/+9
clarify Arc::clone overflow check comment I had to read this twice to realize that this is explaining that the code is technically unsound, so move that into a dedicated paragraph and make the wording a bit more explicit.
2022-06-23Rollup merge of #96173 - jmaargh:jmaargh/with-capacity-doc-fix, r=Dylan-DPCMichael Goulet-93/+129
Fix documentation for `with_capacity` and `reserve` families of methods Fixes #95614 Documentation for the following methods - `with_capacity` - `with_capacity_in` - `with_capacity_and_hasher` - `reserve` - `reserve_exact` - `try_reserve` - `try_reserve_exact` was inconsistent and often not entirely correct where they existed on the following types - `Vec` - `VecDeque` - `String` - `OsString` - `PathBuf` - `BinaryHeap` - `HashSet` - `HashMap` - `BufWriter` - `LineWriter` since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked `BufReader`, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well.
2022-06-21clarify Arc::clone overflow check commentRalf Jung-8/+9
2022-06-21remove use of &Alloc in btree testsRalf Jung-6/+6
2022-06-20Rollup merge of #96609 - ibraheemdev:arc-downcast-unchecked, r=m-ou-seDylan DPC-5/+80
Add `{Arc, Rc}::downcast_unchecked` Part of #90850.
2022-06-19Fix documentation for with_capacity and reserve families of methodsjmaargh-93/+129
Documentation for the following methods with_capacity with_capacity_in with_capacity_and_hasher reserve reserve_exact try_reserve try_reserve_exact was inconsistent and often not entirely correct where they existed on the following types Vec VecDeque String OsString PathBuf BinaryHeap HashSet HashMap BufWriter LineWriter since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked BufReader, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well. Fix with_capacity* methods for Vec Fix *reserve* methods for Vec Fix docs for *reserve* methods of VecDeque Fix docs for String::with_capacity Fix docs for *reserve* methods of String Fix docs for OsString::with_capacity Fix docs for *reserve* methods on OsString Fix docs for with_capacity* methods on HashSet Fix docs for *reserve methods of HashSet Fix docs for with_capacity* methods of HashMap Fix docs for *reserve methods on HashMap Fix expect messages about OOM in doctests Fix docs for BinaryHeap::with_capacity Fix docs for *reserve* methods of BinaryHeap Fix typos Fix docs for with_capacity on BufWriter and LineWriter Fix consistent use of `hasher` between `HashMap` and `HashSet` Fix warning in doc test Add test for capacity of vec with ZST Fix doc test error
2022-06-19Rollup merge of #98233 - RalfJung:ref-alloc, r=thomccDylan DPC-6/+6
Remove accidental uses of `&A: Allocator` Cc https://github.com/rust-lang/rust/issues/98232 Fixes https://github.com/rust-lang/rust/issues/98176 (for real this time)
2022-06-18make btree not use &A: Allocator instanceRalf Jung-6/+6
2022-06-18Auto merge of #98004 - paolobarbolini:vecdeque-extend-trustedlen, r=the8472bors-0/+176
Add VecDeque::extend from TrustedLen specialization Continuation of #95904 Inspired by how [`VecDeque::copy_slice` works](https://github.com/rust-lang/rust/blob/c08b235a5ce10167632bb0fddcd0c5d67f2d42e3/library/alloc/src/collections/vec_deque/mod.rs#L437-L454). ## Benchmarks Before ``` test vec_deque::bench_extend_chained_bytes ... bench: 1,026 ns/iter (+/- 17) test vec_deque::bench_extend_chained_trustedlen ... bench: 1,024 ns/iter (+/- 40) test vec_deque::bench_extend_trustedlen ... bench: 637 ns/iter (+/- 693) ``` After ``` test vec_deque::bench_extend_chained_bytes ... bench: 828 ns/iter (+/- 24) test vec_deque::bench_extend_chained_trustedlen ... bench: 25 ns/iter (+/- 1) test vec_deque::bench_extend_trustedlen ... bench: 21 ns/iter (+/- 0) ``` ## Why do it this way https://rust.godbolt.org/z/15qY1fMYh The Compiler Explorer example shows how "just" removing the capacity check, like the [`Vec` `TrustedLen` specialization](https://github.com/rust-lang/rust/blob/c08b235a5ce10167632bb0fddcd0c5d67f2d42e3/library/alloc/src/vec/spec_extend.rs#L22-L58) does, wouldn't have been enough for `VecDeque`. `wrap_add` would still have greatly limited what LLVM could do while optimizing. --- r? `@the8472`
2022-06-18Auto merge of #98178 - RalfJung:btree-alloc, r=thomccbors-241/+270
btree: avoid forcing the allocator to be a reference The previous code forces the actual allocator used to be some `&A`. This generalizes the code to allow any `A: Copy`. If people truly want to use a reference, they can use `&A` themselves. Fixes https://github.com/rust-lang/rust/issues/98176
2022-06-17comments explaining why we have and don't have ManuallyDropRalf Jung-0/+6
2022-06-18Expose iter::ByRefSized as unstable feature and use itPaolo Barbolini-1/+2
2022-06-18Add VecDeque::extend from TrustedLen specializationPaolo Barbolini-0/+175
2022-06-17Rollup merge of #95392 - Xuanwo:stablize_try_reserve_2, r=dtolnayDylan DPC-4/+2
std: Stabilize feature try_reserve_2 This PR intends to stabilize feature `try_reserve_2`, closes https://github.com/rust-lang/rust/issues/91789 This PR will also replace the previous PR: https://github.com/rust-lang/rust/pull/95139
2022-06-16btree: avoid forcing the allocator to be a referenceRalf Jung-241/+264
2022-06-16Rollup merge of #98125 - KarlWithK:entry_add_modify_doc, r=Dylan-DPCMatthias Krüger-1/+6
Entry and_modify doc This PR modifies the documentation for [HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html#) and [BTreeMap](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#) by introducing examples for `and_modify`. `and_modify` is a function that tends to give more idiomatic rust code when dealing with these data structures -- yet it lacked examples and was hidden away. This PR adds that and addresses #98122. I've made some choices which I tried to explain in my commits. This is my first time contributing to rust, so hopefully, I made the right choices.
2022-06-16std: Stabilize feature try_reserve_2Xuanwo-4/+2
Signed-off-by: Xuanwo <github@xuanwo.io>
2022-06-15change "1" to "c" to pass testKarlWithK-1/+1
Incorrectly wrote "1" twice when writing test.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-03 04:15:23 +0000