crossbeam Custom comparators for SkipList

It would be useful to be able to specify a custom C++-style comparator function to override SkipList key order at runtime, specifically for an ordered K/V store like fjall (issue here).

The implementation would be easy. Unfortunately, Rust has no standard API for custom comparators, so there's no obvious, future-proof design to go with. The closest reference points I'm aware of are the compare crate and C++ std::map.

Feb 14 '25 07:02 matthew-mcallister

Is this the same as the already merged https://github.com/crossbeam-rs/crossbeam/pull/1132? Or are you requesting something different?

Feb 16 '25 05:02 taiki-e

Different. The idea is essentially to add a type parameter C and a field comparator: C to SkipList that implements a trait similar to (pseudocode)

trait Comparator<K> {
   fn compare(&self, left: &K, right: &K) -> std::cmp::Ordering;
}

When comparing keys, instead of key1.compare(key2), you write self.comparator.compare(key1, key2). The default comparator would be to do the same thing that SkipList already does:

impl<K: Ord> Comparator<K> for DefaultComparator {
    fn compare(&self, left: &K, right: &K) -> Ordering {
        Ord::cmp(left, right)
    }
}

But the use case I had in mind was to use Box<dyn Comparator> as the comparator to support an arbitrary or dynamic comparison function on Vec<u8> keys.

That said, fjall seems to be moving towards a custom skiplist implementation, at which point the feature could be implemented without support from crossbeam.

Feb 16 '25 06:02 matthew-mcallister

Different. The idea is essentially to add a type parameter C and a field comparator: C to SkipList that implements a trait similar to (pseudocode)

trait Comparator<K> { fn compare(&self, left: &K, right: &K) -> std::cmp::Ordering; } When comparing keys, instead of key1.compare(key2), you write self.comparator.compare(key1, key2). The default comparator would be to do the same thing that SkipList already does:

impl<K: Ord> Comparator<T> for DefaultComparator { fn compare(&self, left: &K, right: &K) -> Ordering { Ord::cmp(left, right) } } But the use case I had in mind was to use Box<dyn Comparator> as the comparator to support an arbitrary or dynamic comparison function on Vec<u8> keys.

That said, fjall seems to be moving towards a custom skiplist implementation, at which point the feature could be implemented without support from crossbeam.

If you want to use a skiplist that supports custom comparators, then skl seems to meet your requirements. But, skl is designed for databases and it is an ARENA-style implementation.

Feb 16 '25 16:02 al8n

@matthew-mcallister Thanks for the explanation.

I think if we do this before (unreleased) https://github.com/crossbeam-rs/crossbeam/pull/1132 is released, we can put in this without a breaking change using the default type parameter, I honestly don't have a strong opinion on whether we want this or not. For simple cases, I think just using a wrapper like std::cmp::Reverse would be sufficient, though....

Feb 16 '25 16:02 taiki-e

@matthew-mcallister Thanks for the explanation.

I think if we do this before (unreleased) #1132 is released, we can put in this without a breaking change using the default type parameter, I honestly don't have a strong opinion on whether we want this or not. For simple cases, I think just using a wrapper like std::cmp::Reverse would be sufficient, though....

I think this is useful because currently, the comparison is stateless, which means users cannot provide some extra information for comparison, e.g., strip prefixes, or ignore suffixes. Although users can use a key wrapper, the problem is it will bring a bunch of traits to implement.

Feb 16 '25 16:02 al8n

I also forked a version of crossbeam-skiplist (https://docs.rs/crossbeam-skiplist-fd/0.1.5) to support custom comparators several months ago. If we want to support custom comparators before a new release, I can work on this.

Feb 16 '25 16:02 al8n

I think if we do this before (unreleased) #1132 is released, we can put in this without a breaking change using the default type parameter, I honestly don't have a strong opinion on whether we want this or not. For simple cases, I think just using a wrapper like std::cmp::Reverse would be sufficient, though....

FWIW, if fjall were the only consumer of this feature, I would probably lean towards shelving it, since that crate is officially looking to implement a custom skiplist anyways. But it looks like there will be others who would like to use their own comparators as well.

The feature should be straightforward to implement and test, and I wouldn't mind doing it myself either. I think the main challenge is getting the design right for the Comparator trait, which it seems will have to support the semantics of https://github.com/crossbeam-rs/crossbeam/pull/1132 while also enabling the use cases that it was designed for.

Feb 17 '25 06:02 matthew-mcallister

I also forked a version of crossbeam-skiplist (https://docs.rs/crossbeam-skiplist-fd/0.1.5) to support custom comparators several months ago.

Um, that crate has 9 traits in comparison related...? If they are really needed for this functionality, so I feel this functionality is quite complicated.

Feb 21 '25 13:02 taiki-e

I also forked a version of crossbeam-skiplist (https://docs.rs/crossbeam-skiplist-fd/0.1.5) to support custom comparators several months ago.

Um, that crate has 9 traits in comparison related...? If they are really needed for this functionality, so I feel this functionality is quite complicated.

Yeah, it is complicated in that crate because it was originally just for a POC. The comparison-related traits can be simplified in a production implementation (only need one trait for sure)

Feb 21 '25 13:02 al8n

I'm working on a branch that only requires one trait.

Feb 23 '25 21:02 matthew-mcallister

FWIW, if fjall were the only consumer of this feature, I would probably lean towards shelving it, since that crate is officially looking to implement a custom skiplist anyways. But it looks like there will be others who would like to use their own comparators as well.

We (https://github.com/slatedb/slatedb) are also interested in this feature (see https://github.com/slatedb/slatedb/issues/663). We use the crossbeam skip list for our in memory mem-tables and want to allow users to supply their own comparator so they can sort byte keys in whatever order they want, so we cannot hardcode it in the Ord function for our internal byte representation.

@matthew-mcallister happy to help out with the PR / review as appropriate.

Jul 02 '25 17:07 agavra

@matthew-mcallister happy to help out with the PR / review as appropriate.

The PR is https://github.com/crossbeam-rs/crossbeam/pull/1182. You should take a look and leave feedback if there are any specifics for your use case that need consideration. Other than that, the PR has been in "needs review" limbo for some time.

Jul 02 '25 17:07 matthew-mcallister

@taiki-e @al8n - would be great to get a committer review on #1182, this would really help us over at SlateDB 😅

Jul 30 '25 20:07 agavra

@taiki-e @al8n - would be great to get a committer review on #1182, this would really help us over at SlateDB 😅

I am happy to have those changes and the code looks good to me.

Jul 30 '25 20:07 al8n

Thanks for working on this. We would really benefit from this for our usecase in SlateDB as well. Excited about having this merged.

Aug 05 '25 04:08 nomiero