9
\$\begingroup\$

I am learning Rust and decided to create a simple program to calculate n-th Fibonacci number. It uses a vector for memoization. The program works, but what would you suggest to improve here? Maybe store memo inside fib function as a static variable?

I tried to use u32 everywhere, but 48-th fib number doesn't fit into u32, so I decided to use u64.

use std::io;
use std::io::Write;
use std::str::FromStr;

fn fib(n: u32, memo: &mut Vec<u64>) -> u64 {
    if n < 2 {
        return n as u64;
    }
    else if memo[(n-1) as usize] != 0 {
        return memo[(n-1) as usize];
    }

    memo[(n-1) as usize] = fib(n - 1, memo) + fib(n - 2, memo);
    memo[(n-1) as usize]
}

fn main() {
    loop {
        print!("n = ");
        io::stdout().flush().unwrap();

        let mut str: String = String::new();
        io::stdin().read_line(&mut str)
            .expect("Error getting number");

        str.pop();
        match u32::from_str(&str) {
            Ok(n) => {
                let mut memo: Vec<u64> = vec![0; n as usize];
                println!("fib({})={}", n, fib(n, &mut memo));
                break;
            }
            Err(_e) => {
                println!("Error parsing number.");
                println!("Try again");
            }
        };
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Related Q&A Recursive Fibonacci in Rust with memoization \$\endgroup\$ Mar 14, 2021 at 8:53
  • 3
    \$\begingroup\$ I am not familiar with Rust conventions, but I feel some comments should be in place, if only to split segments of main, and to define what fibonacci does (maybe this is redundant, since most people already know the function, but good habits are best learned early). You mention overflow due to u32/u64. This is an example of stuff which often should/could be mentioned in-code, although it is often commented in-documentation instead. \$\endgroup\$
    – mazunki
    Mar 14, 2021 at 15:44

3 Answers 3

11
\$\begingroup\$

I like this. Your code is clean and pretty readable. I recommend using rustfmt, if only because it will stop annoying people on the internet from recommending you use rustfmt. But the minor code formatting differences are not something to be overly concerned about, if you have a style and stick with it.

I have two major suggestions:

  1. Don't populate the cache with a sentinel value (zero) and then test whether each value is zero or not. Instead, make the vector start small and grow as you populate it. To avoid reallocation, you can initialize it with a large capacity and small length. You can further simplify the logic by (a) using push to add a value to the cache when you know the length is n; and (b) initializing the cache to [0, 1], which will play into the next point:

  2. Split fib into two functions: one that takes a cache as argument, and one that creates the cache inside itself (and calls the first one to do the heavy lifting). If you expose both of these in an API, then the user can decide whether reusing the cache is appropriate or not.

Here's the main code with both suggestions implemented:

fn fib_cached(n: u32, memo: &mut Vec<u64>) -> u64 {
    if (n as usize) < memo.len() {
        memo[n as usize]
    } else {
        let ret = fib_cached(n - 2, memo) + fib_cached(n - 1, memo);
        // At this point we know that memo.len() is at least n, because
        // fib_cached(n - 1, memo) will have populated memo[n-1]. Furthermore, if
        // memo.len() had been greater than n, we would have taken the other
        // branch of the if. There are no other functions capable of modifying
        // memo because we hold a &mut reference to it, so memo.len() is exactly n
        // and push(ret) will make memo[n] = ret.
        memo.push(ret);
        ret
    }
}

fn fib(n: u32) -> u64 {
    let mut cache = Vec::with_capacity(n as usize);
    cache.extend(&[0, 1]);
    fib_cached(n, &mut cache)
}

Here are some more observations, in no particular order:

  • Even this modified version is somewhat fragile, since it's easy to call fib_cached with a too-small cache, which may panic. If you were writing a library for others to use, I would suggest making a wrapper type around Vec<u64> so you can insist on correctly-initialized caches. This would be a start:

    struct FibCache {
        data: Vec<u64>,
    }
    
    impl FibCache {
        fn with_capacity(n: usize) -> Self {
            let mut data = Vec::with_capacity(n);
            data.extend(&[0, 1]);
            FibCache {data}
        }
    }
    
    fn fib_cached(n: u32, memo: &mut FibCache) -> u64 {
        if (n as usize) < memo.data.len() {
            memo.data[n as usize]
        } else {
            let ret = fib_cached(n - 2, memo) + fib_cached(n - 1, memo);
            memo.data.push(ret);
            ret
        }
    }
    
    fn fib(n: u32) -> u64 {
        let mut cache = FibCache::with_capacity(n as usize);
        fib_cached(n, &mut cache)
    }
    

    This means nobody can call fib_cached without creating a FibCache object with a constructor you define. It also lets you make backwards-compatible changes to the type of cache -- you could use a HashMap, as 6005 suggests, or another data structure, without changing the outward-facing API of the library.

  • n as usize is another source of fragility. Casting between integer types can have surprising results, so you're usually well-advised to use usize::try_from(n).unwrap() instead, which will panic if the conversion can't be done. In this code, I don't regard this as a major issue because u32 is losslessly convertible to usize on virtually all Rust targets and because any n that would overflow a usize, on any target, is already too large for this algorithm. Just be aware you should normally use the conversion traits instead of casting.

  • Changing fib to use internal static state is pretty simple, using lazy_static or once_cell. I'll use lazy_static here, and assume the FibCache API above:

    fn fib(n: u32) -> u64 {
        use lazy_static::lazy_static; // 1.4.0
        use std::sync::Mutex;
        lazy_static! {
            static ref CACHE: Mutex<FibCache> = Mutex::new(FibCache::with_capacity(10));
        }
        fib_cached(n, &mut *CACHE.lock().expect("Could not lock static cache"))
    }
    

    Whether this is a good idea or not is rather up for debate. Ultimately it's replacing contention for one resource (the heap) with contention for another resource (the lock). Neither is necessarily the best choice, which is why it's important to expose fib_cached as well so your users aren't stuck with your choice of implementation for fib. Making access to FibCache lock-free could make static memory much more appealing by removing the contention aspect.

  • Don't use str as the name of a variable, since it's also the name of a built-in type. It will mess with syntax highlighting (as it does on this very site).

  • Obviously, this is a slow and wasteful algorithm for calculating Fibonacci numbers. So I assume what you're looking for is feedback on the general shape and style of the solution, not the choice of algorithm, and I've written this review based on that assumption. Peter's review deals with algorithmic improvements.

\$\endgroup\$
5
  • \$\begingroup\$ Great suggestions, particularly the use of lazy_static / once_cell. \$\endgroup\$
    – 6005
    Mar 14, 2021 at 0:28
  • 1
    \$\begingroup\$ Taking a lock to access the tiny array sounds pretty terrible, like never worth it instead of "only worth it in contrived cases to answer Fib(n) queries very fast from an array that stays hot in cache". What could be worth it is lock-free atomics; I assume Rust has a way to something equivalent to C++ std::atomic<>. A memory_order_relaxed load from the array will either be 0 or the value we want; if 0, we can go and compute that Fibonacci number from lower elements... As long as we always check for 0, don't assume that seeing a non-zero means lower entries are also non-0, we're fine. \$\endgroup\$ Mar 14, 2021 at 8:34
  • \$\begingroup\$ Blocking multiple writers isn't needed; they'll both be writing the same value. Once nobody's writing (to the same cache line), you get perfect read-side scaling to N readers on N CPU cores. \$\endgroup\$ Mar 14, 2021 at 8:34
  • \$\begingroup\$ Good points @Peter. I'm happy to sweep the awfulness of locking under the "irrelevant for this algorithm, but maybe..." rug, for the most part. More practically, using &mut in the API almost insists upon the lock, since it's an exclusive reference, but you could certainly relax that to & and use atomics from the Rust standard library instead. If I get bored enough this afternoon, maybe I'll try it. \$\endgroup\$
    – trent
    Mar 14, 2021 at 11:41
  • 1
    \$\begingroup\$ I posted an answer about algorithmic optimizations (e.g. keeping track of your memo cache fill point instead of basically linear-searching for it backwards). I notice you used fib_cached(n - 2, memo) + fib_cached(n - 1, memo); but didn't comment on doing n-2 first, which is what current rustc seems to do, even if there's no language guarantee of eval order(?). I wrote some about the effect: turns out no reduction in total number of calls, or of memo-cache misses, but it does cut the max recursion depth in half. (I don't really know Rust, so unfortunately I didn't flesh out some of the ideas) \$\endgroup\$ Mar 14, 2021 at 12:06
6
\$\begingroup\$

Looks good in general. Your main loop for parsing the input is generally idiomatic, except I would remove that pesky .unwrap() and explicitly report the error: .flush().expect("Yikes! Failed to flush stdout!")

The fib logic is a bit convoluted in terms of readability, mainly for two reasons: first the (n-1) everywhere in the memoization vec, and second the fact that the memoization entry could be 0 and this implicitly behaves like a None value. At the cost of an extra hash computation, it would be most natural to use a HashMap for memoization, something like this:

use std::collections::HashMap;

fn fib(n: u32, memo: &mut HashMap<u32, u64>) -> u64 {
    if n < 2 {
        return n as u64;
    }
    memo.get(&n).cloned().unwrap_or_else(|| {
        let result = fib(n - 1, memo) + fib(n - 2, memo);
        memo.insert(n, result);
        result
    })
}

Much cleaner! One would have to do some profiling to see the extent of the performance difference. Alternatively if you still want to use a Vec, remove the n - 1 offset, and consider letting the vector grow: currently your code

memo[(n-1) as usize]

has a silent runtime error when the memo map is not large enough --- not good. Letting it grow also has the advantage that you don't need to initialize with 0s. Growing won't make any performance difference from what you have now as long as you initialize with a starting capacity Vec::with_capacity. If you don't allow the vec to grow, use the memo.get(i) method instead of memo[i], or as a last resort, heavily document the in-bounds requirement and add debug_assert!(n <= memo.len()) to raise an error in debug mode on out-of-bounds input.

Using a static variable for memoization is an option, but as it requires unsafe to modify and generally leads to less transparent performance for the end user, I wouldn't recommend it over having a slightly more complex API.

Finally, you mention that fib(n) gets too large as n grows for a u32 -- indeed, it is even too large for a u64, looks like starting at n = 94. So fib is actually a great use case for using a true (unbounded) integer library, such as the num::BigInt crate.

\$\endgroup\$
2
  • \$\begingroup\$ "code memo[(n-1) as usize] has a silent runtime error when the memo map is not large enough" - it does not, because if n = 0, it will use the branch: if n < 2 at the top. I tested it with n = 0 and 1. It works. \$\endgroup\$
    – user4035
    Mar 14, 2021 at 10:32
  • 2
    \$\begingroup\$ @user4035 Maybe I was unclear -- I am not talking about n = 0, but the case where n > memo.len(). \$\endgroup\$
    – 6005
    Mar 15, 2021 at 1:30
4
\$\begingroup\$

Why use slow recursion for the case where you do need to fill the cache? Just to make memoization look good by comparing it to an O(Fib(n)) naive implementation instead of an O(n) simple loop? That's not a great choice if you're actually trying to answer queries for Fib(n) as fast as possible.

Although to be fair, Fib(93) is the largest value that will fit in a u64, so in real life you'd just fill the array when you allocate the cache because it's so fast, then every query is a single array index, after a bounds check (explicit in the source or using memo.get(i)).

Or don't cache at all, since the max 93 iterations will go very fast, especially on a 64-bit CPU. Perhaps using x.overflowing_add(y) or .checked_add to detect overflow, although checking n against a known constant ahead of the loop will keep that work out of the loop. Anyway, let's imagine you were using arbitrary precision num::BigInt, or a different function with similar recursion but less fast growth, so the memo cache could get big enough to be interesting. Or just for the sake of optimizing.


If you kept a fill-position counter as part of a memo object, you could fill it up to where you need with a simple x+=y; y+=x; unrolled loop. That can over-fill by 1 past where you need, but it's so cheap that it's worth it. Just make sure to use .wrapping_add() so it's safe even on overflow, or start your array with memo[0] = Fib(0) = 0, avoiding the n-1 and making your pairs end with an odd number. So 0,1 2,3 ... 92,93 ending with 93, the last Fibonacci number that doesn't overflow u64.

What you're doing now is effectively a (recursive) linear search for the highest non-zero entry in your memo cache1. If you don't want to keep a previous fill mark, you can at least speed up the search. If you drop the recursion, it would be easy to write a loop that steps backwards more than 1 element at a time. (e.g. by 4 might be good here, or larger if the max possible cache size is a lot larger than 93). This does make things more complex: the possibility of n-4 wrapping means you'd want a checked_sub, or fill the first 4 Fib memo entries to start with.

You could even binary search: you can tell whether you're above or below the point you're looking for by checking it against 0. And you only need to get close, e.g. stop on a non-zero when the known range is small. (This would be pain to do recursively, but would make sense as a search loop ahead of a fill-the-memo iterative loop.)

If you want to keep the recursion, having fib(n-2, memo) evaluated first limits recursion depth. That gives you a linear search with a stride of 2 instead of 1, reducing the max recursion depth by a factor of 2. But it turns out there's no saving in total work, though. After fib n-2 runs, the fib n-1 in the same line will also miss in the memo cache and itself recurse. If you did it in the other order, fib n-1 then fib n-2, the n-2 calls would always return right away. We can fix this by having fib(n) fill the memo cache up to n+1 by doing another add, basically sneaking an unrolled iteration in there.

Apparently Rust evaluation order is guaranteed left-to-right for the operands of operators like + in the latest nightly builds. Before that, all I could find were old discussions like this), where there was no definite conclusion about any guarantee. In practice at least, rustc 1.50 does run the left hand side first in this case (https://godbolt.org/z/3h15nW). To guarantee that the n-2 call runs first, you can do it in a separate statement. I chose to use an initializer list, which is also guaranteed for the latest nightly, and which does in practice do what I want with earlier rustc.

//    memo[(n-1) as usize] = fib(n - 1, memo) + fib(n - 2, memo);

    let (mut x, y) = (fib(n - 2, memo), fib(n - 1, memo));
    x += y;
    memo[(n-1) as usize] = x;
    memo[n as usize] = y + x;    // fill an extra entry so the fib(n-1) in our caller will hit in cache

(I'm only barely learning Rust myself, that's not a coding-style recommendation. I posted this review almost entirely to review the algorithmic choices, not the Rust details.)

This of course requires memo[] to have allocated space higher up. As @trentcl pointed out, you could be using memo.push() to simplify allocation, avoiding the caller needing to reserve space beyond where it wants to fill. (The caller shouldn't have to be managing the dynamic-array bounds of the memo cache at all, unless that caller is a wrapper around the recursive function which exposes a clean API.)

I added instrumentation (counting up total calls, and memo misses (calls that get past the first if/else) in the otherwise-unused memo[0]). https://godbolt.org/z/1rc1s3 is a hacked up version I was playing around with to learn some Rust and see if I could get the compiler to do bounds checking once for n, not repeatedly for n-1 and n-2 (nope). Anyway, input is replaced by a string literal; The Godbolt compiler explorer lets you run programs these days, but not with interactive input.

That last line updating memo[n] along with evaluating fib(n-2) first cuts each of total calls and misses in about half. e.g. for fib(40):

  • original strategy: calls 79, misses 39
  • fib(n-2) first, updating memo to make its sibling hit: calls = 41, misses = 20

Footnote 1: Keep in mind that unless you use a different algorithm2 for evaluating the Nth Fibonacci number, you'll evaluate all previous numbers along the way, so the memo cache will have a contiguous range of set values, and above that all 0. Unless you want to only cache a pair of numbers every 32 or something: e.g. on a memo hit you have a starting point to iterate from with a small upper bound on how much work needs to be done to get from there to the Fib(n) you want. Shrinks your cache by a factor of 16; could be valuable for num::BigInt.

sub-footnote 2: It's possible to do Fib(n) in log2(n) steps with the Lucas sequence binary matrix exponentiation method which each use a couple integer multiplies and adds, still pure integer math. No risk of FP rounding error from the closed-form golden-ratio power closed-form formula. You wouldn't be building your cache along the way (although maybe you could do some?)

Or as this answer points out, there's F(n) = 4 * F(n-3) + F(n-6) which only fills in every 3rd entry. But it means doing all the work for F(n) doesn't help at all for F(n+1). Maybe there's some mathematical trick to pick up somewhere and get an adjacent pair of Fibonacci numbers out of this, so you could go from this every-third cache to any arbitrary number you need, but I don't know it.

\$\endgroup\$
10
  • \$\begingroup\$ I believe the function argument eval order is covered by Rust's blanket guarantee of "no breakage in safe code post-1.0" even though it's not explicitly documented anywhere (which would obviously be preferable). My review swapped them mostly on a hunch; I wasn't sure it would make a difference, but limiting the maximum recursion depth makes sense. \$\endgroup\$
    – trent
    Mar 14, 2021 at 17:03
  • 1
    \$\begingroup\$ @KonradRudolph: When I said "slow recursion", I didn't mean to imply that all recursion is slow, just that this recursive strategy is slow; doing about twice as many steps as necessary (even with memoization), and each step doing much more work than a simple loop. (But also, you need the resulting machine-code to be iterative for maximum performance. Yes, you can get that by writing your recursion in a way that the compiler can handle. Or see my hand-written x86 asm that cleverly IMO handles odd vs. even N for branchless unroll to fill an array.) \$\endgroup\$ Mar 15, 2021 at 0:35
  • 2
    \$\begingroup\$ @PeterCordes Ah, of course. Anyway, regarding your parenthetical note, the code I posted is tail recursive, and the equivalent C version obviously compiles down to assembly code without any calls. \$\endgroup\$ Mar 15, 2021 at 9:40
  • 1
    \$\begingroup\$ @PeterCordes I found this great video explaining the fast matrix multiplication algorithm for calculating fibs: youtube.com/watch?v=EEb6JP3NXBI. \$\endgroup\$
    – user4035
    Mar 16, 2021 at 23:11
  • 1
    \$\begingroup\$ I've just learned that the nightly reference now specifies left-to-right, as-written-in-the-source-code evaluation order for most expressions, including arithmetic operators and tuple expressions (initializer lists). This relatively recent change hasn't yet hit stable, which is why it's hard to find. \$\endgroup\$
    – trent
    Mar 21, 2021 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.