How to use slice from mutable Vec<Vec<u32>> as key in the HashMap

Hello!
I’ve created this thread https://stackoverflow.com/questions/57001816/how-to-use-slice-from-mutable-vec-as-key-in-the-hashmap .

One user tried to answer but without succes so far.

Pattern I am trying to implement is essential for minimizing RAM footprint and lookup time overhead for big data structures.

I would apreciate any help.
Thank you!

Hi, I agree with hellow on Stack Overflow, there isn’t a single solution to your problem. Also the compiler won’t let you compile one that isn’t safe (unlike C(++) that let you compile and then blows up in your face at runtime). It’s even more important for you since you plan on going multithreaded in the future.

Now my proposition: have a DB-like in memory data-structure owning your data and giving you ids. Store these ids in a HashMap<u32, id> where u32 is the hash of your data.

If you removed samples from the main table, the hashmap would end up having dangling pointers. You know your intent is not to ever remove samples, but the borrow checker has no way of knowing that.

You could make the container a Vec<Arc<[u32]>>. Arc is reference-counted, so it will give a guarantee that it won’t be freed while hashmap is using it. [u32] makes it hold fixed-length slice directly (so you avoid double-indirection of Arc<Vec<u32>>.

It’s possible to implement exactly what you want with unsafe by using unchecked raw pointers internally (to bypass the borrow checker) and enforcing elements are never removed. This is what most “arena” crates do, e.g.

Guys thank you for your input! More similar thoughts about Rc/Arc was added to disscussion on SO. As I said on SO :" From feedback from good people here and rust-lang forum it is look like there is no Safe Rust solution with multiple mutable borrowing for serious reasons. Reference counting is the next best thing. It’s overhead is only one pointer derefencing and integer increment. It is totally acceptable. I consider this approach as the answer to problem."

Kind user @trentcl even presented ready solution for this thread’s problem

[https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=cf7b4509813916b1b31fd9e71b3aeb1a]

Thank you again:)

Hey, that’s me! Different name, on this site.

I’m glad my example helped. I’ll take this opportunity to elaborate on a few of the changes I made, that I didn’t want to get into on SO.

  • Increasing a Vec's capacity doesn’t increase its length, so you can’t grow the Vec by assigning to indices; you have to use methods like push. So that’s why I used Default to implement new. You could write SampleTable::with_capacity that gives the Vec (and the HashMap) an initial capacity but for the purpose of the example I figured it wasn’t important.
  • add_sample and replace_sample accept impl Into<Sample>, which means you can pass in a Vec<u32> and have it converted automatically (Rc<[u32]> implements From<Vec<u32>>). Unfortunately this does mean copying the slice, because Rc and Arc store the refcount in-line with the data so it has to reallocate. Rc<Vec<u32>> would avoid copying the slice at the cost of double indirection; it’s a tradeoff.
  • try_from / try_into are preferred over as casts because you can decide what to do with the failure case.

Hi, @ trentj :slight_smile:
That are very intersting details! Thank you again!
Now I know that I need to learn much more about this powerfull language.
At least this is kind of complexity that rewards you with RELIABLE and fast programs. Yes, C++, I am looking at you! You are overcomplicated abomination full of UB from 80’s :)))