HashMap key access across threads where data is non-Send

help
1

Here's an interesting little problem. I have a HashMap<K,V>. K, the key type, is Copy and Send. V, the data type, is not Send, because it contains an Rc cell. I really need V to be an Rc.

I want to find out, from another thread, if the HashMap contains a key k.

The problem is, I can't put the HashMap inside an Arc<Mutex<HashMap<K,V>>> because V is not Send. So there's no way to test if K is in the map.

Right now, as a workaround, I'm maintaining a HashSet in parallel to to the HashMap. The HashSet just has a list of the keys in the HashMap. The HashSet can be put inside Arc<Mutex<HashSet>>. Works, but doubles storage and time.

Is there a better way?

2

If you're OK with unsafe you could write a custom accessor type that wraps your shared map with a restricted key-only API, and then unsafely implement Send/Sync for it.

Alternatively, you could make the main thread an actor that responds to "is this key in the map" queries from other threads over a channel. That has the nice effect of avoiding shared mutability entirely.

2 Likes
3

That's a quite interesting problem. I agree that you could do it correctly with unsafe.

4

I had the same thoughts and wrote this up, but waited to post it until others chimed in. You're technically relying on HashMap to be well-behaved and that Rc's documentation is exaggerating from a pedantic point of view (i.e. it's OK to Send an Rc that isn't manipulated).

1 Like
5

Note also that this is not ok when using an Arc to share it across threads. This is because if the key-only version is the last Arc to get dropped, then you are running the destructor of non-Send values on a new thread.

1 Like
6

OK, there's no really great solution. Didn't think so. Just wanted to see if someone was going to say "Oh, that is easy using the XYZ crate" or "you need to use feature ABC" or something.

This is actually the first time, in a year, that I've hit a locking granularity problem. I expected this to come up more often when new to Rust.

7

I think that maintaining two parallel datastructures is probably required, but you might be able to get better performance with a different distribution of responsibilities. A generational arena like thunderdome, for example, could let you avoid calculating the hash value multiple times:

  • Shared: Arc<Mutex<HashMap<K, thunderdome::Index>>>
  • Thread local: thunderdome::Arena<V>
8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.