Learning Rust: Zero Cost Abstraction

Blazing fast, incredibly abstracted: How does Rust achieve this?

A program may comprise thousands or millions of lines of code. If we try to keep all the details of this code in our minds all the time, we may quickly feel overwhelmed. Instead, we use abstraction to hide away the details and expose only the most relevant parts.

Consider a filesystem. The interface behind it is very simple. You can list directories, read or write files. Everything is so simple, without needing to know about its complexity, security, and optimizations.

However, abstraction often comes at a cost. This cost is typically paid in the performance of the abstracted code. Generally, the higher the abstraction, the slower the code becomes. Methods, wrappers, interfaces and infamous polymorphism, all introduce a hidden cost.

Let’s explore a simple problem. Imagine we have a structure with only a single field called “age”. We can compare these structures if we derive or implement certain traits. The code may look like the following:

#[derive(PartialEq, Eq, PartialOrd)]
pub struct Person {
    age: u8,
}

impl Ord for Person {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // make it so complex to avoid inlining
        let left: u8 = format!("{}", self.age).parse().unwrap();
        let right: u8 = format!("{}", other.age).parse().unwrap();

        left.cmp(&right)
    }
}

pub fn compare_normal(people: [Person; 2]) -> core::cmp::Ordering {
    people[0].cmp(&people[1])
}

The additional function compare_normal takes an array of two people and determines their ordering. It can produce three different outcomes.

What if I want its behavior to be the exact opposite? I could create another structure, place the Person struct as a field, and implement a reversed comparator. Fortunately, Rust already provides such a structure: std::cmp::Reverse<T>. I can use it to compare in a reversed order as follows:

pub fn compare_normal(people: [Person; 2]) -> core::cmp::Ordering {
    people[0].cmp(&people[1])
}

pub fn compare_reversed(people: [std::cmp::Reverse<Person>; 2]) -> core::cmp::Ordering {
    people[0].cmp(&people[1])
}

Is this approach costly? Having experience with C#, Python, or Java, my answer would be: yes. In the OOP world, the Reverse struct wrapper might consume some heap space for data and use polymorphic overridden operators. This structure would reverse the parameters and then invoke the original operators. Such a cost wouldn’t be negligible.

However, Rust is different. It can translate high-level concepts like the Reverse structure into instructions as if you had written them without any abstraction. How am I certain of this? Let’s examine the assembly code for both comparisons:

example::compare_normal:
        push    rax
        mov     word ptr [rsp + 6], di
        lea     rsi, [rsp + 7]
        lea     rdi, [rsp + 6]
        call    qword ptr [rip + <example::Person as core::cmp::Ord>::cmp@GOTPCREL]
        pop     rcx
        ret

example::compare_reversed:
        push    rax
        mov     word ptr [rsp + 6], di
        lea     rdi, [rsp + 7]
        lea     rsi, [rsp + 6]
        call    qword ptr [rip + <example::Person as core::cmp::Ord>::cmp@GOTPCREL]
        pop     rcx
        ret

At first glance, it’s evident that both pieces of code are of the same length. Secondly, the assembly doesn’t invoke the Reverse functions at all. So, what’s happening? The compiler reverses the values to be compared in the rdi and rsi registers. That’s truly remarkable! Amazing!

The level of abstraction and optimization in Rust is astounding, far beyond what I’ve demonstrated in this post. While not everything can be optimized to Zero Cost, with careful usage, verification and benchmarking, you can come close to achieving it.