#cache #memoization


A copy-less and clone-less function caching library

8 releases (1 stable)

1.0.0 Jan 28, 2023
0.5.0 Nov 14, 2019
0.4.1 Sep 19, 2019
0.3.0 Aug 31, 2019
0.1.1 Aug 24, 2019

#66 in Caching

Download history 8/week @ 2023-06-04 1/week @ 2023-06-18 8/week @ 2023-06-25 11/week @ 2023-07-02 2/week @ 2023-07-23 1/week @ 2023-07-30 1/week @ 2023-08-06 8/week @ 2023-08-13 184/week @ 2023-08-20 52/week @ 2023-08-27 261/week @ 2023-09-03 1/week @ 2023-09-10 67/week @ 2023-09-17

381 downloads per month

MIT license

703 lines

fn_cache crate

This crate implements an easy way to cache values for a function. If you have a slow running function, this can be used to speed up successive runs dramatically. It is also quite useful for memoization of recursive functions, to prevent calculating the same function twice in different calls.

Of particular note, this caching is done without cloning or copying, allowing functions to return large objects, while the cache only returns a reference to them instead of copying them.

Allowed functions

This crate attempts to remain fairly flexible with the functions it accepts. All of the following should be allowed:

  • fn types.
  • Fn types that have no references.
  • Fn + 'static types that take only static references.
  • Fn + 'a types that take references of lifetime 'a.

For obvious reasons, FnMut and FnOnce are not allowed, as functions need to be rerunnable and pure.


The caches can handle recursive functions, with a shortcut for defining it with non-recursive functions. Each cache has a recursive function to create a recursion capable cache, but requires the function to accept the cache as the first argument. Each new function takes a function that does not require the cache as an argument.


Here is an example for a function that takes a while to calculate. Instead of running the calculations each time you'd like to do it just once, and recall the value. The results are stored in a HashCache for random access.

use fn_cache::{FnCache, HashCache};
use std::{thread, time};

let sleep_time = time::Duration::from_secs(3);

let mut cache = HashCache::new(|&x| {

let start = time::Instant::now();
assert_eq!(cache.get(100), &100);
assert_eq!(cache.get(100), &100);

// time elapsed is only slightly longer than the sleep time
// far less than twice.
assert!(time::Instant::now() - start < sleep_time.mul_f32(1.1));


The following example shows a recursive fibonacci implementation, which would be O(2ⁿ) without memoization (caching). With memoization, it becomes O(n), and can easily be calculated.

use fn_cache::{FnCache, HashCache};

let mut cache = HashCache::<u8,u128>::recursive(|cache, x|
    match x {
        0 => 0,
        1 => 1,
        _ => *cache.get(x - 1) + *cache.get(x - 2),


For even bigger results, the num crate might be employed. In order to avoid copying the BigUints while accessing the cache twice, you can to change the result to be stored in an Rc. Additionally, since the inputs start at 0 and each value must be filled before the next is calculated, you might use a VecCache as an optimization.

Note: The only reason you need an Rc is because you need two references at the same time. If only a single reference is needed for the recursion, Rc is unnecessary.

use std::rc::Rc;
use fn_cache::{FnCache, VecCache};
use num_bigint::BigUint;

let mut cache = VecCache::<Rc<BigUint>>::recursive(|cache, x|
    match x {
        0 => BigUint::new(vec![0]),
        1 => BigUint::new(vec![1]),
        _ => cache.get(x - 1).clone().as_ref()
            + cache.get(x - 2).clone().as_ref(),

    &BigUint::parse_bytes(b"26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626", 10).unwrap()

No runtime deps