RFC: Hash and Eq requirement for values

[jeff-hiner]

Maybe a duplicate of #45 but I figured I'd ask anyway.

I'm trying to use evmap as the base store for an MQTT broker. For simple subscription matches I'm keying off the topic, and my initial attempt uses a struct containing a token+futures::channel::mpsc::Sender as the value item in order to route messages. The evmap crate seems to be a good fit for this application: the most common case is using the collection to look up subscribers for a topic, and then pushing publish messages into their queues. I want this to be lock-free and fast. Occasionally I have to modify the subscriptions list when subscribers come and go, and I don't want to have to block all publishers to do so. And having the value be a collection is actually useful, because each topic can have multiple routing destinations. Storing a list of these items is something I'd have to do anyway. But using hashbag internally creates some challenges:

1. futures::channel::mpsc::Sender doesn't impl Eq or Hash, and in fact most senders don't even implement PartialEq let alone Hash (futures_channel, crossbeam, flume). I used the derivative crate to try out an implementation where senders to the same receiver were equivalent, but...
2. A lot of sender implementations require &mut to send. For reasons that are obvious in retrospect (extensive use of interior aliasing) evmap isn't set up to allow interior mutability of values. I can work with unbounded channels in a prototype because I don't need &mut, but this isn't a great approach in a production application-- I'm trying to bound memory usage and balance performance for clients that can publish lots of messages in a short time, and using an unbounded channel could cause resource starvation or long tails elsewhere.

I can actually work around the second issue with flume, because the sender doesn't need to be mutable. But flume doesn't have a way to determine whether two senders point at the same receiver, and I'm not sure how to sanely implement Hash for it either.

So I guess I'm trying to figure out whether it makes any sense at all to attempt a feature patch/PR that removes the Eq and Hash requirement by allowing a different container, perhaps a normal linear sequence like Vec for Long. Are there other reasons for using hashbag that I'm not seeing?

[jonhoo]

Sorry for the super late reply!

So, this is a tricky one. The hashbag is there very specifically to support efficient removes from value sets, and there it's pretty much impossible to avoid. I think that the workaround here would be to have a complete copy of the implementation that was single-valued (as you observed, this is #45), but that's also a sub-optimal solution.

Now, in your particular case, since you don't need to remove individual values from a value set, you can actually work around this by sticking a newtype around your tuple and just implement Hash + Eq for it with a trivial implementation that always returns true for equality and always hashes to the same value. It feels dirty, but it should work as long as you only ever use that newtype for your thing when it's placed in an evmap value, and as long as you never have more than one value in any given value set. If you do need to have multiple values per value set, but just don't need support for individual removes, you'd have to make Eq return false instead, but that violates the spec of Eq (it's no longer reflexive) and is more likely to cause unexpected issues.

The broader solution here, I think, is to find a way to implement #45 without copying the whole implementation. I'll put a comment over there with some thoughts.

[jeff-hiner]

Thanks! Sorry, I didn't realize you were in the middle of your PhD defense. How did it go?

[jonhoo]

Hehe, I have now graduated 🎉 :)

[jonhoo]

I'm going to close this following the merge of #73 :)