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. key_type
5. store_type
6. store_init
7. Store inference and the default store
8. Type requirements
   1. General bounds
   2. Store bounds
9. Generic functions
10. Functions that take no input
11. How it works
12. Why must key_expr be provided
13. Support and feedback
14. Authored by Mobus Operandi

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;
#[memoized(key_expr = input)]
fn f(input: usize) -> usize {
    // expensive calculation
    # unimplemented!()
}

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

A store type may be provided via the store_type argument. 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, MemoizationStore};
use std::collections::HashMap;
#[memoized(key_expr = input, store_init = HashMap::with_capacity(500))]
fn f(input: usize) -> usize {
    // expensive calculation
    # unimplemented!()
}

Store inference and the default store

An omitted store_type may be inferred from a provided store_init. If both are omitted, the default store_type is [HashMap].

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.

And the return type must be [Clone] because it is cloned for insertion into the store.

Store bounds

Another source of bounds on the key type and the return type is the implementation of [MemoizationStore] for the store type. By the way, the provided implementation of [MemoizationStore] for the default store type [HashMap] bounds K: Eq + Hash.

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: '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;
#[memoized(key_expr = ())]
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).cloned();
    drop(store_mutex_guard);
    if let Some(hit) = attempt {
        return hit;
    } else {
        let miss = #original_fn_body;
        STORE.lock().unwrap().insert(key, miss.clone());
        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;
// pretend that `key_expr` is omitted and that this is the default
#[memoized(key_expr = (a, _b))]
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.

Authored by Mobus Operandi

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