Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do I remove excessive `clone` calls from a struct that caches arbitrary results?

Tags:

rust

I am reading the section on closures in the second edition of the Rust book. At the end of this section, there is an exercise to extend the Cacher implementation given before. I gave it a try:

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 it. What really bugs me is that cacher.value(...) has 5(!) calls to clone() in it. Is there a way to avoid this?

like image 492
itmuckel Avatar asked Sep 24 '17 10:09

itmuckel


People also ask

Is it possible to remove data from a cloned phone?

There’s no “cloned phone” in your phone, so there’s nothing to remove. (Even if someone did clone your phone, all they’d clone would be your SIM card [before you connected to the network] - it’s not in your phone. That wouldn’t do anyone any good.) Nowadays the phone cloning is the biggest scam in cheap electronics markets.

Can you make and receive phone calls from a clone?

The other cell phone becomes the exact replica of the original cell phone like a clone. As a result, while calls can be made from and received by both phones, only the legitimate subscriber is billed as the service provider network does not have a way to differentiate between the legitimate phone and the “cloned” phone.

What happens if someone Clone Your Phone?

(Even if someone did clone your phone, all they’d clone would be your SIM card [before you connected to the network] - it’s not in your phone. That wouldn’t do anyone any good.) Nowadays the phone cloning is the biggest scam in cheap electronics markets. So, the problems that you should be faced if your phone is being cloned.

What is cloning and how does it work?

Cloning involves rewriting the IMEI ( International Mobile Equipment Identity) on a GSM phone, or MEID ( Mobile equipment identifier) on a CDMA cell phone, on another cell phone, to match that your phone. It has to do with the vulnerability to be able to do this on the hardware being used to clone your phone.


2 Answers

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

Cloning the entire cache

The one to start with is the call to self.values.clone() - it creates a copy of the entire cache on every single access.

After non-lexical lifetimes

Remove this clone.

Before non-lexical lifetimes

As you likely discovered yourself, simply removing .clone() doesn't compile. This is because the borrow checker considers the map referenced for the entire duration of match. The shared reference returned by HashMap::get points to the item inside the map, which means that while it exists, it is forbidden to create another mutable reference to the same map, which is required by HashMap::insert. For the code to compile, you need to split up the match in order to force the shared reference to go out of scope before insert is invoked:

// 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 path, where the value is already cached, now consists of only a single clone, and that one is actually necessary because the original value must remain in the hash map. (Also, note that cloning doesn't need to be expensive or imply deep copying - the stored value can be an Rc<RealValue>, which buys object sharing for free. In that case, clone() will simply increment the reference count on the object.)

Clone on cache miss

In case of cache miss, the key must be cloned, because calculation is declared to consume it. A single cloning will be sufficient, though, so we can pass the original arg to insert without cloning it again. The key clone still feels unnecessary, though - a calculation function shouldn't require ownership of the key it is transforming. Removing this clone boils down to modifying the signature of the calculation function to take the key by reference. Changing the trait bounds of T to T: Fn(&K) -> V allows the following formulation 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
    }
}

Avoiding double lookups

Now are left with exactly two calls to clone(), one in each code path. This is optimal, as far as value cloning is concerned, but the careful reader will still be nagged by one detail: in case of cache miss, the hash table lookup will effectively happen twice for the same key: once in the call to HashMap::get, and then once more in HashMap::insert. It would be nice if we could instead reuse the work done the first time and perform only one hash map lookup. 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've also taken the opportunity to move the .clone() call after the match.

Runnable example in the playground.

like image 70
user4815162342 Avatar answered Nov 15 '22 11:11

user4815162342


I was solving 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 only makes a single copy of the key in the value() method. It does not copy the resulting value, but instead returns a reference with a lifetime specifier, which is equal to the lifetime of the enclosing Cacher instance (which is logical, I think, because values in the map will continue to exist until the Cacher itself is dropped).

Here's a 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 its output:

calculating slowly...
10
calculating slowly...
20
10
calculating slowly...
3
calculating slowly...
6
3
like image 25
Andrei Tomashpolskiy Avatar answered Nov 15 '22 10:11

Andrei Tomashpolskiy