📝

奥深いstr::to_lowercaseの世界

2024/12/16に公開

Rust

この記事はとあるサークルのOB/OGが行っているN代アドベントカレンダー2024の16日目です。

はじめに

突然ですが、以下の2つの関数、どちらの方が実行に時間がかかるでしょうか？
理由も含めて答えられますか？
コードブロックのすぐ下から解答・解説が始まるのでスクロールに気をつけて考えてみてください。

const LOREM1: &str = r#"  Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla sit amet leo libero. Morbi tortor lorem, porta at imperdiet ac, bibendum sit amet dui. Vestibulum condimentum mi nec nisi scelerisque, a feugiat justo mollis. Nulla pulvinar purus eget sapien tincidunt faucibus. Nunc in dui finibus nisi blandit ultricies eget ac purus. Morbi venenatis id lectus nec venenatis. Fusce tempus nulla arcu, sit amet imperdiet nulla cursus pellentesque. Aenean sit amet sodales ligula, et bibendum nibh. Pellentesque ullamcorper, mauris nec lacinia egestas, libero lectus semper nisi, eu ornare libero quam vitae augue.
Sed pellentesque pretium accumsan. Fusce tempor quam eget urna elementum ultricies. Nullam nec fringilla felis. Duis at laoreet dolor. Donec tristique, velit at scelerisque commodo, sapien neque viverra nibh, eu viverra nisl tortor vitae risus. Ut interdum ullamcorper neque sed tincidunt. Proin pretium nibh a magna sodales, et iaculis velit posuere. Proin mi diam, pretium eget hendrerit vitae, feugiat in libero. Ut et suscipit nulla, non blandit urna. Cras sit amet nunc magna. Vivamus pellentesque ligula sapien, ut varius risus scelerisque id. Ut magna enim, bibendum eu sem ut, commodo porta orci.
Pellentesque nec est dictum, accumsan enim nec, consectetur sem. Nullam maximus id justo non finibus. Nulla nunc est, scelerisque eget faucibus egestas, dictum vitae purus. Nulla ex magna, suscipit tempus arcu a, ullamcorper consectetur justo. Nam quis gravida sapien, vel posuere lectus. Vivamus semper efficitur felis, non tincidunt nunc lobortis vel. Suspendisse vulputate dui volutpat, ornare ipsum in, vehicula odio. Duis mi mauris, auctor vel turpis eget, ullamcorper aliquet lectus. Pellentesque consequat, leo volutpat scelerisque fringilla, justo ex molestie justo, vitae consectetur sapien leo quis purus. Suspendisse potenti. Curabitur ac sodales ligula. In egestas lorem erat, a molestie nisl laoreet id. Nulla et commodo nulla. Nullam vulputate sed lectus vel fringilla.
Integer fringilla sapien tincidunt lacinia fermentum. Phasellus vel enim lacus. Vivamus suscipit ante tortor, a aliquet nisl varius non. Praesent scelerisque, leo et ultricies volutpat, dolor turpis pretium urna, nec vestibulum orci nisi id ante. Vestibulum fringilla porttitor pharetra. In elementum lectus id laoreet varius. Cras in aliquam massa. Aenean ac augue nibh. Cras finibus dictum commodo. Suspendisse a lobortis libero, vel fringilla sem.
Nam tempus tellus vel venenatis tempus. Integer non augue condimentum, ultrices risus vel, cursus ex. Nulla sit amet tortor nunc. Nullam metus eros, aliquet ut mi molestie, rutrum tempus turpis. Cras accumsan eleifend odio vitae dapibus. Nunc accumsan, arcu et scelerisque interdum, ligula augue consequat felis, eu porttitor quam ex id ante. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Mauris in leo ac lectus laoreet dapibus.
Ut mollis est et mi tempor gravida. Aenean quis nisl congue, blandit dolor eget, efficitur ante. Fusce finibus lorem vitae egestas feugiat. In arcu ligula, volutpat vel pretium non, tincidunt nec dui. Suspendisse laoreet hendrerit mauris non tempus. Pellentesque non fermentum erat. Donec volutpat magna a placerat semper. Nunc mauris odio, vulputate sed metus sed, iaculis suscipit nisi. Etiam elementum luctus rutrum. Nullam consectetur justo ut tortor venenatis ullamcorper. Duis ornare in diam sit amet auctor. Nullam egestas velit velit. Sed ut scelerisque risus. Fusce non aliquam ipsum, eu ultricies odio. Sed egestas orci a pellentesque dictum. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos.
Praesent nec suscipit risus. Quisque odio urna, viverra a lacinia non, ullamcorper eu purus. Interdum et malesuada fames ac ante ipsum primis in faucibus. Ut porta elit eget tristique finibus. Morbi pellentesque, urna quis molestie luctus, dolor ante volutpat arcu, at pulvinar justo nisi sit amet lacus. Ut tincidunt justo eu purus placerat tristique. Nunc convallis posuere iaculis. Pellentesque pulvinar, eros vitae elementum mollis, ligula enim imperdiet mi, et mattis orci quam quis massa. Maecenas non turpis at ante ornare semper. Duis pellentesque dolor quis ex lacinia, sed maximus purus facilisis. Praesent vitae euismod massa. Proin efficitur condimentum lorem, eu lobortis risus consequat sit amet. Morbi in luctus tortor. Duis sodales ac justo tincidunt placerat. Phasellus quis nisl vel neque convallis lacinia eu eu augue. Nam blandit ac lorem nec gravida.
Sed malesuada varius turpis, et hendrerit nunc facilisis id. Integer finibus finibus tortor quis eleifend. Sed nunc est, auctor vitae viverra volutpat, sagittis non quam. Sed ac pharetra lorem. Proin commodo sagittis nulla, eget rhoncus nulla iaculis eu. Ut sit amet molestie eros, sed porttitor leo. Phasellus id ante lacus. Aenean porttitor mattis augue ut dignissim. Nunc sapien ante, pulvinar a lorem eget, dapibus lobortis ante. Nulla facilisi.
Fusce vel nibh tellus. Sed at semper leo. Fusce aliquet tellus ante, et laoreet massa hendrerit at. Mauris vitae quam facilisis, vulputate quam id, consequat felis. Nam urna ex, laoreet vel ligula eget, sollicitudin imperdiet augue. Nam nisl purus, pulvinar id porttitor ut, bibendum et neque. Nulla a felis consequat, iaculis sem vel, auctor sem. Duis nec facilisis erat. Integer consectetur velit in hendrerit vestibulum. Sed tristique neque bibendum tortor tincidunt, eu venenatis turpis sollicitudin. Aliquam at nisi mollis, convallis lorem eu, sollicitudin arcu. Vivamus in commodo elit, in hendrerit urna. Curabitur sollicitudin lorem mi, non commodo risus rhoncus vitae. Fusce quis condimentum sapien. Suspendisse accumsan vulputate mauris sit amet molestie. Aenean aliquet ante dignissim tortor blandit blandit.
Nam hendrerit elementum velit lobortis laoreet. Duis fringilla, dolor nec congue cursus, eros magna venenatis mauris, et rutrum dui tortor et leo. Nam aliquam luctus augue, auctor porttitor sem vulputate id. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia curae; Donec a ex hendrerit mi ultrices convallis ac quis lectus. Donec ac mauris non libero suscipit imperdiet et vitae nibh. Pellentesque a neque ut enim consequat volutpat non et erat. Maecenas vel velit tincidunt, tincidunt ex eget, condimentum ex. Donec pulvinar mi ipsum, sit amet viverra justo imperdiet sit amet. Morbi dolor lectus, consectetur id feugiat a, feugiat a mi. Ut varius quam ac dolor dictum, ut congue lorem semper.
Integer sit amet bibendum est. Integer fringilla vulputate justo sed consectetur. Morbi lorem arcu, lacinia ut sem vestibulum, eleifend aliquet nisi. Sed id vehicula urna, in ultrices erat. Curabitur vitae eros orci. Donec eu.
"#;

const LOREM2: &str = r#"　Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla sit amet leo libero. Morbi tortor lorem, porta at imperdiet ac, bibendum sit amet dui. Vestibulum condimentum mi nec nisi scelerisque, a feugiat justo mollis. Nulla pulvinar purus eget sapien tincidunt faucibus. Nunc in dui finibus nisi blandit ultricies eget ac purus. Morbi venenatis id lectus nec venenatis. Fusce tempus nulla arcu, sit amet imperdiet nulla cursus pellentesque. Aenean sit amet sodales ligula, et bibendum nibh. Pellentesque ullamcorper, mauris nec lacinia egestas, libero lectus semper nisi, eu ornare libero quam vitae augue.
Sed pellentesque pretium accumsan. Fusce tempor quam eget urna elementum ultricies. Nullam nec fringilla felis. Duis at laoreet dolor. Donec tristique, velit at scelerisque commodo, sapien neque viverra nibh, eu viverra nisl tortor vitae risus. Ut interdum ullamcorper neque sed tincidunt. Proin pretium nibh a magna sodales, et iaculis velit posuere. Proin mi diam, pretium eget hendrerit vitae, feugiat in libero. Ut et suscipit nulla, non blandit urna. Cras sit amet nunc magna. Vivamus pellentesque ligula sapien, ut varius risus scelerisque id. Ut magna enim, bibendum eu sem ut, commodo porta orci.
"#;

pub fn lorem1() -> String {
    LOREM1.to_lowercase()
}

pub fn lorem2() -> String {
    LOREM2.to_lowercase()
}

解答・解説

ぱっと見では

文字数の多いlorem1の方が時間がかかる説
コンパイラ最適化のもとではどちらもほぼ変わらず、差があっても統計誤差で説明できる説

などが思いつくかもしれません。
しかし、lorem2の方が明らかに時間がかかります。実はLOREM1の先頭は半角スペース2つ、LOREM2の先頭は全角スペース（U+3000）1つという違いがありました。それ以外はどちらも全てごく普通のASCII文字で構成されています。
そして、Rustのstr::to_lowercaseは「先頭から見ていって非ASCII文字に出会うまではASCII文字のみに対応した効率的な変換を行い、それ以降は全文字種に対応した変換方法を用いる」というような挙動をします（詳細は後述）。この差の影響が文字数の影響よりも大きかったため、lorem2の方が時間がかかります。

Rustのベンチマーク用クレートcriterionで確認した結果を以下に示します。

ソースコード

コンパイラ最適化を明示的に阻害するblack_box関数もありますが、今回のケースではblack_box関数を用いても用いなくても結果はほぼ同じです。

benches/benchmark.rs

use criterion::{criterion_group, criterion_main, Criterion};

const LOREM1: &str = r#"  Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla sit amet leo libero. Morbi tortor lorem, porta at imperdiet ac, bibendum sit amet dui. Vestibulum condimentum mi nec nisi scelerisque, a feugiat justo mollis. Nulla pulvinar purus eget sapien tincidunt faucibus. Nunc in dui finibus nisi blandit ultricies eget ac purus. Morbi venenatis id lectus nec venenatis. Fusce tempus nulla arcu, sit amet imperdiet nulla cursus pellentesque. Aenean sit amet sodales ligula, et bibendum nibh. Pellentesque ullamcorper, mauris nec lacinia egestas, libero lectus semper nisi, eu ornare libero quam vitae augue.
Sed pellentesque pretium accumsan. Fusce tempor quam eget urna elementum ultricies. Nullam nec fringilla felis. Duis at laoreet dolor. Donec tristique, velit at scelerisque commodo, sapien neque viverra nibh, eu viverra nisl tortor vitae risus. Ut interdum ullamcorper neque sed tincidunt. Proin pretium nibh a magna sodales, et iaculis velit posuere. Proin mi diam, pretium eget hendrerit vitae, feugiat in libero. Ut et suscipit nulla, non blandit urna. Cras sit amet nunc magna. Vivamus pellentesque ligula sapien, ut varius risus scelerisque id. Ut magna enim, bibendum eu sem ut, commodo porta orci.
Pellentesque nec est dictum, accumsan enim nec, consectetur sem. Nullam maximus id justo non finibus. Nulla nunc est, scelerisque eget faucibus egestas, dictum vitae purus. Nulla ex magna, suscipit tempus arcu a, ullamcorper consectetur justo. Nam quis gravida sapien, vel posuere lectus. Vivamus semper efficitur felis, non tincidunt nunc lobortis vel. Suspendisse vulputate dui volutpat, ornare ipsum in, vehicula odio. Duis mi mauris, auctor vel turpis eget, ullamcorper aliquet lectus. Pellentesque consequat, leo volutpat scelerisque fringilla, justo ex molestie justo, vitae consectetur sapien leo quis purus. Suspendisse potenti. Curabitur ac sodales ligula. In egestas lorem erat, a molestie nisl laoreet id. Nulla et commodo nulla. Nullam vulputate sed lectus vel fringilla.
Integer fringilla sapien tincidunt lacinia fermentum. Phasellus vel enim lacus. Vivamus suscipit ante tortor, a aliquet nisl varius non. Praesent scelerisque, leo et ultricies volutpat, dolor turpis pretium urna, nec vestibulum orci nisi id ante. Vestibulum fringilla porttitor pharetra. In elementum lectus id laoreet varius. Cras in aliquam massa. Aenean ac augue nibh. Cras finibus dictum commodo. Suspendisse a lobortis libero, vel fringilla sem.
Nam tempus tellus vel venenatis tempus. Integer non augue condimentum, ultrices risus vel, cursus ex. Nulla sit amet tortor nunc. Nullam metus eros, aliquet ut mi molestie, rutrum tempus turpis. Cras accumsan eleifend odio vitae dapibus. Nunc accumsan, arcu et scelerisque interdum, ligula augue consequat felis, eu porttitor quam ex id ante. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Mauris in leo ac lectus laoreet dapibus.
Ut mollis est et mi tempor gravida. Aenean quis nisl congue, blandit dolor eget, efficitur ante. Fusce finibus lorem vitae egestas feugiat. In arcu ligula, volutpat vel pretium non, tincidunt nec dui. Suspendisse laoreet hendrerit mauris non tempus. Pellentesque non fermentum erat. Donec volutpat magna a placerat semper. Nunc mauris odio, vulputate sed metus sed, iaculis suscipit nisi. Etiam elementum luctus rutrum. Nullam consectetur justo ut tortor venenatis ullamcorper. Duis ornare in diam sit amet auctor. Nullam egestas velit velit. Sed ut scelerisque risus. Fusce non aliquam ipsum, eu ultricies odio. Sed egestas orci a pellentesque dictum. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos.
Praesent nec suscipit risus. Quisque odio urna, viverra a lacinia non, ullamcorper eu purus. Interdum et malesuada fames ac ante ipsum primis in faucibus. Ut porta elit eget tristique finibus. Morbi pellentesque, urna quis molestie luctus, dolor ante volutpat arcu, at pulvinar justo nisi sit amet lacus. Ut tincidunt justo eu purus placerat tristique. Nunc convallis posuere iaculis. Pellentesque pulvinar, eros vitae elementum mollis, ligula enim imperdiet mi, et mattis orci quam quis massa. Maecenas non turpis at ante ornare semper. Duis pellentesque dolor quis ex lacinia, sed maximus purus facilisis. Praesent vitae euismod massa. Proin efficitur condimentum lorem, eu lobortis risus consequat sit amet. Morbi in luctus tortor. Duis sodales ac justo tincidunt placerat. Phasellus quis nisl vel neque convallis lacinia eu eu augue. Nam blandit ac lorem nec gravida.
Sed malesuada varius turpis, et hendrerit nunc facilisis id. Integer finibus finibus tortor quis eleifend. Sed nunc est, auctor vitae viverra volutpat, sagittis non quam. Sed ac pharetra lorem. Proin commodo sagittis nulla, eget rhoncus nulla iaculis eu. Ut sit amet molestie eros, sed porttitor leo. Phasellus id ante lacus. Aenean porttitor mattis augue ut dignissim. Nunc sapien ante, pulvinar a lorem eget, dapibus lobortis ante. Nulla facilisi.
Fusce vel nibh tellus. Sed at semper leo. Fusce aliquet tellus ante, et laoreet massa hendrerit at. Mauris vitae quam facilisis, vulputate quam id, consequat felis. Nam urna ex, laoreet vel ligula eget, sollicitudin imperdiet augue. Nam nisl purus, pulvinar id porttitor ut, bibendum et neque. Nulla a felis consequat, iaculis sem vel, auctor sem. Duis nec facilisis erat. Integer consectetur velit in hendrerit vestibulum. Sed tristique neque bibendum tortor tincidunt, eu venenatis turpis sollicitudin. Aliquam at nisi mollis, convallis lorem eu, sollicitudin arcu. Vivamus in commodo elit, in hendrerit urna. Curabitur sollicitudin lorem mi, non commodo risus rhoncus vitae. Fusce quis condimentum sapien. Suspendisse accumsan vulputate mauris sit amet molestie. Aenean aliquet ante dignissim tortor blandit blandit.
Nam hendrerit elementum velit lobortis laoreet. Duis fringilla, dolor nec congue cursus, eros magna venenatis mauris, et rutrum dui tortor et leo. Nam aliquam luctus augue, auctor porttitor sem vulputate id. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia curae; Donec a ex hendrerit mi ultrices convallis ac quis lectus. Donec ac mauris non libero suscipit imperdiet et vitae nibh. Pellentesque a neque ut enim consequat volutpat non et erat. Maecenas vel velit tincidunt, tincidunt ex eget, condimentum ex. Donec pulvinar mi ipsum, sit amet viverra justo imperdiet sit amet. Morbi dolor lectus, consectetur id feugiat a, feugiat a mi. Ut varius quam ac dolor dictum, ut congue lorem semper.
Integer sit amet bibendum est. Integer fringilla vulputate justo sed consectetur. Morbi lorem arcu, lacinia ut sem vestibulum, eleifend aliquet nisi. Sed id vehicula urna, in ultrices erat. Curabitur vitae eros orci. Donec eu.
"#;

const LOREM2: &str = r#"　Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla sit amet leo libero. Morbi tortor lorem, porta at imperdiet ac, bibendum sit amet dui. Vestibulum condimentum mi nec nisi scelerisque, a feugiat justo mollis. Nulla pulvinar purus eget sapien tincidunt faucibus. Nunc in dui finibus nisi blandit ultricies eget ac purus. Morbi venenatis id lectus nec venenatis. Fusce tempus nulla arcu, sit amet imperdiet nulla cursus pellentesque. Aenean sit amet sodales ligula, et bibendum nibh. Pellentesque ullamcorper, mauris nec lacinia egestas, libero lectus semper nisi, eu ornare libero quam vitae augue.
Sed pellentesque pretium accumsan. Fusce tempor quam eget urna elementum ultricies. Nullam nec fringilla felis. Duis at laoreet dolor. Donec tristique, velit at scelerisque commodo, sapien neque viverra nibh, eu viverra nisl tortor vitae risus. Ut interdum ullamcorper neque sed tincidunt. Proin pretium nibh a magna sodales, et iaculis velit posuere. Proin mi diam, pretium eget hendrerit vitae, feugiat in libero. Ut et suscipit nulla, non blandit urna. Cras sit amet nunc magna. Vivamus pellentesque ligula sapien, ut varius risus scelerisque id. Ut magna enim, bibendum eu sem ut, commodo porta orci.
"#;

pub fn lorem1(c: &mut Criterion) {
    c.bench_function("lorem1 lowercase", |b| b.iter(|| LOREM1.to_lowercase()));
}

pub fn lorem2(c: &mut Criterion) {
    c.bench_function("lorem2 lowercase", |b| b.iter(|| LOREM2.to_lowercase()));
}

criterion_group!(benches, lorem1, lorem2);
criterion_main!(benches);

Cargo.toml

[package]
name = "lowercase_bench"
version = "0.1.0"
edition = "2021"

[dev-dependencies]
criterion = "0.5.1"

[[bench]]
name = "benchmark"
harness = false

結果

さらに、ハンデだった文字数を揃えるとlorem2の推定平均計算時間は3.3020 μsから18.161 μsになりlorem1の10倍を超えます。

詳細な話

str::to_lowercase関数の内部実装を見ることで、何がこの差を生み出しているのか確認します。

pub fn to_lowercase(&self) -> String {
    let out = convert_while_ascii(self.as_bytes(), u8::to_ascii_lowercase);
    // Safety: we know this is a valid char boundary since
    // out.len() is only progressed if ascii bytes are found
    let rest = unsafe { self.get_unchecked(out.len()..) };
    // Safety: We have written only valid ASCII to our vec
    let mut s = unsafe { String::from_utf8_unchecked(out) };
    for (i, c) in rest.char_indices() {
        // 中略
    }
    return s;
}

まず、前半のASCII文字特化の処理を詳しく見てみます。
convert_while_asciiは以下のような実装になっています。なお、USIZE_SIZEは8なのでNは16です。

fn convert_while_ascii(b: &[u8], convert: fn(&u8) -> u8) -> Vec<u8> {
    let mut out = Vec::with_capacity(b.len());

    const USIZE_SIZE: usize = mem::size_of::<usize>();
    const MAGIC_UNROLL: usize = 2;
    const N: usize = USIZE_SIZE * MAGIC_UNROLL;
    const NONASCII_MASK: usize = usize::from_ne_bytes([0x80; USIZE_SIZE]);

    let mut i = 0;
    unsafe {
        while i + N <= b.len() {
            // Safety: we have checks the sizes `b` and `out` to know that our
            let in_chunk = b.get_unchecked(i..i + N);
            let out_chunk = out.spare_capacity_mut().get_unchecked_mut(i..i + N);

            let mut bits = 0;
            for j in 0..MAGIC_UNROLL {
                // read the bytes 1 usize at a time (unaligned since we haven't checked the alignment)
                // safety: in_chunk is valid bytes in the range
                bits |= in_chunk.as_ptr().cast::<usize>().add(j).read_unaligned();
            }
            // if our chunks aren't ascii, then return only the prior bytes as init
            if bits & NONASCII_MASK != 0 {
                break;
            }

            // perform the case conversions on N bytes (gets heavily autovec'd)
            for j in 0..N {
                // safety: in_chunk and out_chunk is valid bytes in the range
                let out = out_chunk.get_unchecked_mut(j);
                out.write(convert(in_chunk.get_unchecked(j)));
            }

            // mark these bytes as initialised
            i += N;
        }
        out.set_len(i);
    }

    out
}

while文に入った直後のlet in_chunk = ..では、bの未処理の部分をちょうど16バイト読み込みます。次にこれを8バイトずつに分けてビット論理和をとり、ASCII文字でないものが含まれているかどうかチェックします。もし含まれていたらwhileを抜けて直前のループまでの結果を返します。
全てASCII文字である場合、in_chunkを1バイト（=1文字）ずつ読み込みconvert関数を適用した結果をout_chunkの空き領域に書き込み、whileの条件判定に戻ります。

convert_while_asciiに渡していたu8::to_ascii_lowercaseは、引数がA〜ZであればASCII_CASE_MASKとのビット論理和を返し、そうでなければ引数の値をそのまま返します。

これでASCII文字に特化した変換方法がわかりました。まとめると以下のようになります。

16バイトまとめて読み込み、全てASCII文字かどうかチェックする
u8::to_ascii_lowercaseで1バイトずつ変換する
まだ16バイト以上残っていれば上に戻り、繰り返す

次に、ASCII文字でない場合にも対応したアルゴリズムを見ていきます。先ほど省略したstr::to_lowercase関数のforループの中身を以下に示します。ここにif c == 'Σ'という非常に面白い分岐があります。本題ではないので軽く触れるにとどめますが、Σは原則σに変換される一方で単語の終わりにある場合のみςに変換されます。これはRustに限ったことではなく、他の言語でも同様です。

for (i, c) in rest.char_indices() {
    if c == 'Σ' {
        // Σ maps to σ, except at the end of a word where it maps to ς.
        // This is the only conditional (contextual) but language-independent mapping
        // in `SpecialCasing.txt`,
        // so hard-code it rather than have a generic "condition" mechanism.
        // See https://github.com/rust-lang/rust/issues/26035
        let out_len = self.len() - rest.len();
        let sigma_lowercase = map_uppercase_sigma(&self, i + out_len);
        s.push(sigma_lowercase);
    } else {
        match conversions::to_lower(c) {
            [a, '\0', _] => s.push(a),
            [a, b, '\0'] => {
                s.push(a);
                s.push(b);
            }
            [a, b, c] => {
                s.push(a);
                s.push(b);
                s.push(c);
            }
        }
    }
}

char_indicesメソッドはchar単位のイテレータを作成しますが、このイテレータを消費するたびに文字列を表すバイト列が先頭から1バイトずつ読まれ、UTF-8の仕様に照らして文字の境界かどうかチェックされ、境界に出会うまで最大4バイト読み出されます。

内部実装のコード

pub unsafe fn next_code_point<'a, I: Iterator<Item = &'a u8>>(bytes: &mut I) -> Option<u32> {
    // Decode UTF-8
    let x = *bytes.next()?;
    if x < 128 {
        return Some(x as u32);
    }

    // Multibyte case follows
    // Decode from a byte combination out of: [[[x y] z] w]
    // NOTE: Performance is sensitive to the exact formulation here
    let init = utf8_first_byte(x, 2);
    // SAFETY: `bytes` produces an UTF-8-like string,
    // so the iterator must produce a value here.
    let y = unsafe { *bytes.next().unwrap_unchecked() };
    let mut ch = utf8_acc_cont_byte(init, y);
    if x >= 0xE0 {
        // [[x y z] w] case
        // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
        // SAFETY: `bytes` produces an UTF-8-like string,
        // so the iterator must produce a value here.
        let z = unsafe { *bytes.next().unwrap_unchecked() };
        let y_z = utf8_acc_cont_byte((y & CONT_MASK) as u32, z);
        ch = init << 12 | y_z;
        if x >= 0xF0 {
            // [x y z w] case
            // use only the lower 3 bits of `init`
            // SAFETY: `bytes` produces an UTF-8-like string,
            // so the iterator must produce a value here.
            let w = unsafe { *bytes.next().unwrap_unchecked() };
            ch = (init & 7) << 18 | utf8_acc_cont_byte(y_z, w);
        }
    }

    Some(ch)
}

str::to_lowercaseに話を戻します。match conversions::to_lower(c) { .. }の部分を見てみます。conversions::to_lower関数は以下のようになっています。

pub fn to_lower(c: char) -> [char; 3] {
    if c.is_ascii() {
        [(c as u8).to_ascii_lowercase() as char, '\0', '\0']
    } else {
        LOWERCASE_TABLE
            .binary_search_by(|&(key, _)| key.cmp(&c))
            .map(|i| {
                let u = LOWERCASE_TABLE[i].1;
                char::from_u32(u).map(|c| [c, '\0', '\0']).unwrap_or_else(|| {
                    // SAFETY: Index comes from statically generated table
                    unsafe { *LOWERCASE_TABLE_MULTI.get_unchecked((u & (INDEX_MASK - 1)) as usize) }
                })
            })
            .unwrap_or([c, '\0', '\0'])
    }
}

この関数はcが0x7F以下ならば前半と同じu8::to_ascii_lowercaseを用います。そうでない場合、詳細は端折りますがハードコードされた変換結果一覧から対応する文字を二分探索で探し出します。戻り値には1〜3個の有効なcharが含まれるので、それをstr::to_lowercase側で受け取ってString型のsにpushします。
まとめると以下のようになります。

for (i, c) in rest.char_indices()で以下のようにして1文字ずつ読み込む
1. 1バイト読む
2. 正しい文字の境界かチェック
3. 違ったらもう1バイト読む
4. 以下略
ASCII文字ならu8::to_ascii_lowercaseで変換、そうでなければハードコードされたテーブルから探索
結果を1文字ずつpush

これで材料が揃いました。冒頭の問題ではどちらも先頭の空白以外はASCII文字なので、ハードコードされたテーブル云々の影響は小さいです（LOREM2の長さをLOREM1に揃えた時の処理時間の伸び方から明らかです）。ASCII文字特化の方法では16バイトまとめて読み込み、文字境界チェックとASCII文字チェックをbits & NONASCII_MASK != 0で1回で判定できます。一方全文字種対応の方法では文字境界チェックとASCII文字チェックを1バイトずつ行います。つまり、LOREM2の変換が遅かったのは、それぞれの文字を小文字にする変換処理そのものが遅くなったわけではなく、ASCII文字かどうかを判定する処理が効率的に行えず遅くなっていたのです。

他の言語では？

ECMAScriptでは初めに文字列全体をコードポイントの配列に変換し、Unicode Default Case Conversionに従って変換します。しかし、変換の内部アルゴリズムは指定されておらず実装に委ねられています。^[1]。
Denoでベンチマークを取ってみました。JITコンパイラの最適化を阻害するため、結果を適当に利用するようなコードを書いています（こうしないと1回あたり約2.3 ns、つまりRustの1000倍くらい速いなどというありえない結果を出してきます）。また、LOREM1、LOREM2、LOREM3は先頭/末尾の空白以外は冒頭のRustコードに出てきたLOREM2と同じです。

let c = 0

Deno.bench({
  name: "全角スペースなし",
  fn() {
    c += LOREM1.toLowerCase().length
  }
})

Deno.bench({
  name: "先頭に全角スペース",
  fn() {
    c += LOREM2.toLowerCase().length
  }
})

Deno.bench({
  name: "末尾に全角スペース",
  fn() {
    c += LOREM3.toLowerCase().length
  }
})

結果は以下のようになりました。

benchmark                        time (avg)        iter/s             (min … max)       p75       p99      p995
--------------------------------------------------------------------------------- -----------------------------
全角スペースなし                        104.54 ns/iter   9,565,527.4     (90.59 ns … 137 ns) 110.63 ns 125.42 ns 129.27 ns
先頭に全角スペース                       901.22 ns/iter   1,109,610.0   (862.28 ns … 1.01 µs) 908.97 ns 1.01 µs 1.01 µs
末尾に全角スペース                       894.09 ns/iter   1,118,460.6   (847.94 ns … 1.04 µs) 903.12 ns 1.04 µs 1.04 µs

最適化阻害については、まだRustより速いことになってしまっていますが何も対策しないよりはずっとマシです。3つを見比べると全角スペースがない場合は有意に速くなりますが、他二つは大差ないことがわかります。したがってJavaScript（Deno）では文字列全体がASCII文字のみの場合については最適化されていると考えられます。V8のソースコードは公開されているのでそれを読めば答え合わせできるのですが、~~面倒なのでやめておきます~~賢明な読者への課題とします。

PythonもECMAScriptと同様、細かいアルゴリズムまでは明記されていません。^[2]。
以下のようなコードで実験しました。

from time import time
REP = 1000000 # 10^6

t1 = time()
for _ in range(REP):
    pass
t2 = time()
print("empty:", t2 - t1)
t3 = time()
for _ in range(REP):
    LOREM1.lower()
t4 = time()
print("全角スペースなし:", t4 - t3)
t5 = time()
for _ in range(REP):
    LOREM2.lower()
t6 = time()
print("先頭に全角スペース", t6 - t5)
t7 = time()
for _ in range(REP):
    LOREM3.lower()
t8 = time()
print("末尾に全角スペース", t8 - t7)

結果は以下の通りです。

empty: 0.017852306365966797
全角スペースなし: 0.2810392379760742
先頭に全角スペース 3.1710331439971924
末尾に全角スペース 3.1704206466674805

多少のばらつきはありますが、だいたい有効数字2～3桁くらいです。したがってPythonは文字列全体がASCIIのみの場合について最適化されていると考えられます。なお、この実験で用いたPython環境は以下の通りです。

$ python3
Python 3.12.2 (main, Feb  6 2024, 20:19:44) [GCC 11.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>

Golang（1.23.4）のstrings.ToLowerでは初めに1バイトずつ読んで全ての文字がASCII文字のみかどうか判定し、全てASCII文字ならば最適化された方法で、1文字でも非ASCII文字があれば全体を一般的な方法で変換します^[3]。

以上より、JavaScript（Deno）、Python（CPython 3.12）、Golang（Go 1.23.4）では文字列全体がASCIIのみかどうかで最適化されている（可能性が高い）ことがわかりました。先ほど紐解いたRustの戦略は、実はそれほど一般的ではなかったようです。

おわりに

実際のプログラミングでこれほど長く、かつASCII文字とそうでない文字が混ざった文字列をto_lowercaseする機会は少なく、実務上の影響を考慮する必要はほぼ無いと言えるでしょう。しかし、アドベントカレンダーのネタの1つくらいにはなるかもしれません。みなさんも普段使っている言語の中身に時折目を向けてみてはいかがでしょうか。

脚注