Over Engineering: Using reference (borrow?) on HashMap key in Rust

Question

I'm making a search algorithm (BFS/DFS) to search a tree of game states. I already made the thing in C, but I was wondering if Rust would be faster, and since I've been meaning to learn Rust anyway I figured I would give it a shot.

I'm trying to optimize this thing to the point of over engineering (I like it, let me be), and I have made an optimization in C that I thought was cool, but I can't figure out how to (/if it is possible) in Rust.

The outline of my algorithm is this:

Add the start state to a queue, and make a hashmap [State -> Previous State, Action]
// I use this hashmap to find the way back later, and to check if I have been in a state before.

Take a state S0 from the queue:
   for all possible actions, calculate next state S1:
      if S1 is already a key in the hashmap, continue
      and add [ S1 -> S0, action taken ] to the hashmap
      add S1 to the queue,
   ...
   // some other stuff here to check when to stop

One of the optimizations I did in C was this: Instead of copying the state struct data into the queue, I copy a pointer to that same data in the hashmap (since I just added it to the hashmap anyway) into the queue, this way I don't have to copy the state data, but the queue just consists of pointers to the same data in the hashmap.

This works easily in C because I have my own hashmap implementation, so it was easy to make a function to return the pointer to the right data in the hashmap.

In Rust I now have this:

// Add all possible moves to be searched through later
for m in possible_moves.iter() {
    if let Some(new_state) = popped.do_move(m) { // popped is S0 from my algorithm outline
        if backmap.contains_key(&new_state) { continue; }
        queue.push_back(new_state);
        backmap.insert(new_state, Wayback {
        prev_state: popped, did_move: m });
    }
}

But this means that the new_state data is copied into the queue and the hashmap. I wonder if there is a way to not copy this data in Rust, like my C version (or some other way).

I would like this optimization because I just like the optimized feeling of it, but in Rust's case also because right now this copy means that I have #[derive(Clone, Copy)] above all my structs, which is just not nice imo, if there is not a way to do my over-engineered optimization, but there is a way to not have to derive to copy and clone traits I would still like to know.

Thank you very much for any help!

P.S. I recognize that this is not your regular code question, and it might be quite unclear from my explanation, so if there is any questions about what I mean, I will answer them asap.

question from:https://stackoverflow.com/questions/65887910/over-engineering-using-reference-borrow-on-hashmap-key-in-rust

Answer 1

I would like this optimization because I just like the optimized feeling of it, but in Rust's case also because right now this copy means that I have #[derive(Clone, Copy)] above all my structs, which is just not nice imo

Depending on the size of the struct… does it actually matter? a Copy is just a memcpy.

if there is not a way to do my over-engineered optimization, but there is a way to not have to derive to copy and clone traits I would still like to know.

The problem here is that Rust wants a clear static owner for each piece of data, but that doesn't exist in your algorithm: the state is "owned" by both the map and the queue. The way to "share" unclear ownership is to use an Rc, but that translates into a heap allocation (the refcount traffic doesn't really matter when it's not atomic), which would probably be a pessimisation if state