早い段階で停止しない：メモリ速度でのソースコードのケースフォールディング

分岐のないループとバイト空間演算により、GitHub が単一コアでコード検索の全バイトを 45 GiB/s を超える速度でケースフォールディングする方法。

The GitHub Blog · Jul 31, 2026

Don’t stop early: Case-folding source code at memory speed

ユーザーが café を検索し、コーパスに CAFÉ が含まれている場合や、ユーザーが straße と入力し、STRASSE が保存されている場合を考えてみましょう。これらを一致とみなすには、大文字と小文字の違いを消す正規形が必要であり、大文字と小文字のみが異なる 2 つの文字列を等しく比較できます。その形がケースフォールディングであり、テキストが表示ではなく一致処理される場面（検索エンジン、正規表現の (?i) フラグ、大文字と小文字を区別しないユーザー名やホスト名など）で登場します。

基本的な処理ですが、GitHub では頻繁に実行します。GitHub のコード検索エンジン Blackbird は 1 億 8,000 万を超えるリポジトリ（480TB 以上のソースコード）をインデックス化しています。インデックス作成時に ngram を抽出する前に全バイトがケースフォールディングされ、クエリ結果の候補ごとに、もう一度（暗黙的または明示的に）ケースフォールディング処理が行われます。この規模では、基本的な処理でも速度が重要になります。

本記事では、それを高速化した方法を紹介します。意外な事実から始まります。ASCII 高速パスの最大の改善は、最適化を追加したことではなく、削除したことにあります。非 ASCII バイトで早期終了するより、分岐なしでバッファ全体を走査する方が高速であることがわかりました。その成果を Rust クレート casefold としてオープンソース化しました。

フォールディングは小文字化ではない

str::to_lowercase に手を伸ばしたくなりますが、小文字化とフォールディングは目的が異なる操作です。

小文字化は表示用で、ロケールや文脈に依存します。ギリシャ語の語末シグマは単語末尾では ς に、それ以外では σ に小文字化され、トルコ語の I は英語の I とは異なる小文字化が行われます。ケースフォールディングは比較用で、文脈に依存せずロケール非依存であることが意図されています。重要なのは、A が B に一致するようフォールディングされるなら、B も A に一致するようフォールディングされるという、安定した対称的な関係を保つことです。Unicode Character Database はまさにそのための CaseFolding.txt を提供しています。

2 つの操作は実際の文字（ß、İ、語末シグマ）で乖離するため、小文字化を代用すると誤った一致が静かに発生します。このクレートは単純（1 対 1）フォールディング（CaseFolding.txt のステータス C と S）のみを実装し、マルチ文字の「完全」フォールディング（ß → ss）やトルコ語ロケールフォールディング（点付きの İ）は実装していません。これは珍しい選択ではなく、ripgrep などの一般的なツールや正規表現エンジンも同じ制限を設けており、ツール間で一貫性を保つことは重要です。

直感に反する核心：早い段階で停止しない

主にソースコードを扱うため、フォールディング対象のテキストは ASCII が圧倒的に多く、メモリ速度で実行することが最も重要です。他の処理は、稀な非 ASCII パスがそれを損なわないようにするだけで十分です。

ASCII 文字のフォールディングは単純です。A..=Z は a..=z にマップされ、それ以外は変更されません。つまり ASCII パスは「バッファを走査し、その場で小文字化する」だけです。LLM に依頼すると、次のようなコードが得られるかもしれません。

let bytes = s.as_bytes_mut(); 
for (i, b) in bytes.iter_mut().enumerate() { 
    if *b >= 0x80 { 
        break; // 非 ASCII がインデックス i に存在：残りを Unicode パスへ 
    } 
    if b.is_ascii_uppercase() { 
        *b += 32; // 'A'..='Z' → 'a'..='z' 
    } 
}

理想的に見えます。安価なバイト処理を行い、非 ASCII バイトに到達した瞬間に break して「本物の」Unicode パスに任せる：「安価な処理は必要なときまで行う」。Apple M4 では約 3 GiB/s で動作します。単独では問題ないように聞こえますが、分岐のために「最適」より 15 倍以上遅い のです。

すべての分岐を削除してみましょう。

if b >= 0x80 { break } → 一切停止しない。high_bit_acc |= *b で全バイトをアキュムレータに OR し、ループ終了後に一度だけ検査する。同じ情報（非 ASCII バイトがあったか？）を、分岐ゼロで得られます。
A..=Z の範囲検査 → 算術演算に置き換え。b.wrapping_sub(b'A') < 26 は A..=Z のときにのみ真となり（他のバイトは 26 以上にラップアラウンド）、分岐なしで 0/1 マスクを生成します。
条件付き書き込み → マスクをストアに組み込む。| (is_upper << 5) でビット 5 をセットすると、大文字が小文字になり、他の文字には影響しません。バイトは常に書き込まれ、分岐は発生しません。

残るのは、本体に分岐がなく早期終了もないコードです。

let mut high_bit_acc: u8 = 0; 
for b in &mut bytes { 
    high_bit_acc |= *b; // 非 ASCII バイトを検出 
    let is_upper = b.wrapping_sub(b'A') < 26; // 分岐なしの A..=Z 検査 
    *b |= u8::from(is_upper) << 5; // ビット 5 をセット → 小文字化、それ以外は no-op 
} 
if high_bit_acc & 0x80 == 0 { 
    return bytes; // 純粋な ASCII：その場でフォールディング済み、2 つ目のバッファ不要 
}

データ依存の制御フローがないループは自明にベクトル化可能です。LLVM は 16 バイト単位の NEON を出力し、全体で 45 GiB/s を超える 速度（実質メモリ帯域幅）で動作します。また、high_bit_acc から、非 ASCII の残り処理が必要かどうかをループ終了時にすでに把握しています。

各ステップの影響はどれほどだったでしょうか。純粋な ASCII（Apple M4、5.7 KB バッファ）で累積測定した結果です。

バージョン	スループット	ベクトル化？
素朴（break + 分岐検査）	3.1 GiB/s	いいえ（ベクトル命令 0）
→ 分岐なしの検査/書き込み、break は保持	2.6 GiB/s	いいえ（ベクトル命令 0）
→ 早期終了の break を削除	7.6 GiB/s	部分的（ベクトル命令 25）
→ 分岐なしの検査 + 書き込み（最終ループ）	>45 GiB/s	完全（ベクトル命令 41）

早期終了がベクトル化を阻害しています。break を残したまま本体を完全に分岐なしにしても、ベクトル命令はゼロ（約 2.6 GiB/s）のままです。データ依存のループ出口だけで、ループはスカラーに留まります。break を削除して初めて、コンパイラはベクトル化できます。最後のステップ（大文字フォールディングを分岐なしにする）で、部分的にベクトル化されたループ（条件付きストアが compare-blend-masked-store にコンパイルされ、約 7.6 GiB/s）が、メモリ帯域幅に到達する直線的な算術演算に変わります。

注：分岐なしはスカラーコードでは逆最適化になる。表をもう一度見てください。本体を分岐なしにしつつ break を保持した場合（2.6 GiB/s）は、素朴な分岐付きループ（3.1 GiB/s）より実際に遅いのです。アセンブリが理由を説明します。分岐付き版は実際に変更されたバイトだけをストアし、条件付き strb は小文字・数字・スペース（実際のテキストの大部分）ではスキップされ、それを守る予測容易な分岐はほぼ無料です。分岐なし版は、ほとんど発生しないストアを無条件の strb毎イテレーションに置き換え、約 5,700 バイトすべてを書き戻します。余計な書き込みトラフィックで利益なし。分岐なし書き込みが有利になるのは、ループがベクトル化されたときだけです。その場合、ストアは内容に関係なく 16 バイトのベクトル書き込みになり、1 バイトあたりのコストが消えます。教訓：分岐なしの本体は、ベクトル化を可能にする手段としてのみ価値があります。単独では、スカラーコードでコストになる可能性があります。

中間的な選択肢もあり、標準ライブラリが採用しています。1 バイトずつ検査する代わりに、[u8]::is_ascii はマシンワード単位で走査します。64 ビットターゲットでは、2 つの u64 レーンを OR し、高位ビットを & 0x8080_8080_8080_8080 マスクで一度に検査することで、1 イテレーションあたり 16 バイトを検査します。その上に ASCII 高速パスを構築できます。チャンク走査で ASCII プレフィックスを見つけ、その上で分岐なし（ベクトル化可能）の変換を実行するのです。早期終了機能は保持されつつ（最初の非 ASCII ブロックで終了）、両方の半分を高速にできます。欠点はデータを2 回読む（走査用と変換用）ことで、約 23 GiB/s になります。単一パスの分岐なし走査の半分程度で、素朴な break ループの約 7 倍です。一般用途の堅実なデフォルトですが、ループ全体を制御でき、検出と変換を 1 つの分岐なしパスにまとめられる場合には絶対的な上限ではありません。

2 つのパスを融合すれば速くなるのでは？ 当然の次の考えです。チャンク単位の早期終了を保持しつつ、ASCII と確認した直後に各 16 バイトブロックを変換すれば、データを1 回だけ読みます。測定結果は 約 2.6 倍遅い ものでした。2 パス方式の 23 GiB/s に対し 8.7 GiB/s です。内部のブロック変換は 16 バイトの単一演算にベクトル化されますが、16 バイトごとにデータ依存の早期終了分岐が発生し、その分岐がループを 1 ブロックずつに固定します。コンパイラはブロックをまたいだ展開やソフトウェアパイプラインを行わず、各イテレーションは load→test→branch→convert→store の全レイテンシを隠す余地なく支払います。2 つのパスに分割すると、それぞれがクリーンです。走査は分岐が少なくストアなしのワード走査でメモリを高速に駆け抜け、変換は 45 GiB/s を超える完全ベクトル化・分岐なしの走査になります。2 つの高速で分岐なしのパスが、1 つの分岐付き融合パスを上回ります。融合版はデータへのタッチ回数が半分なのにです。繰り返しになりますが、ホットループでは分岐が敵です。

ヒープの回避

45 GiB/s は、不要な割り当てを一切行わないことも意味します。simple_fold は入力 String を値で受け取り、ミューテートして返せるヒープバッファを所有します。OR アキュムレータの最上位ビットがクリアなら、入力は純粋な ASCII でその場でフォールディング済みです。同じ割り当てをそのまま返し、2 つ目のバッファもコピーも必要ありません。そうでなければ memchr で最初の非 ASCII バイトを探し、そこから末尾を走査し、異なるバイトにフォールディングされる文字に到達するまで出力バッファを未割り当て（null 書き込みカーソル）のままにします。マルチバイト内容が一切フォールディングされないテキスト（CJK、Hangul、Kana、Arabic、Hebrew、記号）も、元の割り当てを触れずに返し、1 バイトもコピーしません。

ASCII パスのようにその場で書き換えるのではなく、なぜ2 つ目のバッファが必要なのでしょうか。フォールディングは文字列を長くすることがあるからです。ほぼすべてのフォールディングは UTF-8 長を維持または短縮しますが、2 つの例外が長さを増やします。U+023A (Ⱥ) と U+023E (Ɀ) はそれぞれ 2 バイトですが、3 バイト文字（ⱥ、ɀ）にフォールディングされます。いずれかが出現すると、出力は入力のバイト数に収まらず、新しい場所に書き込む必要があります。

そのバッファは最悪ケース向けにサイズ指定して一度だけ割り当て、フォールディングが出現するたびに拡張しません。増分的な reserve 呼び出しは容量再検査、 occasional な再割り当て、書き込み済み内容のコピー、長さ/容量管理の juggling を意味します。事前の一括割り当てなら、生の書き込みカーソルが余計な処理なしに終端まで直進できます。また、カーソルは最初の長さ増加/変更フォールディングまで null なので、「追加バッファをすでに割り当てたか？」のフラグも兼ねられます。

サイズ指定には成長の上限が必要で、同じ 2 つの例外がそれを与えます。入力 2 バイトあたり最大 3 出力バイトになるため、出力は入力の 1.5 倍に収まります。これが予約する容量です。

out = Vec::with_capacity(bytes.len() + bytes.len() / 2 + 4);

その後、ループは容量検査なしで生ポインタ経由で書き込み、最後に一度 set_len を呼びます。分岐を減らすための 2 つの工夫があります。2 つのフォールディングの間の変更なしバイト列は、1 バイトずつではなく copy_nonoverlapping で一度に移動します。各フォールディングは、リトルエンディアンのワード 4 バイトを無条件に書き込んでから、カーソルをフォールディング後の長さ（1–4）だけ進めます。出力長に関する分岐をホットパスから排除し、予約時の +4 が末尾文字のオーバーストアを安全にします。

Unicode も安価にする

文字が実際にフォールディングされるときも、崖から落ちたくはありません。UTF-8 デコード、ハッシュルックアップ、再エンコードです。Unicode 16.0 には 1484 の単純フォールディングマッピングがありますが、それらは非常に疎で非常に構造化された関係です。4 つの観察により、1776 バイトに縮小し、完全な文字を一度もデコードせずにフォールディングを実行できます。

非 ASCII パスでも、圧倒的多数の文字はフォールディングされません。ホットな操作は「この文字をフォールディングする」ではなく、「この文字はフォールディングされるか？」です。ほぼ常に「いいえ」です。テーブルは、その否定検査をできるだけ安価にする必要があります。実際のフォールディングは、すでに稀なパスの稀なケースです。この優先順位が以下のレイアウトを形作っています。ページビットマップは、まさに非フォールディング文字を先頭 UTF-8 バイトから直接、1 回のビット検査で却下し、デコードや走査を不要にするために存在します。

これが、HashMap<u32, u32> がこの仕事に不適切な形状である理由であり、単に大きいというだけではありません。ハッシュマップはヒットに最適化されています。存在するキーを大体 1 回のプローブで見つけ、負荷率や衝突が発生したときだけ追加作業（さらなるプローブ、完全なキー比較）を行います。しかし、私たちのワークロードはミスが支配的です。テーブルに一切存在しない文字です。ミスはハッシュマップが最も苦手とするクエリです。キーのハッシュ計算、バケットへのジャンプ、欠席を証明するのに十分なプローブシーケンスの走査が依然として必要です。

フォールディング可能なコードポイントは 64 コードポイントの「ページ」に集まる

フォールディング可能なコードポイントはまとまって現れます。コード空間を 64 コードポイントの「ページ」に切り分けると、約 1484 のフォールディングは約 1960 の可能なページのうちわずか 59 ページにしか触れません。1 ビット/ページの存在ビットマップは、それだけで否定検査に答えられます。ビットがクリアなら決定的な「フォールディングなし」— そのままコピーして完了 — となり、フォールディングのないスクリプトを安価にします。ビットがセットされた場合のみ、2 つ目の構造体（累積 popcount サイドテーブル）に相談し、そのページが何番目の非空ページかをランク付けしてエントリのスライスを見つけ、約 1900 の空ページについては何も保存しません。

let (word_idx, bit_idx, c_len) = if lead < 0xE0 { 
    (0usize, lead & 0x1F, 2usize) // 2 バイト：word 0 
} else if lead < 0xF0 { 
    ((lead & 0x0F) as usize, bytes[read + 1] & 0x3F, 3) // 3 バイト：word = nibble 
 
} else { 
    ( 
        (((lead & 0x07) as usize) << 6) | (bytes[read + 1] & 0x3F) as usize, 
        bytes[read + 2] & 0x3F, 
        4usize, 
    ) // 4 バイト：2 バイトをマージ 
}; 
// デコードせずに却下：クリアビット ⇒ フォールディングなし 
if word_idx >= PAGE_BITMAP.len() || (PAGE_BITMAP[word_idx] >> bit_idx) & 1 == 0 { 
    read += c_len; 
    continue; 
}

word_idx は先頭バイト（および 4 バイトシーケンスの場合は最初の継続バイト）のみに依存するため、ビットマップロードを早期に発行できます。

ページ内ではフォールディングは連続する

ページビットがセットされると、そのページに何かがフォールディングされることはわかりますが、どのコードポイントが何にフォールディングされるかはわかりません。自明なエンコーディングは、フォールディング可能なコードポイントごとに 1 エントリですが、どちらも大きく検索が遅いです。ページには数十のフォールディングが含まれる可能性があり、現在一致するものを見つけるためにすべてを走査する必要があります。データの構造が再び助けてくれます。隣接するコードポイントは、フォールディング先へのデルタを圧倒的に共有します。A–Z はすべて +32 にマップされ、ラテン文字拡張には 0x0100、0x0102、0x0104、… のような交互の連続が満ちており、1 つおきのコードポイントがフォールディングされます。コードポイントごとのエントリではなく、ラン（開始、終了、ストライド、デルタ）を保存し、1 ビットのストライドフラグで連続と 1 つおきの両方をカバーします。この区間圧縮により、約 1484 の個別フォールディングを 59 ページにまたがるわずか 238 のラン（ページあたり約 4 つ）にまとめ、ページ内検索で数十ではなく数個のエントリしか見る必要がなくなります。この範囲＋デルタエンコーディング（ストライドのトリックを含む）は Go の unicode パッケージから借用したもので、CaseRange レコードは Lo/Hi 範囲とケースごとのデルタを保存し、UpperLower 番兵が交互ブロックをマークします。ランはページ境界で分割され、ランが 2 つのページにまたがることはありません。

ランレコードは 2 バイトのクリーンなデータ

両端点が 1 ページ内に収まるため、6 ビットで収まり、2 つの配列に分割されます。RUN_END_LOW[``i``] = end & 0x3F（走査キー）と RUN_START_STRIDE[``i``] = (start & 0x3F) | ((stride − 1) << 6)（ヒット時のみ読み取り）です。各キーが 1 つのクリーンなバイトであるため、ページ内検索をワイドに行えます。cp & 0x3F をランごとに 1 つずつ比較するのではなく、8 個の end_low バイトを単一の u64 にロードし、1 回の分岐なし SWAR ステップで一度に検査します。(chunk | 0x80…80) − broadcast(low) & 0x80…80 で、キーが ≥ cp & 0x3F の各レーンの最上位ビットをセットします。そのマスクの単一ビットスキャン（キーはソート済みなので、最初のセットされたレーンが目的のラン）でスロットが見つかります。ページあたりの平均ラン数は約 4 つで、1 回の 8 ワイド比較で検索全体をほぼ常に 1 ステップで解決します。1 つの不運なページだけが 30 ランを持ち、その場合、比較は 8 キーずつ進む短いループ内に入りますが、そのループは Unicode 全体でちょうど 1 ページでのみ数回トリップし、一般的なページでは決して発生しません。いずれにせよ、ランごとの分岐はなく、コードポイント再構築も一切ありません。

/// ページ内の `n` ランの中で `end_low >= low_v` を満たす最初のランのオフセット、
/// 存在しなければ `n` を返す。SWAR で 8 バイトの `end_low` を走査。
#[inline] 
fn scan_end_low(lo: usize, n: usize, low_v: u8) -> usize { 
    const HIGH: u64 = 0x8080_8080_8080_8080; 
    const ONES: u64 = 0x0101_0101_0101_0101; 
    let bcast = (low_v as u64).wrapping_mul(ONES); 
    let mut base = 0; 
    while base < n { 
        // RUN_END_LOW は 8 バイトのパディングがあるため、この読み取りは常に範囲内。
        let chunk = u64::from_le_bytes( 
            RUN_END_LOW[lo + base..lo + base + 8] 
                .try_into() 
                .expect("8-byte slice"), 
        ); 
        // `(b | 0x80) - low_v` は、b >= low_v の場合にハイビットを保持（クロスレーン借用なし）。
        // 最初のセットされたレーンが low_v 以上の最初のラン。
        let ge = (chunk | HIGH).wrapping_sub(bcast) & HIGH; 
        if ge != 0 { 
            let j = base + (ge.trailing_zeros() / 8) as usize; 
            return if j < n { j } else { n }; 
        } 
        base += 8; 
    } 
    n 
}

フォールディングはリトルエンディアンのバイト加算

リトルエンディアンマシンでは、フォールディングされた文字の UTF-8 バイトを u32 として読むと、ソースバイト（u32 として）にランごとの定数を加えた値になります。並列の BYTE_DELTA[i] テーブルにより、フォールディング全体がマスク付きロード、1 回の wrapping_add、4 バイトストアになります。

let word = u32::from_le_bytes(next_four_bytes) & length_mask; // この文字のバイトを保持 
let folded = word.wrapping_add(BYTE_DELTA[i]); // 1 回のバイト加算としてのフォールディング 
write_u32_le(dst, folded); // 4 バイトすべてをストア… 
dst += utf8_len(folded); // …フォールディング後の長さだけ進める

このスニペットの 2 つの長さ（ソース文字用の length_mask と宛先用のフォールディング後の長さだけ進める）は、もう 1 つの小さなトリックから得られます。UTF-8 シーケンスの長さは先頭バイトの上位 4 ビットで決まるため、16 個の可能な長さを 1 つの 64 ビット定数（0x4322_1111_1111_1111）に 1 ニブルずつ詰め込めます。長さはシフトとマスクで (LEN_BITS >> (4 * (lead >> 4))) & 0xF と得られ、if チェーンもテーブルメモリも、予測器が誤る余地もありません。（count leading ones—(!lead).leading_zeros()—も動作します。先頭バイトはシーケンスの各バイトごとに 1 つの先頭 1 ビットを持つためです。）

/// 先頭バイト `lead` の UTF-8 シーケンスのバイト数。
#[inline] 
pub fn utf8_len(lead: u8) -> usize { 
    const UTF8_LEN_BY_LEAD: u64 = 0x4322_1111_1111_1111; 
    ((UTF8_LEN_BY_LEAD >> (4 * (lead >> 4))) & 0xF) as usize 
}

フォールディング後の長さだけ進めるため、長さ変更フォールディング（U+212A KELVIN SIGN（3 バイト）→ k（1 バイト）、または U+023A Ⱥ（2 バイト）→ U+2C65 ⱥ（3 バイト））も、読み取ったバイトより少なくまたは多く書き込むことで処理できます。これは私たちが本当に新しいと信じている部分です。私たちが調べた他のフォルダー（ICU、Go の unicode、Rust の regex、CPython、glibc）はいずれも UTF-8 をコードポイントにデコードし、そこでフォールディングを適用し、再エンコードします（SIMD フォルダーも先にデコードします）。バイト空間で算術演算を行うことで、デコードとエンコードの両方をスキップします。これが、デコード不要のパスが、答えをすでに表に持つハッシュマップを上回れる理由です。ハッシュマップは依然としてキーのデコードと結果のエンコードが必要です。バイト空間演算は、入力が整形式の最短形 UTF-8であることを前提としています。各コードポイントが最小バイト数でエンコードされています。ソースバイトを u32 として読み、ランごとのデルタを加えると、ソースが正規形の場合にのみ正しいフォールディング後のエンコーディングに到達します。オーバーロングエンコーディング（コードポイントを必要以上に多くのバイトにパディングしたもの、例: / を 0xC0 0xAF で表す）は異なるバイトパターンを持ち、length_mask とデルタ演算を破壊します。これは Rust では実際の制約ではありません。&str/String は有効な UTF-8 を保持することが保証されており、オーバーロングシーケンスは定義上拒否されるためです。ただし、他の場所から生バイトを渡す呼び出し元は、事前に検証（または正規化）する必要があります。

末尾ループでの ASCII ショートカット

末尾ループを完成させるもう 1 つのショートカットがあります。最初のパスですでにすべての ASCII バイトを小文字化済みであることを思い出してください。したがって、走査が末尾で ASCII バイトに遭遇した場合、1 バイトだけ進めて次に進みます。ページ検査もテーブルへのタッチも一切ありません。また、そのバイトをコピーすることもありません。変更されないバイト（ASCII と非フォールディングのマルチバイトの両方）は 1 バイトずつ移動されません。走査は実際にフォールディングされる文字に到達するまで歩き続け、最後のフォールディングと今回のフォールディングの間の変更なしラン全体を copy_nonoverlapping で一度にフラッシュします。混合テキスト（ASCII の空白や句読点を含む CJK、または時折アクセント付き識別子を含むコード）は、ASCII の詰め物を高速に通過し、本物のマルチバイト文字に対してのみビットマップを参照し、1 バイトずつではなく一括でコピーします。

まとめ：テーブル全体

コンポーネント	バイト数
PAGE_BITMAP（64-cp ページあたり 1 ビット）	248
POPCNT_SAMPLES（累積 popcount）	32
PAGE_OFFSET（非空ページごと）	60
RUN_END_LOW（走査キー、end & 0x3F、+8 パディング）	246
RUN_START_STRIDE（start & 0x3F \| stride）	238
BYTE_DELTA（ランごとのリトルエンディアンフォールディングデルタ）	952
合計	1776

これは フォールディングエントリあたり 9.6 ビットで、その半分以上がデコード不要パスと引き換えにする BYTE_DELTA サイドテーブルです。インデックス＋ランレコードだけで約 4.4 ビット/エントリです。

自明な代替案と比べると、1776 バイトは 1 桁以上小さく、しかもほとんどの代替案と異なり、文字を一度もデコードしません。

表現	サイズ
素朴な [(u32, u32); 1484]	約 11.6 KB
regex-syntax の case_folding_simple テーブル	約 70 KB
Go の unicode.SimpleFold（orbit + ASCII + ranges）	約 7.3 KB
実行時の HashMap<u32, u32>	約 17 KB
本クレート（ページビットマップ＋パックドラン）	1776 B

代替案との比較

一般的なケースである ASCII では、メモリ帯域幅（45 GiB/s を超える）でフォールディングが実行され、他の実フォルダーより 1 桁以上速く、（等価でない）str::to_lowercase 関数より 50% 以上高速です。非 ASCII ケースの大まかな「上限」を得るため、実際のケースフォールディングを行わず、simdutf クレートを用いた最適化された Utf8 デコード＋エンコードのラウンドトリップを測定しました。この実験は一貫して約 2 GB/秒を達成し、最悪ケースの全フォールディング入力に対して、私たちの解の約 2 倍の速度でした。素朴なハッシュマップは、すべてのワークロードで他のすべてに遅れを取ります。

3 列は同一の出力を生成する実在のケースフォルダーです。simple_fold（本クレート）、simd_normalizer（simd-normalizer クレート）、HashMap（素朴な CaseFolding.txt ルックアップ）です。ワークロード行は、典型的から最悪ケースまでの異なるシナリオを模擬するように選択されています。

ワークロード（入力サイズ）	simple_fold	simd_normalizer	HashMap（バイトパス）
純粋な ASCII（5.7 KB）	>45 GiB/s	1.21 GiB/s	213 MiB/s
Chinese/Japanese/Korean、フォールディングなし（8.1 KB）	2.95 GiB/s	1.97 GiB/s	558 MiB/s
記号 / ミャンマー、フォールディングなし（9.0 KB）	2.96 GiB/s	1.56 GiB/s	410 MiB/s
最悪ケース：ラテン文字/ギリシャ文字/キリル文字（Unicode U+0000–U+FFFF）、全フォールディング（8.8 KB）	869 MiB/s	922 MiB/s	334 MiB/s
長さ変更フォールディング（1.7 KB）	1.26 GiB/s	716 MiB/s	233 MiB/s

絶対値は参考値であり、移植性はありません。設計全体が自動ベクトル化、SWAR、リトルエンディアンバイト演算に依存しているため、数値や行間の比率は、異なるマイクロアーキテクチャ（より広い/狭いベクトルユニット、異なるメモリ帯域幅、ビッグエンディアンターゲット、x86 vs ARM）で大幅に変動する可能性があります。

詳細は README のパフォーマンスセクションを参照してください。

持ち帰っていただきたいこと

ケースフォールディングはテキスト操作の基本中の基本であり、それだけに取り組む価値がありました。インデックス化するすべてのバイトに対して実行するからです。得られた改善は、どちらも直感に反する 2 つのアイデアから来ています。早期終了せずにバッファ全体を分岐なしで走査すること、そしてコードポイントにデコードするのではなくバイト空間演算としてフォールディングを行うことです。これらにより、一般的なケースがメモリ帯域幅で動作し、稀なフォールディングがデコードなしで動作し、常駐可能なサイズ（1776 バイト）のテーブルに収まります。デコード不要のバイト空間フォールディングは、私たちが本当に新しいと信じている部分です。これが、すでに答えを持っているハッシュマップをこのパスが上回れる理由です。

ここにはまだ発見すべきことが surely あり、私たちも見たいと思っています。クレートは casefold です。生成されたテーブルと完全な設計ノートはソースと一緒に公開されています。

Read the original source Next news