Convert struct to use references instead of owning its values

struct Fibonnaci {
    a: BigUint,
    b: BigUint
}

impl Iterator for Fibonnaci {
    type Item = BigUint;

    fn next(&mut self) -> Option<Self::Item> {
        let n = self.a.clone();
        self.a = self.b.clone();
        self.b = self.b.clone() + n.clone();
        Some(n)
    }
}

I want to make this faster by using references in the Fibonnaci struct, so something like

struct Fibonnaci<'a> {
    a: &'a mut BigUint,
    b: &'a mut BigUint
}

But I'm having some trouble with converting the next() function into something that uses references. Here's my attempt:

impl<'a> Iterator for Fibonnaci<'a> {
    type Item = BigUint;

    fn next(&mut self) -> Option<Self::Item> {
        let n = self.a.clone();
        self.a = self.b;
        self.b = &mut (self.b.clone() + n);
        Some(n)
    }
}

but I'm getting lifetime of reference outlives lifetime of borrowed content... at the line self.a = self.b;. I don't quite understand why this is a problem as I thought the reference annotations in struct Fibonnaci<'a> mean that self.a and self.b should have the same lifetime.

I'm not sure if using references will actually buy you much: BigUints are a wrapper around Vec, so they're already using a layer of indirection. You can reduce the number of clones to one while keeping an owned approach:

struct Fibonnaci {
    a: BigUint,
    b: BigUint
}

impl Iterator for Fibonnaci {
    type Item = BigUint;

    fn next(&mut self) -> Option<Self::Item> {
        let n = std::mem::replace(&mut self.a, self.b.clone());
        self.b += &n;
        Some(n)
    }
}

Playground


You can't move the &mut out of self.b without leaving something in its place, so the compiler does a "reborrow" here instead, making a new reference to *self.b. This new reference can't outlive the body of the next function. To do this with references, the code needs to look something like this:

impl<'a> Iterator for Fibonnaci<'a> {
    type Item = BigUint;

    fn next(&mut self) -> Option<Self::Item> {
        let n = self.a.clone();
        std::mem::swap(&mut self.a, &mut self.b);
        *self.b += &*self.a;
        Some(n)
    }
}

Playground

1 Like

Why do you think references are faster?

If you want to make the struct smaller by adding a layer of indirection, then Box is the correct way to store things by reference.

In Rust &mut is an exclusive temporary borrow, which also implies that it does not store the value.

So you can't make a new value of BigUint inside next, not store it anywhere, and then borrow it from… nowhere. In Rust borrowing always implies things being stored somewhere else.

2 Likes

This is a very clear explanation, thank you!

My thought process was that by using references, I would be able to make self.a point to the same BigUint as self.b, hence I wouldn't have to clone it over. Perhaps a better question would be how could I reduce the number of .clone()'s in the next() function, but my assumption was that this required references. Thanks for your answer!

&mut is only one of many types of pointers that Rust has (like Box and Arc which are owning equivalents of &mut and &).

In this case temporary references are inappropriate, because they're borrowing instead of owning, but iterator makes new values, so something has to own them.

It's the same mistake as using &str instead of String, even though both are strings, and both have string data behind a pointer, one is borrowing the data and the other is owning.

As others have already answered, in this case the key trick is to use swap or replace to change these values without additional copies. In other situations wrapping things in Arc allows cheaply referencing an object from multiple places, while also owning its content.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.