如何从缓存任意结果的结构中删除过多的`clone`调用？

Question

我正在阅读第二版Rust书中关于闭包的部分.在本节的最后,有一个练习来扩展Cacher之前给出的实现.我试了一下:

use std::clone::Clone;
use std::cmp::Eq;
use std::collections::HashMap;
use std::hash::Hash;

struct Cacher<T, K, V>
where
    T: Fn(K) -> V,
    K: Eq + Hash + Clone,
    V: Clone,
{
    calculation: T,
    values: HashMap<K, V>,
}

impl<T, K, V> Cacher<T, K, V>
where
    T: Fn(K) -> V,
    K: Eq + Hash + Clone,
    V: Clone,
{
    fn new(calculation: T) -> Cacher<T, K, V> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    fn value(&mut self, arg: K) -> V {
        match self.values.clone().get(&arg) {
            Some(v) => v.clone(),
            None => {
                self.values
                    .insert(arg.clone(), (self.calculation)(arg.clone()));
                self.values.get(&arg).unwrap().clone()
            }
        }
    }
}

创建一个最终有效的版本后,我真的很不高兴.真正让我烦恼的是它cacher.value(...)有5(!)个调用clone().有办法避免这种情况吗？

Answer 1

你的怀疑是正确的,代码包含太多的调用clone(),打败了非常优化Cacher的目的.

开始的是调用self.values.clone()- 它在每次访问时创建整个缓存的副本.但是,正如您可能发现自己,只是删除.clone()不编译.这是因为借用检查器会考虑整个持续时间内引用的地图match.由HashMap::get点指向地图内的项返回的共享引用,这意味着当它存在时,禁止创建对同一地图的另一个可变引用,这是必需的HashMap::insert.对于要编译的代码,您需要拆分匹配,以便在insert调用之前强制共享引用超出范围:

// avoids unnecessary clone of the whole map
fn value(&mut self, arg: K) -> V {
    if let Some(v) = self.values.get(&arg).map(V::clone) {
        return v;
    } else {
        let v = (self.calculation)(arg.clone());
        self.values.insert(arg, v.clone());
        v
    }
}

对于大多数实际用途来说,这要好得多,而且可能"足够好".值已经缓存的热路径现在只包含一个克隆,而实际需要一个克隆,因为原始值必须保留在哈希映射中.(另请注意,克隆不需要昂贵或暗示深度复制 - 存储的值可以是一个Rc<RealValue>,它可以免费购买对象共享.在这种情况下,clone()只需增加对象的引用计数.)

在高速缓存未命中的情况下,必须克隆密钥,因为calculation声明要使用它.但是,单个克隆就足够了,所以我们可以将原始文件传递arg给insert它而不再克隆它.但是,密钥克隆仍然没有必要 - 计算功能不应该要求它正在转换的密钥的所有权.删除此克隆归结为修改计算函数的签名以通过引用获取密钥.改变的性状界限T到T: Fn(&K) -> V允许的下列配方value():

// avoids unnecessary clone of the key
fn value(&mut self, arg: K) -> V {
    if let Some(v) = self.values.get(&arg).map(V::clone) {
        return v;
    } else {
        let v = (self.calculation)(&arg);
        self.values.insert(arg, v.clone());
        v
    }
}

现在剩下两个调用clone(),每个代码路径一个.就价值克隆而言,这是最佳的.但细心的读者仍然会被一个细节所困扰:在缓存未命中的情况下,对于相同的密钥,哈希表查找将有效地发生两次:一次在调用中HashMap::get,然后再一次在HashMap::insert.如果我们可以重新使用第一次完成的工作并且只执行一次哈希映射查找,那将是很好的.这可以通过更换来实现get(),并insert()具有entry():

// avoids the second lookup on cache miss
fn value(&mut self, arg: K) -> V {
    match self.values.entry(arg) {
        Entry::Occupied(entry) => entry.into_mut(),
        Entry::Vacant(entry) => {
            let v = (self.calculation)(entry.key());
            entry.insert(v)
        }
    }.clone()
}

在操场上的可运行的例子.