我有兴趣寻找或实现一个 Rust 数据结构,它提供了一种零成本的方式来记忆具有任意输出类型的单个计算T。具体来说,我想要一个通用类型Cache<T>,其内部数据占用的空间不超过Option<T>,并具有以下基本 API:
impl<T> Cache<T> {
/// Return a new Cache with no value stored in it yet.
pub fn new() -> Self {
// ...
}
/// If the cache has a value stored in it, return a reference to the
/// stored value. Otherwise, compute `f()`, store its output
/// in the cache, and then return a reference to the stored value.
pub fn call<F: FnOnce() -> T>(&self, f: F) -> &T {
// ...
}
}
Run Code Online (Sandbox Code Playgroud)
这里的目标是能够Cache在单个线程内共享对 a 的多个不可变引用,并且此类引用的任何持有者都能够访问该值(如果是第一次,则触发计算)。由于我们只要求能够Cache在单个线程中共享 a,因此没有必要这样做Sync。
unsafe这是一种在幕后安全地实现 API 的方法(或者至少我认为它是安全的) :
use std::cell::UnsafeCell;
pub struct Cache<T> {
value: UnsafeCell<Option<T>>
}
impl<T> Cache<T> {
pub fn new() -> Self {
Cache { value: UnsafeCell::new(None) }
}
pub fn call<F: FnOnce() -> T>(&self, f: F) -> &T {
let ptr = self.value.get();
unsafe {
if (*ptr).is_none() {
let t = f();
// Since `f` potentially could have invoked `call` on this
// same cache, to be safe we must check again that *ptr
// is still None, before setting the value.
if (*ptr).is_none() {
*ptr = Some(t);
}
}
(*ptr).as_ref().unwrap()
}
}
}
Run Code Online (Sandbox Code Playgroud)
是否有可能在安全的 Rust 中实现这样的类型(即不编写我们自己的unsafe代码,仅间接依赖unsafe标准库中的代码)?
显然,该call方法需要 mutating self,这意味着Cache必须使用某种形式的内部可变性。但是,似乎不可能使用 a 来执行此操作Cell,因为Cell无法按照上述所需 API 的要求检索对所包含值的引用call。这是有充分理由的,因为提供这样的引用是不合理的Cell,因为它无法确保引用的值在引用的生命周期内不会发生变化。另一方面,对于该Cache类型,在call调用一次之后,上面的 API 不提供任何方法让存储的值再次发生变化,因此它可以安全地分发一个生命周期很长的引用。就像它Cache本身一样。
如果Cell不能工作,我很好奇 Rust 标准库是否可以为内部可变性提供一些其他安全的构建块,可以用来实现这个Cache。
既不RefCell实现Mutex这里的目标:
Option<T>,并添加不必要的运行时检查。Ref或 ,MutexGuard这不是同一件事。仅使用 anOption不会提供相同的功能:如果我们共享对 的不可变引用Cache,则此类引用的任何持有者都可以调用call并获取所需的值(并在此过程中改变Cache,以便将来的调用将检索相同的值);然而,共享对 an 的不可变引用Option,则不可能改变Option,因此它无法工作。