`crossbeam-skiplist`: allows lookup to be customized.

[al8n]

Hi, this PR solves #1133, which changes the lookup API from

where
  K: Borrow<Q>,
  Q: ?Sized + Ord,

to

where
  Q: ?Sized + Ord + equivalent::Comparable<K>,

The equivalent is the crate used by indexmap.

I would like to suggest this change because when using SkipMap, I find the lookup API are limited by Borrow trait. e.g., with Borrow trait, this example cannot be implemented as we cannot implement impl<'a> core::borrow::Borrow<FooRef<'a>> for Foo because of Rust's rule.

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Foo {
    a: u64,
    b: u32,
}

#[derive(PartialEq, Eq)]
struct FooRef<'a> {
    data: &'a [u8],
}

impl PartialOrd for FooRef<'_> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for FooRef<'_> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let a = u64::from_be_bytes(self.data[..8].try_into().unwrap());
        let b = u32::from_be_bytes(self.data[8..].try_into().unwrap());
        let other_a = u64::from_be_bytes(other.data[..8].try_into().unwrap());
        let other_b = u32::from_be_bytes(other.data[8..].try_into().unwrap());
        Foo { a, b }.cmp(&Foo {
            a: other_a,
            b: other_b,
        })
    }
}

impl<'a> core::borrow::Borrow<FooRef<'a>> for Foo {
    fn borrow(&self) -> &FooRef<'a> {
        // we cannot return a reference to a local variable
        todo!()
    }
}

fn lookup() {
    let s = SkipMap::new();
    let foo = Foo { a: 1, b: 2 };
    s.insert(foo, 12);

    let buf = 1u64
        .to_be_bytes()
        .iter()
        .chain(2u32.to_be_bytes().iter())
        .copied()
        .collect::<Vec<_>>();

    let foo_ref = FooRef { data: &buf };
    let ent = s.get(&foo_ref).unwrap();
    assert_eq!(ent.key().a, 1);
    assert_eq!(ent.key().b, 2);
    assert_eq!(*ent.value(), 12);
}

After change to Q: ?Sized + Ord + Comparable<K>, just like how indexmap do in its lookup API, the above example can be implemented.

use equivalent::{Comparable, Equivalent};

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Foo {
    a: u64,
    b: u32,
}

#[derive(PartialEq, Eq)]
struct FooRef<'a> {
    data: &'a [u8],
}

impl PartialOrd for FooRef<'_> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for FooRef<'_> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let a = u64::from_be_bytes(self.data[..8].try_into().unwrap());
        let b = u32::from_be_bytes(self.data[8..].try_into().unwrap());
        let other_a = u64::from_be_bytes(other.data[..8].try_into().unwrap());
        let other_b = u32::from_be_bytes(other.data[8..].try_into().unwrap());
        Foo { a, b }.cmp(&Foo {
            a: other_a,
            b: other_b,
        })
    }
}

impl Equivalent<Foo> for FooRef<'_> {
    fn equivalent(&self, key: &Foo) -> bool {
        let a = u64::from_be_bytes(self.data[..8].try_into().unwrap());
        let b = u32::from_be_bytes(self.data[8..].try_into().unwrap());
        a == key.a && b == key.b
    }
}

impl Comparable<Foo> for FooRef<'_> {
    fn compare(&self, key: &Foo) -> std::cmp::Ordering {
        let a = u64::from_be_bytes(self.data[..8].try_into().unwrap());
        let b = u32::from_be_bytes(self.data[8..].try_into().unwrap());
        Foo { a, b }.cmp(key)
    }
}

fn lookup() {
    let s = SkipMap::new();
    let foo = Foo { a: 1, b: 2 };

    s.insert(foo, 12);

    let buf = 1u64
        .to_be_bytes()
        .iter()
        .chain(2u32.to_be_bytes().iter())
        .copied()
        .collect::<Vec<_>>();
    let foo_ref = FooRef { data: &buf };

    let ent = s.get(&foo_ref).unwrap();
    assert_eq!(ent.key().a, 1);
    assert_eq!(ent.key().b, 2);
    assert_eq!(*ent.value(), 12);
}

This feature is quite important when using some zero-copy deserialization frameworks like rkyv's types with SkipMap to avoid the allocation.

[marvin-j97]

I ran across this recently too, unfortunately the skiplist sits in my hot path, so the allocation is unfortunate. Using this PR increased performance by like 10% (for the entire read path, of which the skiplist is only a part of):

Before

You can see that most of the time stems from allocating and drop_in_place of the Key Arc...

After

@al8n Very nice change!

[marvin-j97]

Is there anything that can be done to move this forward? I guess this could be a breaking change, but crossbeam is < 1.0 anyway - I've been thinking of forking crossbeam-skiplist, just so I can get this change into my code base...

[taiki-e]

Thank for the PR.

To be honest, I suspect that the “efficiency” issue here can actually be resolved in some cases by using the appropriate key wrappers...

[al8n]

Is there anything that can be done to move this forward? I guess this could be a breaking change, but crossbeam is < 1.0 anyway - I've been thinking of forking crossbeam-skiplist, just so I can get this change into my code base...

I have already published a forked version crossbeam-skiplist-pr1132 to the crates.io for tmp solution, this may help your case.

[taiki-e]

It seems that @cuviper has tried something similar to this before (https://github.com/indexmap-rs/indexmap/issues/253#issuecomment-1459160166). The approach there does not seem to have type inference issues unlike this PR? (or am I missed something?)

[al8n]

It seems that @cuviper has tried something similar to this before (indexmap-rs/indexmap#253 (comment)). The approach there does not seem to have type inference issues unlike this PR? (or am I missed something?)

I finished the changes about flipping K and Q, now we do not need turbofish anymore. The only problem is that we cannot use the equivalent crate directly(In the current equivalent crate, K and Q are not flipped), I have to add Comparable and Equivalent in lib.rs.

[taiki-e]

Nice! Could you revert the turbofish addition on crossbeam-skiplist/tests/map.rs and crossbeam-skiplist/tests/set.rs as well?

https://github.com/crossbeam-rs/crossbeam/pull/1132/files#diff-75f4f67227e1c745e030de5d756b0cc4cb11ccd273aac4bd1cf8277d4c7abc30 https://github.com/crossbeam-rs/crossbeam/pull/1132/files#diff-83acf27b3801996150152093e109e25ebe594f6595ead4c9297986b1d0a3ec27

[al8n]

Nice! Could you revert the turbofish addition on crossbeam-skiplist/tests/map.rs and crossbeam-skiplist/tests/set.rs as well?

https://github.com/crossbeam-rs/crossbeam/pull/1132/files#diff-75f4f67227e1c745e030de5d756b0cc4cb11ccd273aac4bd1cf8277d4c7abc30 https://github.com/crossbeam-rs/crossbeam/pull/1132/files#diff-83acf27b3801996150152093e109e25ebe594f6595ead4c9297986b1d0a3ec27

Finished.

[al8n]

LGTM.

Could I merge this PR?

[taiki-e]

The first version of this PR was a breaking change because it required turbofish in some places, but I guess the current version will actually not cause the breakage that would be considered a breaking change.

[marvin-j97]

@taiki-e Can this change be published (possibly as pre-release) to crates?

[taiki-e]

New release is blocked by what to do with https://github.com/crossbeam-rs/crossbeam/pull/1158.

[marvin-j97]

New release is blocked by what to do with #1158.

That doesn't seem to change the API though, seems more like a refactor to me.

[taiki-e]

I think such a change is a breaking change when done after this change is released. See https://github.com/tokio-rs/bytes/issues/479#issuecomment-1011065884 for more.

[al8n]

I think such a change is a breaking change when done after this change is released. See tokio-rs/bytes#479 (comment) for more.

Actually, I am fine with keeping Comparable and Equivalent in the crossbeam-skiplist, if compatibility is important, I can close #1158.

I will also give a look how indexmap plays with equivalent crate.