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.

Duplicate of [How do I create a global, mutable singleton?](http://stackoverflow.com/questions/27791532/how-do-i-create-a-global-mutable-singleton). — Shepmaster, Mar 26 '16 at 02:18
Or you can alter the signature of `cached_expensive` to accept the cache as another parameter. — Shepmaster, Mar 26 '16 at 02:20
I don't think this is a duplicate. My question is specifically about caching and, while my starting point is a global, mutable singleton, that is incidental and a good solution might explain how (for example) a `RefCell` or `Mutex` could make this better, or offer a completely different alternative structurally. — Peter Hall, Mar 26 '16 at 02:23
I disagree, but I won't use the magic dupehammer until others agree with me. In short, there's *nowhere* else to store data. Either you pass in a place to store it (via an explicit argument or implicitly via `self`) or it has to be stored in global storage. The latter has the restriction that you are required to handle concurrent access to the cache. — Shepmaster, Mar 26 '16 at 02:26
While I'm not quite able to reason it out right now, I have a feeling that the proposed `unsafe` block in the question doesn't uphold the safety guarantees that it is required to. For example, I'm pretty sure that concurrent calls to the function can have partial reads/writes to the storage (as there's no mutual exclusion), causing strange behavior in arbitrary circumstances. — Shepmaster, Mar 26 '16 at 02:31
@Shepmaster Yes, this was my concern, which led me to post the question. I have read the question that you linked to as a dupe, and it's actually very helpful. The `Arc>` construction looks like what I need. But I am going to rethink if I can't just do this differently. I'm coming into an existing codebase, so it's not so straightforward.. — Peter Hall, Mar 26 '16 at 02:34
@Shepmaster is right. Your code as written will permit unsynchronized reads/writes to the same location in memory. The `lazy_static` approach in the question linked is probably what you want. (To a first approximation. There may be faster approaches...) — BurntSushi5, Mar 26 '16 at 02:53

score 8 · Accepted Answer · answered Apr 14 '16 at 16:19

8

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
}

answered Apr 14 '16 at 16:19

malbarbo

10,717
1
42
57

So you agree this is a duplicate of [How do I create a global, mutable singleton?](http://stackoverflow.com/questions/27791532/how-do-i-create-a-global-mutable-singleton) as suggested in the comments? – Shepmaster Apr 14 '16 at 16:24
1

Yes. But I decide to write the answer to show that the global variable can be declared inside the function, so the scope is local. – malbarbo Apr 14 '16 at 16:28

score 7 · Answer 2 · answered Oct 29 '18 at 14:13

7

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

answered Oct 29 '18 at 14:13

zakum1

895
6
20

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

2 Answers2

Linked