micjie（听起来像Mickey）——一个属性宏，用于为函数添加记忆化。

目录

1. 特性
2. 非特性
3. key_expr
4. store_type
5. store_init
6. 类型要求
   1. 一般界限
   2. 存储界限
7. 泛型函数
8. 无输入函数
9. 工作原理
10. 为什么必须提供 key_expr
11. 支持和反馈

特性

• 支持
  • 普通函数
  • 泛型函数
  • 实现块中的函数
  • 特质实现块中的函数
  • 默认特质实现函数
• 线程安全
• 扩展仅依赖于 std
• 卫生
• 支持递归函数
• 自行提供存储

非特性

• 缓存特性：此仓库不提供除了一些简单的实现之外的缓存机制。它允许您自行提供。
• "闪电般快"：此仓库旨在提供一种简单易用的方法来记忆化函数。如果您真正需要微优化记忆化，那么您很可能需要自己实现它。

key_expr

在每次调用中都会获得一个键。它用于查询函数的缓存存储以查找可能的命中。必须通过 key_expr 参数提供评估为键的表达式。表达式可以使用函数的参数中的绑定。在以下示例中，key_expr 简单地是唯一参数的名称。

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

store_type

具体存储类型必须通过 store_type 参数提供，或者从 store_init（下一节）推断。

提供类型必须实现 MemoizationStore。为 BTreeMap 和 HashMap 提供了 MemoizationStore 的实现。在以下示例中，提供了 BTreeMap 作为存储。

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

默认情况下，商店通过 [Default::default()] 进行初始化。可以通过表达式将不同的初始化提供给 store_init

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

类型要求

边界适用于键类型和函数的返回类型。其中一些来自通用仪器，其他则是通过商店类型对 MemoizationStore 的实现。

一般界限

以下适用于键类型和函数的返回类型

• Sized：首先，仪器将键存储在一个 let 绑定中。
• 'static：键和返回值由一个静态拥有的商店拥有。
• Send 和 Sync：用于并行访问。

存储界限

键类型和返回类型的另一个边界来源是商店类型的 MemoizationStore 实现。

泛型函数

在通用函数上使用时，请注意 类型要求

use michie::memoized;
use std::hash::Hash;
use std::collections::HashMap;
#[memoized(key_expr = input.clone(), store_type = HashMap<A, B>)]
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()
}

无输入函数

没有输入的函数是 编译时评估 的良好候选，这通常比运行时缓存（如此软件包提供的）更受青睐。尽管如此，一些函数不能在编译时评估。对于没有输入的函数，一个合理的 key_expr 是 ()

use michie::memoized;
use std::collections::HashMap;
#[memoized(key_expr = (), store_type = HashMap<(), f64>)]
fn f() -> f64 {
    // expensive calculation
    # unimplemented!()
}

工作原理

原始函数扩展成类似于以下内容

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);
    drop(store_mutex_guard);
    if let Some(hit) = attempt {
        return hit;
    } else {
        let miss = #original_fn_body;
        let miss = STORE.lock().unwrap().insert(key, miss);
        return miss;
    };
}

为什么必须提供 key_expr

唯一可考虑的默认 key_expr 是整个输入。例如，对于一个函数签名

fn f(a: usize, _b: usize) -> usize

默认的 key_expr 将是 (a, _b)。两个潜在问题：一些参数可能不满足 键类型的边界。此外，生成的键可能是 实际计算输入 的超值。为了解释后一个问题，以下是一个示例

use michie::memoized;
use std::collections::HashMap;
// pretend that `key_expr` is omitted and that this is the default
#[memoized(key_expr = (a, _b), store_type = HashMap<(usize, usize), usize>)]
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!

如果提供了准确的 key_expr = a，第二次执行将是一个命中。总之，key_expr 是强制性的，以鼓励对其的适当考虑。

支持和反馈

在 GitHub 讨论中。