michie (sounds like Mickey) — an attribute macro that adds memoization to a function.

Table of contents

1. Features
2. Non-features
3. key_expr
4. store_type
5. store_init
6. Type requirements
   1. General bounds
   2. Store bounds
7. Generic functions
8. Functions that take no input
9. How it works
10. Why must key_expr be provided
11. Support and feedback

Features

• Supports
  • Plain functions
  • Generic functions
  • Functions in impl blocks
  • Functions in trait implementation blocks
  • Functions that are default trait implementations
• Thread safe
• Expansion depends on only std
• Hygienic
• Supports recursive functions
• Bring your own store

Non-features

• Caching features: this crate does not provide a caching mechanism other than some trivial implementations. It allows you to bring your own.
• "Blazingly fast": this crate aims to provide a simple and easy-to-use means of memoizing a function. If you actually really require micro-optimized memoization then you'd most likely have to implement it yourself.

key_expr

In each invocation a key is obtained. It is used to query the function's cache store for a possible hit. An expression that evaluates into a key must be provided via the key_expr argument. The expression may use bindings from the function's parameters. In the following example the key_expr is simply the name of the only parameter.

use michie::memoized;
use std::collections::HashMap;
#[memoized(key_expr = input, store_type = HashMap<usize, usize>)]
fn f(input: usize) -> usize {
    // expensive calculation
    # unimplemented!()
}

store_type

A concrete store type must be either provided via the store_type argument or inferred from the store_init (next section).

The provided type must implement MemoizationStore. Implementations of MemoizationStore for BTreeMap and HashMap are provided. In the following example, BTreeMap is provided as the store:

use michie::memoized;
use std::collections::BTreeMap;
#[memoized(key_expr = input, store_type = BTreeMap<usize, usize>)]
fn f(input: usize) -> usize {
    // expensive calculation
    # unimplemented!()
}

store_init

By default, the store is initialized via [Default::default()]. Different initialization may be provided via an expression to store_init:

use michie::memoized;
use std::collections::HashMap;
#[memoized(key_expr = input, store_init = HashMap::<usize, usize>::with_capacity(500))]
fn f(input: usize) -> usize {
    // expensive calculation
    # unimplemented!()
}

Type requirements

Bounds apply to the key type and the function's return type. Some are from the general instrumentation and others are via the store type's implementation of MemoizationStore.

General bounds

The following apply to the key type and to the function's return type:

• Sized: for one, the instrumentation stores the key in a let binding.
• 'static: key and return values are owned by a store which is owned by a static.
• Send and Sync: for parallel access.

Store bounds

Another source of bounds on the key type and the return type is the implementation of MemoizationStore for the store type.

Generic functions

Be mindful of the type requirements when using on a generic function:

use michie::memoized;
use std::hash::Hash;
use std::collections::HashMap;
#[memoized(key_expr = input.clone(), store_type = HashMap<A, B>)]
fn f<A, B>(input: A) -> B
where
    A: 'static + Send + Sync // bounds from instrumentation
        + Eq + Hash // store-specific bounds
        + Clone, // used in this function's `key_expr`
    B: 'static + Send + Sync + Clone // bounds from instrumentation
        + From<A>, // used in this function's body
{
    input.into()
}

Functions that take no input

Functions that take no input are good candidates for compile-time evaluation, which is usually preferred over runtime caching (such as this crate provides). Nonetheless, some functions cannot be evaluated at compile time. A reasonable key_expr for a function that takes no input is ():

use michie::memoized;
use std::collections::HashMap;
#[memoized(key_expr = (), store_type = HashMap<(), f64>)]
fn f() -> f64 {
    // expensive calculation
    # unimplemented!()
}

How it works

The original function expands into something similar to this:

fn f(input: Input) -> Output {
    static STORE = Mutex::new(#store_init);
    let key = #key_expr;
    let store_mutex_guard = STORE.lock().unwrap();
    let attempt = store_mutex_guard.get(&key);
    drop(store_mutex_guard);
    if let Some(hit) = attempt {
        return hit;
    } else {
        let miss = #original_fn_body;
        let miss = STORE.lock().unwrap().insert(key, miss);
        return miss;
    };
}

Why must key_expr be provided

The only conceivable default key_expr is the entire input. For example, for a function signature:

fn f(a: usize, _b: usize) -> usize

the default key_expr would be (a, _b). Two potential problems: some parameters might not satisfy bounds on the key type. Also, the resulting key might be a supervalue of the input of the actual calculation. To explain the latter problem, here is an example:

use michie::memoized;
use std::collections::HashMap;
// pretend that `key_expr` is omitted and that this is the default
#[memoized(key_expr = (a, _b), store_type = HashMap<(usize, usize), usize>)]
fn f(a: usize, _b: usize) -> usize {
    // the actual calculation uses a subvalue of the input — only `a`
    # a
}
f(0, 0); // expected miss because it's the first invocation
f(0, 1); // avoidable miss!

If an accurate key_expr = a had been provided, the second execution would have been a hit. To summarize, key_expr is mandatory in order to encourage proper consideration of it.

Support and feedback

In the GitHub Discussions.