早期停止しない:メモリ速度でのソースコードのケースフォールディング
Don't stop early: Case-folding source code at memory speed (github.blog)
要約
GitHubのエンジニアリングチームは、ソースコードのケースフォールディング(大文字・小文字の区別をなくす処理)をメモリ速度で実行する最適化手法について解説しています。この最適化により、コード解析ツールのパフォーマンスが大幅に向上し、開発ワークフローの効率化に貢献します。
全文翻訳
早期終了しない:メモリ速度でのソースコードのケースフォールディング
ユーザーが「café」と検索し、コーパスに「CAFÉ」が含まれている場合や、「straße」と入力して「STRASSE」が保存されている場合を考えてみましょう。これらの検索を一致させるには、大文字・小文字の区別をなくし、大文字・小文字のみが異なる2つの文字列が等しく比較されるような正規形が必要です。それがケースフォールディングであり、テキストが表示されるのではなく照合されるあらゆる場所(検索エンジン、正規表現の(?i)フラグ、大文字・小文字を区別しないユーザー名やホスト名)に現れます。
これは基本的な操作ですが、GitHubでは大量に実行します。GitHubのコード検索エンジンであるBlackbirdは、1億8000万以上のリポジトリ、つまり480TB以上のソースコードをインデックス化しています。すべてのバイトは、ngramを抽出しインデックスを構築する前にケースフォールディングされ、潜在的なクエリ結果ごとに、一致を見つけるために別の(暗黙的または明示的な)ケースフォールディング操作が必要です。その規模では、基本的な操作であっても速度が重要になってきます。
この記事では、それをどのように高速化したかについて説明します。それは、直感に反する場所から始まります。ASCIIの高速パスにおける最大の成果は、最適化を追加したのではなく、削除したことから得られました。最初の非ASCIIバイトで早期に終了するよりも、分岐なしでバッファ全体をスキャンする方が高速であることが判明しました。その結果を casefold というRustクレートとしてオープンソース化しました。
フォールディングは小文字化ではない
str::to_lowercase に手を伸ばしたくなるかもしれませんが、小文字化とフォールディングは異なる目的を持つ異なる操作です。
小文字化は表示用であり、ロケールやコンテキストに依存します。ギリシャ語の末尾シグマは単語の末尾では ς に、それ以外では σ に小文字化され、トルコ語の I は英語の I とは異なる小文字化をします。ケースフォールディングは比較用であり、意図的にコンテキストフリーでロケールに依存しません。その目的は、安定して対称的な関係を維持することです。つまり、AがBと一致するようにフォールドされれば、BもどのロケールでもAと一致するようにフォールドされるべきです。Unicode文字データベースは、まさにそのための 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; // インデックスiで非ASCII: 残りはUnicodeパスに渡す
}
if b.is_ascii_uppercase() {
*b += 32; // 'A'..='Z' → 'a'..='z'
}
}
理想的に見えます。安価なバイト処理を行い、非ASCIIバイトに遭遇したらすぐにブレークして、「実際の」Unicodeパスに引き継ぎます。「必要なまで安価な処理だけを行う」ということです。Apple M4では、これは約 3 GiB/s で実行されます。これは単独では問題ないように聞こえますが、if分岐のため、「最適」な速度の 15倍以上 短いです。
行ごとに、すべての分岐を削除しましょう。
if b >= 0x80 { break }→ 決して停止しない。すべてのバイトをORでアキュムレータに集め、ループの 後に 一度だけテストします:high_bit_acc |= *b。同じ情報(非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を設定 → 小文字化、そうでなければノープ
}
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バッファ)での累積的なラダーを測定します。
| バージョン | スループット | ベクトル化? |
|---|---|---|
| naive (break + branch test) | 3.1 GiB/s | いいえ (0 ベクトル命令) |
| → branchless test/write, keep break | 2.6 GiB/s | いいえ (0 ベクトル命令) |
| → drop the early-exit break | 7.6 GiB/s | 部分的に (25 ベクトル命令) |
| → branchless test + write (the loop) | >45 GiB/s | 完全 (41 ベクトル命令) |
早期終了はベクトル化を妨げる要因です。ブレークを維持しても本体を完全に分岐なしにしても、依然として ゼロ 個のベクトル命令しか得られません(約2.6 GiB/s)。データ依存のループ終了だけで、ループをスカラーに保つのに十分です。ブレークがなくなって初めて、コンパイラはベクトル化できます。最終ステップ(大文字フォールドを分岐なしにする)は、部分的に ベクトル化されたループ(まだ比較-ブレンド-マスクドストアにコンパイルされる、約7.6 GiB/s)を、メモリ帯域幅に到達する直線的な算術演算に変換します。
注意:分岐なしはスカラーコードではペナルティです。 表をもう一度見てください。ブレークを 維持したまま 本体を分岐なしにすると(2.6 GiB/s)、実際にはナイーブな分岐ループ(3.1 GiB/s)よりも 遅く なります。アセンブリがその理由を説明しています。分岐バージョンは、実際に変更がある場合にのみバイトをストアします。その条件付きstrbは、小文字、数字、スペース(実際のテキストの大部分)ではスキップされ、ガードする予測しやすい分岐はほぼ無料です。分岐なしバージョンは、そのまれにしか実行されないストアを、反復ごとに 無条件の strb に置き換えます。これは、大文字の数バイトではなく、約5,700バイトすべてを書き戻します。メリットなしの追加書き込みトラフィックです。分岐なし書き込みは、ループがベクトル化された場合にのみ 勝利 します。その場合、ストアは内容に関係なく単一の16バイトベクトル書き込みになり、バイトあたりのコストはなくなります。教訓:分岐なし本体は、ベクトル化を可能にする場合にのみ価値があります。それ自体では、スカラーコードではコストがかかる可能性があります。
中間的なアプローチもあり、標準ライブラリが使用しているのはそれです。1バイトずつテストする代わりに、[u8]::is_ascii は マシンワード単位 でスキャンします。64ビットターゲットでは、2つのu64レーンをORで結合し、すべての高ビットを single & 0x8080_8080_8080_8080 マスクでチェックすることにより、1回の反復で16バイトをテストします。その上にASCII高速パスを構築できます。チャンクをスキャンしてASCIIプレフィックスを見つけ、次にその上で分岐なし(ベクトル化可能)の変換を実行します。これにより早期終了機能が維持されます(非ASCIIブロックで停止します)が、両方の部分を高速化できます。ただし、データを 2回 読み取ります(一度スキャン用、一度変換用)。結果は約 23 GiB/s で、単一パスの分岐なしスキャン(メモリ帯域幅)の約半分、ナイーブなブレークループの約7倍です。堅実で汎用的なデフォルトですが、ループ全体を制御して検出と変換を1つの分岐なしパスに統合できる場合は、絶対的な上限ではありません。
2つのパスを 融合 することはより高速ではないでしょうか? それは明白な次の考えです。チャンク化された早期終了を維持しつつ、ASCIIであることを確認した直後に各16バイトブロックを変換し、データを 1回だけ 読み取ります。測定すると、約2.6倍遅く なります(8.7 GiB/s 対 2パスの23 GiB/s)。内部ブロック変換は依然として単一の16バイト操作にベクトル化されますが、今や16バイトごとにデータ依存の早期終了分岐があり、その分岐はループを1ブロックずつに固定します。コンパイラはブロック間でアンロールしたりソフトウェアパイプライン化したりせず、各反復はロード→テスト→分岐→変換→ストアのレイテンシ全体を支払い、それを隠すものが何もありません。2つのパスに分割すると、それぞれがクリーンになります。スキャンは分岐が少なく、ストアなし のワードスキャンでメモリを駆け抜け、変換はメモリ帯域幅の >45 GiB/s で完全にベクトル化された分岐なしスキャンです。2つの高速な分岐なしパスは、融合バージョンがデータを半分しか触らないにもかかわらず、1つの分岐あり融合パスよりも優れています。同じ教訓がもう一度:ホットループでは、分岐は敵です。
ヒープの回避
45 GiB/s という速度は、不要な割り当てをゼロにすることも意味します。simple_fold は入力 String を値として受け取り、変更して返せるヒープバッファを所有します。ORアキュムレータの高ビットがクリアされていた場合、入力はすでにインプレースでフォールドされた純粋なASCIIでした。私たちは 同じ割り当て をそのまま返します。2番目のバッファもコピーもありません。それ以外の場合は、最初の非ASCIIバイトまで memchr し、そこから残りをスキャンします。出力バッファは、文字が 異なるバイトにフォールドされる まで 割り当てられません(ヌル書き込みカーソル)。マルチバイトの内容が決してフォールドされないテキスト(CJK、Hangul、Kana、Arabic、Hebrew、記号)も、元の割り当てをそのまま返します。バイトをコピーすることはありません。
なぜASCIIパスのようにインプレースで書き直すのではなく、2番目のバッファが必要なのでしょうか?フォールドによって文字列が 長くなる可能性がある ためです。ほとんどのフォールドはUTF-8長を維持するか短縮しますが、2つの例外があります。U+023A (Ⱥ) と U+023E (Ɀ) はそれぞれ2バイトですが、3バイト文字(ⱥ、ɀ)にフォールドされます。これらが1つでも出現すると、出力は入力バイトに収まらなくなり、書き込み先として新しい場所が必要になります。
私たちはそのバッファを 1回だけ、最悪ケースを想定したサイズで割り当てます。より多くのフォールドが出現するたびに成長させるのではなく。段階的な予約呼び出しは、容量の再確認、場合によっては再割り当て、それまでに書き込まれたすべてのもののコピー、および追加の長さ/容量のブックキーピングの管理を意味します。単一の事前割り当てにより、生の書き込みカーソルがそれなしで最後まで実行できます。カーソルが最初の成長/変更フォールドまで null であるため、これは「追加バッファはすでに割り当てられたか?」フラグとしても機能します。
サイズ設定には成長の上限が必要です。それらの2つの例外がそれを与えます。入力バイト2バイトごとに最大3バイトの出力が得られ、出力は入力の 1.5倍 に制限されます。これはまさに予約する容量です。
out = Vec::with_capacity(bytes.len() + bytes.len() / 2 + 4);
その後、ループは生のポインタを使用して書き込み、容量チェックなしで、最後に set_len を1回呼び出します。さらに2つの詳細により、分岐を少なく保ちます。2つのフォールド間の変更されていないバイトの連続は、バイトごとではなく、単一の copy_nonoverlapping で移動されます。そして、各フォールドは、カーソルを折りたたまれた長さ(1〜4)だけ進めながら、リトルエンディアンワードの4バイトすべてを無条件に書き込みます。これにより、ホットパスからの出力長に関する分岐がドロップされ、予約の+4は最後の文字のオーバーフローを安全にするヘッドルームとなります。
Unicodeも安価にする
文字が実際にフォールドする場合でも、急落したくない(UTF-8をデコードし、ハッシュルックアップし、再エンコードする)。Unicode 16.0には1484個の単純フォールドマッピングがありますが、それらは 非常にまばら で 非常に構造化された 関係です。4つの観察により、それらを 1776バイト に縮小し、完全な文字をデコードすることなく フォールドを実行できるようにします。
非ASCIIパスでも、圧倒的多数の文字はフォールドしません。ホットな操作は実際には「この文字をフォールドする」ではなく、「この文字はフォールドするか?」です。ほとんどの場合、いいえ。テーブルは、その 否定的なテスト を可能な限り安価にする必要があります。実際のフォールドは、すでにまれなパスにおけるまれなケースです。その優先順位が以下のレイアウトを形作っています。ページビットマップは、非フォールド文字がデコードやスキャンなしで、UTF-8の先頭バイトから単一のビットテストで拒否されるように存在します。
これが、HashMap<u32, u32> が単に大きいだけでなく、間違った 形状である理由です。ハッシュマップは ヒット に最適化されています。キーが存在する場合、約1回のプローブで検索し、ロードファクターや衝突が発生した場合にのみ追加の作業(より多くのプローブ、完全なキー比較)を行います。しかし、私たちのワークロードは ミス によって支配されています。テーブルに存在しない文字が多く、ミスはハッシュマップの 最も嫌いな クエリです。キーのハッシュ、バケットへのジャンプ、および不在を 証明する のに十分なプローブシーケンスのウォークを依然として行う必要があります。
フォールディング可能なコードポイントは64コードポイントの「ページ」にクラスタ化する
フォールディング可能なコードポイントは集まっています。コード空間を64コードポイントの「ページ」に分割すると、約1484個のフォールドが、約1960個の可能なページのうち 59 ページにのみ触れます。ページあたりの1ビットの 存在ビットマップ が否定的なテストを単独で処理します。クリアされたビットは 決定的な 「フォールドなし」であり、コピーして完了です。これは、フォールドフリーのスクリプトを安価にする理由です。セットされたビットの場合にのみ、2番目の構造、つまりページをランク付けする 累積ポップカウントサイドテーブル(先行するポピュレーションされたページの数)を参照して、エントリのスライスを見つけます。約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)
} 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つのエントリですが、それはかさばり、検索も遅いです。1ページには数十個のフォールドが含まれる可能性があり、現在のコードポイントに一致するものを検索するためにすべてをスキャンする必要があります。データの構造が再び私たちを救います。隣接するコードポイントは、フォールドへのデルタをほぼ同じように共有します。A–Z はすべて +32 にマッピングされ、Latin Extended は 0x0100、0x0102、0x0104、… のような 交互の ランで満たされており、2番目のコードポイントごとにフォールドします。コードポイントごとのエントリの代わりに、私たちは ラン(開始、終了、ストライド、デルタ)を格納します。そして、1ビットのストライドフラグが、連続ケースと交互ケースの両方をカバーします。この間隔圧縮により、約1484個の個別のフォールドが59ページにわたるわずか 238 のランに圧縮されます(平均約4ページあたり)。これにより、ページ内検索は数十個ではなく、わずかなエントリを確認するだけで済みます。この範囲とデルタエンコーディング(ストライドトリックを含む)は、Goのunicodeパッケージから借用されています。そのCaseRange レコードは、Lo/Hi範囲と、UpperLower セントネルが交互ブロックを示すものに加えて、デルタを格納します。ランはページ境界で分割されるため、ランが2つのページにまたがることはありません。
ランレコードは2つのクリーンなバイト
両方の終端が同じページ内にあるため、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にロードし、分岐なしのSWARステップで一度にすべてをテストします。(chunk | 0x80…80) − broadcast(low) & 0x80…80 は、キーが ≥ cp & 0x3F であるすべてのレーンの最上位ビットを設定します。そのマスクの単一ビットスキャン(キーはソートされているため、最初にセットされたレーンが目的のランです)がスロットを見つけます。ページには平均約4つのランが含まれています。その8バイト幅の比較は、ほとんどの場合、単一ステップで全体の検索を解決します。1つの不運なページには30個のランが含まれていますが、これは比較を8キーずつ進む短いループ内に配置します。しかし、そのループはUnicode全体で最大でも数回しかトリップせず、一般的なランでは決してトリップしません。いずれにせよ、ランごとの分岐はなく、コードポイントの再構築もありません。
/// `end_low >= low_v` である最初のランのオフセット(`n`個のランのページ内)、
/// または `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); // ...フォールドされた長さだけ進める
このスニペットの両方の長さ(ソース文字の length_mask と、宛先の フォールドされた長さによる進み)は、さらに別の小さなトリックから来ています。UTF-8シーケンスの長さは、先頭バイトの上位4ビットによって固定されます。これにより、16個の可能な長さがそれぞれ1つのニブルにパックされた単一の64ビット定数(0x4322_1111_1111_1111)になります。長さはシフトとマスクになります。 (LEN_BITS >> (4 * (lead >> 4))) & 0xF。if連鎖もテーブルメモリも、予測子が間違えるものもありません。(先頭ビット数 - (!lead).leading_zeros() - も機能します。先頭バイトはシーケンスのバイトごとに1つの先頭1ビットを持つため)。
/// UTF-8シーケンスのバイト数。その先頭バイトは `lead` です。
#[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ショートカット
さらに別のショートカットがテールループを完成させます。最初のパスですでにすべてのASCIIバイトを小文字化していたことを思い出してください。スキャンがテールでASCIIバイトに遭遇すると、1バイト進んで続行します。ページプローブもテーブルタッチも一切ありません。また、そのバイトをコピーすることもありません。変更されていないバイト(ASCIIおよびフォールドしないマルチバイトの両方)は、1バイトずつ移動されません。スキャンは、実際にフォールドする文字に到達するまで歩き続け、最後に copy_nonoverlapping で、最後のフォールドとその文字の間の変更されていないバイトの連続全体をフラッシュします。混合テキスト(ASCIIスペースや句読点を含むCJK、または時折アクセント付き識別子を含むコード)は、ASCIIフィラーを駆け抜け、マルチバイト文字のみに対してビットマップを参照し、バイトごとではなく一括でコピーします。
まとめ:テーブル全体
| コンポーネント | バイト数 |
|---|---|
| PAGE_BITMAP (64cpページあたり1ビット) | 248 |
| POPCNT_SAMPLES (累積ポップカウント) | 32 |
| PAGE_OFFSET (ポピュレーションされたページあたり) | 60 |
| RUN_END_LOW (スキャンキー、end & 0x3F、+8パディング) | 246 |
| RUN_START_STRIDE (start & 0x3F | stride) |
| BYTE_DELTA (ランごとのリトルエンディアンフォールドデルタ) | 952 |
| 合計 | 1776 |
これは、フォールドエントリあたり 9.6ビット です。その半分以上は、デコードフリーパスと引き換えにした BYTE_DELTA サイドテーブルです。インデックスとランレコードだけでも、エントリあたり約4.4ビットです。
明白な代替案と比較して、その1776バイトは桁違いに小さいです。そして、ほとんどの代替案とは異なり、文字をデコードすることはありません。
| 表現 | サイズ |
|---|---|
| Naïve [(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ケースの「上限」を大まかに把握するために、最適化されたUtf8デコード+エンコードのラウンドトリップを、実際のケースフォールディングを実行せずにsimdutfクレートを使用して測定しました。この実験は一貫して約2GB/secを達成し、最悪ケースの全フォールド入力に対するソリューションの約2倍の速度です。ナイーブなハッシュマップは、すべてのワークロードで最後に位置します。
3つの列は、同一の出力を生成する実際のケースフォルダーです:simple_fold(このクレート)、simd_normalizer(simd-normalizerクレート)、およびHashMap(ナイーブなCaseFolding.txtルックアップ)。ワークロード行は、典型的なシナリオから最悪ケースまでをシミュレートするように選択されています。
| ワークロード(入力サイズ) | simple_fold | simd_normalizer | HashMap (byte path) |
|---|---|---|---|
| 純粋なASCII (5.7 KB) | >45 GiB/s | 1.21 GiB/s | 213 MiB/s |
| 中国/日本/韓国、フォールドなし (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対ARM)では大幅に変動する可能性があります。
詳細については、READMEのパフォーマンスセクション を参照してください。
まとめ
ケースフォールディングは、テキスト操作としては基本的なものですが、それだけに労力をかける価値がありました。私たちはそれをインデックス化するすべてのバイトに適用します。成果は、両方とも本能に反する2つのアイデアから生まれました。早期終了ではなく、分岐なしでバッファ全体をスキャンすること、そしてコードポイントへのデコードではなく、バイト空間での算術演算としてフォールドを実行することです。これらを組み合わせることで、一般的なケースをメモリ帯域幅で実行し、まれなフォールドをデコードなしで、常駐できるほど小さい(1776バイト)テーブルで実行できます。デコードフリーのバイト空間フォールドは、私たちが本当に新しいと考えている部分です。これが、すでに答えを持っているハッシュマップを上回ることができる理由です。
ここには間違いなくさらに発見すべきことがあります。そして、それを見たいと思っています。クレートはcasefoldです。生成されたテーブルと完全な設計ノートはソースと共にあります。
執筆者
[画像: Alexander Neubeck]
Principal Software Engineer, GitHub
[画像: Greg Orzell]
Principal Software Engineer