typedef sz_status_t(*) sz_kernel_overlap_engine_init_t(struct sz_overlap_engine_t *, sz_strings_view_t const *, sz_size_t const *, sz_size_t, sz_size_t, sz_allocator_t *, sz_stream_t);A window is a fixed-width byte n-gram, and the overlap of two texts at that width is the count of one's windows that occur in the other, over whichever of the two has more. Every query is hashed once into one B-tree over every width's window hashes, and every candidate then streams through the forest, hashing its own windows and probing. Nothing is stored per candidate, so the candidates may change round to round while the queries and the widths stay.
Window hashes come from a prefix difference, H(i, w) = P(i + w) − P(i) × bʷ mod p, which costs one modular multiply-add at any width and any offset; widths need not form a doubling chain. The modulus is a 32-bit prime chosen for collision weight, so a window hash is full-width.
Public API
- sz_overlap_engine_init → prepares a batch of queries for the best capability of a mask, on the host or on one device;
- sz_overlap_scores → the [queries,candidates,widths] match counts of one round, on the capability its engine was prepared for;
- sz_overlap_engine_free → returns both of the engine's blocks;
- sz_overlap_find_kernel → the kernel either would run, for a caller that keeps it.
Every register-level step behind these - the prefix chain, the window hashing, the key sort and the B-tree probe - is public per backend in overlap/serial.h and its SIMD backends, named by positions per step, such as sz_overlap_f64x4_prefix_hash_step_haswell, so a caller driving its own loops binds those steps and skips these verbs entirely. The tree layout is the same on every backend, so any of them may probe it.
API
Types
sz_kernel_overlap_engine_init_tSignature of every sz_overlap_engine_init kernel.
sz_kernel_overlap_scores_tSignature of every sz_overlap_scores kernel.
typedef sz_status_t(*) sz_kernel_overlap_scores_t(struct sz_overlap_engine_t *, sz_strings_view_t const *, sz_f32_t, sz_u32_t *, sz_size_t, sz_size_t, sz_stream_t);Functions
sz_overlap_engine_initPrepares queries into one block from allocator, for the best capability of capabilities that has an init kernel.
sz_status_t sz_overlap_engine_init(
sz_overlap_engine_t *engine,
sz_strings_view_t const *queries,
sz_size_t const *window_widths,
sz_size_t window_widths_count,
sz_size_t candidates_budget,
sz_capability_t capabilities,
sz_allocator_t *allocator,
sz_stream_t stream);Backends
sz_overlap_engine_initserialhaswellskylakeneoncudablackwellrocmmetal
Every width's window hashes of one query share that query's B-tree, so its sort runs once per batch rather than once per round, and the probe depth grows only logarithmically as widths are added to the batch.
Parameters
engine | out | Left untouched unless the call succeeds. |
|---|---|---|
queries | in | The texts whose windows are sorted into the forest; read on the host. |
window_widths | in | Window widths in bytes; a width past a text scores zero for its pairs. |
window_widths_count | in | Number of widths, which is the last axis of every output. |
candidates_budget | in | Candidates one round may carry, for a backend whose rounds keep state per candidate, zero asking for its default; one that keeps none ignores it. |
capabilities | in | One device's capabilities, like sz_capabilities_enabled_cpu or sz_capabilities_enabled_metal report; its group picks the CPU or a GPU vendor. |
allocator | in | Source of the forest's block, or STRINGZILLA_NULL for sz_allocator_init_unified_best of capabilities; stored by value, so sz_overlap_engine_free needs no allocator of its own. |
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_kZero widths.sz_device_memory_mismatch_kOn a device, memory or astreamit cannot use.
sz_overlap_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_overlap_engine_free(
sz_overlap_engine_t *engine,
sz_stream_t stream);sz_overlap_scoresWindow overlap of every prepared query with every candidate, at every width of the batch, by the kernel of the capability engine was prepared for, exact within radius.
sz_status_t sz_overlap_scores(
sz_overlap_engine_t *engine,
sz_strings_view_t const *candidates,
sz_f32_t radius,
sz_u32_t *matches,
sz_size_t matches_query_stride,
sz_size_t matches_candidate_stride,
sz_stream_t stream);Backends
sz_overlap_scoresserialhaswellskylakeneoncudablackwellrocmmetal
A batch of queries prepared once scores any number of candidate batches, and a host round block only grows, so a batch within the longest seen allocates nothing. A width's count is the candidate's windows the query also holds. A pair's misses are the longer side's windows the other leaves unmatched, summed over every width, and its distance is those misses over the longer side's windows in all. A pair within radius is counted exactly; a pair past it counts zero at every width, on every backend, or exactly when within rounding of the share, less than 2⁻²⁴ past it. A pair is dropped once its misses provably pass that share of its longer side, often from the two lengths alone, before a byte is read.
The count of query q, candidate c and width w sits at:
* matches[q * matches_query_stride + c * matches_candidate_stride + w]
* Parameters
engine | in | The prepared forest; a host round block grows here and is never shrunk. A device engine keeps no stream, so on CUDA any number of streams may score it at once; on Metal its one round block orders the rounds on the device's one queue. |
|---|---|---|
candidates | in | The texts whose windows are probed against the forest's, on the residency the 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. |
radius | in | The share of its longer side's windows a pair may miss, in [0, 1]; 1 or more keeps every count exact. |
matches | out | Counts with a unit-strided width axis, laid out as shown below. |
matches_query_stride | in | Entries from one query's plane to the next, at least the candidates times matches_candidate_stride. |
matches_candidate_stride | in | Entries between candidate rows, at least the widths the engine was prepared at. |
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
- Asymmetric: a candidate's window occurrences count against a query's distinct windows, so swapping sides changes the count when either repeats a window.
- Never joins, so the caller joins
streambefore readingmatches.
Statuses
sz_unexpected_dimensions_kEither stride is under the axis it spans.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_overlap_engine_init_serialPrepares queries into one block from allocator, for the serial kernels.
sz_status_t sz_overlap_engine_init_serial(
sz_overlap_engine_t *engine,
sz_strings_view_t const *queries,
sz_size_t const *window_widths,
sz_size_t window_widths_count,
sz_size_t candidates_budget,
sz_allocator_t *allocator,
sz_stream_t stream);Backends
sz_overlap_engine_initserialhaswellskylakeneoncudablackwellrocmmetal
Parameters
engine | out | Left untouched unless the call succeeds. |
|---|---|---|
queries | in | The texts whose windows are sorted into the forest; read on the host. |
window_widths | in | Window widths in bytes; a width past a text scores zero for its pairs. |
window_widths_count | in | Number of widths, which is the last axis of every output. |
candidates_budget | in | Candidates one round may carry; the serial rounds keep no state per candidate and ignore it. |
allocator | in | Source of the forest's block, or STRINGZILLA_NULL for sz_allocator_init_unified_serial; stored by value, so sz_overlap_engine_free needs no allocator of its own. |
stream | in | Null on the CPU. |
Statuses
sz_unexpected_dimensions_kZero widths.
sz_overlap_scores_serialWindow overlap of every prepared query with every candidate, at every width of the batch, by the kernel of the capability engine was prepared for, exact within radius.
sz_status_t sz_overlap_scores_serial(
sz_overlap_engine_t *engine,
sz_strings_view_t const *candidates,
sz_f32_t radius,
sz_u32_t *matches,
sz_size_t matches_query_stride,
sz_size_t matches_candidate_stride,
sz_stream_t stream);Backends
sz_overlap_scoresserialhaswellskylakeneoncudablackwellrocmmetal
A batch of queries prepared once scores any number of candidate batches, and a host round block only grows, so a batch within the longest seen allocates nothing. A width's count is the candidate's windows the query also holds. A pair's misses are the longer side's windows the other leaves unmatched, summed over every width, and its distance is those misses over the longer side's windows in all. A pair within radius is counted exactly; a pair past it counts zero at every width, on every backend, or exactly when within rounding of the share, less than 2⁻²⁴ past it. A pair is dropped once its misses provably pass that share of its longer side, often from the two lengths alone, before a byte is read.
The count of query q, candidate c and width w sits at:
* matches[q * matches_query_stride + c * matches_candidate_stride + w]
* Parameters
engine | in | The prepared forest; a host round block grows here and is never shrunk. A device engine keeps no stream, so on CUDA any number of streams may score it at once; on Metal its one round block orders the rounds on the device's one queue. |
|---|---|---|
candidates | in | The texts whose windows are probed against the forest's, on the residency the 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. |
radius | in | The share of its longer side's windows a pair may miss, in [0, 1]; 1 or more keeps every count exact. |
matches | out | Counts with a unit-strided width axis, laid out as shown below. |
matches_query_stride | in | Entries from one query's plane to the next, at least the candidates times matches_candidate_stride. |
matches_candidate_stride | in | Entries between candidate rows, at least the widths the engine was prepared at. |
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
- Asymmetric: a candidate's window occurrences count against a query's distinct windows, so swapping sides changes the count when either repeats a window.
- Never joins, so the caller joins
streambefore readingmatches.
Statuses
sz_unexpected_dimensions_kEither stride is under the axis it spans.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_overlap_find_kernelFinds the overlap kernel of kind, from the best of capabilities.
sz_status_t sz_overlap_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.