To put this in perspective, we are all already relying on basic optimizations to perform function inlining, convert stack values to registers, remove multiple layers of references, and so on.
3 Likes
One missed devirtualization opportunity is very unlikely to be a 10x drop in performance; on my laptop, for example, the worst case difference between a direct call and an indirect call is 22 clock cycles; that's the difference between a perfectly predicted direct call and an indirect branch where both the target and the condition are mispredicted.
It would be far more useful if, instead of requiring that a given optimization happens, you could put a compiler-checked "work limit" on a function such that you got a compiler error if the function would take too long. This work limit would have to be expressed in terms of the parameters to the function (e.g. "takes not more than self.foo * bar * TIME_PER_ITERATION + SETUP_TIME milliseconds on Apple Silicon M4"), not least because such a check would catch cases where devirtualization has happened because more important optimizations haven't fired when they should have done.
You would be surprised.
Let's speak about some real numbers:
| Operation | Approx. ticks |
|---|---|
Direct jmp — short or near |
~1–2 |
Indirect jmp rax / jmp [rax] |
~1–2 when predicted |
Direct call + ret |
~4–5 |
Indirect call + ret |
~4–5 when predicted |
Just because you using call instead jmp, it already would cost you x2 or x5 more.
Than when you doing calls, you my want to pass some arguments through stack, or at least push your register into stack for further use.
That's will cost you another 1.5 tick per every register or function argument.
| Operation | Approx. ticks |
|---|---|
push one 64-bit value |
~1 throughput cost |
pop one 64-bit value |
~0.5 throughput cost |
But the real problem not even here, the real problem will start to happen, when you will start dealing with pipeline reset due to wrong branch prediction or cache miss. In worse case it can cost you, not just x10 times but x100 time drop.
| Event | Approx. ticks | Approx. time |
|---|---|---|
| Wrong branch/target prediction | ~17–20 | ~4–5 ns |
| Pointer load: L1 hit | ~4 | ~1 ns |
| Pointer load: L1 miss → L2 hit | ~12 | ~3 ns |
| Pointer load: L2 miss → L3 hit | ~42 | ~10.5 ns |
| Pointer load: L3 miss → RAM | ~246 | ~61.5 ns |
This how it works, when you have static dispatch everywhere, and you code inlined, everything will run in collocated memory address space, once you will start doing dynamic dispatch, your code could be spread in many places, if your code just jumping to different random memory pages, instead of running everything in single one, you could exhaust your cache and especially L3 cache miss is dramaticall one.
That's was a theory, let speak about practice and some benchmarks.
Enum dispatch made a benchmark, and this their claim, that hey observing x10 drop on dynamic dispatch comparing to static dispatch.
- https://docs.rs/enum_dispatch/latest/enum_dispatch/
- https://docs.rs/enum_dispatch/latest/enum_dispatch/#the-benchmarks
Rust is built with philosophy of zero cost abstraction, is something could be done at compile time instead of runtime, why we should keep it at runtime, especially if it is philosophy of rust.
https://doc.rust-lang.org/beta/embedded-book/static-guarantees/zero-cost-abstractions.html
If performance and keeping runtime small is not really a concern, I don't really see a reason to consider rust then, we can do things in java or python much easier then.
And some information about typical size of L1-L3 caches on CPU:
| CPU class / example | L1 instruction + data, per core | L2 per core | L3 total per CPU |
|---|---|---|---|
| High-end server: AMD EPYC 9755, 128 cores | 32 KB + 48 KB | 1 MB | 512 MB, divided into 16 × 32 MB |
| High-end desktop: Ryzen 9 9950X, 16 cores | 32 KB + 48 KB | 1 MB | 64 MB, divided into 2 × 32 MB |
| Embedded Linux: Raspberry Pi 5, Cortex-A76 | 64 KB + 64 KB | 512 KB | 2 MB shared |
| Microcontroller: STM32H743, Cortex-M7 | 16 KB + 16 KB | None | None |
Missing 64MB of L3 cache miss even on Desktop is not that easy, but writing code for Raspberry PI you can easily get missed if it just 2MB of L3 cache.
Rust is about writing optimal code.
So when we speaking about High-end server: this 512MB L3 is shared for 128 cores, which could run very different workloads, that averages 4 MB of L3 per core, so problem is not really going away.
That is a microbenchmark - the best case on my CPU is 1 clock cycle for a direct jump (devirtualized), and the worst case is 22 clock cycles for an indirect jump that's fully mispredicted but in cache.
Obviously, if you have a cache miss in L1, times go up. enum_dispatch's benchmark shows that the penalty for genuinely random (thus unpredictable) dispatch, in a case where what you do is predominately dispatch (and no real work), your dynamic dispatch penalty is about 10x static dispatch, not the 22x difference between best case for static dispatch and worst case for dynamic dispatch.
BUT: we are not talking about the case where you're doing no work at all, by definition - we're talking about a case where the codebase has become so complex that the compiler can no longer see that static dispatch is an option. In that case, the cost of dispatch becomes negligible; your called and calling code is so complex and doing so much that a missed devirtualization is in the noise, as compared to other optimizations.
Hence me saying that what you want is not a guarantee that certain optimizations fire (which may well not affect your final outcome at all), but a guarantee that no matter how complicated your code gets, each function in your binary will be fast enough for your needs. That's far more important than whether a given optimization fires.
Or are you saying that you'd be happier with a fully devirtualized binary where the compiler has missed all other optimizations than with a binary where some dispatch is left dynamic, but only where the benefit from devirtualizing is in the noise, and the core compute where performance matters is optimized fully?
I don't see any reason why complex abstraction can't still run effectively in runtime?
That's why I am using high-level language, I want to put some complex abstraction, and give to compiler to do the work for optimization. And honestly I don't want to really bother much, about how optimization is done, I just want it done. I guess you want the same?
Let's say, If I know that compiler will do de-virtualization reliably, I wouldn't care about any other means, I would just use dyn Trait for simplicity whenever I need. And that Pre-RFC that I am putted here is not needed anymore.
So the question than where that gurantees then? Whether de-virtualization would work or not?
BTW: I've added few number in comment about typically L1-L3 cache sizes, if you curious about.
This all starts with you claiming that a complex abstraction makes it impossible for the compiler to optimize the code down to run effectively, and you need a guarantee that certain optimizations will fire in order to be confident that your code is simple enough for the compiler to optimize to run effectively.
If you trust the compiler to optimize well, then you don't care about which optimizations fire - the quality of the output is what matters, and that is best expressed not in terms of "has this optimization fired everywhere?" but "is this binary performant enough to meet my needs?". Failing to devirtualize may make a given snippet of code 10x slower - but failure to do loop invariant code motion can easily dwarf that (I've had code in the past where a failure of LICM was a 1,000,000x difference in performance).
Ultimately, though, if you care about time taken, memory consumption, or other performance metrics, looking in terms of "will this optimization always fire" is leading you down the wrong path - you should be benchmarking the things you care about and looking at whether your benchmarks are good enough, or not, and if they're not, looking into why.
And dyn Trait is not always simpler than monomorphic code; it's often more complicated. For example, you could write fn foo(param: &dyn std::fmt::Display), but it's often a much clearer expression of your intent if you write fn foo(param: &str) instead.
1 Like
Agree with you about benchmarking. Something I can't afford, especially when prototyping. That's why I am looking for feature, that will give me a trust to compiler.
If I want to make a RFC, perhaps I need to do a benchmarking, and I need to find a way to fool the compiler that it will not do de-virtualization. I guess I need to collect metrics, when de-virtualization happening and when it is not.
The fact that try_as_dyn goes through dynamic dispatch is, in my understanding, a matter of making the implementation complexity not too bad. If try_as_dyn were to work out, there's nothing fundamental preventing us from switching that to use a syntax similar to yours, and not going through dynamic dispatch.
So, I think focusing on the dynamic dispatch part is focusing on the wrong part of the feature. There are enough other problems with the feature already, and I would suggest that you do some research on those first.
5 Likes
One caveat here is that indirect branch target prediction is in some situations a security issue (if code with a lower privilege level can trick the branch predictor into making a specific misprediction, it will speculatively execute code that might potentially be chosen by an attacker, and speculatively executed code can change the state of the caches in ways that an attacker can detect even though it doesn't have any affect on registers or memory). As such, code that runs near privilege boundaries (e.g. browsers running JavaScript specified by untrusted websites, or kernels processing system calls from user-mode programs) generally either has to avoid using indirect branch instructions, or else do something time-consuming to reset the branch predictor as the privilege level changes. Devirtualization can thus (at least on some processors) potentially give considerable savings by avoiding the problem entirely. (On some other processors, it doesn't help due to the use of branch predictors that can incorrectly predict that an instruction will be an indirect branch when in fact it was an entirely unrelated instruction.)
1 Like
Have you seen Criterion? It's a pre-existing library that makes benchmarking very easy to manage in Rust, because it handles all of the "boilerplate" bits about benchmarking (warming up, statistical tests, excluding the cost of the harness etc) for you, allowing you to focus on the code path you want to benchmark.
If you care about performance, setting up Criterion benchmark groups (for functions with input-dependent performance) is well worth the small amount of effort it takes - and that catches not just missed devirtualization, but also bigger fails (like missed LICM, and acccidentally quadratic behaviour in your algorithms).
1 Like
Actually I run few benchmarks.
It's not x10, but realistically got x5.
If curious about, I putted all the code and README with description here:
I tad to fight against optimizer to disable de-virtualization, it wasn't that easy.
Next thing, that I want to examine, looks like rust have
cargo rustc --release -- -C remark=all
Or even maybe:
cargo rustc --release -p devirtualization-test-lib -- \
-C debuginfo=1 \
-C remark=all 2>&1 \
| grep -v ' inline '
Actually it telling me something about that line of code, where dynamic dispatch is happening:
note: ~/Projects/devirtualization-test/lib-crate/src/lib.rs:26:16 asm-printer (analysis): BasicBlock:
MOV64rr: 2
CALL64r: 1
DEC64r: 1
JCC_1: 1
Perhaps I can incorporate this somehow into code CD process, so I would know if something wrong with performance just happened.
Just run this rustc remark on some my real project:
And it gave me:
asm-printer (analysis): BasicBlock:
CALL64m: 1
JMP_1: 1
MOVSDrm_alt: 1
On this line:
#[enum_dispatch(...)]
That's actually surprise me 
, because this is what they claim, that they doing static dispatch(+inline), not another call...
I've implemented my library for same reason, just trying to get more flexibility:
https://crates.io/crates/match-variants
And I don't see ASM CALL instruction there, compiler was able to inline everything. 
By the way, it is possible to perform conditional trait impl's in today's stable Rust without relying on dynamic dispatch at all.
Here is a simple example to demonstrate how to achieve a relation, T: TraitA or TraitB <==> T: TraitC:
pub trait TraitA {
fn method_a(self);
}
pub trait TraitB {
fn method_b(self);
}
trait SealForTraitC {}
/// This is what we want to implement according to the downstream
/// user's choice of which trait to implement, TraitA or TraitB.
pub trait TraitC: SealForTraitC {
fn method_c(self);
}
trait SealForTag {}
trait ValidTag: SealForTag {}
pub struct TagA;
impl SealForTag for TagA {}
impl ValidTag for TagA {}
pub struct TagB;
impl SealForTag for TagB {}
impl ValidTag for TagB {}
trait Helper<Tag: ValidTag> {
fn intermediate_method(self);
}
impl<T: TraitA> Helper<TagA> for T {
fn intermediate_method(self) {
// Implement logic using `TraitA::method_a`.
}
}
impl<T: TraitB> Helper<TagB> for T {
fn intermediate_method(self) {
// Implement logic using `TraitB::method_b`.
}
}
pub trait TagSelector {
type Tag: ValidTag;
}
impl<T: TagSelector> SealForTraitC for T
where
T: Helper<T::Tag>,
{}
impl<T: TagSelector> TraitC for T
where
T: Helper<T::Tag>,
{
#[inline(always)]
fn method_c(self) {
self.intermediate_method()
}
}
In this demo, the following relation is guaranteed:
T: TraitA + TagSelector<TagA> xor TraitB + TagSelector<TagB> <==> T: TraitC
as long as the API designer does not manually implement Helper<Tag>, which is usually the case. The primary difference between this approach and your proposal is that the downstream user has a right to decide which trait to use for TraitC. If you do not want to expose TagSelector as a public API, you can make a wrapper macro which automatically implements it under the hood when the downstream user implements either TraitA or TraitB.
In regard to a negative bound, in particular the else branch in your T: Describe block, it is impossible to achieve this in the current stable Rust. I personally think this is an intentional langugage design rather than a technical limitation. If Rust allowed such a bound, not implementing a trait would be a public contract. In other words, T: !Describe would have to be interpreted as to mean that the crate author intentionally did not implement the trait rather than he or she simply did not implement it at the time. Consequently, implementing any traits at later times would become major breaking changes. This is why the negative bound feature is restricted to the compiler internal.
However, it is still possible to approximate such a behavior by introducing a new trait characterizing types used for your Describe trait. Here is another demo for this purpose:
trait Boolean {}
pub struct True;
impl Boolean for True {}
pub struct False;
impl Boolean for False {}
pub trait Describability {
type IsStaticallyDescribable: Boolean;
}
pub trait Describe: Describability<
IsStaticallyDescribable = False,
> {
fn describe(&self) -> &'static str;
}
pub trait StaticDescribe: Describability<
IsStaticallyDescribable = True,
> {
fn describe_static() -> &'static str;
}
In this way, you can enforce the downstream user to decide which trait to use explicitly.