Full Unicode Search at 50× ICU Speed with AVX‑512

今年作った最も醜いが実用的なオープンソースライブラリ

私は StringZilla をご紹介できることをうれしく思います。これは AVX‑512 に対応した、非常に高速化された Unicode ツールキットで、一般的な UTF‑8 操作を 速く かつ 正確に 行うことができます。
以下は元の記事を整理したものです。改行や不要な記号は削除しています。

1. なぜ重要なのか

• 2024 年時点で、インターネット上の約 98 % が UTF‑8 を採用しています。
• UTF‑8 は 100 万文字以上を表現できますが、その扱いは決して簡単ではありません。
• Chrome・Chromium や OS カーネルなど多くのライブラリは ICU に Unicode サポートを委ねていますが、ICU には高速な大文字小文字不敏感部分文字列検索機能が欠けています。

StringZilla はそのギャップを埋めます。以下の機能を提供します：

-i

2. UTF‑8 の概要

UTF‑8 は可変長エンコーディングです：

U+0000–U+007F : 1 バイト   0xxxxxxx
U+0080–U+07FF : 2 バイト 110xxxxx 10xxxxxx
U+0800–U+FFFF: 3 バイト 1110xxxx 10xxxxxx 10xxxxxx
U+10000–U+10FFFF: 4 バイト 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

解析には逐次アクセス（

i → i+1

3. 現代言語における Unicode

String

string

str

unicodedata

これらの違いから、UTF‑8 を生データとして処理する必要があるライブラリは、Python の

stringzilla

stringzilla

4. 大文字小文字変換と部分文字列検索

展開例

• ドイツ語

  ß

  → “ss”
• トルコ語

  İ

  → “i̇”（小文字 i + 組み合わせ点）
• 合字（

  fi

  ）→ “fi”

これらの展開により、1 つのコードポイントが複数バイトになる場合があります。

安全ウィンドウ手法

1. 短く安全なニードルスライス を見つける。
   • 折りたたみ後で ≤ 16 バイトに収まるもの。
   • 何らかの「アラーム」（展開・合字・ケルビン記号）を起こさないもの。
2. このウィンドウを SIMD スキャンで検索。
3. ヒットがあれば、ヘッド＋テール全体をスカラーで検証。

これにより SIMD のスループットを保ちつつ正確性も保証します。

5. 性能

すべての数値は AVX‑512 対応の AMD Zen 5 インスタンスで測定。

ICU や PCRE2 と比較して、StringZilla は「純粋な大文字小文字不敏感検索」で 50–100 倍高速です。またすべての Unicode エッジケースに対応しています。

6. StringZilla の使い方

C / C++

#include <stringzilla/stringzilla.h>
char src[] = "Straße";
char dst[64];          // ≥ 3 × source length
size_t folded_len = sz_utf8_case_fold(src, strlen(src), dst);

const char *haystack = "Der große Hund";
const char *needle   = "GROSSE";
sz_size_t hay_len = strlen(haystack);
sz_size_t nee_len = strlen(needle);

sz_utf8_case_insensitive_needle_metadata_t meta = {};
sz_size_t match_len;
char const *match = sz_utf8_case_insensitive_find(
    haystack, hay_len,
    needle, nee_len,
    &meta,
    &match_len
);

C++ (string views)

namespace sz = ashvardanian::stringzilla;

sz::string_view text = "Der große Hund";
auto [offset, length] = text.utf8_case_insensitive_find("GROSSE");

sz::utf8_case_insensitive_needle pattern("STRASSE");
auto match = sz::string_view("Straße").utf8_case_insensitive_find(pattern);

Python

import stringzilla as sz

# One‑liner search
offset = sz.utf8_case_insensitive_find("Der große Hund", "GROSSE")
print(offset)          # 4 (byte offset)

# Iterator for repeated searches
for match in sz.utf8_case_insensitive_find_iter(
        "Straße STRASSE strasse", "strasse"):
    print(match, match.offset_within("Straße STRASSE strasse"))

Rust

use stringzilla::stringzilla::{utf8_case_insensitive_find, Utf8CaseInsensitiveNeedle};

assert_eq!(utf8_case_insensitive_find("Straße", "STRASSE"), Some((0, 7)));

let needle = Utf8CaseInsensitiveNeedle::new(b"STRASSE");
assert_eq!(utf8_case_insensitive_find("strasse", &needle), Some((0, 7)));

Swift

import StringZilla

let haystack = "Der große Hund"
if let range = haystack.utf8CaseInsensitiveFind(substring: "GROSSE") {
    print(haystack[range])   // "große"
}

Node.js

const sz = require('stringzilla');

const text = Buffer.from("Straße");
const patternBytes = Buffer.from("STRASSE");

console.log(sz.utf8CaseInsensitiveFind(text, patternBytes)); // { index: 0n, length: 7n }

7. インストール

pip install stringzilla

cargo add stringzilla

npm install stringzilla

主要アーキテクチャ向けにビルド済みバイナリが用意されています。GPU/CPU 並列化パッケージ（

stringzilla-cpus

stringzilla-cuda

8. 今後の計画

• ジョージア語、韓国語など他スクリプト向けの専用 SIMD カーネル
• ARM 対応（NEON/SVE） – 現在は 128‑bit ベクトルに限定
• 動的ディスパッチ遅延のさらなる低減

StringZilla は Apache 2.0 ライセンスで GitHub 上で公開されています：https://github.com/ashvardanian/StringZilla

コーディングを楽しんでください！