Refactor vtable encoding and optimize it for the case of multiple marker traits #113856

WaffleLapkin · 2023-07-19T12:15:59Z

This PR does two things

Refactor prepare_vtable_segments (this was motivated by the other change, prepare_vtable_segments was quite hard to understand and while trying to edit it I've refactored it)
- Mostly remove loops labeled breaks/continues whenever there is a simpler solution
- Also use ?
Make vtable format a bit more efficient wrt to marker traits
- See the tests for an example

Review wise it's probably best to review each commit individually, as then it's more clear why the refactoring is correct.

I can split the last two commits (which change behavior) into a separate PR if it makes reviewing easier

I always forget what the `bool` means :/

Reasoning: if the stack is empty, the loop will be infinite, so the assumption is that the stack can't be non empty. Unwrap makes the assumption more clear (and removes an indentation level)

Less explicit loops -- easier to read.

1. Hide the option as an iterator, so it's nicer to work with 2. Replace a loop with `find`

rustbot · 2023-07-19T12:16:05Z

r? @oli-obk

(rustbot has picked a reviewer for you, use r? to override)

oli-obk · 2023-07-20T15:17:28Z

That was a pleasure to review. I had several comments, and subsequent commits resolved them, so now I got nothing.

@bors r+ rollup=never (theoretical perf impact and changing vtable layout could be desirable to get bisected in the future)

bors · 2023-07-20T15:17:30Z

📌 Commit 1f02c75 has been approved by oli-obk

It is now in the queue for this repository.

bors · 2023-07-20T20:34:10Z

⌛ Testing commit 1f02c75 with merge 399b068...

bors · 2023-07-20T22:22:25Z

☀️ Test successful - checks-actions
Approved by: oli-obk
Pushing 399b068 to master...

rust-timer · 2023-07-21T00:42:57Z

Finished benchmarking commit (399b068): comparison URL.

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

@rustbot label: -perf-regression

Instruction count

This is a highly reliable metric that was used to determine the overall result at the top of this comment.

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

Max RSS (memory usage)

Results

This is a less reliable metric that may be of interest but was not used to determine the overall result at the top of this comment.

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

Cycles

Results

This is a less reliable metric that may be of interest but was not used to determine the overall result at the top of this comment.

	mean	range	count
Regressions ❌ (primary)	3.7%	[1.3%, 4.8%]	7
Regressions ❌ (secondary)	1.1%	[1.1%, 1.1%]	1
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	3.7%	[1.3%, 4.8%]	7

Binary size

Results

This is a less reliable metric that may be of interest but was not used to determine the overall result at the top of this comment.

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

Bootstrap: 648.763s -> 650.713s (0.30%)

nbdd0121 · 2023-08-09T15:54:34Z

tests/ui/traits/vtable/multiple-markers.stderr

           Method(<S as T>::method),
-           TraitVPtr(<S as T>),
           TraitVPtr(<S as M2>),


Why is TraitVPtr needed for M2?

The short answer: it is not needed. The longer answer is that we currently keep the order of all things from the traits, so since M2 comes after T, it can't be inlined there. I've filled #114942 to track this.

…mpiler-errors When determining if a trait has no entries for the purposes of omitting vptrs from subtrait vtables, consider its transitive supertraits' entries, instead of just its own entries. When determining if a non-first supertrait vptr can be omitted from a subtrait vtable, check if the supertrait or any of its (transitive) supertraits have methods, instead of only checking if the supertrait itself has methods. This fixes the soundness issue where a vptr would be omitted for a supertrait with no methods but that itself had a supertrait with methods, while still optimizing the case where the supertrait is "truly" empty (it has no own vtable entries, and none of its (transitive) supertraits have any own vtable entries). Fixes <#145752> ----- Old description: ~~Treat all non-auto traits as non-empty (possibly having methods) for purposes of determining if we need to emit a vptr for a non-direct supertrait (and for new "sibling" entries after a direct or non-direct supertrait).~~ This fixes (I believe) the soundness issue, ~~but regresses vtable sizes and possibly upcasting perf in some cases when using trait hierarchies with empty non-auto traits (see `tests/ui/traits/vtable/multiple-markers.stderr`) since we use vptrs in some cases where we could re-use the vtable.~~ Fixes <#145752> Re-opens (not anymore) <#114942> Should not affect <#131813> (i.e. the soundness issue is still fixed, ~~though the relevant vtables in the `trait Evil` example will be larger now~~) cc implementation history <#131864> <#113856> ----- ~~It should be possible to check if a trait has any methods from itself *or* supertraits (instead of just from itself), but to fix the immediate soundness issue, just assume any non-auto trait could have methods. A more optimistic check can be implemented later (or if someone does it soon it could just supercede this PR 😄).~~ Done in latest push `@rustbot` label A-dyn-trait F-trait_upcasting

…mpiler-errors When determining if a trait has no entries for the purposes of omitting vptrs from subtrait vtables, consider its transitive supertraits' entries, instead of just its own entries. When determining if a non-first supertrait vptr can be omitted from a subtrait vtable, check if the supertrait or any of its (transitive) supertraits have methods, instead of only checking if the supertrait itself has methods. This fixes the soundness issue where a vptr would be omitted for a supertrait with no methods but that itself had a supertrait with methods, while still optimizing the case where the supertrait is "truly" empty (it has no own vtable entries, and none of its (transitive) supertraits have any own vtable entries). Fixes <rust-lang/rust#145752> ----- Old description: ~~Treat all non-auto traits as non-empty (possibly having methods) for purposes of determining if we need to emit a vptr for a non-direct supertrait (and for new "sibling" entries after a direct or non-direct supertrait).~~ This fixes (I believe) the soundness issue, ~~but regresses vtable sizes and possibly upcasting perf in some cases when using trait hierarchies with empty non-auto traits (see `tests/ui/traits/vtable/multiple-markers.stderr`) since we use vptrs in some cases where we could re-use the vtable.~~ Fixes <rust-lang/rust#145752> Re-opens (not anymore) <rust-lang/rust#114942> Should not affect <rust-lang/rust#131813> (i.e. the soundness issue is still fixed, ~~though the relevant vtables in the `trait Evil` example will be larger now~~) cc implementation history <rust-lang/rust#131864> <rust-lang/rust#113856> ----- ~~It should be possible to check if a trait has any methods from itself *or* supertraits (instead of just from itself), but to fix the immediate soundness issue, just assume any non-auto trait could have methods. A more optimistic check can be implemented later (or if someone does it soon it could just supercede this PR 😄).~~ Done in latest push `@rustbot` label A-dyn-trait F-trait_upcasting

WaffleLapkin added 9 commits July 19, 2023 09:44

Document PredicateSet::insert

eabd306

I always forget what the `bool` means :/

Use ? in prepare_vtable_segments

348f26e

Replace if let with unwrap in prepare_vtable_segments

f8f5d7a

Reasoning: if the stack is empty, the loop will be infinite, so the assumption is that the stack can't be non empty. Unwrap makes the assumption more clear (and removes an indentation level)

Refactor 'diving_in loop internals in prepare_vtable_segments

364fc44

Less explicit loops -- easier to read.

Slightly refactor 'exiting_out loop in prepare_vtable_segments

d567f0f

1. Hide the option as an iterator, so it's nicer to work with 2. Replace a loop with `find`

Simplify last prepare_vtable_segments loop even more

d87db8e

Fix comment

f33936c

Add a (failing test) for issue 113840

b5d1228

Don't emit useless vptrs for marker traits

1f02c75

rustbot assigned oli-obk Jul 19, 2023

rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels Jul 19, 2023

WaffleLapkin added the F-trait_upcasting `#![feature(trait_upcasting)]` label Jul 19, 2023

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-review Status: Awaiting review from the assignee but also interested parties. labels Jul 20, 2023

bors added the merged-by-bors This PR was explicitly merged by bors. label Jul 20, 2023

bors merged commit 399b068 into rust-lang:master Jul 20, 2023

rustbot added this to the 1.73.0 milestone Jul 20, 2023

WaffleLapkin deleted the vtablin' branch July 20, 2023 22:27

Urgau mentioned this pull request Jul 21, 2023

add feature gate to permit measuring memory usage of dyn upcasting #112355

Closed

nbdd0121 reviewed Aug 9, 2023

View reviewed changes

WaffleLapkin mentioned this pull request Aug 17, 2023

Imperfect vtable layout with an empty super trait comming after non-empty one #114942

Closed

zachs18 mentioned this pull request Aug 24, 2025

When determining if a trait has no entries for the purposes of omitting vptrs from subtrait vtables, consider its transitive supertraits' entries, instead of just its own entries. #145807

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Refactor vtable encoding and optimize it for the case of multiple marker traits #113856

Refactor vtable encoding and optimize it for the case of multiple marker traits #113856

Uh oh!

WaffleLapkin commented Jul 19, 2023 •

edited

Loading

Uh oh!

rustbot commented Jul 19, 2023

Uh oh!

oli-obk commented Jul 20, 2023

Uh oh!

bors commented Jul 20, 2023

Uh oh!

bors commented Jul 20, 2023

Uh oh!

bors commented Jul 20, 2023

Uh oh!

rust-timer commented Jul 21, 2023

Uh oh!

nbdd0121 Aug 9, 2023

Uh oh!

WaffleLapkin Aug 17, 2023

Uh oh!

Uh oh!

Refactor vtable encoding and optimize it for the case of multiple marker traits #113856

Refactor vtable encoding and optimize it for the case of multiple marker traits #113856

Uh oh!

Conversation

WaffleLapkin commented Jul 19, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

rustbot commented Jul 19, 2023

Uh oh!

oli-obk commented Jul 20, 2023

Uh oh!

bors commented Jul 20, 2023

Uh oh!

bors commented Jul 20, 2023

Uh oh!

bors commented Jul 20, 2023

Uh oh!

rust-timer commented Jul 21, 2023

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

Instruction count

Max RSS (memory usage)

Cycles

Binary size

Uh oh!

nbdd0121 Aug 9, 2023

Choose a reason for hiding this comment

Uh oh!

WaffleLapkin Aug 17, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

WaffleLapkin commented Jul 19, 2023 •

edited

Loading