Rust benchmark: cached lowercase keys beat iterator sort, unicase close

A Rust developer benchmarked three ways to sort a Vec case insensitively, after noticing their code used sort_by_cached_key together with .to_lowercase() and wondering whether that beat a plain iterator based comparison. The three approaches tested were: sort_by_cached_key with .to_lowercase() (allocates one lowercased String per element up front), sort_by comparing char::to_lowercase() iterators directly on each comparison (no allocation, but repeated conversion work), and sort_by using the unicase crate's UniCase wrapper. Getting the iterator version to compile required a workaround: Iterator has a cmp method but does not implement Ord, because calling cmp exhausts the iterator, so the comparison has to interleave lowercase conversion with the sort_by call rather than using a simpler cached-key style API. The benchmark used the divan crate (41 ns timer precision) on an M2-MAX MacBook Pro, generating fake English names with the fake crate and sorting lists of 1, 5, 10, 100, 1000 and 10000 names, with 100 samples per case. Results varied by list size. At the smallest sizes, the plain iterator comparison and unicase both beat the cached key approach: at 5 elements, median times were 215.5 ns for cached key, 137.4 ns for the iterator comparison, and 91.86 ns for unicase, meaning unicase was roughly 2.3 times faster than the cached key version. That pattern reversed as the lists grew. At 100 elements, cached key (5.291 microseconds) and unicase (4.833 microseconds) were close, with the plain iterator comparison well behind at 18.16 microseconds. At 10000 elements the gap widened sharply: median times were 864.8 microseconds for the cached key approach, 1.757 milliseconds for unicase, and 5.572 milliseconds for the plain iterator comparison, making the iterator version about 6.4 times slower than caching the key. The author's stated conclusion is that unless a list has only one element, the trivial case, sort_by_cached_key is worth the up front allocation, and that iterating over UTF-8 characters to do case conversion turned out a lot slower than expected, which erases the benefit of avoiding that allocation. The author calls it a real surprise that the unicase crate can often be faster despite making the comparison itself more complex, without offering an explanation for why.

Key facts

The benchmark compares three case insensitive sort strategies for Vec in Rust: sort_by_cached_key with .to_lowercase(), sort_by comparing char::to_lowercase() iterators directly, and sort_by using the unicase crate, across list sizes from 1 to 10000, using divan on an M2-MAX MacBook Pro.
At 10000 elements, median sort times were 864.8 microseconds for the cached lowercase key, 1.757 milliseconds for unicase, and 5.572 milliseconds for the plain iterator comparison, making the iterator approach about 6.4 times slower than the cached key.
At small sizes the ranking flips: at 5 elements, unicase (91.86 ns) and the plain iterator comparison (137.4 ns) both beat the cached key approach (215.5 ns), with unicase about 2.3 times faster than caching the key.
The author's takeaway is that sort_by_cached_key is worth it unless sorting only a single element, and that character by character lowercase conversion is far slower than expected, which cancels out the benefit of not allocating.
Rust's Iterator type has a cmp method but does not implement Ord because calling cmp exhausts the iterator, which is why the iterator based comparison has to interleave lowercase conversion with sort_by rather than use a cached-key style call.

Why it matters

Case insensitive sorting is a routine task, and it is easy to assume that avoiding an allocation (comparing on the fly) will always beat allocating a lowercased copy of every string up front. This benchmark shows that assumption is wrong for anything beyond a handful of elements: iterating over Unicode characters to lowercase them on every comparison scales badly, because a sort makes far more than one comparison per element as the list grows.

Who it affects

Rust developers who sort user-facing text such as names, filenames or tags and need the sort to ignore letter case. It also matters to anyone choosing between rolling a manual Unicode-aware comparison and pulling in a small crate like unicase for the same job.

How to use it

For lists past a few dozen items, sort_by_cached_key with .to_lowercase() is the safer default: it allocates one lowercased String per element up front but avoids repeating the conversion on every comparison. The unicase crate is a close, sometimes faster, alternative that needs no manual key extraction and does not require the cached-key workaround for Iterator's lack of Ord. A plain iterator based comparison written by hand is only competitive at very small list sizes, around five elements or fewer in this benchmark.

How solid is it

This is a single informal benchmark run on one machine, an M2-MAX MacBook Pro, using the divan benchmarking crate with 100 samples per case and synthetic English names generated by the fake crate, across sizes from 1 to 10000. It is a real, reproducible measurement with code included, but it reflects one hardware target and one kind of input string rather than a broad, peer-reviewed study.

Risks and caveats

The results come from one machine and one input shape (short English names); behavior could differ on other hardware, with longer strings, or with non-Latin scripts where case folding is more complex. The author offers no explanation for why unicase often beats the hand-rolled cached-key approach despite a more complex comparison, so that finding is reported without a settled cause. No version numbers are given for the divan, fake, or unicase crates used, and no date is given for when the benchmark was run.

“unless you only have one element (which is the trivial case), sort_by_cached_key is worth it”

— the blog's author