Fighting Rust; or immutability, borrowing and lifetimes

So I’ve decided to learn Rust. Rust is a ‘systems’ programming language, which essentially means a language designed for writing systems code. A bit circular as definitions go, so lets see what Wikipedia has to say on it:

A system programming language usually refers to a programming language used for system programming; such languages are designed for writing system software, which usually requires different development approaches when compared with application software.

Not too useful either. If we follow the link then we actually get to the more important bit:

… whereas systems programming aims to produce software and software platforms which provide services to other software, are performance constrained, or both (e.g. operating systems, computational science applications, game engines and AAA video games, industrial automation, and software as a service applications)

The main take-away, is that systems programming languages tend to produce faster code, that is also smaller and can run in more constrained environments, be that CPU, memory or a combination of the two. My reason for learning it is to produce a tiling window manager for an ultrawide monitor.

Anyway, it turns out that Rust is actually quite hard! I’m a Python, C, Bash, Javascript (and CoffeeScript) programmer, who also knows a few SQL dialects. I’ve done Scheme and FORTH in the past. Conspicuously missing from this list is Haskell, and that’s interersting because it uses a similar type system to Rust: the Hindley-Milner type system. Which means I’m not that familiar with it.

However, what really sets Rust apart from the other similar languages (think Go, C, C++) is that it uses the concept of borrowing, which, at first, is confusing. And this post is a little example of the frustrations I’m having.


So, to learn a programming language you can do a number of things. Read a book, dive in and code a project you’ve been meaning to do, or try out some exercises. These are not mutually exclusive, so you can do all three.

I read most of the book and, currently, I’m working through the Rust exercises on Exercism. This seems to be a pretty useful way of getting aquainted with a (new) language as it forces you to try to program. And I’m a big fan of learning by doing, so it seems an ideal way to get started.

So I worked through the exercises and got to …

Pascal’s Triangle

If you’ve done any maths at all, you’ve come across Pascal’s Triangle. So The triangle looks like this:

r0        1
r1       1 1
r2      1 2 1
r3     1 3 3 1
r4    1 4 6 4 1
...

And there is a nifty bit of maths you can use to calculate the number at row (r) position (n). But where’s the fun in that? I wanted to explore the language a bit, so I decided I’d actually try to calculate the next row from the row I have. So looking at r3, to make r4:

r3:    1 3 3 1 0
r3->:  0 1 3 3 1 +
----------------
r4:    1 4 6 4 1

i.e. add the elements of r3 to r3 shifted one column, and insert 0’s to fill the spaces.

First part: lifetimes

After many attempts, I got to the following (almost) compilable piece of Rust code for making a new row from a previous one:

// taking Rn, make Rn+1 from it
fn make_next_row(v: &Vec<u32>) -> Vec<u32> {
    let i1 = [0].iter().chain(v.iter());   // 1.
    let i2 = v.iter().chain([0].iter());   // 2.

    // sum the two lists together.
    i1.zip(i2).map(|(a, b)| a + b).collect()   // 3. implicit return here
}

Can you see the bug? No, I didn’t either.

So what line 1. is (supposed to be) doing is creating an iterator i1 that is made up of a 0 followed by the contents of the vector passed to it. And then line 2. is similar, but adds the 0 to the end of the iterator. This gives us two iterators of the same length based on the borrowed v (that’s what the little & in the v: &Vec<u32> means).

Then line 3. zips the two iterators together (an iterator of pairs), then uses the map function to sum those pairs, and finally the collect() function consumes the iterator into a Vec<u32> whose type is inferred from the iterators.

Except: it doesn’t work. If you compile this you get (amongst many other errors):

error: borrowed value does not live long enough
  --> src/lib.rs:81:44
   |
81 |     let mut i1 = [0].iter().chain(v.iter());
   |                  ---                       ^ temporary value dropped here while still borrowed
   |                  |
   |                  temporary value created here
...
89 | }
   | - temporary value needs to live until here
   |
   = note: consider using a `let` binding to increase its lifetime

Okaaay. So [0] is an array (or slice; I’m not sure yet) that is temporary, and thus its lifetime doesn’t extend beyond the end of the let statement! i.e. it would possibly just be optimised away before it could used. The compiler does helpfully provide an indication of how to make it work: use a let binding:

// taking Rn, make Rn+1 from it
fn make_next_row(v: &Vec<u32>) -> Vec<u32> {
    let zero = [0];
    let i1 = zero.iter().chain(v.iter());
    let i2 = v.iter().chain(zero.iter());

    // sum the two lists together.
    i1.zip(i2).map(|(a, b)| a + b).collect()
}

And this now works. But we have to explicitly tell the compiler how to extend the lifetime of [0] as assigning it to zero increases the lifetime to the end of the scope (the } at the end of the function), and by then it’s been used in the summing function (map(|a, b)| a + b) so it can then be reclaimed.

Second part: borrowing

So the second problem I ran into, and what made me think really hard about what is going on is the concept of borrowing, mutability and how to convince the compiler to just make some code.

The code to do that eventually ended up looking like this, but again, wouldn’t compile:

pub struct PascalsTriangle {
    rows: u32,
}

impl PascalsTriangle {
    pub fn new(row_count: u32) -> Self {
        PascalsTriangle { rows: row_count }
    }

    pub fn rows(&self) -> Vec<Vec<u32>> {
        let mut rs: Vec<Vec<u32>> = Vec::new();       // 1.
        let mut current_row: Vec<u32>;

        if self.rows == 0 { return rs; }              // 2.
        rs.push(vec![1]);                             // 3.
        if self.rows == 1 { return rs; }              // 4.
        current_row = vec![1];                        // 5.
        for _ in 1..self.rows {                       // 6.
            current_row = make_next_row(current_row); // 7.
            rs.push(current_row);                     // 8.
        }
        rs                                            // 9.
    }
}

Compiling this produces a bunch of errors. Anyway, what’s the code supposed to do? (Also, this is not nice code; I don’t think this is good style or idiomatic Rust!)

So that deals with the 0 and 1 rows. Now to the intersting bit:

Fix ownership

This code doesn’t work. It looks like it should, coming from a language like Python, but there are problems. The first is on line 7:

current_row = make_next_row(current_row)
^                           ^
|                           |
|                           - current_row is moved to the make_next_row(...) function
|
- can't use current_row here as we've already moved it!

Basically, this transfers ownership of the thing that current_row points to to the make_next_row(..) function which means basically that we can’t use it any more. But we need to retain ownership of the current_row in this function, so we have to lend it to the function only:

current_row = make_next_row(&current_row)

The little & is the borrow indication that means we only intend to allow an immutable use of thing that current_row represents to the make_next_row(...) function. It’s immutable because, by default, borrows are immutable unless a mut is included as part of the borrow. When make_next_row(...) returns we get ownership of current_row back.

As a side note, a variable can be a mutable borrow many times, but only an immutable borrow once. As the Rust book states:

You may have one or the other of these two kinds of borrows, but not both at the same time:

  • one or more references (&T) to a resource,
  • exactly one mutable reference (&mut T).

Obviously (!) the receiving function also has to have an argument signature that indicates that it accepts borrowed variables, which I ‘hid’ in the first part above:

fn make_next_row(v: &Vec<u32>) -> Vec<u32> {
   ...

(Note the & that is part of v: &Vec<u32>).

Fixing the other subtle bug that the compiler finds for you

The next bug is here:

            rs.push(current_row);                     // 8.

This bug is curious. We’re basically saying to Rust: “add the current row to rs, and take ownership of it”. We have to give rs something it can own because it’s going to return it to the caller as part of the rs structure, which means the lifetime of the object has to exist beyond the scope of this function. So it has to move and this is done by transferring ownership (the default) to rs with the push(...) function.

But, we also want to use the mutable current_row again to make the next row as part of the iteration. The solution is to clone() the vector and give that to rs to own:

            rs.push(current_row.clone());                     // 8.

So this is a working solution, but I wasn’t that happy with it:

pub struct PascalsTriangle {
    rows: u32,
}

impl PascalsTriangle {
    pub fn new(row_count: u32) -> Self {
        PascalsTriangle { rows: row_count }
    }

    pub fn rows(&self) -> Vec<Vec<u32>> {
        let mut rs: Vec<Vec<u32>> = Vec::new();
        let mut current_row: Vec<u32>;

        if self.rows == 0 { return rs; }
        rs.push(vec![1]);
        if self.rows == 1 { return rs; }
        current_row = vec![1];
        for _ in 1..self.rows {
            current_row = make_next_row(&current_row);
            rs.push(current_row.clone());
        }
        rs
    }
}

A little better; more idiomatic?

So the next iteration looked like this:

    pub fn rows(&self) -> Vec<Vec<u32>> {
        match self.rows {
            0 => Vec::new(),
            1 => { vec![vec![1]] },
            _ => {
                (1..self.rows).fold(
                    vec![vec![1]],
                    |v, _| {
                        let mut vs = v.clone();
                        vs.push(make_next_row(v.last().unwrap()));
                        vs
                    })
            },
        }
    }

This uses a match statement instead of the multiple if statements, and uses a fold(...) to constuct the vector of vectors that represents the rows of Pascal’s Triangle.

Note that v.last().unwrap() is already a borrow, so can be given to make_next_row(...), and the accumulator in the fold is vs for each iteration which is also created on each iteration. There must be some way to NOT have to not only make a new vector, but also to clone it on every iteration.

Eliminating the v.clone()

I’m making two vectors for each iteration. The one from make_next_row(...) and the v.clone(). So it is possible to re-arrange the internals of the fold(...) to eliminate the clone:

        (1..self.rows).fold(
                vec![vec![1]],
                |v, _| {
                    let x = vec![make_next_row(&v.last().unwrap())];
                    [v, x].concat()
                })

The difference here is that we use a temporary variable to make the next row using a borrow of v, and then construct a new vector of v and x in the [v, x].concat(). Note we can’t do this:

    [v, vec![make_next_row(&v.last().unwrap()].concat()

We can’t do it because the first v (as in [v, ...]) moves v into the [...].concat() expression, so we can’t then take a mutable borrow inside that expression. Annoying, but true!

Performance, abstractions and Python

I’ve written two versions of the Pascal’s Triangle producer code; one is using a mutable approach; the other takes a functional approach and thus (I think) creates more vectors on the heap. I thought it would be good to see how much, if any, the additional abstractions offered in Rust actually cost in terms of performance. And for fun, I thought I’d compare it to a Python equivalent.

The Python code (for the first solution):

class PascalsTriangle:

    def __init__(self, rows):
        self.num_rows = rows

    def rows(self):
        rs = []
        if self.num_rows == 0:
            return rs
        rs.append([1])
        if self.num_rows == 1:
            return rs
        current_row = [1]
        for _ in range(1, self.num_rows):
            current_row = make_next_row(current_row)
            rs.append(current_row)
        return rs

def make_next_row(current_row):
    return [a + b for a, b in zip([0] + current_row,
                                  current_row + [0])]

and for the second solution (just the rows() method):

    def rows(self):
        if self.num_rows == 0:
            return []
        if self.num_rows == 1:
            return [[1]]

        return functools.reduce(
            lambda a, _: a + [make_next_row(a[-1])],
            range(1, self.num_rows),
            [[1]])

Performance

To eliminate compile/load times, I’ve built the timing into the code for each language, and ran 1,000,000 loops. For comparison purposes the machine is an Intel 6800k at stock clocks, running Ubuntu Linux 16.10.

For Python, 1,000,000 iterations of asking for 10 rows for the two approaches is:

PascalsTriangle1: 12.373533822013997
PascalsTriangle2: 13.359421955014113

So the more ‘functional’ version is about 8% slower than the imperative version. For the Rust version:

PascalsTriangle1: 0.710322107
PascalsTriangle2: 2.002551761

The Rust version 1 (using mutable variables) is about 17 times faster that the Python equivalent, and version 2 only around 6 times faster when comparing functional versions. I’m guessing an experienced Rust programmer could get more performance by knowing how to get the Rust compiler to produce a more optimised version.

Most of the code used in this post is available here.


Final thoughts

Obviously, I’m a complete beginner with Rust. Writing the Rust versions of Pascal’s Triangle was both time consuming and frustrating. I had to spend a lot of time looking at compiler errors, going and reading documentation, and then trying out new things until I eventually got the program to compile.

However, the odd thing was, is that once I got a version to compile it almost always did what I wanted it to. There were no type errors (obviously) and the (trivial) program gave the correct output.

The contrast with the Python program couldn’t be more different. I’m an experienced Python programmer, and I tried to write the Python in a similar style to the Rust program, which I wrote first. It was much quicker to write, but I discovered I made ‘silly’ errors, and these were only picked up when I ran the trial program. So the write-debug process was: change the program, run it, look at the runtime errors, change something, try again.

Whilst the latter approach is great, and quick, for small scripts, it becomes extremely painful for very large programs with long runtimes. I think in that case the stricter, and, frankly, harder-to-get-working Rust approach would lead to more bullet-proof and likely-to-work programs. Which is the selling point for Rust.

It also produces runtimes, even for a beginner like me, that are considerably quicker than the equivalent Python program.

I’m enjoying Rust, but I’d also like to compare it to Go, so I will spend a little time with that next.

comments powered by Disqus