Rust: Tracking issue for sorting by expensive-to-compute keys (feature slice_sort_by_cached_key)

[dato]

Hi—

Ideally, the implementation of sort_by_key() would invoke the received key function exactly once per item. This is highly beneficial when a costly computation (e.g., a distance function) needs to be used for sorting.

But Rust’s implementation as of 1.9 (link) calls the key function each time:

 pub fn sort_by_key(&mut self, mut f: F)
{
    self.sort_by(|a, b| f(a).cmp(&f(b)))
}

For comparison, on its day Python highlighted this in the release notes for 2.4. As per their current Sorting HOW TO:

The value of the _key_ parameter should be a function that takes a single argument and returns a key to use for sorting purposes. This technique is fast because the key function is called exactly once for each input record.

Many thanks for considering. It’d be great if Rust could behave the same way.

[Thiez]

I suspect the method works this way to avoid allocation. Most people would expect this method not to allocate, and to sort in place. If you want to calculate keys only once, perhaps you could introduce some kind of caching inside f. This should be possible because sort_by_key takes a FnMut.

[hanna-kruppe]

@Thiez [T]::sort_by uses merge sort and thus already allocates.

[Thiez]

I stand corrected :-)

[ExpHP]

I imagine that the current method may still be more optimal for simple key functions like |obj| obj.some_member which lend themselves well to further optimization.

This is a marked difference from Python's case, where even the simplest key function still has overhead (making a Schwartzian transform-style sort the clear winner).

[DemiMarie]

I think @ExpHP is correct: CPython's string sort, which is written in C, is much faster than any key function written in Python. Note that this is not necessarily true for PyPy (which has a JIT), and is definitely not true in Rust.

[arthurprs]

The lambda is just passed down as a comparator, you'd be surprised by how much the optimizer can do with that. The name is misleading but this is not the key argument python in python sort(ed) this would actually be the cmp argument

The behavior you suggest has it's uses but it's probably something that belong to an external crate.

[ExpHP]

The name is misleading but this is not the key argument python in python sort(ed) this would actually be the cmp argument

To play devil's advocate a bit, this is not entirely a fair assessment; rust already provides the capability of cmp via sort_by. So to me it does not seem unreasonable for some to expect that sort_by_key might be more than just a convenience method.

Actually, for that reason, _I was surprised to learn that a sort_by_key method had been added in the first place!_ As somebody coming from Python, prior to 1.7.0 I was always frustrated by having to write things like |a,b| a.member.cmp(&b.member), and often dearly wished for a convenience method like the sort_by_key that exists today.

Then one day while converting some Python code I came across a sort with an expensive key method, and suddenly _it all made sense._ There are two different idioms to sorting a list by a key, each suited to different use cases. At the time, I concluded that this must have been the reason why rust had no sort_by_key.

[varkor]

There now exists an unstable method, sort_by_cached_key that achieves this purpose. A new method was added to make sure performance was never sacrificed. Essentially,sort_by_cached_key should be more efficient on anything but extremely simple key functions (e.g. property accesses).

Note that, when this is stabilised, we should add a clippy lint to suggest using this method over sort_by_key in appropriate circumstances, if possible.

[scottmcm]

Reopening as the unstable tag on the method is pointing here as a tracking issue (https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.sort_by_cached_key).

[varkor]

If/when this is stabilised, it is worth considering whether adding is_sorted_by_cached_key would be a good idea, if sort_by_key is: https://github.com/rust-lang/rust/issues/53485.

[varkor]

Also partition_dedup_by_cached_key (https://github.com/rust-lang/rust/issues/54279), though this might be a bit niche.

[stjepang]

@varkor Can't we just cache the key for the last visited element in is_sorted_by_key and the last unique element in partition_dedup_by_key?

[varkor]

Yes, there's so little key recalculation in the two methods that there's probably no need for specific cached methods. I'll admit I hadn't thought too much about them when I referenced them here: I was just making a quick note to remind myself later! You're right, though!

[Kerollmops]

partition_dedup_by_cached_key could make the difference when you have extensive key computation. For example you will have to compute for 100 elements that are the same 200 times the same keys and only 101 times for the cached version, according to the current algorithm which computes the first key two times.

There is something we must be careful with, the current function that is used by partition_dedup_by_key is FnMut(&mut T) -> K. We must be sure that the user know that the function will only be called once on the last unique element. Or we can use another function signature that doesn't let the user change the value.

[lcnr]

Should we add sort_unstable_by_cached_key as well?

[scottmcm]

@lcnr sort_unstable is in libcore because it doesn't use additional memory, but _by_cached_key needs additional memory, so if you need cached keys you're probably fine with stable sort.

[varkor]

In addition, the stability of the current sort_by_cached_key is a side-effect of the implementation. It's unclear to me how you would implement an unstable version that had any benefits over the stable version.

[lcnr]

@varkor I would add an unstable version that currently has no benefit over the stable version for the sake of completeness/to express intent. If someone does not need the stability of sort_by_cached_key, he could use sort_unstable_by_cached_key instead, even if the function is implemented like this:

#[inline(always)]
pub fn sort_unstable_by_cached_key<K, F>(&mut self, f: F)
    where F: FnMut(&T) -> K, K: Ord
{
    self.sort_by_cached_key(f)
}

In case we are able to think of a slightly faster unstable version in the far distant future, there would be no need to check every single invocation of sort_by_cached_key to check if the stability is actually needed.

[scottmcm]

And it's in! Anyone want to update https://en.wikipedia.org/wiki/Schwartzian_transform#Comparison_to_other_languages? :smirk: