StringZillas for C and C++

StringZillas is a bulk-processing framework for fingerprinting and fuzzy matching of web-scale text corpora and bioinformatics sequences. Unlike the single-string stringzilla library, every operation here is a stateful engine that you initialize once and reuse across many calls. Each engine consumes large collections of strings at once, scoring them as a cross-product matrix or sketching them into compact fingerprints. And each call runs across a chosen slice of CPU cores or a CUDA GPU, selected through a lightweight device handle you pass on every call.

Installation

StringZillas is compiled, not header-only: the heavy template instantiations for every engine are baked into precompiled libraries so you link them rather than recompile them. The CMake project is named stringzilla, and it exposes four StringZillas library targets gated by two options.

The CPU libraries stringzillas::cpus_shared and stringzillas::cpus_static are built when STRINGZILLAS_BUILD_SHARED is on. The CUDA libraries stringzillas::cuda_shared and stringzillas::cuda_static are additionally built when STRINGZILLA_BUILD_CUDA is on. The longer stringzilla::stringzillas_cpus_shared spelling still resolves, and likewise for the rest.

Pull the project in with FetchContent or add_subdirectory, then link a target:

include(FetchContent)
FetchContent_Declare(
    stringzilla
    GIT_REPOSITORY https://github.com/ashvardanian/stringzilla
    GIT_TAG main)
set(STRINGZILLAS_BUILD_SHARED ON CACHE BOOL "" FORCE)
FetchContent_MakeAvailable(stringzilla)

add_executable(my_app main.c)
target_link_libraries(my_app PRIVATE stringzillas::cpus_shared)

To also build and link the GPU engines, enable CUDA and link the matching target:

set(STRINGZILLA_BUILD_CUDA ON CACHE BOOL "" FORCE)
# ... after FetchContent_MakeAvailable ...
target_link_libraries(my_app PRIVATE stringzillas::cuda_shared)

An installed build exposes the same engines as their own CMake package, separate from the single-string stringzilla one:

find_package(stringzillas REQUIRED)

target_link_libraries(my_app PRIVATE stringzillas::cpus_shared)

Only the shared variants are exported: the static archives are assembled from OBJECT libraries that an installed package cannot carry, so stringzillas::cpus_static and stringzillas::cuda_static are reachable in-tree only, and ship the same engines for local testing and benchmarking. All four propagate the headers and the SZ_DYNAMIC_DISPATCH=1 interface definition, so a consumer externs the precompiled engines instead of re-instantiating them.

The public C surface is one header:

#include <stringzillas/stringzillas.h>

The Engine Model

Every StringZillas operation follows the same lifecycle: an opaque engine handle, created with *_init, called many times, and released with *_free. The engine owns its scratch arenas and pre-configured costs, so reusing one handle across batches amortizes setup over the whole corpus.

The C handles are opaque pointers:

typedef void *szs_levenshtein_distances_t;
typedef void *szs_levenshtein_distances_utf8_t;
typedef void *szs_needleman_wunsch_scores_t;
typedef void *szs_smith_waterman_scores_t;
typedef void *szs_fingerprints_t;

Every call also takes a device scope, an opaque handle describing where the work runs:

typedef void *szs_device_scope_t;

sz_status_t szs_device_scope_init_default(szs_device_scope_t *scope, char const **error_message);
sz_status_t szs_device_scope_init_cpu_cores(sz_size_t cpu_cores, szs_device_scope_t *scope, char const **error_message);
sz_status_t szs_device_scope_init_gpu_device(sz_size_t gpu_device, szs_device_scope_t *scope, char const **error_message);
sz_status_t szs_device_scope_get_cpu_cores(szs_device_scope_t scope, sz_size_t *cpu_cores, char const **error_message);
sz_status_t szs_device_scope_get_gpu_device(szs_device_scope_t scope, sz_size_t *gpu_device, char const **error_message);
sz_status_t szs_device_scope_get_capabilities(szs_device_scope_t scope, sz_capability_t *capabilities, char const **error_message);
void szs_device_scope_free(szs_device_scope_t scope);

szs_device_scope_init_default picks system defaults. szs_device_scope_init_cpu_cores targets a fraction of CPU cores: pass 0 for all cores, 1 to use only the calling thread. szs_device_scope_init_gpu_device targets a specific GPU by device index. One device scope can be shared across engines and calls, then freed with szs_device_scope_free.

Inputs: Sequences and Apache Arrow Tapes

Engines accept three input layouts, all describing a collection of strings. The flexible sz_sequence_t (from the stringzilla headers) is a std::vector<std::string_view>-like structure indexed by a getter callback. The two tape types are Apache Arrow-like contiguous layouts: one data blob plus count + 1 offsets, where lengths[i] = offsets[i + 1] - offsets[i].

typedef struct sz_sequence_u32tape_t {
    sz_cptr_t data;
    sz_u32_t const *offsets;
    sz_size_t count;
} sz_sequence_u32tape_t;

typedef struct sz_sequence_u64tape_t {
    sz_cptr_t data;
    sz_u64_t const *offsets;
    sz_size_t count;
} sz_sequence_u64tape_t;

Use sz_sequence_u32tape_t for space-efficient collections under 4 GB and sz_sequence_u64tape_t for larger ones. Each engine exposes a call on each layout, for example szs_levenshtein_distances, szs_levenshtein_distances_u32tape, and szs_levenshtein_distances_u64tape.

Unified Memory

For zero-copy sharing between the CPU and the GPU, initialize the allocator with unified memory. On CUDA-capable systems it uses cudaMallocManaged, so the same buffers are reachable from both host and device.

sz_status_t sz_memory_allocator_init_unified(sz_memory_allocator_t *alloc, char const **error_message);
void *szs_unified_alloc(sz_size_t size_bytes);
void szs_unified_free(void *ptr, sz_size_t size_bytes);

Pass the resulting sz_memory_allocator_t * as the alloc argument of any engine's *_init, or pass NULL to use the default allocator.

The Cross Product Convention

Every similarity engine scores each queries[query_index] against each candidates[candidate_index] and writes cell (query_index, candidate_index) to results[query_index * results_row_stride + candidate_index]. The results_row_stride is the number of elements between consecutive query rows, and must be at least the candidate count, so the matrix can live inside a wider allocation. Passing candidates == NULL requests symmetric self-similarity of queries: the lower triangle is computed and mirrored, with rows == columns.

Edit Distances

The Levenshtein engines compute the minimum-cost edit distance between strings as an unsigned sz_size_t matrix. szs_levenshtein_distances compares byte by byte, while szs_levenshtein_distances_utf8 compares codepoint by codepoint for correct results on multibyte UTF-8 text.

Both *_init calls take per-edit costs and a gap model. With open == extend the gaps are linear (every inserted or deleted run costs the same per position); with extend < open the gaps are affine (opening a gap is dearer than extending it).

sz_status_t szs_levenshtein_distances_init(
    sz_error_cost_t match, sz_error_cost_t mismatch, sz_error_cost_t open, sz_error_cost_t extend,
    sz_memory_allocator_t const *alloc, sz_capability_t capabilities,
    szs_levenshtein_distances_t *engine, char const **error_message);

sz_status_t szs_levenshtein_distances(
    szs_levenshtein_distances_t engine, szs_device_scope_t device,
    sz_sequence_t const *queries, sz_sequence_t const *candidates,
    sz_size_t *results, sz_size_t results_row_stride,
    char const **error_message);

void szs_levenshtein_distances_free(szs_levenshtein_distances_t engine);

The UTF-8 variant mirrors this exactly with szs_levenshtein_distances_utf8_init, szs_levenshtein_distances_utf8, and szs_levenshtein_distances_utf8_free, plus _u32tape and _u64tape call variants.

A self-contained byte-distance example over a tiny corpus:

#include <assert.h>
#include <stringzillas/stringzillas.h>

void run(void) {
    char const *strings[] = {"listen", "silent", "kitten"};
    sz_size_t lengths[] = {6, 6, 6};
    sz_sequence_t queries;
    queries.count = 3;
    queries.handle = strings;
    queries.get_start = NULL; // ... wire your own getters in real code
    queries.get_length = NULL;

    szs_device_scope_t device = NULL;
    char const *error = NULL;
    sz_status_t status = szs_device_scope_init_default(&device, &error);
    assert(status == sz_success_k);

    szs_levenshtein_distances_t engine = NULL;
    status = szs_levenshtein_distances_init(
        0, 1, 1, 1, // ... match, mismatch, open, extend (linear gaps)
        NULL, szs_capabilities(), &engine, &error);
    assert(status == sz_success_k);

    sz_size_t results[9];
    status = szs_levenshtein_distances(engine, device, &queries, NULL, results, 3, &error);
    assert(status == sz_success_k);
    assert(results[0] == 0); // ... distance of "listen" to itself

    szs_levenshtein_distances_free(engine);
    szs_device_scope_free(device);
    (void)lengths;
}

Alignment Scores

For sequence alignment the engines maximize a signed similarity score, written into an sz_ssize_t matrix. szs_needleman_wunsch_scores performs global alignment (Needleman-Wunsch, end-to-end), while szs_smith_waterman_scores performs local alignment (Smith-Waterman, best-scoring subsequence). These are the workhorses of bioinformatics: aligning DNA, RNA, and protein sequences against reference databases at scale.

Both engines take a compact, class-based substitution matrix instead of a full 256x256 table. A 256-entry byte_to_class array maps each input byte to one of 32 character classes, and a row-major 32x32 class_substitution_costs matrix gives the signed cost between any two classes. This folds the common biological alphabets (and ASCII case-folding tables) into a SIMD-friendly 32-class form while still expressing matrices like BLOSUM62 or NUC44. Gap costs use the same open and extend pair as the edit-distance engines.

sz_status_t szs_needleman_wunsch_scores_init(
    sz_u8_t const *byte_to_class, sz_error_cost_t const *class_substitution_costs,
    sz_error_cost_t open, sz_error_cost_t extend,
    sz_memory_allocator_t const *alloc, sz_capability_t capabilities,
    szs_needleman_wunsch_scores_t *engine, char const **error_message);

sz_status_t szs_needleman_wunsch_scores(
    szs_needleman_wunsch_scores_t engine, szs_device_scope_t device,
    sz_sequence_t const *queries, sz_sequence_t const *candidates,
    sz_ssize_t *results, sz_size_t results_row_stride,
    char const **error_message);

void szs_needleman_wunsch_scores_free(szs_needleman_wunsch_scores_t engine);

Smith-Waterman exposes the identical shape through szs_smith_waterman_scores_init, szs_smith_waterman_scores, and szs_smith_waterman_scores_free, and both engines provide _u32tape and _u64tape call variants.

A self-contained protein-style alignment setup:

#include <assert.h>
#include <stringzillas/stringzillas.h>

void run(void) {
    sz_u8_t byte_to_class[256] = {0};        // ... map each byte to one of 32 classes
    sz_error_cost_t class_costs[32 * 32] = {0}; // ... row-major 32x32 substitution costs

    szs_device_scope_t device = NULL;
    char const *error = NULL;
    sz_status_t status = szs_device_scope_init_default(&device, &error);
    assert(status == sz_success_k);

    szs_smith_waterman_scores_t engine = NULL;
    status = szs_smith_waterman_scores_init(
        byte_to_class, class_costs,
        4, 1, // ... gap open and extend (affine: extend < open)
        NULL, szs_capabilities(), &engine, &error);
    assert(status == sz_success_k);

    char const *proteins[] = {"MKExample", "MKExampla"};
    sz_size_t lengths[] = {9, 9};
    sz_sequence_t queries;
    queries.count = 2;
    queries.handle = proteins;
    queries.get_start = NULL;
    queries.get_length = NULL;

    sz_ssize_t results[4];
    status = szs_smith_waterman_scores(engine, device, &queries, NULL, results, 2, &error);
    assert(status == sz_success_k);

    szs_smith_waterman_scores_free(engine);
    szs_device_scope_free(device);
    (void)lengths;
}

Fingerprints

The fingerprints engine sketches each string into a fixed-width MinHash plus a Count-Min-Sketch, so two near-duplicate documents land on overlapping hash dimensions even after small edits. This powers near-duplicate detection and multi-pattern search across web-scale corpora: a single pass over a tape yields a compact signature per document that you can index, cluster, or compare cheaply.

The engine rolls several hash windows of different widths over each string and keeps the minimum hash per dimension. dimensions is the total fingerprint width (ideally a multiple of 64 * window_widths_count); alphabet_size tunes the rolling base (256 for binary, 128 for ASCII, 4 for DNA, 22 for protein); window_widths lists the n-gram window sizes, or NULL for the defaults [3, 4, 5, 7, 9, 11, 15, 31]. A seed makes every per-dimension multiplier reproducible.

sz_status_t szs_fingerprints_init(
    sz_size_t dimensions, sz_size_t alphabet_size,
    sz_size_t const *window_widths, sz_size_t window_widths_count, sz_u64_t seed,
    sz_memory_allocator_t const *alloc, sz_capability_t capabilities,
    szs_fingerprints_t *engine, char const **error_message);

sz_status_t szs_fingerprints_sequence(
    szs_fingerprints_t engine, szs_device_scope_t device,
    sz_sequence_t const *texts,
    sz_u32_t *min_hashes, sz_size_t min_hashes_stride,
    sz_u32_t *min_counts, sz_size_t min_counts_stride,
    char const **error_message);

void szs_fingerprints_free(szs_fingerprints_t engine);

Each call writes the MinHash sketch into min_hashes and the Count-Min-Sketch into min_counts, with the per-text strides giving the byte distance between consecutive results. Tape inputs use szs_fingerprints_u32tape and szs_fingerprints_u64tape.

Aim for at least 64 dimensions per window width: that saturates AVX-512 register utilization and activates a full 32-thread CUDA warp (64 for an AMD wave), and for Tweet-sized strings 64 dimensions of each of [3, 5, 7, 9] is a solid default.

#include <assert.h>
#include <stringzillas/stringzillas.h>

void run(void) {
    szs_device_scope_t device = NULL;
    char const *error = NULL;
    sz_status_t status = szs_device_scope_init_default(&device, &error);
    assert(status == sz_success_k);

    szs_fingerprints_t engine = NULL;
    status = szs_fingerprints_init(
        256, 256, // ... 256 dimensions, byte alphabet
        NULL, 0,  // ... default window widths
        42,       // ... reproducibility seed
        NULL, szs_capabilities(), &engine, &error);
    assert(status == sz_success_k);

    char const *docs[] = {"the quick brown fox", "the quick brown dog"};
    sz_size_t lengths[] = {19, 19};
    sz_sequence_t texts;
    texts.count = 2;
    texts.handle = docs;
    texts.get_start = NULL;
    texts.get_length = NULL;

    sz_u32_t hashes[2 * 256];
    sz_u32_t counts[2 * 256];
    status = szs_fingerprints_sequence(
        engine, device, &texts,
        hashes, 256 * sizeof(sz_u32_t),
        counts, 256 * sizeof(sz_u32_t),
        &error);
    assert(status == sz_success_k);

    szs_fingerprints_free(engine);
    szs_device_scope_free(device);
    (void)lengths;
}

Devices and Parallelism

The device scope is the single knob for where and how widely an engine runs, and the same engine handle can be driven by any scope.

Scope	Initializer	Targets
Default	szs_device_scope_init_default	System defaults
CPU slice	szs_device_scope_init_cpu_cores	A fraction of CPU cores
GPU device	szs_device_scope_init_gpu_device	One CUDA GPU

A CPU slice spreads the cross-product (or the corpus of texts) across a thread pool, so you can reserve cores for other work by asking for fewer than all of them. A GPU device offloads the whole batch to one CUDA device, where each engine routes string pairs into size-tiered kernels. Unified memory is what makes the GPU path seamless: allocate inputs and outputs through the unified allocator, and the same pointers are valid on host and device with no explicit copies.

The underlying C++ engines are templated on an executor: dummy_executor_t runs serially, and forkunion_executor_t is the preferred library-grade thread pool, wrapping a ForkUnion pool through its C API so the compiled runtime handles NUMA-aware placement. The C ABI hides this choice behind the device scope, picking the right executor for the cores or GPU you requested.

Runtime Dispatch and Capabilities

Each *_init takes a sz_capability_t mask that pins which instruction set the engine uses. Query the current machine's capabilities and pass them straight through to let StringZillas pick the best available backend:

sz_capability_t szs_capabilities(void);

On x86 this dispatches across Westmere, Goldmont, Haswell (AVX2), Skylake, and Ice Lake (AVX-512) backends; on Arm across NEON, SVE, and SVE2; and on CUDA across the base SIMT, Kepler video-SIMD, and Hopper DPX tiers. The precompiled libraries carry every backend for their platform and select per call at runtime, so one binary runs optimally across a fleet of mixed hardware. You can read back what a device scope resolved to with szs_device_scope_get_capabilities.

Version helpers round out the surface:

int szs_version_major(void);
int szs_version_minor(void);
int szs_version_patch(void);