パズルピースのマッチングと期待外れのベンチマーク

パズルピースのマッチングと期待外れのベンチマーク 2026年3月20日 最近、テキストをソートするために`.to_lowercase()`を使用するコードがありました。これはいくらかのメモリを消費します。良い点としては、そのコードは`.sort_by_cached_key`を使用しており、これはかなりクールです。しかし、多くの文字列で最初の数文字が異なる場合、各エントリに対してStringを割り当てるよりも、`log(n)`回`.to_lowercase()`を行う方が遅くなるのではないかと思いました。 まず、Rustで2つの`&str`を大文字・小文字を区別せずに比較することは可能ですが、少し複雑です。ここでの解決策は、すべての文字をイテレートし、`char::to_lowercase`を呼び出すことです。これは別の文字のイテレータを返します（一部の文字は小文字で複数の文字に対応するため）、それを`flat_map`できます。パズルの2番目のピースは、Iteratorが`cmp`メソッドを持っているが、冪等ではないため`Ord`を実装していないことです。`cmp`を呼び出すと、イテレータは枯渇します。それでも、`sort_by`を使用すれば、小文字変換と比較をインターリーブできます。念のため、ベンチマークに`unicase`クレートも追加しました。 好奇心旺盛な私は、自然とベンチマークを作成しました。これは、ここに再現するのに十分短いものです（興味がない場合は、結論までスクロールしてください）： use fake::faker::name::raw::Name; use fake::{locales::EN, Fake}; fn setup(num: usize) -> Vec<String> { (0..num).map(|_| Name(EN).fake()).collect::<Vec<String>>() } #[divan::bench(args = [1, 5, 10, 100, 1000, 10000])] fn sort_by_cached_lowercase(bencher: divan::Bencher, size: usize) { let names = setup(size); bencher.counter(size).bench_local(|| { let mut sorted = names.clone(); sorted.sort_by_cached_key(|name| name.to_lowercase()); sorted }) } #[divan::bench(args = [1, 5, 10, 100, 1000, 10000])] fn sort_by_iter_lowercase(bencher: divan::Bencher, size: usize) { let names = setup(size); bencher.counter(size).bench_local(|| { let mut sorted = names.clone(); fn caseless(s: &String) -> impl Iterator<Item = char> + '_ { s.chars().flat_map(char::to_lowercase) } sorted.sort_by(|s1, s2| caseless(s1).cmp(caseless(s2))); sorted }) } #[divan::bench(args = [1, 5, 10, 100, 1000, 10000])] fn sort_by_unicase(bencher: divan::Bencher, size: usize) { let names = setup(size); bencher.counter(size).bench_local(|| { let mut sorted = names.clone(); sorted.sort_by(|s1, s2| unicase::UniCase::new(s1).cmp(&unicase::UniCase::new(s2))); sorted }) } fn main() { // Run registered benchmarks. divan::main(); } 私のM2-MAX MacBook Proでの結果： Timer precision: 41 ns low fastest │ slowest │ median │ mean │ samples │ iters ├─ sort_by_cached_lowercase │ │ │ │ │ │ ├─ 1 16.68 ns │ 18.14 ns │ 17.49 ns │ 17.49 ns │ 100 │ 25600 │ │ 59.94 Mitem/s │ 55.1 Mitem/s │ 57.15 Mitem/s │ 57.15 Mitem/s │ │ │ ├─ 5 212.9 ns │ 265 ns │ 215.5 ns │ 219.2 ns │ 100 │ 3200 │ │ 23.47 Mitem/s │ 18.86 Mitem/s │ 23.19 Mitem/s │ 22.8 Mitem/s │ │ │ ├─ 10 452.5 ns │ 567.1 ns │ 457.7 ns │ 462.2 ns │ 100 │ 1600 │ │ 22.09 Mitem/s │ 17.63 Mitem/s │ 21.84 Mitem/s │ 21.63 Mitem/s │ │ │ ├─ 100 5.207 µs │ 11.33 µs │ 5.291 µs │ 5.455 µs │ 100 │ 100 │ │ 19.2 Mitem/s │ 8.824 Mitem/s │ 18.89 Mitem/s │ 18.32 Mitem/s │ │ │ ├─ 1000 73.62 µs │ 110.9 µs │ 75.99 µs │ 78.89 µs │ 100 │ 100 │ │ 13.58 Mitem/s │ 9.009 Mitem/s │ 13.15 Mitem/s │ 12.67 Mitem/s │ │ │ ╰─ 10000 853.7 µs │ 1.053 ms │ 864.8 µs │ 886.3 µs │ 100 │ 100 │ 11.71 Mitem/s │ 9.495 Mitem/s │ 11.56 Mitem/s │ 11.28 Mitem/s │ │ │ ├─ sort_by_iter_lowercase │ │ │ │ │ │ ├─ 1 13.91 ns │ 23.35 ns │ 14.89 ns │ 15.68 ns │ 100 │ 25600 │ │ 71.87 Mitem/s │ 42.81 Mitem/s │ 67.15 Mitem/s │ 63.76 Mitem/s │ │ │ ├─ 5 134.8 ns │ 196 ns │ 137.4 ns │ 148.6 ns │ 100 │ 3200 │ │ 37.08 Mitem/s │ 25.5 Mitem/s │ 36.37 Mitem/s │ 33.64 Mitem/s │ │ │ ├─ 10 442.1 ns │ 1.03 µs │ 483.8 ns │ 519.1 ns │ 100 │ 800 │ │ 22.61 Mitem/s │ 9.702 Mitem/s │ 20.66 Mitem/s │ 19.26 Mitem/s │ │ │ ├─ 100 17.33 µs │ 34.12 µs │ 18.16 µs │ 19.66 µs │ 100 │ 100 │ │ 5.769 Mitem/s │ 2.93 Mitem/s │ 5.504 Mitem/s │ 5.086 Mitem/s │ │ │ ├─ 1000 337.6 µs │ 433 µs │ 352.1 µs │ 355.4 µs │ 100 │ 100 │ │ 2.961 Mitem/s │ 2.309 Mitem/s │ 2.839 Mitem/s │ 2.813 Mitem/s │ │ │ ╰─ 10000 5.543 ms │ 6.579 ms │ 5.572 ms │ 5.602 ms │ 100 │ 100 │ 1.803 Mitem/s │ 1.519 Mitem/s │ 1.794 Mitem/s │ 1.784 Mitem/s │ │ │ ╰─ sort_by_unicase │ │ │ │ │ ├─ 1 15.05 ns │ 22.05 ns │ 15.87 ns │ 16.78 ns │ 100 │ 25600 │ 66.42 Mitem/s │ 45.34 Mitem/s │ 63 Mitem/s │ 59.59 Mitem/s │ │ │ ├─ 5 86.66 ns │ 125 ns │ 91.86 ns │ 97.79 ns │ 100 │ 6400 │ 57.69 Mitem/s │ 39.97 Mitem/s │ 54.42 Mitem/s │ 51.12 Mitem/s │ │ │ ├─ 10 202.5 ns │ 470.8 ns │ 207.7 ns │ 230.9 ns │ 100 │ 1600 │ 49.36 Mitem/s │ 21.24 Mitem/s │ 48.13 Mitem/s │ 43.3 Mitem/s │ │ │ ├─ 100 4.749 µs │ 18.33 µs │ 4.833 µs │ 5.201 µs │ 100 │ 100 │ 21.05 Mitem/s │ 5.454 Mitem/s │ 20.68 Mitem/s │ 19.22 Mitem/s │ │ │ ├─ 1000 107.2 µs │ 158 µs │ 107.5 µs │ 111.4 µs │ 100 │ 100 │ 9.327 Mitem/s │ 6.325 Mitem/s │ 9.298 Mitem/s │ 8.973 Mitem/s │ │ │ ╰─ 10000 1.753 ms │ 1.919 ms │ 1.757 ms │ 1.772 ms │ 100 │ 100 │ 5.702 Mitem/s │ 5.208 Mitem/s │ 5.688 Mitem/s │ 5.641 Mitem/s │ │ │ したがって、要素が1つだけの場合（これは自明なケースです）を除き、`sort_by_cached_key`は価値があり、UTF-8文字をイテレートして大文字変換を行うことは、割り当てを必要としないという利点を打ち消すほど遅いことがわかりました。本当の驚きは、比較をより複雑にしているにもかかわらず、Unicaseがしばしばより高速になる可能性があるということです。