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

```rust 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:

rust ignore 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:

text (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:

```rust compile_fail 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:

rust ignore 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:

```rust use michie::memoized;

[memoized(keytype = u64, keyexpr = 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].

```rust use michie::memoized; use std::collections::BTreeMap;

[memoized(keyexpr = input, storetype = BTreeMap)]

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.

```rust use michie::{memoized, MemoizationStore}; use std::collections::HashMap;

[memoized(keyexpr = input, storeinit = 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:

```rust use michie::memoized; use std::hash::Hash;

[memoized(key_expr = input.clone())]

fn f(input: A) -> B where A: Clone + Send + Sync + 'static + Eq + Hash, B: Clone + Send + Sync + 'static + From, { input.into() } ```