What is the idiomatic way to implement caching on a function that is not a struct method?

Question

I have an expensive function like this:

pub fn get_expensive_value(n: u64): u64 {
   let ret = 0;
   for 0 .. n {
       // expensive stuff
   }
   ret
}

And it gets called very frequently with the same argument. It's pure, so that means it will return the same result and can make use of a cache.

If this was a struct method, I would add a member to the struct that acts as a cache, but it isn't. So my option seems to be to use a static:

static mut LAST_VAL: Option<(u64, u64)> = None;

pub fn cached_expensive(n: u64) -> u64 {
   unsafe {
       LAST_VAL = LAST_VAL.and_then(|(k, v)| {
           if k == n {
              Some((n,v))
           } else {
              None
           }
       }).or_else(|| {
           Some((n, get_expensive_value(n)))
       });
       let (_, v) = LAST_VAL.unwrap();
       v
   }
}

Now, I've had to use unsafe. Instead of the static mut, I could put a RefCell in a const. But I'm not convinced that is any safer - it just avoids having to use the unsafe block. I thought about a Mutex, but I don't think that will get me thread safety either.

Redesigning the code to use a struct for storage is not really an option.

Answer 1

I think the best alternative is to use a global variable with a mutex. Using lazy_static makes it easy and allows the "global" declaration inside the function

pub fn cached_expensive(n: u64) -> u64 {
    use std::sync::Mutex;
    lazy_static! {
        static ref LAST_VAL: Mutex<Option<(u64, u64)>> = Mutex::new(None);
    }
    let mut last = LAST_VAL.lock().unwrap();
    let r = last.and_then(|(k, v)| {
        if k == n {
            Some((n, v))
        } else {
            None
        }
    }).or_else(|| Some((n, get_expensive_value(n))));
    let (_, v) = r.unwrap();
    *last = r;
    v
}

Answer 2

You can also check out the cached project / crate. It memoizes the function with a simple macro.