Rustコトハジメ

プログラミング言語Rustに関する情報をお届けします。

Zero cost abstraction explained

The first time I heard the word "Zero cost abstraction" I had no idea what it is. In the same way I could not soon understand why GC is not needed while free is not needed at the same time, I was confused what zero cost of abstraction is. For those who is sophisticated in zero overhead principle and template programming in C++, it is natural to understand but I think most of you are not. That is why I explain here.

I think the best explaining document about zero cost abstraction is the article below and this article will try to explain the essence in short length.

blog.rust-lang.org

Zero overhead principle in C++

C++ implementations obey the zero-overhead principle: What you don't use, you don't pay for [Stroustrup, 1994]. And further: What you do use, you couldn't hand code any better.

is, in one word, "Don't consume any CPU cycles in GC and indirections".

Traits in Rust is designed for both static and dynamic dispatch

The cornerstone of abstraction in Rust is traits

Trait plays the very important role in zero cost abstraction that is

  • Traits are Rust's sole notion of interface
  • Traits can be statically dispatched
  • Traits can be dynamically dispatched

Let's visit each one

What is static dispatch?

fn print_hash<T: Hash>(t: &T) {
    println!("The hash is {}", t.hash())
}

When there is a function like this and bool and i32 implements Hash and you actually use the function with bool and i32 value. Then Rust generates specialized code like the followings. This is called monomorphization.

fn __print_hash_bool(&bool)
fn __print_hash_i32(&i32)

In result, calling the function will be replaced with the specialized ones and there is no runtime overhead.

The same thing happens for type constraints in class or trait. The A or T will be replaced by the actual types, traits are eventually all eliminated and the code will be like writing with only concrete classes. Since compiler knows the addresses of functions statically, it is called static dispatch.

What is dynamic dispatch?

Only with static dispatch, you are hard to write a code in some cases. The case is as such

trait ClickCallback {
    fn on_click(&self, x: i64, y: i64);
}
struct Button<T: ClickCallback> {
    listeners: Vec<T>,
    ...
}

For Java programmers, the code is pretty much sane but it is useless in Rust because T is statically dispatched and fixed into a concrete type. What we want to do here is that implement various kinds of ClickCallback trait (call them A and B) and register them listeners. However, static dispatch generates a concrete code A or B then B is not able to be registered.

struct ButtonA {
   listeners: Vec<A>
}

This is when dynamic dispatch kicks in. You wrap the trait into Box

struct Button {
    listeners: Vec<Box<ClickCallback>>,
    ...
}

then you are able to write flexible code paying some runtime cost for vtable like Java interface or C++ virtual function.

Static dispatch and dynamic dispatch are complementary tools

Static and dynamic dispatch are complementary tools, each appropriate for different scenarios. Rust's traits provide a single, simple notion of interface that can be used in both styles, with minimal, predictable costs.

In Rust, you are able to use static dispatch in most of the case but you can switch to dynamic dispatch when it is not able. In short, the single concept trait covers every scenario in programming.

So what is zero cost abstraction?

Trait objects satisfy Stroustrup's "pay as you go" principle: you have vtables when you need them, but the same trait can be compiled away statically when you don't.

The word zero cost means that you are only paying cost for what you do. With the Rust's abstraction tool trait you will not pay any abstraction cost when it is statically dispatched and you can pay some whenever you have to.