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

パズルのピースを合わせるのと期待外れのベンチマーク

2026年3月20日

最近、あるコードでテキストをソートするために.to_lowercase()を使用していました。これはいくらかのメモリを消費します。良い点としては、そのコードは pretty cool な .sort_by_cached_key を使用していました。しかし、多くの文字列で最初の数文字が異なっている場合、.to_lowercase()をn回行うことが、エントリごとにStringを割り当てるよりも遅くなるのではないか、と疑問に思いました。

まず、Rustで2つの&strを大文字・小文字を区別せずに比較することは、少し複雑ですが可能です。ここでは、すべてのcharをイテレートし、それぞれにchar::to_lowercaseを呼び出すという方法があります。これは別のcharのイテレータを返すため（一部の文字は小文字で複数の文字に対応することがあるため）、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がしばしばより高速であるということです。