How to remove excessive clone calls from a structure that caches arbitrary results?

Question

I read the section on closures in the second edition of Rust. At the end of this section is an exercise to expand the Cacher implementation given earlier. I tried:

 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() } } } } 

After creating a version that finally works, I am really unhappy with this. What really cacher.value(...) me cacher.value(...) is that cacher.value(...) contains 5 (!) cacher.value(...) clone() . Is there any way to avoid this?

Answer 1

Your suspicion is correct, the code contains too many calls to clone() , Cacher are the very optimizations that Cacher is designed to Cacher .

Cloning the entire cache

Let's start by calling self.values.clone() - it creates a copy of the entire cache with every access.

After non-lexical lives

Delete this clone.

Before non-lexical times of life

As you probably discovered, simply removing .clone() does not compile. This is because the borrower checks the referenced map throughout the match . The shared link returned by HashMap::get points to an element inside the map, which means that while it exists, it is forbidden to create another mutable link to the same map as is required for HashMap::insert . For the code to compile, you need to split the match so that the shared link goes out of scope before 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 } } 

---

This is much better and probably "good enough" for most practical purposes. The hot way, where the value is already cached, now consists of only one clone, and this fact is actually necessary, since the original value should remain in the hash map. (Also note that cloning doesn't have to be expensive or involve deep copying — the stored value could be Rc<RealValue> , which buys shared objects for free. In this case, clone() just increments the reference count for the item.)

No clone cache

In case of cache loss, the key must be cloned, because the calculation its use is declared. Cloning alone will be enough, so we can pass the original arg to insert without cloning it again. The clone of the key still feels unnecessary - the calculation function should not require ownership of the key that it transforms. Removing this clone comes down to changing the signature of the calculation function to take the key by reference. Changing the boundaries of the attribute T to T: Fn(&K) → V allows the following statement of 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 } } 

Double Search Avoidance

Now there are only two calls to clone() , one in each code path. This is optimal from the point of view of cloning values, but the attentive reader will still be dissatisfied with one detail: if the cache is skipped, the search in the hash table will occur twice for the same key: once upon calling HashMap::get , and then another times in HashMap::insert . It would be nice if we could instead reuse the work done for the first time and perform only one hash map search. This can be achieved by replacing get() and insert() with 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() } 

We also took the opportunity to move .clone() after the match.

A workable example on the playground .

Answer 2

I solved the same exercise and ended with the following code:

 use std::thread; use std::time::Duration; use std::collections::HashMap; use std::hash::Hash; use std::fmt::Display; struct Cacher<P, R, T> where T: Fn(&P) -> R, P: Eq + Hash + Clone, { calculation: T, values: HashMap<P, R>, } impl<P, R, T> Cacher<P, R, T> where T: Fn(&P) -> R, P: Eq + Hash + Clone, { fn new(calculation: T) -> Cacher<P, R, T> { Cacher { calculation, values: HashMap::new(), } } fn value<'a>(&'a mut self, key: P) -> &'a R { let calculation = &self.calculation; let key_copy = key.clone(); self.values .entry(key_copy) .or_insert_with(|| (calculation)(&key)) } } 

It makes only one copy of the key in the value() method. It does not copy the resulting value, but instead returns a link with the lifetime specifier, which is equal to the lifetime of the enclosing Cacher instance (which, I think, is logical, since the values ​​on the map will continue to exist until Cacher itself is discarded).

Here's the test program:

 fn main() { let mut cacher1 = Cacher::new(|num: &u32| -> u32 { println!("calculating slowly..."); thread::sleep(Duration::from_secs(2)); *num }); calculate_and_print(10, &mut cacher1); calculate_and_print(20, &mut cacher1); calculate_and_print(10, &mut cacher1); let mut cacher2 = Cacher::new(|str: &&str| -> usize { println!("calculating slowly..."); thread::sleep(Duration::from_secs(2)); str.len() }); calculate_and_print("abc", &mut cacher2); calculate_and_print("defghi", &mut cacher2); calculate_and_print("abc", &mut cacher2); } fn calculate_and_print<P, R, T>(intensity: P, cacher: &mut Cacher<P, R, T>) where T: Fn(&P) -> R, P: Eq + Hash + Clone, R: Display, { println!("{}", cacher.value(intensity)); } 

And his conclusion:

 calculating slowly... 10 calculating slowly... 20 10 calculating slowly... 3 calculating slowly... 6 3 

Answer 3

If you cancel the return value requirement, you do not need to execute any clones using Entry :

 use std::{ collections::{hash_map::Entry, HashMap}, fmt::Display, hash::Hash, thread, time::Duration, }; struct Cacher<P, R, T> where T: Fn(&P) -> R, P: Eq + Hash, { calculation: T, values: HashMap<P, R>, } impl<P, R, T> Cacher<P, R, T> where T: Fn(&P) -> R, P: Eq + Hash, { fn new(calculation: T) -> Cacher<P, R, T> { Cacher { calculation, values: HashMap::new(), } } fn value<'a>(&'a mut self, key: P) -> &'a R { let calculation = &self.calculation; match self.values.entry(key) { Entry::Occupied(e) => e.into_mut(), Entry::Vacant(e) => { let result = (calculation)(e.key()); e.insert(result) } } } } fn main() { let mut cacher1 = Cacher::new(|num: &u32| -> u32 { println!("calculating slowly..."); thread::sleep(Duration::from_secs(1)); *num }); calculate_and_print(10, &mut cacher1); calculate_and_print(20, &mut cacher1); calculate_and_print(10, &mut cacher1); let mut cacher2 = Cacher::new(|str: &&str| -> usize { println!("calculating slowly..."); thread::sleep(Duration::from_secs(2)); str.len() }); calculate_and_print("abc", &mut cacher2); calculate_and_print("defghi", &mut cacher2); calculate_and_print("abc", &mut cacher2); } fn calculate_and_print<P, R, T>(intensity: P, cacher: &mut Cacher<P, R, T>) where T: Fn(&P) -> R, P: Eq + Hash, R: Display, { println!("{}", cacher.value(intensity)); } 

Then you can wrap this in another structure that executes the clone:

 struct ValueCacher<P, R, T> where T: Fn(&P) -> R, P: Eq + Hash, R: Clone, { cacher: Cacher<P, R, T>, } impl<P, R, T> ValueCacher<P, R, T> where T: Fn(&P) -> R, P: Eq + Hash, R: Clone, { fn new(calculation: T) -> Self { Self { cacher: Cacher::new(calculation), } } fn value(&mut self, key: P) -> R { self.cacher.value(key).clone() } }