michie (sounds like Mickey) — an attribute macro that adds [memoization] to a function.
impl blocksstdIn 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.
```rust use michie::memoized;
fn f(input: usize) -> usize { // expensive calculation # unimplemented!() } ```
While the type of the key supports inference, it may also be specified using the key_type argument:
```rust use michie::memoized;
fn f(input: u32) -> u32 { // expensive calculation # unimplemented!() } ```
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:
```rust use michie::memoized; use std::collections::BTreeMap;
fn f(input: usize) -> usize { // expensive calculation # unimplemented!() } ```
By default, the store is initialized via [Default::default()].
Different initialization may be provided via an expression to store_init:
```rust use michie::{memoized, MemoizationStore}; use std::collections::HashMap;
fn f(input: usize) -> usize { // expensive calculation # unimplemented!() } ```
An omitted store_type may be inferred from a provided store_init.
If both are omitted, the default store_type is [HashMap].
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].
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.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, R: Clone.
Be mindful of the type requirements when using on a generic function:
```rust use michie::memoized; use std::hash::Hash;
fn fkey_expr
B: 'static + Send + Sync + Clone // bounds from instrumentation
+ From, // used in this function's body
{
input.into()
}
```
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 ():
```rust use michie::memoized;
fn f() -> f64 { // expensive calculation # unimplemented!() } ```
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;
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;
};
}
The only conceivable default key_expr is the entire input.
For example, for a function signature:
text
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:
``rust
use michie::memoized;
// pretend thatkey_expr` is omitted and that this is the default
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.
In [the GitHub Discussions].
This crate is a work by [Mobus Operandi] — a small community for the regular study of Rust in remote mob programming format.