fuzzgpu

Hardware-Accelerated Fuzzy String Matching & Sequence Alignment

Cross-platform GPU compute via WebGPU (wgpu) & Multi-Core CPU parallelism with Rayon. Zero CUDA dependencies.

Overview

fuzzgpu is a high-throughput string distance and sequence alignment engine written in Rust with native Python and WebAssembly bindings. It leverages GPU compute shaders (wgpu / WGSL) and Rayon multi-threading to accelerate large-scale batch queries and distance matrix computations across:

• Apple Silicon (Metal)
• Linux (Vulkan)
• Windows (DirectX 12 / Vulkan)
• Integrated GPUs (Intel Iris Xe, AMD Radeon)
• WebAssembly (In-browser execution)

No NVIDIA CUDA drivers or complex toolkits required.

What's New in v0.1.7

Bug fixes (Windows DX12 / Jaro shader)

• Jaro GPU shader FXC crash fixed — jaro.wgsl and jaro_matrix.wgsl used dynamic vector component writes (v[j >> 5u] = ...) in bit_set(). FXC (the DX12 HLSL compiler) cannot emit a dynamic register-indexed store for a non-constant index, causing a hard compile failure with X3550/X3511 on every Windows DX12 runner — all 11 Jaro GPU tests were panicking. Fixed by rewriting bit_set with select()-based static construction, which compiles identically on all backends (Vulkan, Metal, DX12).

Bug fixes (arity mismatch — wasm & fuzz crates)

• fuzzgpu-wasm — partial_ratio, token_sort_ratio, token_set_ratio, wratio gained a score_cutoff: f64 parameter in the v0.1.6 Rust core rewrite for rapidfuzz parity, but the WASM bindings were not updated, causing 4 E0061 compile errors. Fixed by passing 0.0 as the cutoff (no cutoff — identical to the previous behaviour).
• fuzzgpu-fuzz — same four callsites in fuzz/src/lib.rs had the same arity mismatch. Fixed identically.

Includes all v0.1.6 features

All features from v0.1.6 are included — see the v0.1.6 changelog below.

Benchmark Results

Hardware: Intel(R) Iris(R) Xe Graphics (Vulkan) + Intel Core i7 (Rayon uses all cores) Versions: fuzzgpu 0.1.6 · rapidfuzz 3.14.5 · python-Levenshtein 0.27.4 Median of 7 runs after warmup. Reproduce: python benchmarks/bench_compare.py

Levenshtein Batch (1 query × N candidates, 10-char strings)

Damerau-Levenshtein Batch (unrestricted Lowrance-Wagner)

Note: rapidfuzz's DamerauLevenshtein uses Optimal String Alignment (OSA). fuzzgpu implements the unrestricted Lowrance-Wagner (1975) algorithm which allows non-adjacent transpositions. For example: damerau("ca", "abc") == 2 (fuzzgpu) vs 3 (rapidfuzz OSA). Use fuzzgpu.distance.OSA for OSA-compatible semantics.

Installation

pip install fuzzgpu

# Rust
[dependencies]
fuzzgpu-core = "0.1.7"

Quickstart

import fuzzgpu

# ── Core distance metrics ─────────────────────────────────────────────────────
lev = fuzzgpu.levenshtein("kitten", "sitting")              # 3
dam = fuzzgpu.damerau("ab", "ba")                           # 1  (transposition)
jw  = fuzzgpu.jaro_winkler("MARTHA", "MARHTA")             # 0.9611...

# ── Batch (auto-routed GPU/CPU) ───────────────────────────────────────────────
candidates = ["hallo", "hullo", "jello", "yellow", "hello world"] * 10_000
distances  = fuzzgpu.levenshtein_batch("hello", candidates)
jw_scores  = fuzzgpu.jaro_winkler_batch("hello", candidates, p=0.1)
nw_scores  = fuzzgpu.needleman_wunsch_affine_batch(
    "AGTACGCA", candidates, match=2, mismatch=-1, gap_open=-3, gap_extend=-1
)

# ── Cross-product distance matrix ─────────────────────────────────────────────
matrix = fuzzgpu.levenshtein_cdist(["abc", "def", "xyz"], ["abd", "axy", "def"])

# ── Zero-allocation outputs (write into preallocated numpy arrays) ────────────
import numpy as np
out_u32 = np.empty(len(candidates), dtype=np.uint32)
out_f64 = np.empty(len(candidates), dtype=np.float64)
mat_u32 = np.empty((3, 3), dtype=np.uint32)
fuzzgpu.levenshtein_batch_into("hello", candidates, out_u32)
fuzzgpu.jaro_winkler_batch_into("hello", candidates, out_f64)
fuzzgpu.levenshtein_cdist_into(["abc", "def", "xyz"], ["abd", "axy", "def"], mat_u32)

# ── Global sequence alignment (Gotoh 1982 affine gap) ────────────────────────
score = fuzzgpu.needleman_wunsch_affine("AGTACGCA", "TATGC", 2, -1, -3, -1)

# ── Fuzzy ratios (rapidfuzz-compatible) ──────────────────────────────────────
from fuzzgpu.fuzz import (
    ratio, partial_ratio, partial_ratio_alignment,
    token_sort_ratio, token_set_ratio,
    partial_token_sort_ratio, partial_token_set_ratio,
    QRatio, WRatio,
)

ratio("fuzzy was a bear", "fuzzy was a bear")           # 100.0
partial_ratio("hello", "oh hello there")               # 100.0
score, src, dst, length = partial_ratio_alignment("hello", "oh hello there")
# (100.0, 0, 3, 5)  ← window starts at char 3 of the longer string

token_sort_ratio("new york mets", "mets new york")      # 100.0
token_set_ratio("fuzzy was a bear", "fuzzy bear")       # 100.0

# ── Alignment helpers (rapidfuzz-compatible) ──────────────────────────────────
from fuzzgpu.distance import Levenshtein
ops   = fuzzgpu.editops("kitten", "sitting")           # top-level alias
codes = fuzzgpu.opcodes("kitten", "sitting")

# ── Search ────────────────────────────────────────────────────────────────────
from fuzzgpu.fuzz import extract, extractOne
best  = extractOne("hellp", ["hello", "world", "help"], score_cutoff=50.0)
# ("help", 88.88888888888889, 2)
top_3 = extract("apple", ["apply", "ape", "banana", "applesauce"],
                score_cutoff=50.0, limit=3)

# ── rapidfuzz.process-compatible API ─────────────────────────────────────────
from fuzzgpu.process import extract, extractOne, cdist
matrix = cdist(["hello", "world"], ["hallo", "wurld"])  # uses GPU/Rayon

# ── distance submodule (rapidfuzz.distance-compatible) ───────────────────────
from fuzzgpu.distance import Levenshtein, DamerauLevenshtein, Jaro, JaroWinkler
from fuzzgpu.distance import Hamming, OSA, Indel

Levenshtein.distance("kitten", "sitting")               # 3
Levenshtein.normalized_similarity("kitten", "sitting")  # 0.571...
Levenshtein.similarity(" abc ", "abc", processor=str.strip)  # 3
DamerauLevenshtein.distance("ca", "abc")                # 2  (unrestricted)
OSA.distance("ca", "abc")                               # 3  (OSA / rapidfuzz-compatible)
JaroWinkler.similarity("MARTHA", "MARHTA", prefix_weight=0.1)  # 0.9611...

# ── Hardware diagnostics ──────────────────────────────────────────────────────
print(fuzzgpu.gpu_info())        # "Intel(R) Iris(R) Xe Graphics (Vulkan)"
print(fuzzgpu.hardware_info())   # adapter, threshold, last routing stats

fuzzgpu.set_gpu_threshold(100)   # force GPU for batches >= 100 pairs
fuzzgpu.set_gpu_threshold(None)  # restore auto-selection
fuzzgpu.set_cpu_only(True)       # force CPU-only mode

Rust API

[dependencies]
fuzzgpu-core = "0.1.7"                                        # GPU + CPU fallback
# fuzzgpu-core = { version = "0.1.7", default-features = false } # CPU-only

use fuzzgpu_core::levenshtein::gpu_ext::GpuLevenshteinKernel;

fn main() -> fuzzgpu_core::Result<()> {
    let kernel = GpuLevenshteinKernel::get()?;

    // Batch
    let pairs = vec![("kitten", "sitting"), ("hello", "hullo")];
    let distances = kernel.compute(&pairs)?;   // [3, 1]

    // Cross-product matrix
    let matrix = kernel.compute_matrix(&["abc", "def"], &["abc", "xyz"])?;

    // Multi-op batch (one GPU dispatch + readback amortized across all ops)
    let mut batch = kernel.batch();
    batch.add(&pairs);
    batch.add(&[("foo", "bar"), ("test", "taste")]);
    let results = batch.execute()?;   // Vec<Vec<u32>>
    Ok(())
}

Available GPU kernels: GpuLevenshteinKernel, GpuJaroKernel, GpuNeedlemanAffineKernel, GpuDamerauKernel.

WebAssembly

cd crates/fuzzgpu-wasm
wasm-pack build --target web --release

import init, {
    levenshtein_distance, jaro_winkler, ratio, extract,
    needleman_wunsch, needleman_wunsch_affine,
} from './pkg/fuzzgpu_wasm.js';
await init();

levenshtein_distance('kitten', 'sitting');   // 3
jaro_winkler('MARTHA', 'MARHTA', 0.1);       // 0.9611...

// Needleman-Wunsch scores are i64 → JavaScript BigInt
needleman_wunsch('AGTACGCA', 'TATGC', 2n, -1n, -2n);        // 1n
needleman_wunsch_affine('AGTACGCA', 'TATGC', 2n, -1n, -3n, -1n); // -2n

Technical Architecture

Execution pipeline

                    ┌─────────────────────────┐
                    │     User Query / API    │
                    └────────────┬────────────┘
                                 │
                   Batch size / dataset assessment
                                 │
          ┌──────────────────────┴──────────────────────┐
          ▼                                             ▼
  Small batches (< threshold)              Large batches (≥ threshold)
          │                                             │
  ┌───────────────────┐                  ┌─────────────────────────────┐
  │  Rayon Parallel   │                  │   wgpu WebGPU Compute       │
  │  Myers bit-vector │                  │   WGSL shaders              │
  │  AVX512/AVX2/NEON │                  │   Metal / Vulkan / DX12     │
  └───────────────────┘                  └─────────────────────────────┘

Key design points

• Myers (1999) bit-vector — O(n) Levenshtein for patterns ≤ 64 chars, zero inner DP loop. Vectorized with AVX512 (8 texts/vector), AVX2 (4), NEON (2), portable scalar fallback. ISA detected at runtime via cached CPUID; override with FUZZGPU_SIMD=portable|neon|avx2|avx512.
• Unrestricted Damerau-Levenshtein — Full Lowrance-Wagner (1975) with non-adjacent transpositions. GPU shader keeps the full DP matrix in workgroup shared memory (≤ 32 chars ASCII).
• Gotoh (1982) affine gaps — 3-state recurrence, O(n) memory. GPU shader computes in f32; automatically routes to CPU when scoring parameters exceed f32 exact range (2²⁴).
• WGSL shaders require no adapter features — bit-vectors implemented as u32×2 pairs (no SHADER_INT64), works on every WebGPU backend including browsers and integrated GPUs.
• Metric-aware routing — iGPUs auto-route Jaro/Damerau to CPU (where AVX2 SIMD wins); discrete GPUs dispatch above a scaled threshold. hardware_info() shows every routing decision.
• Dispatch lock — serializes GPU calls across threads to work around gfx-rs/wgpu#10085 (heap corruption under ≥3 concurrent dispatchers on Intel iGPUs).
• Zero-copy Python bindings — Bound<PyString> pointers, no Vec<String> copies; *_into APIs write directly into caller-supplied numpy arrays.

GPU kernels

Project Structure

fuzzgpu/
├── crates/
│   ├── fuzzgpu-core/        # Core Rust engine + GPU shaders
│   ├── fuzzgpu-python/      # PyO3 Python extension
│   └── fuzzgpu-wasm/        # wasm-bindgen WebAssembly module
├── python/fuzzgpu/          # Python package wrapper + type stubs
│   ├── distance/            # rapidfuzz.distance-compatible modules
│   ├── fuzz.py              # rapidfuzz.fuzz-compatible scorers
│   └── process.py           # rapidfuzz.process-compatible helpers
├── fuzz/                    # libFuzzer targets + stable self-harness
├── benchmarks/              # Comparative benchmark scripts
├── tests/                   # Python pytest suite (174 tests)
└── docs/GPU_TESTING.md      # Fault injection & GPU test conventions

Building from Source

# Prerequisites: Rust 1.87+, Python 3.10+, maturin
git clone https://github.com/kuntal-devrat/fuzzgpu.git
cd fuzzgpu
maturin develop --release
pytest tests/ -v
cargo test --workspace

Environment Variables

License

MIT