Add custom comparators#1182
Conversation
|
cc @al8n |
|
Restored the |
matthew-mcallister
force-pushed
the
comparators
branch
2 times, most recently
from
4e63330 to
b19ede6
Compare
Renamed OrdComparator to BasicComparator and made compatible with the Equivalent/Comparable traits
matthew-mcallister
force-pushed
the
comparators
branch
from
b19ede6 to
fbfe7fd
Compare
|
It's been a while since I circled back to this, but is there a sentiment as to whether to merge? |
agavra
left a comment
agavra
left a comment
There was a problem hiding this comment.
This looks good to me, though I admit I'm a little sketched out by the concept of breaking the hash/eq dependency definition with Equivalator trait...
Would be good to get some committers reviewing this as well! Excited for this feature.
| /// Because you can use `Equivalator` to implement very different comparison | ||
| /// logic from the `Eq` trait for a given type, there is no expectation that | ||
| /// two keys should have the same hash for them to compare equal. For example, | ||
| /// this is a valid implementation that treats two inputs of any type as equal: |
There was a problem hiding this comment.
It would be good to spell out the motivations for this. It is always possible for the user to implement some funky transform of their keys before they insert into a set/map and when retrieving data as a workaround for not having this. (e.g. in your test, I think a much better implementation if the user wanted that is to just set.insert(key.length()) instead of doing something convoluted with the eq function). That being said, you could still have a comparator that sorts based on key.length and considers two keys equivalent for a sort order if they have the same length.
On the other hand, if we introduce this, it would be impossible to leverage traditional hash structures as optimizations in the future (e.g. add a bloom filter on top of a skiplist) because two elements could be equivalent under this equivilator but have different hashes.
It generally seems dangerous to me to break the standard hash/eq dependency that is implicitly used by so many data structures.
There was a problem hiding this comment.
It would be good to spell out the motivations for this.
Agreed. My example was pretty contrived; I can provide more realistic motivation.
Though I will remark that set.insert(key.length()) would produce a totally different program as you'd lose access to the first key inserted. Even skip_map.insert(key.length(), key) is not equivalent since that would give you the last key inserted instead of the first.
It generally seems dangerous to me to break the standard hash/eq dependency that is implicitly used by so many data structures.
Well, this doesn't "break" the Hash/Eq dependency since nothing changes if you stick to the standard library traits. But I think the documentation here may be confusing because hashing was out of scope for this PR, so there is no indication of how you would handle hashing when you need it. In reality, hashing is very easy to accommodate; it just requires another "Hash"-ator trait to go alongside Comparator and Equivalator. This is another concept that has been in the C++ standard library for decades.
There was a problem hiding this comment.
Got it! If there's a good reference implementation in the standard C++ library that gives me a lot more confidence in the approach. Thanks for the explanation.
| } | ||
|
|
||
| /// Returns an iterator over all entries in the map, | ||
| /// sorted by key. |
There was a problem hiding this comment.
| /// sorted by key. | |
| /// sorted by the comparator's ordering of the key. |
There was a problem hiding this comment.
Should also update SkipSet and change all method docs to use the term "equivalent" (instead of equal).
Addressing feedback on the PR. - Clarify the lack of an Equivalator-compatible hashing trait. - More prominently mention comparators in the SkipList/SkipMap docs. - Updated tests and example to be more realistic and less constrived.
matthew-mcallister
force-pushed
the
comparators
branch
from
b1258bc to
ec87e01
Compare
|
Sorry it took me an eternity to circle back round to this. I got busy and I'm bad at multitasking. I pushed a commit that addresses the last round of feedback with respect to comments and tests/examples. Are there any maintainers that want to provide feedback and give a disposition as to whether there is a desire to merge this? Or whether we should perhaps take a different approach, such as spinning out the traits into a new crate and adding a hashing trait for DB folks who want to support this with their Bloom filters? |
|
Hi @taiki-e, any chances to get this PR merge? |
There was a problem hiding this comment.
Pull request overview
This PR adds support for custom comparators to the skip list data structures in crossbeam-skiplist, addressing issue #1180. The feature enables runtime-configurable comparison functions for ordering keys, which is useful for use cases like ordered K/V stores that need custom comparison logic.
Changes:
- Introduces
ComparatorandEquivalatortraits to generalize key comparison, withBasicComparatorproviding the default behavior - Adds a type parameter
C(defaulting toBasicComparator) toSkipList,SkipMap, andSkipSet, along withwith_comparator()constructors - Updates trait bounds throughout the codebase from
K: OrdtoC: Comparator<K>and fromK: Comparable<Q>toC: Comparator<K, Q>
Reviewed changes
Copilot reviewed 8 out of 8 changed files in this pull request and generated 4 comments.
Show a summary per file
| File | Description |
|---|---|
| crossbeam-skiplist/src/comparator.rs | Defines new Equivalator and Comparator traits and BasicComparator implementation |
| crossbeam-skiplist/src/base.rs | Adds comparator type parameter to SkipList and updates all comparison operations to use the comparator |
| crossbeam-skiplist/src/map.rs | Adds comparator type parameter to SkipMap and reorganizes impl blocks based on trait bounds |
| crossbeam-skiplist/src/set.rs | Adds comparator type parameter to SkipSet with similar reorganization |
| crossbeam-skiplist/src/lib.rs | Exports the new comparator module |
| crossbeam-skiplist/tests/map.rs | Adds test demonstrating case-sensitive/insensitive string comparison |
| crossbeam-skiplist/tests/set.rs | Adds test demonstrating dynamic comparator with byte slice encoding |
| Cargo.toml | Allows additional clippy lints for complex types |
Comments suppressed due to low confidence (3)
crossbeam-skiplist/src/map.rs:219
- There's a typo in the documentation: "Print then numbers" should be "Print the numbers".
/// // Print then numbers from least to greatest
crossbeam-skiplist/src/base.rs:2126
- The
SendandSyncimplementations forRefRangeshould explicitly requireC: Send + Syncfor clarity, even though these bounds are implicitly enforced through the requirement that&'a SkipList<K, V, C>must be sendable/shareable. Making the bounds explicit would make the code more self-documenting and easier to understand. For example:unsafe impl<Q, R, K, V, C> Send for RefRange<'_, Q, R, K, V, C> where C: Comparator<K> + Comparator<K, Q> + Send + Sync, ...
unsafe impl<Q, R, K, V, C> Send for RefRange<'_, Q, R, K, V, C>
where
C: Comparator<K> + Comparator<K, Q>,
R: RangeBounds<Q>,
Q: ?Sized,
{
}
unsafe impl<Q, R, K, V, C> Sync for RefRange<'_, Q, R, K, V, C>
where
C: Comparator<K> + Comparator<K, Q>,
R: RangeBounds<Q>,
Q: ?Sized,
{
}
crossbeam-skiplist/src/set.rs:46
- The PR description mentions that the comparator type parameter
Cis "defaulted toOrdComparator", but the actual code usesBasicComparatorinstead. This is a discrepancy between the PR description and the implementation. The description should be updated to sayBasicComparatorto match the actual code.
/// Returns a new, empty map with the given comparator.
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
Co-authored-by: Copilot <[email protected]>
There was a problem hiding this comment.
Pull request overview
Copilot reviewed 8 out of 8 changed files in this pull request and generated no new comments.
Comments suppressed due to low confidence (1)
crossbeam-skiplist/src/base.rs:2125
- The
unsafe impl Sendandunsafe impl SyncforRefRangeshould explicitly requireC: SendandC: Syncrespectively for clarity and safety. While the current implementation is technically safe becauseRefRangecontains&'a SkipList<K, V, C>, andSkipListis onlySyncwhenC: Sync, making the bounds explicit would be clearer and more maintainable. Consider addingC: Sendto theSendimpl andC: Syncto theSyncimpl.
unsafe impl<Q, R, K, V, C> Send for RefRange<'_, Q, R, K, V, C>
where
C: Comparator<K> + Comparator<K, Q>,
R: RangeBounds<Q>,
Q: ?Sized,
{
}
unsafe impl<Q, R, K, V, C> Sync for RefRange<'_, Q, R, K, V, C>
where
C: Comparator<K> + Comparator<K, Q>,
R: RangeBounds<Q>,
Q: ?Sized,
{
}
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
taiki-e
left a comment
taiki-e
left a comment
There was a problem hiding this comment.
LGTM, thanks @matthew-mcallister!
As for Send/Sync, the existing implementations are already questionable, so I'll address on our end before release.
As for documentation, PRs for further improvements are welcome.
Closes #1180.
The diff is large due to having to add a type parameter
Cand update constraints in numerous places, but the logic changes are not large.This trait adds the
ComparatorandEquivalatortraits, which generalize theComparableandEquivalenttraits by taking aselfparameter in addition to the two keys to compare, making it possible to change the comparison function used without changing the key type.Summary
trait Comparator<L, R>andtrait Equivalator<L, R>.struct BasicComparator, which is a zero-sized type that implementsComparatorusing theComparabletrait, which itself falls back onBorrowandOrd.CtoSkipList,SkipMap, andSkipSet.Cis defaulted toOrdComparator. This preserves the existing behavior of functions likeget(),insert(), etc.SkipList::with_comparator(),SkipSet::with_comparator(), andSkipMap::with_comparator()constructors.SkipList::new(),SkipMap::new(), andSkipSet::new()always useC = OrdComparator. It would be nice if it worked for anyCthat implementsDefault, but that would break type inference. This is exactly the reasonstd::collections::HashMap::new()always usesS = RandomStatefor its defaulted parameter even ifSimplementsDefault.Box<dyn Fn(&[u8], &[u8]) -> Ordering>as the comparator.Hashing
Because the goal of these traits is to support totally different comparison operations from the default for the underlying key type,
Equivalatorexplicitly does not require two equivalent keys to have the same hash. If someone, someday wants to supportEquivalatoron their hash map, they will have to generalize theHashtrait as well.Safety
My one minor question is whether
unsafe impl<Q, R, K, V, C> Send for RefRange<'_, Q, R, K, V, C>should requireC: Sync. I don't think so because it doesn't requireKorVto be sync, but it was enough to make me second-guess myself.