Lifetimes of references in HashMaps

help
1

Suppse we have

pub struct cheese {
    things:HashMap<K1, V>,
    refs:HashMap<K2, &V>
}

and the point here is, that things contain key value pairs and refs contains other keys and references to values in things.

So the livetime of each pair in refs, is exactly as the lifetime of the referenced value in things.

How do I tell the compiler that? I mean all elements of things have different lifetimes.

Another question is, if Box would give performance degradation here as the pointers in refs (those of &V type) might already be on the heap since they are elements of a hashmap. (If things need to be as fast as possible, Box is not a good choice in general, as the heap is slow(er))

2

You can't, Rust dislikes self referential types like this, and there is no syntax to safely create them. (Actually, you can make a self referential type with safe Rust, it's just almost useless)

Even if you try and use unsafe, you can't soundly do this because HashMap reallocates on resizes, and this would invalidate all pointers into it.

1 Like
3

So instead of &V, I should store K1... Might be inconvinient if the keys are very large and we have many, though.

4

What problem are you trying to solve?

Would something like this work?

pub struct cheese {
    data: Vec<V>,
    things: HashMap<K1, usize>,
    refs: HashMap<K2, usize>
}
2 Likes
5

Realy I was just trying to figure out a way to store pointers in hashmaps as values. You might have a pool of large objects and you might want to reference them from multiple different keys.

6

Hmm...That looks interesting. I might give it some thought and come back later.

7

If you are careful you can even use get_unchecked to access the elements of the Vec with no bounds checking.

8

If you are trying to optimize memory access and allocation patterns using an object pool, that essentially entails writing a whole new memory allocator with its own strategy (above whatever is provided by the OS and Rust), and it's pretty much unsafe-by-definition. You could just use an already-existing memory pool crate.

If you don't have a specific reason to optimize just yet, I'd recommend going with the safe solution and either cloning the values or just storing the keys as you suggested yourself.

Re your "the heap is slower" assertion, I'm not sure what you mean by that, but the heap is just like any other part of memory, and accessing (reading/writing) it is not intrinsically any slower than using other memory segments.

(Dynamically allocating many objects can be slow, though, because memory allocation algorithms are quite complex nowadays.)

But in any case, I'd advise you to go with the simple and obvious solutions first, and do not try to optimize for cases of which you did not measure the performance.

2 Likes
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.