DEV Community: Daniel Di Dio Balsamo

Optimization exercise with Rust

Daniel Di Dio Balsamo — Wed, 26 Feb 2025 19:10:24 +0000

Introduction

Optimizing code is something we all need to do everyday as developers.
But trying to immediately find the best solution is slow, whereas starting from a naive solution that you incrementally improve is more efficient.

Let's see this through a dynamic programming problem, the Fibonacci sequence, and using Rust.
This problem will be solved with 4 different approaches:

naive solution
top-down approach (memoization)
bottom-up approach
optimized bottom-up approach

Naive solution

The Fibonacci sequence is defined as follows:

n>1F_n = \begin{cases} F_0 = 0\\ F_1 = 1\\ F_n = F_{n-1} + F_{n-2} &\text{for n>1} \end{cases}

Let's start with a naive, yet simple implementation :

fn fibonacci(n: usize) -> u128 {
    match n {
        0 => 0,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

fn main() {
    println!("{}", fibonacci(35));
}

The corresponding time complexity is $O(2^n)$ : every fibonacci call triggers 2 calls, and we're doing that n times.

Exponential runtime... we must avoid that.

Top-down approach (memoization)

A lot of intermediate results are identical: fibonacci(5) computes 3 times fibonacci(2) for example.
Caching the results would avoid to compute them again and again, let's do that.

fn fibonacci(n: usize, memo: &mut [u128]) -> u128 {
    match n {
        0 => 0,
        1 => 1,
        _ => {
            if memo[n] == 0 {
                memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
            }
            memo[n]
        }
    }
}

fn main() {
    let n = 35;
    println!("{}", fibonacci(n, &mut vec![0u128; n + 1]));
}

Now the time complexity is $O (n)$ , since the cached cases immediately return.
But we can do better : this array becomes very big if we try to compute big Fibonacci numbers.
Before removing this array, we need to take another approach.

Bottom-up approach

Let's consider again the first naive solution. It is slow because of recursive calls.
Let's unstack them and store intermediate results :

fn fibonacci(n: usize) -> u128 {
    match n {
        0 => 0,
        1 => 1,
        _ => {
            let mut memo = vec![0; n + 1];
            memo[0] = 0;
            memo[1] = 1;

            for i in 2..=n {
                memo[i] = memo[i - 1] + memo[i - 2];
            }

            memo[n]
        }
    }
}

fn main() {
    println!("{}", fibonacci(35));
}

But wait, we're only considering memo[i - 1] and memo[i - 2], why do we store other results ?

Last optimization

We only need the two last results, let's use two simple variables for this :

fn fibonacci(n: usize) -> u128 {
    if n == 0 {
        return 0;
    }

    let (mut a, mut b) = (0, 1);

    for _ in 2..n {
        let c = a + b;
        a = b;
        b = c;
    }

    a + b
}

fn main() {
    println!("{}", fibonacci(35));
}

Finally, the time complexity is still $O (n)$ , but without the array as in the top-down solution.

Conclusion

Starting from a naive solution allows you to make sure you really understood the problem.
Then you can iterate until your code is optimized enough.

Rust: Trait objects vs generics

Daniel Di Dio Balsamo — Thu, 09 Jan 2025 10:34:21 +0000

Introduction

Abstracting concepts to avoid code duplication is something common.
Rust provides both generics and trait objects to achieve this, but if you look carefully they don't address the exact same problem, and they have different consequences on performance.

In order to compare them, we will consider a simple example : a list.
Let's start with generics.

Generics

struct MyList<T> {
    contents: Vec<T>,
}

fn main() {
    let a = MyList {
        contents: vec![1., 2., 3.],
    };

    let b = MyList {
        contents: vec!["abc".to_owned(), "def".to_owned()],
    };

    println!("{:?}", a.contents);
    println!("{:?}", b.contents);
}

Output:

[1.0, 2.0, 3.0]
["abc", "def"]

MyList is a simple struct containing a Vec whose elements are of type T.
This allows a to contain a Vec<f64> and b a Vec<String>.

Right, what if we try to mix f64 and String in the same list ?

struct MyList<T> {
    contents: Vec<T>,
}

fn main() {
    let not_working = MyList {
        contents: vec![1., "test".to_owned()],
    };

    println!("{:?}", not_working.contents);
}

Output:

error[E0308]: mismatched types
 --> src/main.rs:7:28
  |
7 |         contents: vec![1., "test".to_owned()],
  |                            ^^^^^^^^^^^^^^^^^ expected floating-point number, found `String`

Mismatched types ! To understand why, let's describe how generics are handled by the compiler.
When you use generics, the Rust compiler do something called "monomorphization". It simply means that the compiler looks at all the places generic code is called, and replace the generic type by the concrete ones.
In this example, after monomorphization, the first code example would look like this :

struct MyList_f32 {
    contents: Vec<f32>,
}

struct MyList_string {
    contents: Vec<String>,
}

fn main() {
    let a = MyList_f32 {
        contents: vec![1., 2., 3.],
    };

    let b = MyList_string {
        contents: vec!["abc".to_owned(), "def".to_owned()],
    };

    println!("{:?}", a.contents);
    println!("{:?}", b.contents);
}

Now, how could the compiler generate a struct MyList_f32_string with contents type both Vec<f32> and Vec<String> in the same time ? As you can see, a Vec<T> can only contain elements of the same generic type.
On the other hand, generics have no impact on performance at runtime thanks to monomorphization.

Trait objects

Same idea as before, we want to store items in a list, but this time it contains non primitive types.

trait Entity {
    fn hello(&self) -> String;
}

struct Player {
    name: String,
    xp: usize,
}

impl Entity for Player {
    fn hello(&self) -> String {
        format!("I'm player {} with {} xp", self.name, self.xp)
    }
}

struct Bird {
    xp: usize,
}

impl Entity for Bird {
    fn hello(&self) -> String {
        format!("I'm a bird with {} xp", self.xp)
    }
}

struct MyList {
    contents: Vec<Box<dyn Entity>>,
}

fn main() {
    let world = MyList {
        contents: vec![
            Box::new(Player {
                name: "a".to_owned(),
                xp: 1000,
            }),
            Box::new(Bird { xp: 1 }),
            Box::new(Player {
                name: "b".to_owned(),
                xp: 0,
            }),
            Box::new(Bird { xp: 5 }),
        ],
    };

    for entity in &world.contents {
        println!("{}", entity.hello())
    }
}

Output:

I'm player a with 1000 xp
I'm a bird with 1 xp
I'm player b with 0 xp
I'm a bird with 5 xp

Here we use trait objects instead of generics: contents contains types that must implement the Entity trait (Vec<Box<dyn Entity>>). The compiler doesn't know which type will be used, but it knows it will implement that type.

But shouldn't the compiler complain because types in the list won't have the exact same size ? The list contains Box items, which is the size of a pointer: all items have the same size, everything's fine.

But trait objects have a cost : Rust can't apply monomorphization because it can't guess all types that might be used at runtime, so it keeps a table in which traits methods and concrete types implementations are linked.
In this example, during runtime, when entity.hello() is called for a Player, Rust looks up this table to call the corresponding Player::hello method, and not Bird::hello.

So dynamic dispatch have impacts on performance since it prevents monomorphization and adds a runtime cost due to dynamic dispatch, but sometimes we need it as in the example before.

Conclusion

Generics	Trait objects
refer to one generic type only	refer to any types implementing a specific trait
have no impact on runtime performance	prevent monomorphization and need dynamic dispatch

Sublime Text & Rust

Daniel Di Dio Balsamo — Wed, 20 Mar 2024 16:20:25 +0000

Introduction

There are many good IDE's for developing in Rust, let's see how to setup Sublime Text for this language.
What we're going to achieve :

auto completion
errors / fix suggestions within the editor
doc information on mouse hover (including external dependencies)
auto formatting on save

Note: The following configuration has been successfully tested on build 4169.

Configuration

Syntax highlighting and auto formatting

Open the command palette (Ctrl+Shift+P)
Install Package --> Rust Enhanced
Install Package --> RustFmt

At this stage, syntax highlighting should be enabled, as well as auto formatting on save (otherwise check RustFmt settings under Preferences --> Package Settings)

Auto completion and errors / fix suggestions

Firstly, we need the rust-analyzer binary :

rustup component add rust-analyzer

rust-analyzer needs Rust sources, the easiest way to install them is :

rustup component add rust-src

Note that only the latest version of Rust is fully supported by rust-analyzer, if you need to handle older ones, check this doc

Then we can install LSP (Language Server Protocol) plugins :

Open the command palette (Ctrl+Shift+P)
Install Package --> LSP
Install Package --> LSP-rust-analyzer

At this stage, you should see a little window containing some documentation on mouse hover (as well as links to the definition, references...), and auto completion should also work for all sources (including external dependencies defined in Cargo.toml).

If it doesn't work

Important: it only works if you add a folder containing a Cargo.toml file, a single file alone won't work.

Open the command palette (Ctrl+Shift+P)
LSP: Restart Server
Relaunch Sublime Text

Still not working ? Your environment may need a specific configuration, please check the rust-analyzer doc

Rust & Dockerfile : cache dependencies with cargo chef

Daniel Di Dio Balsamo — Fri, 15 Mar 2024 11:03:44 +0000

Introduction

Let's consider this basic Dockerfile:

# syntax=docker/dockerfile:1
# build in rust env
FROM rust:latest AS builder
WORKDIR /app
COPY . .
RUN cargo build --release

# run in a minimal image
FROM debian:bookworm-slim
COPY --from=builder /app/target/release/hello_world /usr/local/bin/hello_world
CMD hello_world

This Dockerfile produces a valid image, but think about an application with a lot of dependencies : even if you only update application code, all the dependencies are built again. This is time consuming.

Ideally, we should have something like cargo build --dependencies-only, but such a dream hasn't come true yet.
There are many ways to work around this issue.

The least effective solution is to temporary create an empty main.rs using RUN mkdir src && echo "fn main() {}" > src/main.rs. This way, only dependencies are considered during the first build, then copy application code and build again.
It works since first you build with deps only (1 layer), then with your code (another layer) : if your own code changes, the deps layer doesn't change so it's not rebuilt.
In addition of not being efficient, this solution can be hard to maintain: what if Cargo.toml contains a local dependency ? What about workspaces ?
You're going to use sed with a lot of particular cases to handle, and every time Cargo.toml changes, you're going to update your sed commands in Dockerfile.

We can do much better with cargo chef.

cargo-chef solution

This crate caches the dependencies for you. You don't have to install it locally, just use it during docker build.
Let's see how it works :

# syntax=docker/dockerfile:1
# (1) create rust env with cargo chef crate
FROM rust:latest AS chef
WORKDIR /app
RUN cargo install cargo-chef

# (2) generate recipe file to prepare dependencies build
FROM chef AS planner
COPY . /app
RUN cargo chef prepare --recipe-path recipe.json

# (3) build dependencies
FROM chef AS cacher
COPY --from=planner /app/recipe.json recipe.json
RUN cargo chef cook --release --recipe-path recipe.json

# (4) build app
FROM chef AS builder
COPY . /app
COPY --from=cacher /app/target target
COPY --from=cacher /usr/local/cargo /usr/local/cargo
RUN cargo build --release

# (5) run the app
FROM debian:bookworm-slim
COPY --from=builder /app/target/release/hello_world /usr/local/bin/hello_world
CMD hello_world

(1): install cargo-chef crate in a rust env.
(2): cargo chef checks your project and generates a recipe.json file which describes its skeleton. You can consider this file as Python's requirements.txt
(3): cargo chef builds and caches dependencies in release mode.
(4): copy the cache and build your app.
(5): copy the executable and run it in a minimal image.

Now if you update something in the application code, you can see that dependencies aren't built again.
And that's it !

Conclusion

cargo-chef provides an efficient way to avoid building dependencies again and again.
Here's one of my side project which takes advantage of cargo chef