Pre-RFC: Add comparator-api for ordered collections

Summary

Add a new trait Comparator to std::cmp, as a generics argument to all ordered collections.

All codes of RFC can be found at Rust Playground

I prefer the feature gate comparator_api.

Motivation

There are several ordered collections in std library, such as BTreeMap, BTreeSet, BinaryHeap.

While we want to customize the behaviour of the ordering in the collection, the only way is to add a wrapper type on top of original entry type, and implement Ord for them. The solution works in many scenarios (although tedious), but introduce heavy overhead while we need runtime generated comparator.

A typical usecase is database, while we compare two rows in database, the order depends on some runtime schemas and rules, e.g. ORDER BY (x ASC, y DESC, z ASC). We may introduce a dynamic rule struct OrderRule to represents the order.

struct Row {
    x: i32,
    y: i32,
    z: i32,
}
struct OrderRule {
    // true represents ASC, and false represents DESC
    x_is_asc: bool,
    y_is_asc: bool,
    z_is_asc: bool,
}

The only way to store Row in the current BTreeMap is that, create a wrapper type:

struct OrderedRow {
    inner: Row,
    rule: Rc<OrderRule>,
}
impl Ord for OrderedRow {
    fn cmp(&self, rhs: &self) -> Ordering {
        assert!(self.rule == other.rule);
        ...
    }
}

The implementation have two problems:

  1. We have to store extra 16 bytes for Rc in the entry, but the original Row is only 24 bytes, which significantly wastes the space.
  2. We have to assert self.rule == other.rule during run time, although we know they will be always equal.

In many other languages, we can define runtime comparator for ordered collections (of course, they also allow customization of < on entry type), e.g.:

The RFC want to introduce similar thing in rust.

Interface

We can introduce a new trait Comparator in std::cmp.

pub trait Comparator<T> {
    fn compare(&self, lhs: &T, rhs: &T) -> Ordering;
}

The most importent and required method is compare, which receives two items and returns Ordering, and the other methods are trivial.

For compatibility and usability, we also need to introduce a default implementation DefaultComparator:

// A default Comparator implementation, which call Ord directly.
pub struct DefaultComparator<T>(PhantomData<T>);
impl<T> Comparator<T> for DefaultComparator<T>
where
    T: Ord,
{
    fn compare(&self, lhs: &T, rhs: &T) -> Ordering {
        lhs.cmp(rhs)
    }
}

DefaultComparator is ZST, and call Ord::cmp directly, which means that it will not introduce any overhead, then we can add a generics argument for BTreeMap with default implementation:

pub struct BTreeMap<K, V, C = DefaultComparator<K>> {
    // If C is DefaultComparator, then c will be zero-sized.
    c: C,
    // TODO
    _phantom: PhantomData<(K, V)>,
}

impl<K, V, C> BTreeMap<K, V, C> {
    pub fn new_in_comparator(c: C) -> Self {
        Self {
            c,
            _phantom: PhantomData,
        }
    }

    pub fn method_without_order(&self) {
        todo!()
    }
}

impl<K, V, C> BTreeMap<K, V, C>
where
    C: Comparator<K>,
{
    pub fn method_with_order(&self) {
        let k1 = (todo!()) as K;
        let k2 = (todo!()) as K;
        self.c.compare(&k1, &k2);
    }
}

We omit allocator_api here, which is an unstable feature.

The BTreeMap keeps the original behaviour without any break changes:

  1. The default implementation is trivial and zero-overhead.
  2. We can still create a BTreeMap with K: !Ord, and calls a part of methods.

Use Case

We can handle the case above easily without any overhead, all we need to do is impl Comparator for OrderRule:

impl Comparator<Row> for OrderRule {
    fn compare(&self, lhs: &Row, rhs: &Row) -> Ordering {
        match (self.x_is_asc, lhs.x.cmp(&rhs.x)) {
            (true, Ordering::Less) | (false, Ordering::Greater) => Ordering::Less,
            (false, Ordering::Less) | (true, Ordering::Greater) => Ordering::Greater,
            (_, Ordering::Equal) => match (self.y_is_asc, lhs.y.cmp(&rhs.y)) {
                (true, Ordering::Less) | (false, Ordering::Greater) => Ordering::Less,
                (false, Ordering::Less) | (true, Ordering::Greater) => Ordering::Greater,
                (_, Ordering::Equal) => match (self.z_is_asc, lhs.z.cmp(&rhs.z)) {
                    (true, Ordering::Less) | (false, Ordering::Greater) => Ordering::Less,
                    (false, Ordering::Less) | (true, Ordering::Greater) => Ordering::Greater,
                    (_, Ordering::Equal) => Ordering::Equal,
                },
            },
        }
    }
}

We can use it easily:

fn f() {
    let rule = OrderRule {
        x_is_asc: true,
        y_is_asc: false,
        z_is_asc: true,
    };
    let map = BTreeMap::<Row, (), _>::new_in_comparator(rule);
    map.method_with_order();
}

Others

We can create some util methods to simplify the usage, but i prefer implementing them in other feature gates, so we can discuss the details later.

pub struct CompareFn<T, F> {
    inner: F,
    _phantom: PhantomData<T>,
}

impl<T, F> Comparator<T> for CompareFn<T, F>
where
    F: Fn(&T, &T) -> Ordering,
{
    fn compare(&self, lhs: &T, rhs: &T) -> Ordering {
        (self.inner)(lhs, rhs)
    }
}

pub fn compare_fn<T, F>(f: F) -> CompareFn<T, F>
where
    F: Fn(&T, &T) -> Ordering,
{
    CompareFn {
        inner: f,
        _phantom: PhantomData,
    }
}

fn f2() {
    BTreeMap::<i32, (), _>::new_in_comparator(compare_fn(|_x: &i32, _y: &i32| Ordering::Equal));
}

Alternatives

Some languages use key-based customization instead of compare-based one, e.g. Python key functions, which is easier to use in some scenarios, but the compare-based one is more generic.

I prefer to add key_fn and KeyFn impl Comparator, which are similar to compare_fn and CompareFn, and keep the compare-based core design.

TBD

  • compare or cmp?
  • The order of Comparator and Allocator, I prefer <K, V, C, A>
8 Likes

I think it makes more sense to have

pub trait Comparator<T> { ... }

instead of using assoc type.

This would allow a comparator to be used for multiple types, e.g.:

pub struct DefaultComparator;

impl<T> Comparator<T> for DefaultComparator { ... }

In your Row example is polymorphic, e.g. Row<A>, Row<B>, then you can use a single OrderRule instead of having OrderRule<A>, OrderRule<B>.

5 Likes

Just a minor note: you basically never want to use #[inline(always)], and even more never when calling back into unknown (trait) code.

It might look like #[inline(always)] fn foo() { bar() } is a good idea, to make calling foo() identical to calling bar(). Unfortunately, this intuition doesn't work; inlining happens bottom-up, so instead bar is inlined into foo, and then the inlined contents are forced to be inlined into the caller of foo, even if it would've normally called into bar rather than inline it.

There is probably space for a #[inline(shallow)] or similar which is a top-down inlining pass over MIR in rustc rather than an instruction to LLVM for cases like this, but for the time being, methods like this should be marked #[inline], and not #[inline(always)].

#[inline(always)] should basically be reserved for "it's already #[inline] and both micro- and macro-benchmarks show that #[inline(always)] is a notable improvement." And the LLVM inliner is pretty good, so that's not very often.

7 Likes

Is there a reason for the Comparator trait to define the helper functions beyond compare? If not, what advantage does using Comparator have over just for<'a> FnMut(&'a T, &'a T) -> Ordering?

Along those lines, should Comparator take &mut? If it has to work with shared access, why?

Even if Comparator is considered a useful trait to have, stdlib can (and I think should) implement the trait for closures with the comparing shape (rather than use a wrapper type), though probably not for all FnMut? (In the :unicorn: far future :unicorn: it will be possible to implement Fn traits for custom types.)

Thanks, I've updated my RFC, and remove the usage of assoc type.

I don't think the helper functions would be useful, but I don't think it should take FnMut, The fact that FnMut can't (yet) be directly implemented would hurt the usability. Also from my experience HRTB + closure often causes inference issues where closure is inferred with a early bound life-time.

1 Like

Is there a reason for the Comparator trait to define the helper functions beyond compare ? If not, what advantage does using Comparator have over just for<'a> FnMut(&'a T, &'a T) -> Ordering ?

  1. The helper functions are useful but not necessary, and we can remove them currently. But it seems that a Comparator trait is still better, we may extend them later for some specification. It seems that std::cmp::Ord also has several methods for customization.

Just for completeness, if it takes impl FnMut and you have an object with a compare method, you could use

new_with_compare(move |lhs, rhs| db.compare(lhs, rhs))

to adapt a named method to a closure.

I have removed the helper functions, but I kept the trait, Comparator may need some customizations at least consistent with Ord.

to adapt a named method to a closure.

How about impl Comparator for Fn(<&T, &T>) -> Ordering?

But at least, we can always have new_with_compare_fn(Fn<&T, &T> -> Ordering), and convert it to CompareFn internally.

Along those lines, should Comparator take &mut ? If it has to work with shared access, why?

  1. I'me not sure whether it's reasonable to take &mut. In most cases, to compare with deterministic result, it may only need &. If &mut was taken, it will make it impossible to share the same comparator instance between different collections.

This isn't true; the collection owns the impl Comparator by value. So if you wanted to share the same state between multiple collections, the comparator would have to hold &State itself, and Wrap(&State): Comparator.

But ultimately, owning a comparator is the wrong API. Because while this is a better case than having SortBy(T, impl FnMut), where every item has to have a copy of the maybe-not-zero-sized comparator, the multiple collections now still need to hold onto potentially redundant copies of/handles to the comparator.

For allocators, this is the right trade-off; collections need to dealloc on drop, so they need a handle for that, and it's very wrong to use a different allocator, so it'd have to be wildly unsafe to inject the allocator at use time anyway.

For comparators (or hashers, or...), though, these are "things the collection does," not "things the collection owns/has/needs-access-to-be".

HashMap is an interesting example, because it does have S: BuildHasher! (So maybe we should be having S: BuildComparator? How many abstraction layers is practical, and when does it become enterprise Java AbstractSingletonProxyFactoryBean?) But it also has the very useful and illustrative raw_entry API, which allows you to [completely bypass] to completely bypass all of the requirements of K: Hash + Eq, S: BuildHasher and inject what the map actually needs to work. This is practically useful when storing custom handle types in a map, such as interned strings.

BuildHasher is important because T: Hash is the "what data to hash, and H: Hasheris "how to hash the data;" these are separate concerns.raw_entry` for hashmaps allows you to replace one, the other, or both.

Ultimately, I think the analogous improvement to ordered collections is to add their own raw_entry APIs that provide for injection for comparison, rather than adding a comparison factory.


(But if a comparison factory were to exist, I agree that the order should be BTreeMap<K, V, S = DefaultComparator, A = GlobalAlloc> to match the order of HashMap<K, V, S = DefaultBuildHasher, A = GlobalAlloc>. And impl<T: Ord> Comparator<T> for DefaultComparator, of course. Unfortunately, I have a strong suspicion that this would significantly regress compile error quality for ordered collections, as common methods would now be DefaultComparator: Comparator<T>, not T: Ord, so the error would point at the first prior obligation, not the latter, which the user can and should be providing. And IIRC has a special error to mention "can be compared" in addition to the trait bound.)

1 Like

Ultimately, I think the analogous improvement to ordered collections is to add their own raw_entry APIs that provide for injection for comparison, rather than adding a comparison factory.

As commented in the raw_entry API tracking issue, it is considered a poor API and has been rejected, because it is trying to do too much at once. It is trying to serve two different types of use cases (high level cases & low level cases).

The comparator-api is a relatively high-level use case, so a more ergonomical API is preferable than low-level access. Just like switching a hash algorithm should not require low-level access.

But ultimately, owning a comparator is the wrong API.

I think the overhead of owning a comparator for each collection is accepetable, and a giant improvement compared with a comparator for each item. But as for the flavor of the API, I don't have a strong opinion.

Given that default comparator is ZST and has no runtime penalties, I won't say owning a comparator is wrong.

It makes the standard collections more extensible in a "only pay for what you use" way, and has practical use cases, so I'm in favor of it.

As of whether to use a comparator factory or comparator instance, I prefer the former because it's more ergonomic, while also being fine with the latter.

2 Likes

Out of curiosity, I read the tracking issue for custom hashers, and I found people strive to avoid naming it "factory" to avoid java-isms, but the factory pattern seems unavoidable due to the internal complexities of hashing (stream, seed, ...). The comparator case is simple enough to use a single comparator trait without factory.

The distinction between Hash (for data) and Hasher (for algorithm) is more important, but I guess in the case of comparators, marking data comparable without specifying how to compare is less meaningful.

1 Like

I'm not sure whether it's reasonable to have BuildComparator. A Hasher is always mutable and we must create a new Hasher for every different key, so it's unavoidable for HashMap to own a "Hasher Factory" instead of Hasher itself, but it seems that there is no benefit for BuildComparator.

1 Like

In the prior arts you could mention:

  • the binary-heap-plus crate, which pretty much implements the API you're proposing for BinaryHeap;
  • raw_entry, and in particular from_hash, which tries to solve a similar problem for HashMap/HashSet by delegating the hashing and equality to the user for each call.
  • hashbrown::raw::RawTable which is a similar approach to raw_entry but moved in its own type.

Searching in a collection (e.g. a BTreeMap) takes &self so the collection needs shared access to the Comparator if we want to allow bundling them together.

5 Likes

Wow, the binary-heap-plus crate is interesting, it does almost the same as this pre-RFC, although its motivation is just for flexibility, without considering the runtime generated comparator problem here.

I found its pre-RFC, closed for inactivity. Maybe we can learn from the discussions and propose an official RFC this time! :grinning_face_with_smiling_eyes: (cc @sekineh

1 Like

When mentioning java-ism :grin: here comes the name bikeshedding: I guess that Compare would be a better name than Comparator. Anyway, I support the proposal as I think it would be really nice to have a way to compare items in collections without wrapper types.

1 Like

Why just Comparator?

Would this not also imply that we should have Hashor and Equalitor as well?

And do we need Partial* versions of them as well?

3 Likes