StringZilla 성능 비교를 위한 레포지토리 소개

문자열 처리를 위한 훌륭한 라이브러리가 많이 있습니다! 대부분 물론 Assembly, C, 그리고 C++로 작성되었지만, Rust로 작성된 것도 일부 존재합니다.

Rust가 C와 C++에 비해 뛰어난 점은 의존성 관리의 단순함이며, 이는 '시스템 소프트웨어(Systems Software)'를 벤치마킹하고 네이티브 크레이트(native crates)와 해당 Python 바인딩 간의 사과 대 사과 비교를 가능하게 합니다.

따라서 StringZilla의 개발 속도를 높이기 위해 (Rust 및 Python 바인딩을 포함한) C, C++, 그리고 CUDA 라이브러리를 만들었고, 이를 제가 커뮤니티에서 가장 좋아하는 Rust 프로젝트들(예: 서브스트링 검색을 위한 memchr, 편집 거리 및 정렬을 위한 rapidfuzz와 bio, 해싱을 위한 aHash, xxhash-rust, foldhash, blake3, 다중 패턴 검색을 위한 aho_corasick과 regex, 컬렉션 및 정렬을 위한 arrow와 polars, 유니코드 처리를 위한 icu, 암호화를 위한 ring과 sodiumoxide)과 비교할 수 있도록 이 레포지토리를 만들었습니다.

물론 프로젝트들의 기능은 다르며, API와 사용 패턴도 다릅니다. 그래서 저는 StringZilla가 설계된 워크로드에 초점을 맞추고 핵심 연산의 처리량(throughput)을 비교하는 데 중점을 두었습니다. 특히, 기존 라이브러리 및 도구에서 자주 지원되지 않는, 2015년 Intel Skylake-X CPU부터 시작되는 x86의 마스크가 장착된 AVX-512와 같은 더 넓은 범위의 SIMD 명령어 지원이나, Arm의 최신 조건부 가변 길이 SVE 및 SVE2와 같은 하드웨어에서도 성능을 테스트했습니다.

중요 사항
아래 표에 제시된 수치는 참고용이며 CPU, 컴파일러, 데이터셋, 토큰화 방식에 따라 달라질 수 있습니다. 대부분의 결과는 Rust를 사용하고 -C target-cpu=native 최적화 플래그를 적용하여 Intel Sapphire Rapids (SPR) 및 Granite Rapids (GNR) CPU와 Nvidia Hopper 기반 H100 및 Blackwell 기반 RTX 6000 Pro GPU에서 얻었습니다.
결과를 재현하려면 아래의 'Replicating the Results' 섹션을 참조해 주십시오.

많은 해싱 라이브러리가 존재하지만, 재현 가능한 출력(reproducible outputs), 스트리밍 지원(streaming support), 또는 교차 언어 가용성(cross-language availability)이 부족한 경우가 많습니다. 짧은 단어와 긴 라인에서의 처리량(Throughput):

Short Words Long Lines
Rust:
stringzilla::hash ████████████████████ 1.84 ████████████████████ 11.38 GB/s
...

자세한 내용은 hash/README.md를 참조하세요.

Bloom 필터와 cuckoo 필터는 동일 키에 대한 많은 독립적인 해시(independent hashes)가 필요합니다. StringZilla의 hash_multiseed는 키를 한 번 준비하고 저렴한 시드당 라운드를 재실행하는 반면, 다른 대안들은 64~128비트마다 키를 다시 준비해야 합니다.
다이제스트(Digest) 처리량 (1024비트 다이제스트, 단어당 16개 독립 해시):

Rust:
stringzilla::hash_multiseed ████████████████████ 71.85 G bits/s
xxh3::xxh3_128 ████████▏ 29.30 G bits/s
...

자세한 내용은 containers/README.md를 참조하세요.

전체 케이스 폴딩(case folding)을 지원하는 유니코드 인식 대소문자 구분 없는 검색 (ß↔SS, σ↔ς). 약 100MB의 다국어 코퍼스 전반에 걸친 검색 처리량:

Rust:
English German
stringzilla ████████████████████ 12.79 ████████████████████ 10.67 GB/s
...

자세한 내용은 normalization/README.md를 참조하세요.

부분 문자열 검색(Substring search)은 대부분의 언어에서 C의 memmem 또는 strstr로 오프로드되지만, SIMD 최적화 구현이 더 나은 성능을 낼 수 있습니다.
긴 라인에서의 처리량:

Left to right Reverse order
Rust:
memmem::Finder ████████████████████ 10.99
...

자세한 내용은 find/README.md를 참조하세요.

문자 집합(탭, HTML 마크업, 숫자) 검색은 일반적으로 정규 표현식(regex) 또는 Aho-Corasick 오토마타를 사용합니다. 긴 라인에서 모든 일치 항목을 계산하는 처리량:

Rust:
stringzilla ████████████████████ 8.17 GB/s
regex::find_iter ████████████▊ 5.22 GB/s
...

자세한 내용은 find/README.md를 참조하세요.

여러 개의 니들(needles)을 전체 코퍼스(corpus)에 한 번의 패스로 매칭하는 것이 바로 Aho-Corasick 오토마타(automata)가 하는 일이며, 이 오토마타가 메모리에 어떻게 배치되는지가 검색 루프보다 처리량(throughput)을 훨씬 더 결정합니다. 카운팅(Counting), 가장 왼쪽 커버 해결(resolving a leftmost cover), 리라이팅(rewriting), 그리고 BM25 스코어링 모두 동일한 컴파일된 딕셔너리를 사용합니다. 숫자들은 조용한 기계를 기다리며, 스윕과 그 프레이밍은 substrings/README.md에 있습니다.

이 테이블에서 꼭 말해줘야 할 두 가지가 있습니다: 모든 경쟁자(rival)는 싱글 스레드(single-threaded)이며 CPU 전용이기 때문에, 진정한 정면 대결은 멀티 코어 또는 GPU 행이 아닌 stringzillas::Substrings<1cpu>와 합니다.

또한 여기의 BM25는 역 인덱스(inverted index)가 아니라 고정된 쿼리(query)에 대한 스캔이기 때문에, bm25와 bm25s는 인덱스 빌드와 쿼리를 별도로 비교합니다.

자세한 내용은 substrings/README.md를 참조하세요.

다양한 스크립트가 UTF-8을 다르게 처리합니다: 한국어는 단일 바이트 공백과 함께 3바이트 한글을 사용하고(토큰화의 대표 예시), 아랍어는 2바이트 문자를, 영어는 주로 1바이트 ASCII를 사용합니다. AMD Zen5 Turin에서의 처리량:

Newline splitting:
English Arabic
stringzilla ████████████████ 15.45 ████████████████████ 18.34 GB/s
...

(Latin, Cyrillic, Greek, Armenian)과 중국어를 참고하여 문자 대소문자 폴딩(Case folding):

Case folding:
English 16x German 6x
stringzilla ████████████████████ 7.53 ████████████████████ 2.59 GB/s
...

코도포인트 인덱싱(Codepoint indexing) — N번째 코도포인트의 바이트 오프셋 — 에서 SIMD가 가장 큰 효과를 발휘합니다: 표준 라이브러리는 버퍼를 바이트 단위로 재스캔하는 반면, StringZilla는 단일 SIMD 스캔으로 해당 위치에 점프합니다.

Byte offset of the Nth codepoint, full corpora:
English Korean
stringzilla::find_nth ████████████████████ 7.14 ████████████████████ 12.14 GB/s
...

자세한 내용은 tokenization/README.md와 normalization/README.md를 참조하세요.

데이터프레임 라이브러리와 검색 엔진은 문자열 정렬에 크게 의존합니다. SIMD 가속 비교와 특화된 Radix Sort가 일반적인 알고리즘보다 성능이 뛰어날 수 있습니다.

모든 경쟁사들은 StringZilla와 일치하도록 안정적인 정렬(stable sort)으로 구성되어 있는데, StringZilla는 호출자가 소유한 버퍼에 순열을 기록하는 argsort를 사용합니다. 이는 Python의 NumPy out= 배열과 같으며, 제로 할당 인덱스 정렬이 가능하게 합니다.

짧은 단어에서의 처리량(Throughput):

Rust:
stringzilla.argsort ████████████████████ 209.32 M cmp/s
polars::sort ███████████████████▋ 205.21 M cmp/s
...

GPU: cudf

H100에서 짧은 단어에 대해 9,463 M cmp/s에 도달합니다.

자세한 내용은 sequence/README.md를 참조하세요.

랜덤 바이트 생성과 조회 테이블(lookup tables)은 이미지 처리 및 생물정보학(bioinformatics)에서 흔하게 사용됩니다. 긴 라인에서의 처리량:

Rust:
stringzilla ████████████████████ 10.57 GB/s
zeroize ████████▉ 4.73 GB/s
...

자세한 내용은 memory/README.md를 참조하세요.

편집 거리(Edit distance)는 검색 엔진, 데이터 클리닝, 자연어 처리(NLP), 생물정보학에 필수적입니다. 계산 복잡도가 O(n*m)으로 높아 비용이 많이 들지만, GPU와 멀티 코어 병렬 처리가 도움을 줍니다. 약 1,000 바이트 라인에서의 Levenshtein distance (MCUPS = Million Cell Updates Per Second):

Rust:
1 Core 1 Socket
bio::levenshtein █▏ 823
...

자세한 내용은 similarities/README.md를 참조하세요.

가변 길이 문자열을 고정 길이 스케치(Min-Hashing과 같은)로 변환하는 것은 대규모 검색에서 빠른 근사 매칭을 가능하게 합니다. 약 1,000 바이트 라인에서의 처리량:

Rust:
1 Core 1 Socket
pc::MinHash ████████████████████ 3.16
...

자세한 내용은 fingerprints/README.md를 참조하세요.

ChaCha20 및 AES256 암호화 처리량 비교 (긴 라인):

Rust:
ring::aes256 ████████████████████ 2.89 GB/s
ring::chacha20 ████████▏ 1.19 GB/s
...

자세한 내용은 encryption/README.md를 참조하세요.

모든 의존성을 가져오고 컴파일하려면 다음 명령을 호출할 수 있습니다:

RUSTFLAGS="-C target-cpu=native" cargo build --benches --all-features # 모든 것을 컴파일하기 위함
RUSTFLAGS="-C target-cpu=native" cargo check --benches --all-features --all-targets # 경고 발생 시 실패하도록 설정하기 위함

기본적으로 StringWars는 CPU 모드에서 stringzilla를 연결합니다.
만약 CUDA가 설치된 NVIDIA GPU를 사용하는 경우, 벤치마크를 실행할 때 명시적으로 CUDA 커널을 활성화해야 합니다. 예를 들면 다음과 같습니다:

RUSTFLAGS="-C target-cpu=native" \
STRINGWARS_DATASET=README.md \
STRINGWARS_TOKENS=lines \
... 

Wars는 항상 오래 걸리며, 이 벤치마크들도 마찬가지입니다.
각 벤치마크에는 CPU 캐시가 채워지고 결과가 콜드 스타트(cold start)나 SIMD 관련 주파수 스케일링에 의해 영향을 받지 않도록 몇 초간의 워밍업(warm-up) 단계가 포함되어 있습니다.
각 벤치마크는 데이터셋, 토큰화 및 오류 경계를 제어하기 위해 몇 가지 환경 변수를 허용합니다.
이것들은 Linux에서 awk를 사용하여 파일 레벨 문서를 출력함으로써 확인할 수 있습니다:

awk '/^">//!/ { print } !/^">//!/ { exit }' find/bench.rs

자주 사용되는 환경 변수는 다음과 같습니다:

STRINGWARS_DATASET

• 텍스트 데이터셋 파일의 경로.
  STRINGWARS_TOKENS
• 토큰화 모드: file, lines, 또는 words.
  STRINGWARS_ERROR_BOUND
• Levenshtein 거리에서 허용되는 최대 오류 값.

Unix와 같은 시스템에서 일반적인 벤치마크 실행 예시는 다음과 같습니다:

RUSTFLAGS="-C target-cpu=native" \
STRINGWARS_DATASET=README.md \
STRINGWARS_TOKENS=lines \
... 

Windows에서 PowerShell을 사용하는 경우 환경 변수를 다르게 설정해야 합니다:

$env:STRINGWARS_DATASET="README.md"
cargo bench --features bench_hash --bench bench_hash --jobs $(nproc)

Python 의존성 관리 및 벤치마크 실행에는 uv를 사용하는 것이 권장됩니다.
모든 벤치마크의 모든 의존성을 설치하려면 다음을 사용하세요:

uv venv --python 3.12
uv pip install -r requirements.txt -r requirements-cuda.txt
uv pip install --only-binary=:all: -r requirements.txt -r requirements-cuda.txt

개별 벤치마크의 의존성을 설치하려면 다음을 사용하세요:

PIP_EXTRA_INDEX_URL=https://pypi.nvidia.com \
uv pip install '.[find,hash,memory,sequence,fingerprints,similarities,tokenization,normalization,containers,encryption]'

개별 벤치마크를 실행하려면 다음을 호출할 수 있습니다:

Python 벤치마크는 독립적인 PEP 723 스크립트이므로, uv를 사용하면 URL에서 스크립트를 가져오고 종속성을 해결할 수 있습니다. 클론(clone)이나 수동으로 pip install을 할 필요가 없습니다:

uv run https://raw.githubusercontent.com/ashvardanian/StringWars/main/tokenization/bench.py \
--dataset README.md --tokens file

Rust 벤치마크는 StringZilla에 대한 경로 종속성을 가진 Cargo 워크스페이스이므로, 정확히 클론(zero-clone)하는 것은 불가능합니다. cargo install --git은 [[bin]]/[[example]] 타겟만 설치하며, [[bench]]는 그렇지 않습니다.
가장 가벼운 방법은 얕은 클론(shallow clone)입니다:

git clone --depth 1 https://github.com/ashvardanian/StringWars && cd StringWars
RUSTFLAGS="-C target-cpu=native" cargo bench --features bench_hash --bench bench_hash --jobs $(nproc)

다국어 추출 요약(multilingual extractive summarization)을 위해 혼합된 UTF 데이터를 사용했으며, XL Sum 데이터셋을 활용했습니다. 이 데이터셋은 크기가 4.7 GB(압축 시 1.7 GB), 라인 수는 1,004,598개이며 평균 길이로 268,435,456 토큰을 포함하고 있습니다. 다운로드, 압축 해제 및 벤치마크를 실행하려면 터미널에서 다음 bash 스크립트를 실행하십시오:

mkdir -p data/xlsum && curl -fL -o data/xlsum/xlsum.csv.gz https://github.com/ashvardanian/xl-sum/releases/download/v1.0.0/xlsum.csv.gz
gzip -d data/xlsum/xlsum.csv.gz
STRINGWARS_DATASET=data/xlsum/xlsum.csv cargo bench --features bench_hash --bench bench_hash --jobs $(nproc)

대안으로, 훨씬 작고 빠른 실행을 원한다면 Big List of Naughty Strings (BLNS)를 확인해 보세요:

mkdir -p data/blns && curl -fL -o data/blns/blns.txt https://raw.githubusercontent.com/minimaxir/big-list-of-naughty-strings/master/blns.txt
STRINGWARS_DATASET=data/blns/blns.txt cargo bench --features bench_hash --bench bench_hash --jobs $(nproc)

Cohere Wikipedia 데이터셋은 다양한 언어에 대한 전처리된 JSONL 파일을 제공합니다. 이 데이터셋은 개별 환경에서 UTF-8 디코딩 및 매칭 엔진의 상대적 비교를 위한 최적의 데이터셋일 수 있습니다. 모든 위키피디아 언어가 사용 가능한 것은 아니며, 다음 언어들이 특별히 선택되었습니다:

중국어 (zh): 3바이트 CJK 문자, 드문 1바이트 구두점
한국어 (ko): 3바이트 한글 음절, 빈번한 1바이트 구두점
아랍어 (ar): 2바이트 아랍어 스크립트, 규칙적인 1바이트 구두점
프랑스어 (fr): 높은 악센트 밀도를 가진 혼합된 1~2바이트 라틴 문자
영어 (en): 주로 1바이트 ASCII 기준

각 언어별 하나의 파일을 다운로드하고 압축을 해제하려면:

mkdir -p data/wikipedia-22-12
curl -fL -o data/wikipedia-22-12/wiki_en.jsonl.gz https://huggingface.co/datasets/Cohere/wikipedia-22-12/resolve/main/en/000.jsonl.gz && gunzip data/wikipedia-22-12/wiki_en.jsonl.gz
curl -fL -o data/wikipedia-22-12/wiki_zh.jsonl.gz https://huggingface.co/datasets/Cohere/wikipedia-22-12/resolve/main/zh/000.jsonl.gz && gunzip data/wikipedia-22-12/wiki_zh.jsonl.gz
...

각 JSONL 파일은 다음 필드를 가진 한 줄당 하나의 JSON 객체를 포함합니다: id, title, text(단락 내용), url, wiki_id, 및 paragraph_id.