Rust Type Bounds with Traits
Published on 2021-05-16
TLDR: It is often better to do this:
fn my_func<T: MyTrait>(t: T) {
// ...
}
Instead of this:
fn my_func(t: Box<dyn T>) {
// ...
}
Traits and interfaces are great. They let you write code without needing to worry about the actual type you are working with; all you need to know is that it has what you need. You can then share this code across multiple types without needing to repeat yourself.
Let's say we wanted make our own error interface in TypeScript (we'll get to Rust soon I promise). We may have different kinds of errors with different information in them but they will all have a message to display to the user when they occur:
interface MyError {
message(): string;
}
Now we can make a function that can print the message from anything that implements MyError:
function printMessage(e: MyError) {
console.log(e.message());
}
This compiles just fine (technically transpiles since it's TypeScript) and you are good to go. But what happens if we try to do the same thing with Rust:
// WARNING: I don't compile don't copy me
pub trait MyError {
fn message(&self) -> String;
}
pub fn print_message(e: MyError) {
println!("{}", e.message());
}
When we try to compile we get this helpful message:
warning: trait objects without an explicit `dyn` are deprecated
--> src/main.rs:5:25
|
5 | pub fn print_message(e: MyError) {
| ^^^^^^^ help: use `dyn`: `dyn MyError`
|
= note: `#[warn(bare_trait_objects)]` on by default
error[E0277]: the size for values of type `(dyn MyError + 'static)` cannot be known at compilation time
--> src/main.rs:5:22
|
5 | pub fn print_message(e: MyError) {
| ^ doesn't have a size known at compile-time
|
= help: the trait `Sized` is not implemented for `(dyn MyError + 'static)`
= help: unsized locals are gated as an unstable feature
help: function arguments must have a statically known size, borrowed types always have a known size
|
5 | pub fn print_message(e: &MyError) {
| ^
error: aborting due to previous error; 1 warning emitted
Alright so what gives? Let's deal with the error first because warnings are made to be ignored. Our error is:
the size for values of type `(dyn MyError + 'static)` cannot be known at compilation time
This makes sense. Function arguments are allocated on the stack in Rust. To compile our function with an argument allocated on the stack we need to know it's size at compile time. Some other languages assume you want heap allocation in cases like this and will do it for you. While this can be convenient, it takes choices away from you. Rust will do whatever you want, you just need to ask. If we want our argument to be heap-allocated we can wrap it in Box. Under the hood this will pass a pointer to heap-allocated memory into our function and the pointer is of fixed size so we can compile. Also the compiler seems to want us to add the keyword dyn before our trait so let's add it to keep the compiler happy. Our function becomes:
pub fn print_message(e: Box<dyn MyError>) {
println!("{}", e.message());
}
Awesome, that compiles! But what was that pesky dyn business that the compiler was complaining about? dyn is short for dynamic and refers to dynamic dispatch. Before I explain what that is I will explain the opposite of dynamic dispatch, static dispatch. Take a look at this example of someone using MyError:
pub trait MyError {
fn message(&self) -> String;
}
struct DoesNotCompute {}
impl MyError for DoesNotCompute {
fn message(&self) -> String {
return "DOES NOT COMPUTE".to_string();
}
}
fn main() {
let e = DoesNotCompute {};
println!("{}", e.message());
}
Here we are calling message on e which does implement MyError but the compiler knows even more about it: it is a DoesNotCompute. This means that the compiler knows that it will call DoesNotCompute's message function, this is called static dispatch. Don't take my word for it we can see what the compiler has done using an awesome tool called cargo-asm. Just a word of warning before using cargo-asm; the compiler is highly optimized and you may get unexpected results when analyzing programs. Some compilation rules are true in general but can be modified by other optimizations so you may not always see what you expect. We can search our binary for a message function by running cargo asm message:
[ERROR]: could not find function at path "message" in the generated assembly.
Tips:
* make sure that the function is present in the final binary (e.g. if it's a generic function, make sure that it is actually monomorphized)
* try to do a --clean build (sometimes changes are not picked up)
Wait where is our message function? Turns out it got inlined. Calling a function introduces a bit of overhead compared to running just running the same code normally so the compiler replaced our function call with the code itself. For larger functions that are called repeatedly it can sometimes be more efficient not to inline and doing so can result in smaller binaries so the Rust Compiler navigates this tradeoff for you and inlines functions if it thinks it will make your program more efficient. Our function is super tiny so inlining was definitely the right call. As usual, Rust will do whatever you want if you know how to ask and you can tell the compiler that you think you know better and not to inline a function by adding #[inline(never)] above your function. Once I add that over our message implementation and run cargo asm message again we can find our function:
[ERROR]: could not find function at path "message" in the generated assembly.
Is it one of the following functions?
<rust_playground::DoesNotCompute as rust_playground::MyError>::message
Tips:
* make sure that the function is present in the final binary (e.g. if it's a generic function, make sure that it is actually monomorphized)
* try to do a --clean build (sometimes changes are not picked up)
In order to inline, the compiler needs to know exactly what function would have been called so it can inline the correct implementation. This means seeing inlining proves that the function call is being statically dispatched. You can also inspect your main function with cargo asm your_crate_name::main --rust to see the exact call in the assembly though the output is pretty long so I won't include it here. So if static dispatch means calling a specific function that can be known at compile time then it's opposite, dynamic dispatch, means that the compiler doesn't know exactly which function to call at compile time and it needs to be figured out at runtime.
Looking back at our print_message function:
pub fn print_message(e: Box<dyn MyError>) {
println!("{}", e.message());
}
It takes a pointer to a thing that implements MyError but at compile time we have no idea what thing that is. It could be our DoesNotCompute error but for all the compiler knows it could be some other type with some other message implementation. Behind the scenes the compiler creates something called a vtable which is a mapping of trait methods to pointers pointing to their underlying functions. The pointer to the MyError is actually what's called a "fat pointer", it contains both a pointer to the struct itself and a pointer to the vtable. Let's construct a complete program with our print_message implementation and analyze it with cargo asm message to list all of it's compiled functions:
pub trait MyError {
fn message(&self) -> String;
}
struct DoesNotCompute {}
impl MyError for DoesNotCompute {
fn message(&self) -> String {
return "DOES NOT COMPUTE".to_string();
}
}
pub fn print_message(e: Box<dyn MyError>) {
println!("{}", e.message());
}
fn main() {
print_message(Box::new(DoesNotCompute {}));
}
[ERROR]: could not find function at path "message" in the generated assembly.
Is it one of the following functions?
<rust_playground::DoesNotCompute as rust_playground::MyError>::message
Tips:
* make sure that the function is present in the final binary (e.g. if it's a generic function, make sure that it is actually monomorphized)
* try to do a --clean build (sometimes changes are not picked up)
Now our message function isn't inlined even though we didn't use #[inline(never)] and we know the compiler considers this function a good candidate for inlining. This is happening because message is being dynamically dispatched in our print_message function. We need a function pointer to put in the vtable so the function must be created so we can have a pointer to it. If you analyze our program with cargo asm your_crate::print_message --rust you can also see the assembly is considerably more complicated than our static dispatch example's main even though they are both just printing the result of message().
Rust is supposed to give us zero cost abstractions. It looks like to get a function that works for any MyError we have had to pay a cost at runtime. We've even had to give up our inlining. Luckily Rust has the answer: Bounds. Bounds let you specify that a generic parameter must satisfy a type constraint. This means we can make our print_message generic over any type that implements MyError like so:
pub fn print_message<T: MyError>(e: T) {
println!("{}", e.message());
}
Now we can call it without Box:
fn main() {
print_message(DoesNotCompute {});
}
And when we run cargo asm message we see that our inlining (and therefore static dispatch) is back!
In Rust generic functions behave almost like macros, implementations for each type you use them with are generated at compile time. At runtime it is as if you re-wrote an implementation for each type you used the generic with. This can lead to larger binaries but it also gives us generics with zero performance cost. Using bounds like this gives you more flexibility and performance compared to using Box and I recommend it for most use cases.
Traits actually solve two problems and Rust is the only language I know of that separates them. The first problem is when the type can be known at compile time. In this scenario you could actually just re-implement everything manually. The generics just mean you don't need to repeat yourself. You may want a map from String to usize and you can use the same code as someone who wants a map from i32 to i32. Sure you COULD write your own String to usize map but the compiler will do that for you. The second use case is when the type cannot be known at compile time. This only comes up when the type depends on some runtime factor, like user input for example. This case is quite a bit rarer in my experience but most languages pay a runtime penalty to support it by default. I recommend tending towards using generics with bounds by default, especially when writing libraries.
So who cares? Do we really need to worry about every last shred of performance? Java is actually really fast and more than enough for most use cases and it does heap allocation and dynamic dispatch. I agree that sometimes spending time on performance isn't worth it but Rust is giving this to us almost for free. We do not need to spend weeks tweaking algorithms or writing assembly, this is a small syntax shift that can actually make a huge difference across your whole application. For the caller, I would argue it is even more convenient to use bounds rather than Box and Allocation is pretty costly. Often, it can outweigh things like theoretical algorithm performance in practice. In my opinion, distinguishing between these two use cases is awesome. There are two problems here with two optimal solutions and Rust supports both as first class citizens. Rust gives you choices and gives you the tools you need to easily navigate some fundamental tradeoffs. Writing faster and safer programs doesn't have to be hard.