Extract Equivalent trait into a separate crate

[stepancheg]

In our project we have two libraries (one is another implementation of hashmap and another is another implementation of an interner). Both declare own Equivalent trait.

Might be useful is there was a crate which simply declares Equivalent, so the same Equivalent implementation can be implemented for various types without depending on specific use case.

IndexMap can extract Equivalent into a separate crate and reexport this trait to keep indexmap backward compatible.

[cuviper]

Note that hashbrown 0.13 added its own copy of Equivalent -- but we wouldn't want to publicly use that here, because that would expose that version as a public dependency in the API.

If there's a common crate, it should be 1.0 and committed to long-term API stability. I'm not sure if there's much justification for such a micro-crate though. Are there many examples of types that manually implement this? (i.e. types not covered by the blanket Borrow+Eq impl).

[stepancheg]

> Are there many examples of types that manually implement this?

In our project we have a few. Basically each time a key is a struct or enum which contains more than one pointer (struct MyKey(String, String) or enum MyKey { A(String), B(String) }).

But there's another issue I forgot to mention.

We have a Hashed<T> type which caches the key hash (or it could be another generic wrapper). It is placed in common library, let's call it my_proj_util.

And there's another crate my_proj_bin which depends on my_proj_util. my_proj_bin may want to have:

struct MyKey(String, String);

IndexMap<Hashed<MyKey>, u32>

struct MyKeyRef(&str, &str);

and lookup in this hash by Hashed<MyKeyRef>.

It is not possible to implement Equivalent for Hashed outside of my_proj_util crate.

So to deal with it we need either:

• implement Equivalent<Hashed<K>> for Hashed<Q> for for all possible Equivalent trait implementations in all possible maps adding dependencies on all these map crates
• or create wrappers like HashedKey(Hashed<MyKey>), HashedKeyRef(Hashed<MyKeyRef>) and implement Equivalent between them

Not ideal.

> If there's a common crate, it should be 1.0 and committed to long-term API stability

Long term API stability might be an issue.

Equivalent might not not implemented for optimal performance.

In the example above, MyKeyRef already contains pointers, and we pass it as &MyKeyRef making it double pointers while we could pass that "equivalent" key by value, not by reference.

Instead of this:

    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
    where
        Q: Hash + Equivalent<K>,
    { ... }

something like this:

    pub fn get<Q>(&self, key: Q) -> Option<&V>
    where
        Q: Hash + Equivalent<K>,
    { ... }

and still be able to pass &str where the key is String.

However, I tried to change the semantics of Equivalent + get (or our version of IndexMap) and could not make it automatically work for Borrow.

So in our version of indexmap there's a separate get_by_value function:

    // Using `Equivalent` identical to indexmap `Equivalent`
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        Q: Hash + Equivalent<K> + ?Sized,
    { ... }

    pub fn get_by_value<Q>(&self, key: Q) -> Option<&V>
    where
        Q: Equivalent<K>,
    { ... }

And using get_by_value results is measurable whole program perf difference.

But perhaps there's not much to lose here. What's the worst thing can happen? indexmap will have to switch to new long term stable equivalent2 crate for Equivalent trait.

So I don't know what would be the best.

But if such crate is to be added, perhaps better get hashbrown onboard first.

[cuviper]

In our project we have a few. Basically each time a key is a struct or enum which contains more than one pointer (struct MyKey(String, String) or enum MyKey { A(String), B(String) }).

If there are multiple things that could be compared, how do you maintain the requirement, "The implementor must hash like K, if it is hashable." (This seems like more of an issue for the tuple, not the enum.)

Equivalent might not not implemented for optimal performance.

In the example above, MyKeyRef already contains pointers, and we pass it as &MyKeyRef making it double pointers while we could pass that "equivalent" key by value, not by reference.

I think it's fairly likely that this double-indirection will disappear after inlining, especially since get<Q> and its related functions will be monomorphized for your particular instance of Q. There are a lot of abstractions involved, so I can't be sure -- but any change should be accompanied by careful performance measurements.

But perhaps there's not much to lose here. What's the worst thing can happen? indexmap will have to switch to new long term stable equivalent2 crate for Equivalent trait.

Using a different source for Equivalent would be a breaking change in the API. However, the master branch is currently in a 2.0-pre state, as yet unpublished, so if we're going to make any changes, now is the time! Which is not to say that we should definitely make your suggested changes, but we can at least consider it. That's somewhat orthogonal to where Equivalent comes from though.

[stepancheg]

If there are multiple things that could be compared, how do you maintain the requirement, "The implementor must hash like K, if it is hashable." (This seems like more of an issue for the tuple, not the enum.)

There must be some misunderstanding here.

I means, when a key has two pointers like struct MyKey(String, String), to avoid allocation, another key need to be introduced struct MyKeyRef(&str, &str), and Equivalent between them.

Was just stating the obvious.

I think it's fairly likely that this double-indirection will disappear after inlining

I saw it didn't! (In our implementation where everything is marked #[inline] but not #[inline(always)], -O but no LTO. That was probably due to fact that fully inlined get is quite large, get was called from hundreds places and compiler tried to avoid code bloat.)

any change should be accompanied by careful performance measurements

I'm not proposing any changes here. I couldn't make better version of Equivalent trait: so that Equivalent implementation could be passed by value.

[cuviper]

There must be some misunderstanding here.

I means, when a key has two pointers like struct MyKey(String, String), to avoid allocation, another key need to be introduced struct MyKeyRef(&str, &str), and Equivalent between them.

Sorry, yes, that does indeed makes sense.

I think it's fairly likely that this double-indirection will disappear after inlining

I saw it didn't! (In our implementation where everything is marked #[inline] but not #[inline(always)], -O but no LTO. That was probably due to fact that fully inlined get is quite large, get was called from hundreds places and compiler tried to avoid code bloat.)

Not even in its depths? You don't need the whole thing inlined, but the closest thing to a hotspot there is probably the eq callback used in IndexMapCore::get_index_of, and ideally that hashbrown search loop will get inlined. So there might still be extra indirection on the get<Q> entry point, but hopefully not where it matters.

Anyway, I'll take your point that you saw "measurable whole program perf difference."

[stepancheg]

CC @Amanieu

[Amanieu]

I think there is an argument for moving Equivalent into a separate crate so that it can be shared between indexmap and hashbrown (and possibly other crates).

There is a slight complication in the case of hashbrown when it is used inside the standard library, but we can make the equivalent dependency optional (but enabled by default) and use an internal Equivalent trait when building with rustc-dep-of-std.

I don't have any strong opinions on the actual design of Equivalent though.

[cuviper]

I have published equivalent 0.1.0 as a direct extraction of the current trait. I also added a Comparable trait that extends the idea to ordered keys, like tree maps, but I'm not sure there's anyone thinking about that yet. :)
https://crates.io/crates/equivalent

That could work as a drop-in replacement here, just pub use re-exported, but like I said I want to reach 1.0 first.

I also started experimenting with Equivalent taking self by value, with the blanket impl on &Q to maintain the existing kind of get(&key) lookups. Here's what that looks like for indexmap -- although note the Copy additions needed for repeated comparison, so we might want it as a supertrait Equivalent<K>: Copy for that reason. (Copying &Q is fine!)
master...cuviper:indexmap:equivalent-by-value

I guess we also lose trait object safety, but I'm not sure if anyone cares...

[stepancheg]

I also started experimenting with Equivalent taking self by value, with the blanket impl on &Q to maintain the existing kind of get(&key) lookups

I checked, it works even for types declared outside of indexmap crate:

use indexmap::{Equivalent, IndexMap};

#[derive(Copy, Clone, Hash)]
struct BytesAsStringRef<'a>(&'a [u8]);

impl<'a> Equivalent<String> for BytesAsStringRef<'a> {
    fn equivalent(self, key: &String) -> bool {
        self.0 == key.as_bytes()
    }
}

#[test]
fn test() {
    let im: IndexMap<String, i32> = IndexMap::new();
    im.get("123");
    im.get(BytesAsStringRef(b"123"));
}

I don't remember why I struggled to implement it.

[cuviper]

im.get(BytesAsStringRef(b"123"));

Careful! This compiles, but it doesn't work with derive(Hash) because Hasher::write_str includes an extra byte for prefix-freedom. That's an implementation detail of the unstable method, which could even change between different hashers once it is stabilized.

edit: I added a working version of this to my branch.

[cuviper]

I guess we also lose trait object safety, but I'm not sure if anyone cares...

Oh, Hash is a bigger blocker for that anyway, since its methods have the generic H: Hasher parameter.

[stepancheg]

Can you please explain the last comment? What should work but does not work?

[cuviper]

I mean that currently it is possible to form a trait object, like &dyn Equivalent<K>, and we would lose that if the method takes self by value. But Hash can't be a trait object either, so dyn Equivalent<K> isn't useful anyway.