enum sz_similarity_locality_tValues
sz_similarity_global_k | 0 | |
|---|---|---|
sz_similarity_local_k | 1 |
See also
sz_similarity_global_k, sz_similarity_local_k
Includes core APIs with hardware-specific backends:
sz_levenshtein_engine_init- prepares a batch of queries for the best capability of a mask, on the host or on one device.sz_levenshtein_engine_free- returns an engine's blocks to the allocator that built them.sz_levenshtein_distances- the [queries, candidates] edit distances of one batch, on the capability its engine was prepared for.sz_levenshtein_find_kernel- the kernel any of them would run, for a caller that keeps it.
Myers' bit-parallel algorithm treats every query as a pattern, packed 64 symbols per machine word, and every candidate streams one symbol per step. An engine prepares the whole batch's match masks once and advances several candidates per step - one per scalar state, four per YMM, eight per ZMM, one per thread on a device - so the tables are built once per batch rather than once per pair. A byte is its own mask class, while a rune takes the class its query assigned it or class zero when the query lacks it, which sz_levenshtein_symbol_t picks between. Strings of any length are accepted on either side; device queries are bounded by their length index. Long byte pairs on a device use an internal tiled wavefront for intra-pair parallelism.
The building blocks are public as well, for callers that own the loop nest: the query preparation and the transposes on the query side, and per backend a state, a vertical, and the init, step, any-active and score verbs over them, named by candidates per step, such as sz_levenshtein_u64x4_step_haswell. Scoring itself has one entry point per backend, such as sz_levenshtein_distances_haswell, which takes the caller's order and a bound past which a distance need not be exact.
API
Types
sz_similarity_locality_tDescribes the alignment scope for string similarity algorithms.
sz_similarity_objective_tDescribes the alignment objective for string similarity algorithms.
enum sz_similarity_objective_tValues
sz_minimize_distance_k | 0 | |
|---|---|---|
sz_maximize_score_k | 1 |
See also
sz_minimize_distance_k, sz_maximize_score_k
sz_similarity_packing_tDescribes how a similarity kernel packs work across SIMD lanes or a GPU warp's threads.
enum sz_similarity_packing_tone_pair_per_walk_k vectorizes within a single (query, candidate) pair, in anti-diagonal lanes — the intra-sequence form, used for one-off pairs and the ragged tail of a cross-product.
candidates_across_lanes_k vectorizes across many candidates of one shared query, one candidate per lane — the inter-sequence form that keeps every lane busy regardless of string length, the cross-product workhorse.
Values
sz_packing_one_pair_per_walk_k | 0 | |
|---|---|---|
sz_packing_candidates_across_lanes_k | 1 |
See also
sz_packing_one_pair_per_walk_k, sz_packing_candidates_across_lanes_k
sz_similarity_gaps_tDescribes the cost model for gap opening vs extension in string similarity algorithms.
enum sz_similarity_gaps_tValues
sz_gaps_linear_k | 1 | Linear costs require us to build only 1 DP matrix. |
|---|---|---|
sz_gaps_affine_k | 3 | Affine costs require us to build 3 DP matrices. |
See also
sz_levenshtein_symbol_tWhich symbols a batch counts, as the alphabet picks the transpose and the mask layout alike.
enum sz_levenshtein_symbol_tValues
sz_levenshtein_bytes_k | 0 | Every byte is its own symbol, and a distance counts bytes. |
|---|---|---|
sz_levenshtein_runes_k | 1 | Every UTF-8 rune is one symbol, each maximal ill-formed subpart decoding to one U+FFFD. |
sz_kernel_levenshtein_engine_init_tSignature of every sz_levenshtein_engine_init kernel.
typedef sz_status_t(*) sz_kernel_levenshtein_engine_init_t(struct sz_levenshtein_engine_t *, sz_strings_view_t const *, sz_levenshtein_symbol_t, sz_allocator_t *, sz_stream_t);sz_kernel_levenshtein_distances_tSignature of every sz_levenshtein_distances kernel, at either alphabet.
typedef sz_status_t(*) sz_kernel_levenshtein_distances_t(struct sz_levenshtein_engine_t *, sz_strings_view_t const *, sz_size_t const *, sz_size_t const *, sz_size_t, sz_size_t *, sz_size_t, sz_stream_t);Functions
sz_levenshtein_engine_initPrepares queries into one block from allocator, for the best capability of capabilities that has an init kernel.
sz_status_t sz_levenshtein_engine_init(
sz_levenshtein_engine_t *engine,
sz_strings_view_t const *queries,
sz_levenshtein_symbol_t symbol,
sz_capability_t capabilities,
sz_allocator_t *allocator,
sz_stream_t stream);Backends
sz_levenshtein_engine_initserialhaswellskylakeicelakeneoncudablackwellrocmmetal
Parameters
engine | out | Untouched unless the call succeeds; sz_levenshtein_engine_free frees it. |
|---|---|---|
queries | in | The patterns every candidate is scored against, in any layout over host-readable texts, whose symbols and classes size the block. |
symbol | in | Whether a distance counts bytes or UTF-8 runes. |
capabilities | in | One device's capabilities, like sz_capabilities_enabled_cpu or sz_capabilities_enabled_cuda report; its group picks the CPU or a GPU vendor. |
allocator | in | Source of the engine's blocks, or STRINGZILLA_NULL for sz_allocator_init_unified_best of capabilities. |
stream | in | Null on the CPU. On a GPU, the stream to queue on, also naming the device: a cudaStream_t, a hipStream_t, or an id<MTLCommandQueue>; null for the default. |
Notes
May join stream; no scoring verb ever does.
Statuses
sz_missing_kernel_kNo capability of the mask has an init.sz_unexpected_dimensions_kOn a device, an unrepresentable query length.sz_device_memory_mismatch_kOn a device, memory or astreamthe device cannot use.
sz_levenshtein_engine_freeReturns both of engine 's blocks to the allocator that built them, once the work queued on stream is done with them, and leaves it empty.
void sz_levenshtein_engine_free(
sz_levenshtein_engine_t *engine,
sz_stream_t stream);sz_levenshtein_distancesEdit distances from every prepared query to every candidate, by the kernel of the capability engine was prepared for, exact up to bound.
sz_status_t sz_levenshtein_distances(
sz_levenshtein_engine_t *engine,
sz_strings_view_t const *candidates,
sz_size_t const *symbol_counts,
sz_size_t const *order,
sz_size_t bound,
sz_size_t *distances,
sz_size_t distances_stride,
sz_stream_t stream);Backends
sz_levenshtein_distancesserialhaswellskylakeicelakeneoncudablackwellrocmmetal
A query prepared once scores any number of candidate batches: the engine's scratch only grows, so batches no larger than an earlier one allocate nothing. A host sweep advances a few candidates together and costs as long as the longest of them, so an order grouping similar lengths keeps it short, and it stops early once every candidate it holds is past bound.
Parameters
engine | in | The prepared batch; its round scratch may grow. It keeps no stream and no round state on a device, so any number of that device's streams may score it at once. |
|---|---|---|
candidates | in | The texts, on the residency engine was built for: any layout on the CPU, and on a device a tape sz_strings_to_tape_best wrote into a unified allocator. |
symbol_counts | in | Each candidate's length in the engine's symbols by candidate index, as sz_levenshtein_utf8_runes counts runes, or null to count them as the sweep goes. |
order | in | The visiting order, a permutation of the candidate indices, or null for the engine's own. Neither it nor symbol_counts changes a distance, and a device engine, which orders and counts candidates itself, reads neither. |
bound | in | The largest distance reported exactly; a candidate past it reports bound + 1 on every backend. STRINGZILLA_SIZE_MAX keeps every distance exact. |
distances | out | The [count, candidates] distances, query q at distances[q * stride + c], device-reachable on a device. |
distances_stride | in | Entries from one query's row to the next, at least the count. |
stream | in | Null on the CPU. On a GPU, the stream to queue on, which also names the device the round runs on; null for the default. |
Notes
Grows the engine's host scratch when a round needs more than the last one did; never joins, so the caller joins stream before reading distances.
Statuses
sz_unexpected_dimensions_kdistances_strideis under the candidate count.sz_missing_kernel_kAn empty engine.sz_device_memory_mismatch_kOn a device, an engine, an output, an accessor, a tape or a stream the device ofstreamcannot use.
sz_levenshtein_engine_init_serialPrepares queries into one block from allocator, for the serial kernels.
sz_status_t sz_levenshtein_engine_init_serial(
sz_levenshtein_engine_t *engine,
sz_strings_view_t const *queries,
sz_levenshtein_symbol_t symbol,
sz_allocator_t *allocator,
sz_stream_t stream);Backends
sz_levenshtein_engine_initserialhaswellskylakeicelakeneoncudablackwellrocmmetal
Parameters
engine | out | Untouched unless the call succeeds; sz_levenshtein_engine_free frees it. |
|---|---|---|
queries | in | The patterns every candidate is scored against, in any layout over host-readable texts, whose symbols and classes size the block. |
symbol | in | Whether a distance counts bytes or UTF-8 runes. |
allocator | in | Source of the engine's blocks, or STRINGZILLA_NULL for sz_allocator_init_unified_serial. |
stream | in | Null on the CPU. |
Statuses
sz_unexpected_dimensions_kAn unrepresentable query length.
sz_levenshtein_distances_serialEdit distances from every prepared query to every candidate, by the kernel of the capability engine was prepared for, exact up to bound.
sz_status_t sz_levenshtein_distances_serial(
sz_levenshtein_engine_t *engine,
sz_strings_view_t const *candidates,
sz_size_t const *symbol_counts,
sz_size_t const *order,
sz_size_t bound,
sz_size_t *distances,
sz_size_t distances_stride,
sz_stream_t stream);Backends
sz_levenshtein_distancesserialhaswellskylakeicelakeneoncudablackwellrocmmetal
A query prepared once scores any number of candidate batches: the engine's scratch only grows, so batches no larger than an earlier one allocate nothing. A host sweep advances a few candidates together and costs as long as the longest of them, so an order grouping similar lengths keeps it short, and it stops early once every candidate it holds is past bound.
Parameters
engine | in | The prepared batch; its round scratch may grow. It keeps no stream and no round state on a device, so any number of that device's streams may score it at once. |
|---|---|---|
candidates | in | The texts, on the residency engine was built for: any layout on the CPU, and on a device a tape sz_strings_to_tape_best wrote into a unified allocator. |
symbol_counts | in | Each candidate's length in the engine's symbols by candidate index, as sz_levenshtein_utf8_runes counts runes, or null to count them as the sweep goes. |
order | in | The visiting order, a permutation of the candidate indices, or null for the engine's own. Neither it nor symbol_counts changes a distance, and a device engine, which orders and counts candidates itself, reads neither. |
bound | in | The largest distance reported exactly; a candidate past it reports bound + 1 on every backend. STRINGZILLA_SIZE_MAX keeps every distance exact. |
distances | out | The [count, candidates] distances, query q at distances[q * stride + c], device-reachable on a device. |
distances_stride | in | Entries from one query's row to the next, at least the count. |
stream | in | Null on the CPU. On a GPU, the stream to queue on, which also names the device the round runs on; null for the default. |
Notes
Grows the engine's host scratch when a round needs more than the last one did; never joins, so the caller joins stream before reading distances.
Statuses
sz_unexpected_dimensions_kdistances_strideis under the candidate count.sz_missing_kernel_kAn empty engine.sz_device_memory_mismatch_kOn a device, an engine, an output, an accessor, a tape or a stream the device ofstreamcannot use.
sz_levenshtein_find_kernelFinds the Levenshtein kernel of kind, from the best of capabilities.
sz_status_t sz_levenshtein_find_kernel(
sz_kernel_kind_t kind,
sz_capability_t capabilities,
sz_kernel_punned_t *kernel,
sz_capability_t *capability);Parameters
kind | in | The verb whose kernel to find. |
|---|---|---|
capabilities | in | The mask to pick the best capability from. |
kernel | out | The kernel, or null when none of capabilities has it. |
capability | out | The capability the kernel belongs to, or zero. |
Statuses
sz_missing_kernel_ksz_missing_library_kHeader-only.