ARMプロセッサで文字をマッチさせる最速の方法は？

次の問題を考えてみましょう。文字列が与えられたとき、ASCIIの空白文字（\t、\n、\r、およびスペース）と、JSONで重要な一部の文字（:、,、[、]、{、}）をすべてマッチさせる必要があります。JSONはウェブサービスで使用されるテキストベースのデータ形式です。おもちゃのJSONドキュメントは次のようになります。

{
  "name": "Alice",
  "age": 30,
  "email": "[email protected]",
  "tags": ["developer", "python", "open-source"],
  "active": true
}

私たちはSIMD（single-instruction-multiple-data）命令を使ってこの問題を解決したいと思います。この命令を使うと、16バイトのブロックを別の16バイトのブロックと1命令で比較できます。

これは、高速なsimdjson JSONライブラリでJSONドキュメントをインデックス化する際のサブ問題です。私たちはこのタスクをベクトル化分類と呼んでいます。DNSレコードの解析などでも同じ手法を使用しています。実際のsimdjsonライブラリでは、文字列や引用符も処理する必要があり、より複雑になります。

ここで、文字を「マッチさせる」とはどういう意味かを定義する必要があります。私の場合、64バイトの各ブロックに対して、空白用と重要文字用の2つの64ビットマスクを取得すれば十分です。説明のため、16バイト版を考えてみましょう。

{"name": "Ali" }
1000000100000001 // 重要文字
0000000010000010 // 空白

つまり、バイナリ形式で数値0b1000000100000001と0b0000000010000010（10進数でそれぞれ33025と130）を取得したいのです。

ARMプロセッサで利用可能な従来のSIMD命令（NEON）を使った方法については、LangdaleとLemire（2019）を参照してください。彼らの主要なアイデアは、テーブル駆動の分岐なし分類器です。各バイトに対して、SIMDテーブルルックアップを使って各ニブルをビットマスクにマッピングし、比較してそのバイトが対象セット（空白またはJSON構造文字）に属するかどうかを判定します。これにより、文字ごとに多数の個別の等価比較を行う必要がなくなります。

最近のARMプロセッサでは、より良い方法があります。

NEONの128ビット版は、ARMv8-Aアーキテクチャ（AArch64）で2011年に導入されました。Appleが重要な役割を果たし、iPhone 5SのApple A7チップで初めて使用されました。すべての64ビットARMプロセッサでNEONがサポートされていると期待でき、便利です。（32ビットARMプロセッサもありますが、主に組み込みシステムで使用され、メインストリームコンピューティングでは使われません。）

ARM NEONは優れていますが、古くなりつつあります。x64（AMDおよびIntel）プロセッサで利用可能なAVX-512命令セットには及びません。AVX-512命令は、より広いレジスタ（ARM NEONの16バイトに対して64バイト）をサポートするだけでなく、より強力な命令も備えています。

しかしARMには他に提供できるものがあります。Scalable Vector Extension（SVE）とその後継のSVE2です。SVEは2016年に初めて導入されましたが、実際に利用可能になるまで2022年までかかりました。Amazon Graviton 3で使用されているNeoverse V1アーキテクチャが、私がアクセスできた最初のものです。その後すぐに、Neoverse V2およびN2アーキテクチャでSVE2が利用可能になりました。現在では、AWSのGraviton4、AzureのMicrosoft Cobalt 100、Google CloudのGoogle Axion（およびより新しいGoogle Cloud ARM CPU）、NVIDIA Grace CPU、Qualcomm、MediaTek、Samsungの複数のチップで容易に利用できます。含まれていないのは誰でしょうか？Appleです。理由は不明ですが、AppleはまだSVE2を採用していません。

SVE/SVE2については複雑な気持ちです。RISC-Vと同様に、固定長レジスタサイズ（16バイト、32バイト、64バイト）を使用するARM NEONやx64 SIMDのアプローチとは異なります。つまり、レジスタの幅を知らなくてもコードを書くことが求められます。

これはチップメーカーにとって便利です。市場に合わせてレジスタサイズを調整するオプションを与えるからです。しかし、これは失敗したようです。AmazonのGraviton 3プロセッサは256ビットレジスタを持っていましたが…その後のすべての市販チップは128ビットレジスタでした。

利点として、SVE/SVE2にはAVX-512のようなマスクがあり、レジスタのサブセットのみでデータをロードおよび処理できます。これにより、入力がレジスタサイズの倍数でないという、以前のSIMD命令セットにおける長年の問題が解決されます。SVE/SVE2とAVX-512の両方が、末尾処理をより良くする可能性があります。レジスタの一部のみを操作できることで、賢い最適化が可能になります。残念ながら、SVE/SVE2ではAVX-512とは異なり、マスクを汎用レジスタとの間で効率的に移動できません。これは可変長レジスタという設計の直接的な結果です。したがって、レジスタが常に128ビットで16バイトを含んでいたとしても、命令セットはマスクが16ビットワードに収まると仮定することを許可されていません。

SVE/SVE2がARM NEONと相互運用可能であることを知るまで、私はSVE/SVE2について悲観的でした。ARM NEONとSVE/SVE2のコードを混ぜて使うことができるのです。これは、SVE/SVE2レジスタがARM NEONレジスタ（16バイト）と一致することを知っていれば、特にうまく機能します。

私の作業では、2つのSVE2命令が重要です。matchとnmatchです。8ビット版では、次のことを行います。最大16バイトを含む2つのベクトルaとbが与えられたとき、matchはa[i]がb内のいずれかのバイトと等しい各位置iに対して、述語ビットをtrueに設定します。言い換えると、bは小さなルックアップセットとして機能し、matchはaのすべてのバイトに対して同時に集合のメンバーシップをテストします。nmatch命令は論理補数です。a[i]がb内のいずれのバイトとも一致しない場所で、述語ビットをtrueに設定します。したがって、1つの命令で、一連の等価比較とORリダクションを置き換えることができます。以下のコードでは、op_charsに8つのJSON構造文字が、ws_charsに4つの空白文字が保持されています。16バイトのチャンクd0に対してsvmatch_u8を1回呼び出すと、その入力バイトが構造文字である位置に正確にtrueビットを持つ述語が生成されます。このコードはSVE2 intrinsicsを使用しています。これはCPU SIMD命令にほぼ1対1で対応するコンパイラ提供のC/C++関数で、アセンブリを書かずにアセンブリレベルの制御が得られます。

// : , [ ] { }
uint8_t op_chars_data[16] = {
    0x3a, 0x2c, 0x5b, 0x5d, 0x7b, 0x7d, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0
};
// \t \n \r ' '
uint8_t ws_chars_data[16] = {
    0x09, 0x0a, 0x0d, 0x20, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0
};

// SIMDレジスタに文字をロード
svuint8_t op_chars = svld1_u8(svptrue_b8(), op_chars_data);
svuint8_t ws_chars = svld1_u8(svptrue_b8(), ws_chars_data);

// データをロード
// const char * input = ...
svbool_t pg = svptrue_pat_b8(SV_VL16);
svuint8_t d = svld1_u8(pg, input);

// マッチング
svbool_t op = svmatch_u8(pg, d, op_chars);
svbool_t ws = svmatch_u8(pg, d, ws_chars);

このコードスニペットでは、svuint8_tは符号なし8ビットレーン（バイト）を含むSVEベクトル型です。svbool_tはSVE述語（マスク）型です。svptrue_b8()はすべての8ビットレーンがアクティブな述語を構築し、svld1_u8(pg, ptr)は述語pgを使ってメモリからSVEベクトルにバイトをロードし、実際に読み込むレーンを決定します。

ここまで注意深く読んでいたなら、コードにわずかな誤りがあることに気づくかもしれません。文字セットに0を含めているからです。しかし、入力にゼロバイトが存在しないと仮定する限り問題ありません。実際には、文字の1つを繰り返すか、入力に現れることを期待しない偽の文字（有効なUTF-8文字列に現れることのないバイト値0xFFなど）を使用できます。

標準のSVE/SVE2では、opとwsは整数マスクではなく述語です。実用的なトリックは、各述語をバイト（trueの場合は0xFF、falseの場合は0x00）として具現化することです。例えばsvdup_n_u8_zを使います。

svuint8_t opm = svdup_n_u8_z(op, 0xFF);
svuint8_t wsm = svdup_n_u8_z(ws, 0xFF);

SVEベクトルが128ビットの場合、このバイトベクトルはsvget_neonq_u8を介して自然にNEONのuint8x16_tにマッピングされ、そこからNEON操作（マスキングとペアワイズ加算）を使って効率的にスカラービットマスクを構築できます。4つの16バイトチャンクに対してこれを繰り返すことで、64バイトブロックに必要な2つの64ビットマスクが得られます。

AWS Graviton 4で素早くベンチマークを実行したかったのです。AWSが提供するイメージ（RedHat 10を選択）で readily available だったLLVM clang 20を使用しました。

AWS Graviton 4プロセッサはNeoverse V2プロセッサです。Googleはクラウドに独自のNeoverse V2プロセッサを持っています。私のテストでは、2.8 GHzで動作していました。

私のベンチマークは1 MiBのランダムな文字列を生成し、文字の位置を示すビットマップを計算します。GitHubで入手可能です。結果は以下の通りです。

したがって、SVE/SVE2アプローチはNEON版より高速で、25%少ない命令を使用します。これは派手な最適化を一切行っていない状態です。重要なのは、match命令のおかげでコードが比較的シンプルであることです。

SVE2の関数matchは、ARMプロセッサで文字をマッチさせる最速の方法かもしれません。

Credit: この投稿は、GitHubのユーザーliuyang-664によるスケッチがきっかけとなりました。

References

Langdale, G., & Lemire, D. (2019). Parsing gigabytes of JSON per second. The VLDB Journal, 28(6), 941-960.

Koekkoek, J., & Lemire, D. (2025). Parsing millions of DNS records per second. Software: Practice and Experience, 55(4), 778-788.

Lemire, D. (2025). Scanning HTML at Tens of Gigabytes Per Second on ARM Processors. Software: Practice and Experience, 55(7), 1256-1265.