michie (pronounced /'mikɪ/) — an attribute macro that adds memoization to a function.

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

A basic example

use michie::memoized;
#[memoized(key_expr = input)]
fn f(input: usize) -> usize {
    // 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;
    if let Some(hit) = STORE.lock().unwrap().get(&key) {
        return hit;
    } else {
        let miss = #original_fn_body;
        STORE.lock().unwrap().insert(key, miss.clone());
        return miss;
    };
}

key_expr

The key_expr argument is an arbitrary expression. It may use bindings from the function's parameters.

A key_expr must be provided because there is no reasonable default. The only conceivable default is the entire input. In theory, that default could look like:

(param_a, param_b, param_c)

This might not suffice because some parameters might not satisfy the bounds of the key type. Even if they do, this still might not be accurate, because the resulting key might be a supervalue of the input of the actual calculation. To explain what that means, here is an example:

use michie::memoized;
#[memoized]
fn f(a: usize, _b: usize) -> usize {
    // only `a` is used
    # unimplemented!()
}

With the theoretical (a, _b) default key_expr there could be false misses:

f(0, 0); // expected miss
f(0, 1); // avoidable miss!

Had an accurate key_expr = a been provided, the second execution would be a hit.

key_type

While the type of the key supports inference, it may also be specified using the key_type argument:

use michie::memoized;
#[memoized(key_type = u64, key_expr = input.into())]
fn f(input: u32) -> u32 {
    // expensive calculation
    # unimplemented!()
}

store_type

The default store is HashMap. It is provided under the assumption that it will frequently suffice.

A store type may be provided via the store_type argument. The provided type must implement [MemoizationStore].

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

For store initialization store_init takes an expression that returns a store. If omitted, Default::default() is used.

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

Type requirements

Minimal bounds are imposed on the key type and the return type. Some of these bounds are from the general instrumentation and some from the store.

General bounds

On key type and return type:

• Sized: for one, the instrumentation stores the key in a let binding.
• 'static: the key and return values are inserted into the store, which lives across function invocations, therefore the store cannot borrow from these functions.
• Clone: the key and return values are cloned for insertion into the store.
• Send and Sync: for parallel access.

Store bounds

Be mindful of the bounds imposed by the store_type's implementation of [MemoizationStore]. The default store type, HashMap, imposes Eq and Hash on the key.

Generic functions

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

use michie::memoized;
use std::hash::Hash;
#[memoized(key_expr = input.clone())]
fn f<A, B>(input: A) -> B
where
    A: Clone + Send + Sync + 'static + Eq + Hash,
    B: Clone + Send + Sync + 'static + From<A>,
{
    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;
#[memoized(key_expr = ())]
fn f() -> f64 {
    // expensive calculation
    # unimplemented!()
}

Support and feedback

In the GitHub Discussions.

Authored by Mobus Operandi

This crate is a work by Mobus Operandi — a community for the study of Rust in mob programming format.