Custom comparators for SkipList

[matthew-mcallister]

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.

[taiki-e]

Is this the same as the already merged #1132? Or are you requesting something different?

[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<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.

[al8n]

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 {
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 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.

[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....

[al8n]

@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.

[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.

[matthew-mcallister]

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 #1132 while also enabling the use cases that it was designed for.

[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.

[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.

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)