StringZilla

StringZilla is a high-performance string operations library split into two layers:

1. StringZilla: A single-header C library and C++ wrapper for high-performance string operations (search, hashing, sorting, etc.).
2. StringZillas: Parallel CPU/GPU backends used for large-batch operations and accelerators (similarity scoring, fingerprinting).

Both layers are designed for portability across architectures (little-endian/big-endian, 32/64-bit), operating systems, and encodings (ASCII/UTF-8).

The sz_utf8_wordbreaks operation allows you to walk a UTF-8 string and yield individual words according to Unicode UAX-29 word-boundary rules. This ensures that complex tokens like "don't" or CJK (Chinese, Japanese, Korean) character runs are split according to human-readable expectations rather than simply splitting on raw whitespace.

Performance is optimized via a dispatcher that automatically selects the fastest available SIMD backend for your CPU, including haswell and icelake on x86 architectures.

StringZilla implements Levenshtein distance using an anti-diagonal evaluation approach rather than the traditional row-by-row method. This allows for better vectorization and parallel computation of cells within a diagonal, as they are independent.

This approach is suitable for:

• Approximate string matching
• Spell-checking
• Bioinformatics
• Weighted edit-distances (where substitution costs vary)

The sz_utf8_linebreaks operation identifies line-break opportunities in a UTF-8 string according to the Unicode UAX-14 rules. Instead of splitting solely on raw spaces or hard newlines, this kernel yields positions where a text layout engine is permitted to wrap text.

Performance is optimized via a dispatcher that selects the fastest available SIMD backend for the current CPU (e.g., haswell or icelake on x86, or ARM-based backends like NEON or SVE).

StringZilla's C implementation is split into two main components to handle different execution models:

• stringzilla/: Contains the single-threaded core ABI.
• stringzillas/: Contains the batch and parallel engines, including the C lowering of C++ and CUDA templates.

SIMD capabilities are determined during the build process via probes/ programs. These programs perform try-compilations and execute probes/run_capabilities.c to detect which SZ_USE_* SIMD tiers the toolchain can emit and the hardware can execute.

StringZilla provides high-performance memory kernels for common operations. The library uses a dispatcher that automatically selects the fastest available SIMD backend for your CPU (e.g., haswell, skylake, or icelake on x86).

Available operations:

• sz_copy: High-speed memory copying.
• sz_move: High-speed memory moving.
• sz_fill: High-speed memory filling.
• sz_lookup: High-speed memory lookup.

The sz_utf8_sentences operation walks a UTF-8 string and yields each sentence according to the Unicode UAX-29 sentence-boundary rules. It is designed to distinguish real sentence terminators from abbreviation dots or decimal points, preventing incorrect breaks on every period.

Performance is optimized via SIMD backends (including haswell and icelake on x86), with a dispatcher that automatically selects the fastest available backend for the running CPU.

StringZilla provides similarity engines designed for scoring large collections of strings against each other (cross-product matrices), which is useful for fuzzy matching and bioinformatics alignment.

Supported Algorithms

• Levenshtein: Computes minimum-cost edit distance byte by byte.
• Levenshtein UTF-8: Computes edit distance codepoint by codepoint for correct multibyte text handling.
• Needleman-Wunsch: Maximizes a signed global alignment score end-to-end.
• Smith-Waterman: Finds the best-scoring local subsequence.

Performance Metric: GCUPS

Throughput is measured in GCUPS (billions of cell updates per second). One GCUP represents one billion dynamic-programming cell updates. This is the standard metric for alignment efficiency.