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 recursion
• Bring your own cache store (defaults to a [HashMap] in which values live forever)

A basic example

```rust use michie::memoized;

[memoized(key_expr = input)]

fn f(input: usize) -> usize { // expensive calculation # input }

assert_eq!(f(5), 5);

```

A call to f with an input value that it had already been called with is a cache hit. A cache hit means that the implementation of f is not executed. Instead, the return value is obtained from cache.

The cache key

The cache is a key-value map. An expression for obtaining a key value (key_expr) must be provided. The key_type may be specified.

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. It might 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, the resulting key might be a supervalue of the input of the actual calculation. Here is an example:

```rust compile_fail

use michie::memoized;

[memoized]

fn f((a, _b): (usize, usize)) -> usize { // only a is used # a } ```

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

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

The second cache miss could have been a hit given an accurate key_expr: a.

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 # input }

assert_eq!(f(5), 5);

```

store_type and store_init

The default store is implemented using a [HashMap] in which entries live forever. It is provided under the assumption that it will suffice in a significant portion of cases.

In other cases the store_type and store_init arguments can be used. The store_type:

1. Is generic on <K, R> where K is the key type and R is the memoized function's return type.
2. K and R must have no bounds.
3. Provides the following functions where K and R may have bounds:
   • fn insert(&mut self, key: K, value: R) // return type ignored
   • fn get(&self, key: &K) -> Option<&R>

By default, the store_type will be instantiated this way:

text ignore { use ::core::default::Default; StoreType::<K, R>::default() }

For further customization store_init takes an expression. Example:

```rust

use michie::memoized;

use std::marker::PhantomData;

struct Store { // some fields # k: PhantomData, # v: PhantomData, } impl Default for Store { fn default() -> Self { Self::new(0) } } impl Store { // the return type is irrelevant fn insert(&mut self, key: K, value: V) { // insert into cache } fn get(&self, key: &K) -> Option<&V> { // attempt to get from cache # None } fn new(size: usize) -> Self { // create a new cache store # Self { # k: PhantomData, # v: PhantomData, # } } }

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

fn expensive(input: usize) -> usize { // expensive calculation # input }

[memoized(keyexpr = input, storetype = Store, store_init = Store::new(500))]

fn expensiveandlarge(input: usize) -> Vec { // expensive calculation with large return type # vec![] }

assert_eq!(expensive(2), 2);

asserteq!(expensiveand_large(2), vec![]);

```

By the way, [BTreeMap] happens to satisfy the above and therefore may be provided as store_type:

```rust

use michie::memoized;

use std::collections::BTreeMap;

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

fn f(input: usize) -> usize { // expensive calculation # input }

assert_eq!(f(2), 2);

```

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 may be from the cache store.

General bounds

On key type and return type:

• [Sized]: for one, the instrumentation stores the key in a let binding.
• ['static]: the cache store lives across function invocations — it cannot borrow from them.
• [Clone]: the key and return value are cloned for insertion into the store.
• [Sync]: for parallelism

Store type requirements

Be mindful of the bounds of ::get and ::insert of any provided store type. For the default store type, [HashMap], they are for the key type: [Eq] and [Hash].

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 + Sync + 'static + Eq + Hash, B: Clone + Sync + 'static + From, { input.into() }