2
\$\begingroup\$

In https://doc.rust-lang.org/book/ch13-01-closures.html the author recommended to try to implement Cacher that:

  1. Stores values in a HashMap
  2. Allows the closure to be defined with various input/output types.

Here's my implementation of it:

use std::hash::Hash;
use std::collections::HashMap;

fn main() {
    println!("Hello, world!");
}

struct Cacher<ClosureType, ParamType, ReturnType>
where
    ClosureType: Fn(ParamType) -> ReturnType,
    ParamType: Hash + Eq,
{
    calculation: ClosureType,
    values: HashMap<ParamType, ReturnType>,
}

impl<ClosureType, ParamType, ReturnType> Cacher<ClosureType, ParamType, ReturnType>
where
    ClosureType: Fn(ParamType) -> ReturnType,
    ParamType: Hash + Eq + Copy,
{
    fn new(calculation: ClosureType) -> Cacher<ClosureType, ParamType, ReturnType> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    fn value(&mut self, arg: ParamType) -> &ReturnType {
        if self.values.contains_key(&arg) {
            self.values.get(&arg).unwrap()
        } else {
            let result = (self.calculation)(arg);
            self.values.insert(arg, result);
            self.values.get(&arg).unwrap()
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn cacher_works_with_multiple_values() {
        let mut cacher = Cacher::new(|a: i32| -> i32 { a + 1 });

        let value = cacher.value(5);
        assert_eq!(6, value.clone());

        let value = cacher.value(10);
        assert_eq!(11, value.clone());
    }
}

The second task was much more "engaging" and I had some doubts about it:

  1. As soon as I made Cacher generic with 3 type parameters, HashMap started to complain that it does not accept all the types. By guessing I figured I'll add trait bounds around the ParamType (that type will be the key in HashMap) to require both Hash and Eq traits' How do I make sure in such situation what trait bounds are necessary? I tried to find the source code of Rust's HashMap to see exactly which bounds they have defined for K and V, but I couldn't find that source code. I only found this, but it refers to some base, which I did not understand.
  2. I was wondering if the value() method should accept an owned type or maybe a reference? Also, I was wondering if it should return an owned type or a reference. In the end I went with owned type on input and a reference on output. Is it a good design?
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Your code looks very nice! First, answering your questions:

Q1: How do I make sure in such situation what trait bounds are necessary?

It is a combination of reading the documentation and intuition. If we Google something like "hashmap rust", we get to the documentation page, which tells us what we need to know:

It is required that the keys implement the Eq and Hash traits, although this can frequently be achieved by using #[derive(PartialEq, Eq, Hash)].

If you know how a hashmap works, this also makes sense. Keys in the hashmap have to be hashed to find their place in the table, which means the key type must implement Hash. Additionally, if two keys collide (have the same location in the table), we need to know if they are the same key, or different. Hence, the key type must also implement Eq. PartialEq is a requirement for Eq as it is a weaker version.

So you should be requiring Eq and PartialEq, but NOT Copy. As a general rule of thumb, avoid Copy as it is intended for easily-copyable types and makes your code less generic. Instead, use Clone which requires you to explicitly clone a value.

Removing the Copy trait

So, above I said you should remove the Copy trait bound on ParamType, as it's not required by HashMap and should be avoided. Unfortunately, removing Copy usually requires you to think harder about where ownership flows in your program, but fortunately, it's a helpful exercise. :) Once you replace + Copy with + Clone, the Rust compiler will complain about these lines:

let result = (self.calculation)(arg);
self.values.insert(arg, result);
self.values.get(&arg).unwrap()

What's happening here? In the first line, self.calculation is a function type that takes as input a ParamType (NOT a reference). So it needs to take ownership. So, we've already given away our value after the first line! We still need it around, so instead of giving it away, we should make a clone. Similarly, the second line needs ownership in order to insert the parameter arg into the cache self.values. So we need two .clone() calls to please the compiler:

let result = (self.calculation)(arg.clone());
self.values.insert(arg.clone(), result);
self.values.get(&arg).unwrap()

Are two clones necessary? Clones can be expensive -- you should be imagining that arg might be something large, like a string or a vector -- so we should make sure we aren't cloning unnecessarily. It turns out the answer here is that you should be able to do it with one clone, but it's tricky, so I will not discuss it here. You would need to use a special feature of hashmaps called the Entry API.

However, there's an easier way: we can realize that the input parameter, arg is not used at the end of the function (it's been cloned twice, but the original owned value is not needed). So, we can be more efficient by accepting an &arg instead of arg. Here is our final code:

    pub fn value(&mut self, arg: &ParamType) -> &ReturnType {
        if self.values.contains_key(arg) {
            self.values.get(arg).unwrap()
        } else {
            let result = (self.calculation)(arg.clone());
            self.values.insert(arg.clone(), result);
            self.values.get(arg).unwrap()
        }
    }

Additionally, cargo clippy has some helpful suggestions for how to simplify this. We end up with this final version of the code (and we also have to update the unit tests appropriately).

    pub fn value(&mut self, arg: &ParamType) -> &ReturnType {
        if !self.values.contains_key(arg) {
            let result = (self.calculation)(arg.clone());
            self.values.insert(arg.clone(), result);
        }
        self.values.get(arg).unwrap()
    }

That leads us to your second question:

Q2: Is it better to accept/return an owned type or a reference? How can I tell?

If the type is Copy, just accept/return an owned type (copy means creating copies is easy). However now that we have made the code better to require Clone, this doesn't apply. Here are two good questions to ask:

  • If you are accepting an owned value, are you using it? If no, you should accept a reference instead. The answer here was no: we were .clone()ing the argument twice, but discarding it at the end. So we switched to a reference.

  • If you are accepting a reference, are you cloning it exactly once? If yes, you should likely accept an owned value instead and avoid the clone. Here, we are cloning twice, not just once, so this doesn't apply.

  • If you are returning a reference, could you instead return a value (is there a value in the function body that's available to return)? If yes, return the value instead. Here, the answer is no: the return value is stored inside the cache, so we can't take ownership over it without removing it from the cache. So, we can't return a value and can only return a reference.

A general rule of thumb is that read-only methods accept and return references, whereas methods which insert into a data structure accept owned values, and methods which delete from a data structure return owned values. Here, the "data structure" is the cache, so your signature makes sense: it accepts an owned value because it's inserting into the cache, and it returns a reference to the return value in the cache.

Further advice

I realize this got a bit long, but a couple other things:

  • Always try to remove warnings and run cargo clippy. Your code has some unused function errors, which it's best to avoid by making your data structure public: pub struct Cacher, pub fn new, pub fn value.

  • Finally, you have a useless fn main() function. In this case, what you are writing is more of a library than a binary, so what you probably want is to rename main.rs to lib.rs. Then you can get rid of the main function.

Entry API

Since you are interested -- here's how to do it with Entry:

    pub fn value(&mut self, arg: ParamType) -> &ReturnType {
        let result = (self.calculation)(&arg);
        self.values.entry(arg).or_insert(result)
    }

We can now remove Clone, but need to accept an owned ParamType rather than a reference (as in your new code) since we need an owned value to insert into the cache.

\$\endgroup\$
4
  • \$\begingroup\$ Thanks a ton for that review! While reading your remarks about Copy, I started modifying my code, I got to a little bit different result than you proposed. I've changed ClosureType to be like this: Fn(&ParamType) -> ReturnType So, the closure would accept a reference instead of owned type. The closure is supposed to be some simple transformation function that accepts x and returns y, it has no knowledge about storing data in cache (that's something that Cacher adds on top of the closure). I'll post new code as an additional answer. \$\endgroup\$
    – mnj
    Dec 31, 2021 at 14:27
  • \$\begingroup\$ I didn't know about clippy, it's nice! Probably some real IDE would have that functionality integrated to show me tips while I write the code. VS Code is quite poor for anything else than JS in my experience. \$\endgroup\$
    – mnj
    Dec 31, 2021 at 14:28
  • 1
    \$\begingroup\$ @Loreno That design makes sense too! As long as the user doesn't mind providing a closure with read-only access, that doesn't need an owned value. For VS Code, do you have rust-analyzer installed? That's supposed to be much preferred over the default Rust support. \$\endgroup\$ Dec 31, 2021 at 14:34
  • 1
    \$\begingroup\$ No, I had the "official" one installed. I replaced it now with the one you linked to, I'll see how it goes with that one. Thanks! \$\endgroup\$
    – mnj
    Dec 31, 2021 at 14:40
2
\$\begingroup\$

Here's the code after some changes that I did after reading @6005's comment:

use std::hash::Hash;
use std::collections::HashMap;

fn main() {
    println!("Hello, world!");
}

pub struct Cacher<ClosureType, ParamType, ReturnType>
where
    ClosureType: Fn(&ParamType) -> ReturnType,
    ParamType: Hash + Eq,
{
    calculation: ClosureType,
    values: HashMap<ParamType, ReturnType>,
}

impl<ClosureType, ParamType, ReturnType> Cacher<ClosureType, ParamType, ReturnType>
where
    ClosureType: Fn(&ParamType) -> ReturnType,
    ParamType: Hash + Eq + Clone
{
    pub fn new(calculation: ClosureType) -> Cacher<ClosureType, ParamType, ReturnType> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    pub fn value(&mut self, arg: &ParamType) -> &ReturnType {
        if !self.values.contains_key(arg) {
            let result = (self.calculation)(arg);
            self.values.insert(arg.clone(), result);
        }
        self.values.get(&arg).unwrap()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn cacher_works_with_multiple_values() {
        let mut cacher = Cacher::new(|a: &i32| -> i32 { a + 1 });

        let value = cacher.value(&5);
        assert_eq!(6, value.clone());

        let value = cacher.value(&10);
        assert_eq!(11, value.clone());
    }
}

I changed the closure's type to accept a reference instead of owning the argument. I think it makes more sense for closures that are just supposed to transform some value into something else.

One thing that I don't like is that I have to clone() in the value() function. I feel like it should be possible to get rid of it completely, maybe using the Entry API that @6005 pointed at, but I'm not sure.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Since you are interested -- I added to my answer how to do it with Entry: basically, self.values.entry(arg).or_insert(result). We can now remove Clone, but need to accept an owned ParamType rather than a reference (as in your new code) since we need an owned value to insert into the cache. \$\endgroup\$ Dec 31, 2021 at 15:14
  • 1
    \$\begingroup\$ @6005 You are awesome, thanks so much! So it looks a bit like I expected, and I like this new version much better. \$\endgroup\$
    – mnj
    Dec 31, 2021 at 15:57
  • 1
    \$\begingroup\$ You are welcome -- happy new year! \$\endgroup\$ Dec 31, 2021 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.