summary refs log tree commit diff
path: root/library/alloc/src/vec
AgeCommit message (Collapse)AuthorLines
2024-01-25fix: Drop guard was deallocating with the incorrect sizeThe 8472-13/+25
InPlaceDstBufDrop holds onto the allocation before the shrinking happens which means it must deallocate the destination elements but the source allocation. (cherry picked from commit 5796b3c16733f3d9cb2f3476ed1dc0fe05b14e25)
2024-01-25remove alignment-changing in-place collectThe 8472-5/+8
Currently stable users can't benefit from this because GlobaAlloc doesn't support alignment-changing realloc and neither do most posix allocators. So in practice it always results in an extra memcpy. (cherry picked from commit 85d17879623116be76a68c2170c4cb6ff58f4ceb)
2024-01-25update internal ASCII art comment for vec specializationsThe 8472-7/+7
(cherry picked from commit b28a95391b85e17b1d2f7edc1115291d8a86bcd2)
2023-12-06Auto merge of #118460 - the8472:fix-vec-realloc, r=saethlinbors-7/+27
Fix in-place collect not reallocating when necessary Regression introduced in https://github.com/rust-lang/rust/pull/110353. This was [caught by miri](https://rust-lang.zulipchat.com/#narrow/stream/269128-miri/topic/Cron.20Job.20Failure.20.28miri-test-libstd.2C.202023-11.29/near/404764617) r? `@saethlin`
2023-12-05Auto merge of #118273 - AngelicosPhosphoros:dedup_2_loops_version_77772_2, ↵bors-12/+45
r=the8472 Split `Vec::dedup_by` into 2 cycles First cycle runs until we found 2 same elements, second runs after if there any found in the first one. This allows to avoid any memory writes until we found an item which we want to remove. This leads to significant performance gains if all `Vec` items are kept: -40% on my benchmark with unique integers. Results of benchmarks before implementation (including new benchmark where nothing needs to be removed): * vec::bench_dedup_all_100 74.00ns/iter +/- 13.00ns * vec::bench_dedup_all_1000 572.00ns/iter +/- 272.00ns * vec::bench_dedup_all_100000 64.42µs/iter +/- 19.47µs * __vec::bench_dedup_none_100 67.00ns/iter +/- 17.00ns__ * __vec::bench_dedup_none_1000 662.00ns/iter +/- 86.00ns__ * __vec::bench_dedup_none_10000 9.16µs/iter +/- 2.71µs__ * __vec::bench_dedup_none_100000 91.25µs/iter +/- 1.82µs__ * vec::bench_dedup_random_100 105.00ns/iter +/- 11.00ns * vec::bench_dedup_random_1000 781.00ns/iter +/- 10.00ns * vec::bench_dedup_random_10000 9.00µs/iter +/- 5.62µs * vec::bench_dedup_random_100000 449.81µs/iter +/- 74.99µs * vec::bench_dedup_slice_truncate_100 105.00ns/iter +/- 16.00ns * vec::bench_dedup_slice_truncate_1000 2.65µs/iter +/- 481.00ns * vec::bench_dedup_slice_truncate_10000 18.33µs/iter +/- 5.23µs * vec::bench_dedup_slice_truncate_100000 501.12µs/iter +/- 46.97µs Results after implementation: * vec::bench_dedup_all_100 75.00ns/iter +/- 9.00ns * vec::bench_dedup_all_1000 494.00ns/iter +/- 117.00ns * vec::bench_dedup_all_100000 58.13µs/iter +/- 8.78µs * __vec::bench_dedup_none_100 52.00ns/iter +/- 22.00ns__ * __vec::bench_dedup_none_1000 417.00ns/iter +/- 116.00ns__ * __vec::bench_dedup_none_10000 4.11µs/iter +/- 546.00ns__ * __vec::bench_dedup_none_100000 40.47µs/iter +/- 5.36µs__ * vec::bench_dedup_random_100 77.00ns/iter +/- 15.00ns * vec::bench_dedup_random_1000 681.00ns/iter +/- 86.00ns * vec::bench_dedup_random_10000 11.66µs/iter +/- 2.22µs * vec::bench_dedup_random_100000 469.35µs/iter +/- 20.53µs * vec::bench_dedup_slice_truncate_100 100.00ns/iter +/- 5.00ns * vec::bench_dedup_slice_truncate_1000 2.55µs/iter +/- 224.00ns * vec::bench_dedup_slice_truncate_10000 18.95µs/iter +/- 2.59µs * vec::bench_dedup_slice_truncate_100000 492.85µs/iter +/- 72.84µs Resolves #77772 P.S. Note that this is same PR as #92104 I just missed review then forgot about it. Also, I cannot reopen that pull request so I am creating a new one. I responded to remaining questions directly by adding commentaries to my code.
2023-12-05Split `Vec::dedup_by` into 2 cyclesAngelicosPhosphoros-12/+45
First cycle runs until we found 2 same elements, second runs after if there any found in the first one. This allows to avoid any memory writes until we found an item which we want to remove. This leads to significant performance gains if all `Vec` items are kept: -40% on my benchmark with unique integers. Results of benchmarks before implementation (including new benchmark where nothing needs to be removed): * vec::bench_dedup_all_100 74.00ns/iter +/- 13.00ns * vec::bench_dedup_all_1000 572.00ns/iter +/- 272.00ns * vec::bench_dedup_all_100000 64.42µs/iter +/- 19.47µs * __vec::bench_dedup_none_100 67.00ns/iter +/- 17.00ns__ * __vec::bench_dedup_none_1000 662.00ns/iter +/- 86.00ns__ * __vec::bench_dedup_none_10000 9.16µs/iter +/- 2.71µs__ * __vec::bench_dedup_none_100000 91.25µs/iter +/- 1.82µs__ * vec::bench_dedup_random_100 105.00ns/iter +/- 11.00ns * vec::bench_dedup_random_1000 781.00ns/iter +/- 10.00ns * vec::bench_dedup_random_10000 9.00µs/iter +/- 5.62µs * vec::bench_dedup_random_100000 449.81µs/iter +/- 74.99µs * vec::bench_dedup_slice_truncate_100 105.00ns/iter +/- 16.00ns * vec::bench_dedup_slice_truncate_1000 2.65µs/iter +/- 481.00ns * vec::bench_dedup_slice_truncate_10000 18.33µs/iter +/- 5.23µs * vec::bench_dedup_slice_truncate_100000 501.12µs/iter +/- 46.97µs Results after implementation: * vec::bench_dedup_all_100 75.00ns/iter +/- 9.00ns * vec::bench_dedup_all_1000 494.00ns/iter +/- 117.00ns * vec::bench_dedup_all_100000 58.13µs/iter +/- 8.78µs * __vec::bench_dedup_none_100 52.00ns/iter +/- 22.00ns__ * __vec::bench_dedup_none_1000 417.00ns/iter +/- 116.00ns__ * __vec::bench_dedup_none_10000 4.11µs/iter +/- 546.00ns__ * __vec::bench_dedup_none_100000 40.47µs/iter +/- 5.36µs__ * vec::bench_dedup_random_100 77.00ns/iter +/- 15.00ns * vec::bench_dedup_random_1000 681.00ns/iter +/- 86.00ns * vec::bench_dedup_random_10000 11.66µs/iter +/- 2.22µs * vec::bench_dedup_random_100000 469.35µs/iter +/- 20.53µs * vec::bench_dedup_slice_truncate_100 100.00ns/iter +/- 5.00ns * vec::bench_dedup_slice_truncate_1000 2.55µs/iter +/- 224.00ns * vec::bench_dedup_slice_truncate_10000 18.95µs/iter +/- 2.59µs * vec::bench_dedup_slice_truncate_100000 492.85µs/iter +/- 72.84µs Resolves #77772
2023-12-05Fix in-place collect not reallocating when necessaryThe 8472-7/+27
2023-11-29Rollup merge of #118398 - mu001999:std/add_cfgs, r=thomccMatthias Krüger-0/+5
Add proper cfgs in std Detected by #118257
2023-11-28Auto merge of #110353 - the8472:in-place-flatten-chunks, r=cuviperbors-27/+118
Expand in-place iteration specialization to Flatten, FlatMap and ArrayChunks This enables the following cases to collect in-place: ```rust let v = vec![[0u8; 4]; 1024] let v: Vec<_> = v.into_iter().flatten().collect(); let v: Vec<Option<NonZeroUsize>> = vec![NonZeroUsize::new(0); 1024]; let v: Vec<_> = v.into_iter().flatten().collect(); let v = vec![u8; 4096]; let v: Vec<_> = v.into_iter().array_chunks::<4>().collect(); ``` Especially the nicheful-option-flattening should be useful in real code.
2023-11-28Add proper cfgsr0cky-0/+5
2023-11-20docs(GH-118094): make docs a bit more explicitPetr Portnov-3/+3
Signed-off-by: Petr Portnov <me@progrm-jarvis.ru>
2023-11-20chore(GH-118094): explicitly mark `_elem` as unusedPetr Portnov-1/+1
Signed-off-by: Petr Portnov <me@progrm-jarvis.ru>
2023-11-20feat: specialize `SpecFromElem` for `()`Petr Portnov-4/+19
While a better approach would be to implement it for all ZSTs which are `Copy` and have trivial `Clone`, the last property cannot be detected for now. Signed-off-by: Petr Portnov <me@progrm-jarvis.ru>
2023-11-15Re-format code with new rustfmtMark Rousskov-3/+1
2023-11-02Add insta-stable std::hash::{DefaultHasher, RandomState} exportsltdk-1/+1
2023-10-29Increase the reach of panic_immediate_abortBen Kimock-4/+7
2023-10-16Add invariant to Vec::pop that len < cap if pop successfulArthur Carcano-0/+1
Fixes: https://github.com/rust-lang/rust/issues/114334
2023-10-08Bump to latest betaMark Rousskov-2/+2
2023-10-03Bump version placeholdersMark Rousskov-2/+2
2023-09-28Auto merge of #111278 - EFanZh:implement-from-array-refs-for-vec, r=dtolnaybors-0/+30
Implement `From<{&,&mut} [T; N]>` for `Vec<T>` where `T: Clone` Currently, if `T` implements `Clone`, we can create a `Vec<T>` from an `&[T]` or an `&mut [T]`, can we also support creating a `Vec<T>` from an `&[T; N]` or an `&mut [T; N]`? Also, do I need to add `#[inline]` to the implementation? ACP: rust-lang/libs-team#220. [Accepted] Closes #100880.
2023-09-16edit `std::vec::Vec::truncate` docsmxnkarou-2/+2
2023-09-16Auto merge of #114494 - est31:extend_useless_ptr_null_checks, r=jackh726bors-0/+2
Make useless_ptr_null_checks smarter about some std functions This teaches the `useless_ptr_null_checks` lint that some std functions can't ever return null pointers, because they need to point to valid data, get references as input, etc. This is achieved by introducing an `#[rustc_never_returns_null_ptr]` attribute and adding it to these std functions (gated behind bootstrap `cfg_attr`). Later on, the attribute could maybe be used to tell LLVM that the returned pointer is never null. I don't expect much impact of that though, as the functions are pretty shallow and usually the input data is already never null. Follow-up of PR #113657 Fixes #114442
2023-09-03unchecked layout calculations when shrinking during in-place collectThe 8472-2/+12
Reduces the amount of emitted IR. RawVec has similar optimizations
2023-09-03relax size and alignment requirements for in-place iterationThe 8472-8/+11
2023-09-03update in-place-iteration module docsThe 8472-8/+25
2023-09-03don't leak items if alloc::shrink panicsThe 8472-2/+6
2023-09-03Expand in-place iteration specialization to Flatten, FlatMap and ArrayChunksThe 8472-19/+76
2023-08-29Auto merge of #113859 - Manishearth:vec-as-mut-ptr-stacked-borrow, r=dtolnaybors-0/+51
Add note that Vec::as_mut_ptr() does not materialize a reference to the internal buffer See discussion on https://github.com/thomcc/rust-typed-arena/issues/62 and [t-opsem](https://rust-lang.zulipchat.com/#narrow/stream/136281-t-opsem/topic/is.20this.20typed_arena.20code.20sound.20under.20stacked.2Ftree.20borrows.3F) This method already does the correct thing here, but it is worth guaranteeing that it does so it can be used more freely in unsafe code without having to worry about potential Stacked/Tree Borrows violations. This moves one more unsafe usage pattern from the "very likely sound but technically not fully defined" box into "definitely sound", and currently our surface area of the latter is woefully small. I'm not sure how best to word this, opening this PR as a way to start discussion.
2023-08-16Update library/alloc/src/vec/mod.rsManish Goregaokar-1/+1
Co-authored-by: Ralf Jung <post@ralfj.de>
2023-08-16Update library/alloc/src/vec/mod.rsManish Goregaokar-1/+2
Co-authored-by: Ralf Jung <post@ralfj.de>
2023-08-15other elementsManish Goregaokar-3/+3
2023-08-15Update library/alloc/src/vec/mod.rsManish Goregaokar-1/+1
Co-authored-by: Ralf Jung <post@ralfj.de>
2023-08-15Update library/alloc/src/vec/mod.rsManish Goregaokar-1/+1
Co-authored-by: Ralf Jung <post@ralfj.de>
2023-08-12aliasing guaranteeManish Goregaokar-25/+40
2023-08-06Add #[rustc_never_returns_null_ptr] to std functionsest31-0/+2
Add the attribute to standard library functions that are guaranteed to never return null pointers, as their originating data wouldn't allow it.
2023-07-29Documentation: Fix Stilted Language in Vec->IndexingRyan O'Neill-1/+1
Problem Language in the Vec->Indexing documentation sounds stilted due to incorrect word ordering: "... type allows to access values by index." Solution Reorder words in the Vec->Indexing documentation to flow better: "... type allows access to values by index." The phrase "allows access to" also matches other existing documentation.
2023-07-25Add note that Vec::as_mut_ptr() does not materialize a reference to the ↵Manish Goregaokar-0/+35
internal buffer
2023-07-22Auto merge of #113224 - zachs18:vec_extend_remove_allocator_lifetime, r=cuviperbors-3/+3
Remove lifetime bound for A for `impl Extend<&'a T> for Vec<T, A>`. The lifetime of the references being copied from is unrelated to the allocator. Compare with [`impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A>`](https://doc.rust-lang.org/alloc/collections/vec_deque/struct.VecDeque.html#impl-Extend%3C%26'a+T%3E-for-VecDeque%3CT,+A%3E) which does not have the `A: 'a` bound already. Since `Allocator` is unstable, the only possible `A` on stable is `Global`, and `Global: 'static`, so this change is not (should not be) observable on stable (or without `#![feature(allocator_api)]`). [This is observable on nightly](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=8c4aa166c6116a90593d2934d30cfeb3).
2023-07-16Implement `From<{&,&mut} [T; N]>` for `Vec<T>`EFanZh-0/+30
2023-07-01Remove lifetime bound for A for `impl Extend<&'a T> for Vec<T, A>`.Zachary S-3/+3
2023-06-29Fix document examples of Vec::from_raw_parts and Vec::from_raw_parts_inLi Zhanhui-14/+15
Signed-off-by: Li Zhanhui <lizhanhui@gmail.com>
2023-06-26Rollup merge of #112677 - the8472:remove-unusued-field, r=JohnTitorTakayuki Maeda-9/+1
remove unused field Followup to #104455. The field is no longer needed since ExtractIf (previously DrainFilter) doesn't keep draining in its drop impl.
2023-06-21Rollup merge of #112632 - gootorov:vec_alloc_partialeq, r=dtolnayNilstrieb-2/+7
Implement PartialOrd for `Vec`s over different allocators It is already possible to `PartialEq` `Vec`s with different allocators, but that is not the case with `PartialOrd`.
2023-06-18alloc: Implement PartialOrd for `Vec`s over different allocatorsIgor Gutorov-2/+7
2023-06-15remove unused fieldThe 8472-9/+1
since DrainFilter no longer continues draining when it's dropped the panic tracking is no longer needed.
2023-06-14s/drain_filter/extract_if/ for Vec, Btree{Map,Set} and LinkedListThe 8472-22/+22
2023-06-14remove drain-on-drop behavior from vec::DrainFilter and add #[must_use]The 8472-91/+21
2023-06-04Remove ExtendWith and ExtendElementGrisha Vartanyan-26/+10
2023-05-24Stabilize `BuildHasher::hash_one`Scott McMurray-1/+0
2023-05-23Rollup merge of #111609 - LegionMammal978:internal-unsafe, r=thomccDylan DPC-4/+5
Mark internal functions and traits unsafe to reflect preconditions No semantics are changed in this PR; I only mark some functions and and a trait `unsafe` which already had implicit preconditions. Although it seems somewhat redundant for `numfmt::Part::Copy` to contain a `&[u8]` instead of a `&str`, given that all of its current consumers ultimately expect valid UTF-8. Is the type also intended to work for byte-slice formatting in the future?
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-25 14:30:46 +0000