#lru-cache #cache #lru #proc-macro #memoization

nightly cache-macro

一个用于自动缓存函数输出的过程宏

2 个版本

0.4.1 2018 年 11 月 25 日
0.4.0 2018 年 11 月 25 日

#41 in #memoization

MIT 许可证

29KB
360

cache-macro

Build Status cache-macro on docs.rs cache-macro on crates.io

一个过程宏,用于自动缓存给定输入集的函数结果。

之前名为 'lru-cache-macros',但已重命名以反映范围扩大。

示例

use cache_macro::cache;
use lru_cache::LruCache;

#[cache(LruCache : LruCache::new(20))]
fn fib(x: u32) -> u64 {
    println!("{:?}", x);
    if x <= 1 {
        1
    } else {
        fib(x - 1) + fib(x - 2)
    }
}

assert_eq!(fib(19), 6765);

上面的示例只调用了 fib 二十次,值从 0 到 19。所有中间结果由于递归而命中缓存。

用法

只需在您的函数上方放置 #[cache(CacheType : constructor)]。函数必须遵守一些属性才能使用 lru_cache

  • 所有参数和返回值都必须实现 Clone
  • 函数不得以任何形式接受 self

使用的 LruCache 类型必须接受两个泛型参数 <Args, Return>,并必须支持方法 get_mut(&K) -> Option<&mut V>insert(K, V)。目前,lru-cache(用于 LRU 缓存)和 expiring_map(用于 TTL 缓存)符合这些要求。

目前,此包仅在 nightly rust 上工作。然而,一旦 2018 版本稳定以及过程宏诊断接口,它应该能够在稳定版上运行。

配置

可以通过在 #[cache(...)] 下添加额外的属性来配置 lru_cache 宏。

所有配置属性的形式为 #[cache_cfg(...)]。可用的属性有

  • #[cache_cfg(ignore_args= ...)]

这允许在缓存的目的上忽略某些参数。这意味着它们不是散列表键的一部分,因此永远不会影响函数的输出。这对于诊断设置、返回执行次数或其他内省目的可能很有用。

ignore_args接受一个逗号分隔的变量标识符列表以忽略。

示例

use cache_macro::cache;
use lru_cache::LruCache;
#[cache(LruCache : LruCache::new(20))]
#[cache_cfg(ignore_args = call_count)]
fn fib(x: u64, call_count: &mut u32) -> u64 {
    *call_count += 1;
    if x <= 1 {
        1
    } else {
        fib(x - 1, call_count) + fib(x - 2, call_count)
    }
}

let mut call_count = 0;
assert_eq!(fib(39, &mut call_count), 102_334_155);
assert_eq!(call_count, 40);

call_count参数可以变化,缓存仅基于x

  • #[cache_cfg(thread_local)]

将缓存存储在线程本地存储中而不是全局静态存储中。这样可以避免互斥锁定的开销,但每个线程将获得自己的缓存,并且所有缓存都不会影响其他线程。

扩展第一个示例

use cache_macro::cache;
use lru_cache::LruCache;

#[cache(LruCache : LruCache::new(20))]
#[cache_cfg(thread_local)]
fn fib(x: u32) -> u64 {
    println!("{:?}", x);
    if x <= 1 {
        1
    } else {
        fib(x - 1) + fib(x - 2)
    }
}

assert_eq!(fib(19), 6765);

详细信息

除非添加了#[cache_cfg(thread_local)]配置,否则创建的缓存将作为由互斥锁保护的静态变量存储。

默认设置下,fibonacci示例将生成以下代码

fn __lru_base_fib(x: u32) -> u64 {
    if x <= 1 { 1 } else { fib(x - 1) + fib(x - 2) }
}
fn fib(x: u32) -> u64 {
    use lazy_static::lazy_static;
    use std::sync::Mutex;

    lazy_static! {
        static ref cache: Mutex<::lru_cache::LruCache<(u32,), u64>> =
            Mutex::new(::lru_cache::LruCache::new(20usize));
    }

    let cloned_args = (x.clone(),);
    let mut cache_unlocked = cache.lock().unwrap();
    let stored_result = cache_unlocked.get_mut(&cloned_args);
    if let Some(stored_result) = stored_result {
        return stored_result.clone();
    };
    drop(cache_unlocked);
    let ret = __lru_base_fib(x);
    let mut cache_unlocked = cache.lock().unwrap();
    cache_unlocked.insert(cloned_args, ret.clone());
    ret
}

而如果您使用#[lru_config(thread_local)],生成的代码将类似于

fn __lru_base_fib(x: u32) -> u64 {
    if x <= 1 { 1 } else { fib(x - 1) + fib(x - 2) }
}
fn fib(x: u32) -> u64 {
    use std::cell::UnsafeCell;
    use std::thread_local;

    thread_local!(
         static cache: UnsafeCell<::lru_cache::LruCache<(u32,), u64>> =
             UnsafeCell::new(::lru_cache::LruCache::new(20usize));
    );

    cache.with(|c|
        {
            let mut cache_ref = unsafe { &mut *c.get() };
            let cloned_args = (x.clone(),);
            let stored_result = cache_ref.get_mut(&cloned_args);
            if let Some(stored_result) = stored_result {
                stored_result.clone()
            } else {
                let ret = __lru_base_fib(x);
                cache_ref.insert(cloned_args, ret.clone());
                ret
            }
        })
}

依赖关系

~2MB
~46K SLoC