Rust-specific code optimisations vs other languages

[qaopm]

I've seen people say "Rust is faster than XYZ" (and the other way round) but it's usually light on details why is that. Is it because the benchmarked programs use different algorithms/data structures (e.g. different hash map)? Is it the number of memory accesses? Is it because the compiler generates better code? Is it because it can generate better code because the language has some guarantees?

I'm looking for some details/in-depth descriptions/experiments about code generation/optimisations that are possible in Rust but not in other languages like C++.

I'm less interested in comparing standard library implementations and more about language-specific features that enable "better" code generation. One example could be pointer aliasing where Rust should have an advantage over C++, but that's not enabled at the moment.

In other words, what is the class of algorithms for which Rust might/can produce better code than e.g. C++? (In theory and in practice.) Is there a class of algorithms for which Rust can never produce better code?

I came across this old topic that discusses similar concerns and I've been wondering whether there are new articles/ideas/development regarding optimisation techniques.

[alice]

You say other languages but only discuss C++. Are you also interested in comparisons with e.g. GC languages? Because usually when people say Rust is faster, it's in comparison to a GCed language, although there are exceptions of course.

[qaopm]

@alice

You say other languages but only discuss C++.

I'm interested in general comparison although (being a C++ developer) I've paid more attention to C++ vs Rust discussion.

[alice]

Generally Rust and C++ have access to the same kinds of compiler optimizations, so they should in general be able to obtain the same performance on the same problem. Of course the question is if they do in practice.

Specifically when comparing to C++, I mainly hear about two things with respect to Rust obtaining better performance. These are:

1. Rust always makes clones explicit, so it is always visible when you pay the cost of cloning something. This is in comparison to copy constructors in C++, which are implicit.
2. When parsing various formats, you may want to keep pointers into slices of the original data rather than copying the data into the resulting code. This can be dangerous in C++, so people are prone to avoiding this style of parsing, whereas in Rust, the compiler will verify at compile-time that no use-after-frees are possible.

As for classes of algorithms, Rust and C++ can of course write the same algorithms implemented in the same ways. That said, some types of data structures cannot be done in safe Rust, and require significant amounts of unsafe code. The BTreeMap collection is a good example of this, and Learn Rust With Entirely Too Many Linked Lists also provides some examples.

[qaopm]

@alice

Generally Rust and C++ have access to the same kinds of compiler optimizations, so they should in general be able to obtain the same performance on the same problem

Generally yes, but Rust and C++ have different memory models so in the end there will be differences in what kind of optimisation can be done, that's what I've been trying to find more details about.

I can't find it anymore but there was a good C++ talk looking at the generated code of unique_ptr (Box in Rust) and whether the compiler can ever generate the same code as if the program was using raw pointers only. The conclusion was it's not possible (at least for C++14, not sure about 17, 20, ...) because the memory model prevents it.

@alice

Rust always makes clones explicit, so it is always visible when you pay the cost of cloning something. This is in comparison to copy constructors in C++, which are implicit.

Good point. From my experience pretty much all C++ people I've worked with are very aware of passing variables by value and how expensive it can be. I'm new to Rust so I don't know how many know/care about how expensive it is to move something because in the end it can be a memory copy, i.e. the same as C++ copy ctor/assignment operator.

@alice

When parsing various formats, you may want to keep pointers into slices of the original data rather than copying the data into the resulting code. This can be dangerous in C++, so people are prone to avoiding this style of parsing, whereas in Rust, the compiler will verify at compile-time that no use-after-frees are possible.

This might depend on the industry. E.g. in gaming and fintech it's almost guaranteed they'll use the more efficient approach. In any case, I agree that Rust gives the programmer the confidence to use a more efficient approach even though in the end the optimisations might be identical in both.

[steffahn]

@qaopm

I'm new to Rust so I don't know how many know/care about how expensive it is to move something because in the end it can be a memory copy, i.e. the same as C++ copy ctor/assignment operator.

I think the more appropriate comparison is the move constructor in C++. I’m not too deep into C++, but AFAIK the analogy really is pretty much exactly: Rust’s moves are like move constructors in C++ and Rust’s .clone() is like copy constructors. Except that even C++ move constructors can, in theory, do any kind of custom logic they want.

---

Another difference that can hurt C++ performance, if the optimizer doesn’t catch it, is the fact that “moving out of” a value leaves the original value in a kind of null-like state.

This generates two small cost points: first, modifying the value into the null-like state (don’t take the word null too serious; I think the reference calls it something like “an undefined but valid state”), and second, when destructing the moved-out value, there is a run-time check that has to check for the null-state actually being present in order to know that no RAII-resources/allocations have to be freed.

As I said, the compiler might optimize these away often enough, and by the way there’s also situations where the Rust compiler has to generate some boolean flags that need to be set and checked at runtime to figure out if a value has been moved out of at the end of its scope.

A definite win for Rust though here is the fact that the information whether a value has been moved out of does not need to be stored inside of the value itself, which has the potential to save some space. (Rust actually used to have “drop-flags” included in the types/values themselves some time ago but that got changed.) I also think Rust’s way of not specifying data type layouts too much, in particular field order, but also including various enum-related optimizations have the potential to often make datatypes smaller than their C++ code “equivalents” (unless those are hand-optimized, of course), especially around generics (you can’t easily hand-optimize field order for every possible instantiation of a C++ template, can you?).

[jonh]

VTables are stored outside structures. Don't think anyone truly knows what is gained.
Monomorphism is generally a win over dynamic.

[kornel]

I've written a high-level comparison with C: https://kornel.ski/rust-c-speed

[scottmcm]

@qaopm

In other words, what is the class of algorithms for which Rust might/can produce better code than e.g. C++? (In theory and in practice.)

Mostly there's no difference. You can usually write the same thing in both, and LLVM will compile them about the same (so clang and rustc give you about the same thing).

There are a few minor differences that come from the stronger checking in rust:

• Rust understands moves, so doesn't need the concept of an xvalue, a type that's been moved out of but the destructor is still going to run. That's why Box<T> can be better than unique_ptr<T>: the unique_ptr needs to be nullable so the destructor can check whether to deallocate, but with Box there's no check in Drop because if it gets moved the compiler won't call drop on the old one.
• Rust has built-in discriminated unions and layout optimizations to go with it. Box<T> is known not to be null, so Option<Box<T>> has the same size as the box. And this applies recursively, and to other types (though it's not always guaranteed by the spec, but often happens). And rust has ZSTs, so doesn't need things like boost::compressed_pair, thus allowing things like HashMap<T, ()> to be just as space-efficient as a dedicated HashSet<T>.

One day we'll hopefully be able to communicate more of the stronger guarantees about aliasing and such too. Though Rust intentionally doesn't have C++'s strict aliasing rule, so there are plausibly situations where one system or the other will work out better.

---

The other way of looking at it is at what's easy as opposed to what's possible. This post is a great example of that compared to C:

The Observation Deck » The relative performance of C and Rust

At some point, in larger programs, better checking and better abstractions make it feasible to use designs that are impractical to check manually. I would say that's the core of why servo works, for example -- it's not doing anything that would be impossible in C++, but "possible" and "feasible for mortals" are different.

[Gustavo]

Before jumping into Rust I have been looking around into benchmarks .

It seems that in 2018 there was still quite some gap in Rust optimization
https://qph.fs.quoracdn.net/main-qimg-7b939055826c7b757bbbf1298628e0b6

Not quite so in 2020:
https://benchmarksgame-team.pages.debian.net/benchmarksgame/download/fastest.svg
Now there is a clear gap between front-runners (C, C++, Rust) and the rest.

I guess optimizations just take some time to be implemented, and eventually people will copy good ideas from one language to another. Good ideas from one compiler to another and so on.
I don't see any reason why Rust and C++ would significantly outperform each other any soon, they are actually getting more alike (e.g. C++20 get features which Rust had but C++ not), but...
With Rust one does not need to keep hard trying to convince colleagues move to safe coding style, the compiler will.

[TomP]

Since many C and C++ compilers use LLVM, like Rust (and Zig), they all have the same back-end optimizer. In many cases Rust actually has the potential for better optimization, due to its stronger guarantees on mutation and aliasing, but since most LLVM optimization improvements are done for C and C++ it probably requires a significant Rust-focused LLVM contribution for Rust to pull ahead.