Improve alloc `Vec::retain_mut` performance #149784

fereidani · 2025-12-08T19:46:35Z

Hi,

While reading the rustc source code, I noticed it uses smallvec and thin-vec in many places. I started reviewing those crates, optimized their retain_mut implementation, and then realized they were using the exact same algorithm as alloc::vec::Vec with less unsafe So now I’m back here with a PR for the standard library 😂.

In my benchmarks, this version is noticeably faster when retain_mut actually removes elements (thanks to fewer pointer operations, it just advances write_index), while performing identically to the current implementation when nothing is removed.

Let’s see if bors likes this change or not.

rustbot · 2025-12-08T19:46:39Z

r? @joboet

rustbot has assigned @joboet.
They will have a look at your PR within the next two weeks and either review your PR or reassign to another reviewer.

Use r? to explicitly pick a reviewer

fereidani · 2025-12-08T21:45:22Z

@bors try @rust-timer queue

rust-bors · 2025-12-08T21:45:25Z

@fereidani: 🔑 Insufficient privileges: not in try users

Kivooeo · 2025-12-08T23:16:42Z

@bors try @rust-timer queue

Improve alloc `Vec::retain_mut` performance

rust-bors · 2025-12-09T01:34:10Z

☀️ Try build successful (CI)
Build commit: 060d14c (060d14cd2be739e62dd1e1c6daeb2b80ec651c10, parent: 37aa2135b5d0936bd13aa699d941aaa94fbaa645)

rust-timer · 2025-12-09T02:17:38Z

Finished benchmarking commit (060d14c): comparison URL.

Overall result: ❌ regressions - no action needed

Benchmarking this pull request means it may be perf-sensitive – we'll automatically label it not fit for rolling up. You can override this, but we strongly advise not to, due to possible changes in compiler perf.

@bors rollup=never
@rustbot label: -S-waiting-on-perf -perf-regression

Instruction count

Our most reliable metric. Used to determine the overall result above. However, even this metric can be noisy.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	0.4%	[0.3%, 0.5%]	2
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	-	-	0

Max RSS (memory usage)

Results (primary -3.0%, secondary 6.7%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	6.7%	[6.7%, 6.7%]	1
Improvements ✅ (primary)	-3.0%	[-4.5%, -1.5%]	2
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	-3.0%	[-4.5%, -1.5%]	2

Cycles

Results (primary 3.0%, secondary -2.8%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	3.0%	[2.0%, 4.9%]	3
Regressions ❌ (secondary)	-	-	0
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-2.8%	[-3.1%, -2.4%]	3
All ❌✅ (primary)	3.0%	[2.0%, 4.9%]	3

Binary size

Results (primary -0.1%, secondary -0.1%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	-	-	0
Improvements ✅ (primary)	-0.1%	[-0.1%, -0.0%]	41
Improvements ✅ (secondary)	-0.1%	[-0.1%, -0.0%]	24
All ❌✅ (primary)	-0.1%	[-0.1%, -0.0%]	41

Bootstrap: 470.452s -> 473.09s (0.56%)
Artifact size: 389.00 MiB -> 388.97 MiB (-0.01%)

Kivooeo · 2025-12-09T12:21:06Z

is it ready for another perf run?

fereidani · 2025-12-09T12:22:21Z

@Kivooeo Yes, Thank you!

Kivooeo · 2025-12-09T12:23:02Z

@bors try @rust-timer queue

Improve alloc `Vec::retain_mut` performance

rust-bors · 2025-12-09T14:37:53Z

☀️ Try build successful (CI)
Build commit: 3ec64be (3ec64beb1b3da0ca553fcc7f6fb4e8f036199568, parent: d5525a73009e2c61b09daa69df79064530bd4dcf)

rust-timer · 2025-12-09T15:18:52Z

Finished benchmarking commit (3ec64be): comparison URL.

Overall result: ❌✅ regressions and improvements - no action needed

Benchmarking this pull request means it may be perf-sensitive – we'll automatically label it not fit for rolling up. You can override this, but we strongly advise not to, due to possible changes in compiler perf.

@bors rollup=never
@rustbot label: -S-waiting-on-perf -perf-regression

Instruction count

Our most reliable metric. Used to determine the overall result above. However, even this metric can be noisy.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	0.3%	[0.1%, 0.5%]	3
Improvements ✅ (primary)	-0.2%	[-0.2%, -0.2%]	1
Improvements ✅ (secondary)	-0.1%	[-0.1%, -0.1%]	1
All ❌✅ (primary)	-0.2%	[-0.2%, -0.2%]	1

Max RSS (memory usage)

Results (primary -2.3%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	-	-	0
Improvements ✅ (primary)	-2.3%	[-2.7%, -1.9%]	2
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	-2.3%	[-2.7%, -1.9%]	2

Cycles

Results (secondary 1.0%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	2.7%	[2.3%, 3.1%]	2
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-2.5%	[-2.5%, -2.5%]	1
All ❌✅ (primary)	-	-	0

Binary size

This benchmark run did not return any relevant results for this metric.

Bootstrap: 472.272s -> 473.265s (0.21%)
Artifact size: 389.04 MiB -> 388.98 MiB (-0.02%)

rustbot · 2026-01-04T02:00:14Z

This PR was rebased onto a different main commit. Here's a range-diff highlighting what actually changed.

Rebasing is a normal part of keeping PRs up to date, so no action is needed—this note is just to help reviewers.

joboet

The algorithm looks great now, thanks. Just a few nits...

View changes since this review

library/alloc/src/vec/mod.rs

fereidani · 2026-01-05T00:14:12Z

I also applied your requested changes for #150067 , our other similar PR to improve same algorithm for String::retain.

joboet

One nit remaining. And could you squash your commits, please?

View changes since this review

library/alloc/src/vec/mod.rs

fereidani · 2026-01-05T09:58:49Z

Sure thing! It is done. Thank you for reviewing this PR.

joboet · 2026-01-05T12:13:33Z

Alright, let's merge this...
@bors r+

bors · 2026-01-05T12:13:35Z

📌 Commit bd79ea1 has been approved by joboet

It is now in the queue for this repository.

bors · 2026-01-05T14:55:18Z

⌛ Testing commit bd79ea1 with merge bd33b83...

bors · 2026-01-05T18:12:37Z

☀️ Test successful - checks-actions
Approved by: joboet
Pushing bd33b83 to main...

github-actions · 2026-01-05T18:15:19Z

What is this?

This is an experimental post-merge analysis report that shows differences in test outcomes between the merged PR and its parent PR.

Comparing b7bcaa5 (parent) -> bd33b83 (this PR)

Test differences

Show 199 test diffs

199 doctest diffs were found. These are ignored, as they are noisy.

Test dashboard

Run

cargo run --manifest-path src/ci/citool/Cargo.toml -- \
    test-dashboard bd33b83cfdbac9bffa3b04aaef95ec97827909a9 --output-dir test-dashboard

And then open test-dashboard/index.html in your browser to see an overview of all executed tests.

Job duration changes

aarch64-apple: 9624.5s -> 11413.4s (+18.6%)
dist-apple-various: 4358.9s -> 3580.3s (-17.9%)
x86_64-gnu-llvm-20-3: 6125.0s -> 7024.6s (+14.7%)
dist-loongarch64-linux: 6269.6s -> 5391.6s (-14.0%)
test-various: 6626.0s -> 7497.7s (+13.2%)
dist-ohos-armv7: 4519.0s -> 4009.5s (-11.3%)
dist-powerpc64le-linux-gnu: 5765.8s -> 5228.0s (-9.3%)
x86_64-msvc-1: 9353.2s -> 8511.0s (-9.0%)
i686-gnu-nopt-1: 6827.1s -> 7432.7s (+8.9%)
dist-powerpc64le-linux-musl: 5712.6s -> 5212.3s (-8.8%)

How to interpret the job duration changes?

Job durations can vary a lot, based on the actual runner instance
that executed the job, system noise, invalidated caches, etc. The table above is provided
mostly for t-infra members, for simpler debugging of potential CI slow-downs.

rust-timer · 2026-01-05T18:54:00Z

Finished benchmarking commit (bd33b83): comparison URL.

Overall result: ❌ regressions - no action needed

@rustbot label: -perf-regression

Instruction count

Our most reliable metric. Used to determine the overall result above. However, even this metric can be noisy.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	0.6%	[0.5%, 0.6%]	3
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	-	-	0

Max RSS (memory usage)

Results (primary -2.5%, secondary -0.1%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	3.2%	[2.8%, 3.6%]	2
Improvements ✅ (primary)	-2.5%	[-2.5%, -2.5%]	1
Improvements ✅ (secondary)	-2.3%	[-2.5%, -2.0%]	3
All ❌✅ (primary)	-2.5%	[-2.5%, -2.5%]	1

Cycles

Results (primary 2.7%, secondary -1.6%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	2.7%	[2.0%, 3.3%]	2
Regressions ❌ (secondary)	2.7%	[2.7%, 2.7%]	1
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-3.8%	[-4.1%, -3.4%]	2
All ❌✅ (primary)	2.7%	[2.0%, 3.3%]	2

Binary size

Results (primary 0.0%, secondary 0.0%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	0.0%	[0.0%, 0.0%]	4
Regressions ❌ (secondary)	0.0%	[0.0%, 0.1%]	13
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	0.0%	[0.0%, 0.0%]	4

Bootstrap: 474.563s -> 473.344s (-0.26%)
Artifact size: 390.70 MiB -> 390.72 MiB (0.01%)

rustbot assigned joboet Dec 8, 2025

rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-libs Relevant to the library team, which will review and decide on the PR/issue. labels Dec 8, 2025

This comment has been minimized.

Sign in to view

rust-bors bot added a commit that referenced this pull request Dec 8, 2025

Auto merge of #149784 - fereidani:retain_mut, r=<try>

060d14c

Improve alloc `Vec::retain_mut` performance

rustbot added the S-waiting-on-perf Status: Waiting on a perf run to be completed. label Dec 8, 2025

This comment has been minimized.

Sign in to view

rustbot removed the S-waiting-on-perf Status: Waiting on a perf run to be completed. label Dec 9, 2025

This comment has been minimized.

Sign in to view

rust-bors bot added a commit that referenced this pull request Dec 9, 2025

Auto merge of #149784 - fereidani:retain_mut, r=<try>

3ec64be

Improve alloc `Vec::retain_mut` performance

This comment has been minimized.

Sign in to view

rustbot added the S-waiting-on-perf Status: Waiting on a perf run to be completed. label Dec 9, 2025

This comment has been minimized.

Sign in to view

rustbot removed the S-waiting-on-perf Status: Waiting on a perf run to be completed. label Dec 9, 2025

rustbot added the S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. label Dec 31, 2025

This comment has been minimized.

Sign in to view

rustbot added the has-merge-commits PR has merge commits, merge with caution. label Jan 3, 2026

fereidani force-pushed the retain_mut branch from 2042e64 to e8a85b6 Compare January 4, 2026 02:00

rustbot removed S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. has-merge-commits PR has merge commits, merge with caution. labels Jan 4, 2026

fereidani requested a review from joboet January 4, 2026 04:31

rustbot added the S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. label Jan 4, 2026

joboet requested changes Jan 4, 2026

View reviewed changes

library/alloc/src/vec/mod.rs Outdated Show resolved Hide resolved

library/alloc/src/vec/mod.rs Outdated Show resolved Hide resolved

library/alloc/src/vec/mod.rs Outdated Show resolved Hide resolved

library/alloc/src/vec/mod.rs Outdated Show resolved Hide resolved

rustbot added S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. and removed S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. labels Jan 4, 2026

joboet approved these changes Jan 5, 2026

View reviewed changes

library/alloc/src/vec/mod.rs Outdated Show resolved Hide resolved

fereidani added 2 commits January 5, 2026 13:14

Add feature flag likely/unlikely for alloc

0330cc2

Improve and optimize retain_mut implementation

bd79ea1

fereidani force-pushed the retain_mut branch from 67dabd5 to bd79ea1 Compare January 5, 2026 09:49

bors added S-waiting-on-bors Status: Waiting on bors to run and complete tests. Bors will change the label on completion. and removed S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. labels Jan 5, 2026

bors added the merged-by-bors This PR was explicitly merged by bors. label Jan 5, 2026

bors merged commit bd33b83 into rust-lang:main Jan 5, 2026
12 checks passed

rustbot added this to the 1.94.0 milestone Jan 5, 2026

Uh oh!

Improve alloc Vec::retain_mut performance #149784

Improve alloc Vec::retain_mut performance #149784

Uh oh!

Conversation

fereidani commented Dec 8, 2025

Uh oh!

rustbot commented Dec 8, 2025

Uh oh!

This comment has been minimized.

This comment has been minimized.

fereidani commented Dec 8, 2025

Uh oh!

This comment has been minimized.

rust-bors bot commented Dec 8, 2025

Uh oh!

Kivooeo commented Dec 8, 2025

Uh oh!

This comment has been minimized.

This comment has been minimized.

rust-bors bot commented Dec 9, 2025

Uh oh!

This comment has been minimized.

rust-timer commented Dec 9, 2025

Overall result: ❌ regressions - no action needed

Uh oh!

This comment has been minimized.

Kivooeo commented Dec 9, 2025

Uh oh!

fereidani commented Dec 9, 2025

Uh oh!

Kivooeo commented Dec 9, 2025

Uh oh!

This comment has been minimized.

This comment has been minimized.

rust-bors bot commented Dec 9, 2025

Uh oh!

This comment has been minimized.

rust-timer commented Dec 9, 2025

Overall result: ❌✅ regressions and improvements - no action needed

Uh oh!

This comment has been minimized.

This comment has been minimized.

rustbot commented Jan 4, 2026

Uh oh!

joboet left a comment • edited by rustbot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

fereidani commented Jan 5, 2026

Uh oh!

joboet left a comment • edited by rustbot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

fereidani commented Jan 5, 2026

Uh oh!

joboet commented Jan 5, 2026

Uh oh!

bors commented Jan 5, 2026

Uh oh!

bors commented Jan 5, 2026

Uh oh!

bors commented Jan 5, 2026

Uh oh!

Uh oh!

github-actions bot commented Jan 5, 2026

Test differences

Job duration changes

Uh oh!

rust-timer commented Jan 5, 2026

Overall result: ❌ regressions - no action needed

Uh oh!

Reviewers

Assignees

Improve alloc `Vec::retain_mut` performance #149784

Improve alloc `Vec::retain_mut` performance #149784

joboet left a comment •

edited by rustbot

Loading

joboet left a comment •

edited by rustbot

Loading