C API reference
Every function, type and constant of kwker.h, the C library's header (Kwker 0.1.0). Per-type functions are written
kwker_<s>_... here, with the key types each is declared for.
C++ users get the same functions through kwker.hpp: header-only templates over the key type in namespace
kwker (kwker::sort(v), kwker::top_k(v, 10), ...), documented at the top of that header.
Conventions
Kwker C API: sorting, selection, top-k, argsort and key-value sorting of numeric arrays, with the fastest engine for the CPU chosen at run time (AVX-512, AVX2, NEON or portable). Link libkwker_c.a (with -lstdc++ -lm -lpthread -ldl) or libkwker_c.so.
Functions are named kwker_<s>_<operation>, such as kwker_f64_sort(a, n), with s the key type. They return 0, or -1 for an invalid argument, and then write nothing.
Key types (suffix: C type): u8 uint8_t, i8 int8_t, u16 uint16_t, i16 int16_t, u32 uint32_t, i32 int32_t, f32 float, u64 uint64_t, i64 int64_t, f64 double; f16 and bf16 as uint16_t bits, f8e5m2 and f8e4m3 as uint8_t bits.
Order: order is KWKER_ASCENDING (0, smallest first) or KWKER_DESCENDING (largest first), or'ed with
KWKER_NANS_FIRST to put NaNs first instead of last.
Notes: floating-point keys sort -0.0 before +0.0, and NaNs as one block: positive NaNs by bits ascending, then negative NaNs by bits descending. f8e4m3 is OCP FP8 E4M3 (the FN variant). Pointers may be NULL only where n (or k) is 0. Arrays need only their element type's natural alignment; a misaligned pointer is an invalid argument. Functions are thread-safe on disjoint arrays, and their results don't depend on the calling thread's floating-point environment (flush-to-zero, denormals-are-zero, rounding mode).
Operation groups: a library built from the kwker-c crate with some of its cargo features off (all on by default; the release packages have every group) lacks those groups' functions - arrow: kwker_arrow_*; sparse: kwker_<t>_coo_*, _csr_to_csc*, _csc_to_csr*; strings: kwker_argsort_strings / _fixed_strings / _ucs4; dist: kwker_<t>_sample*, _splitters*, _partition_splitters / _partition_indices / _split_points (the k-way merges stay); window: kwker_<t>_median3x3*; int4: kwker_int4_*; group: kwker_group_codes and kwker_<t>_group_reduce / _group_stats; float16: every kwker_f16_*, _bf16_*, _f8e5m2_* and _f8e4m3_* function (the 16- and 8-bit float key types).
Functions
KWKER_ASCENDING, KWKER_DESCENDING, KWKER_NANS_FIRST Page
#define KWKER_ASCENDING 0u
#define KWKER_DESCENDING 1u
#define KWKER_NANS_FIRST 2u
KWKER_FILE_SYNC Page
sort_file / sort_file_records flag, or'ed into order: fsync the output before returning (default: the output is
complete in the page cache, as after sort -o)
#define KWKER_FILE_SYNC 0x100u
kwker_isa Page
The engine in use: "avx512", "avx2", "sse42", "neon", "simd128" (WebAssembly) or "portable".
const char* kwker_isa(void);
Remarks: The engine changes only the speed, never a result (rule 11).
Examples: Runtime controls: Fallback switches
kwker_set_isa Page
Caps the engine of later calls at run time (as KWKER_ISA before the first call): "avx512", "avx2", "sse42", "neon", "simd128" (the AVX2 level: that architecture's SIMD engine), "portable", or NULL for the best the CPU and KWKER_ISA allow; a cap above what the CPU runs gives the best it does. Returns the engine now in use, NULL for an unknown name (nothing changed). Results never depend on the engine, only speed. Process-wide.
const char* kwker_set_isa(const char* name);
Remarks: The engine changes only the speed, never a result (rule 11).
Examples: Runtime controls: Fallback switches
kwker_observe_start, kwker_observe_stop Page
Execution-path report: kwker_observe_start counts the engines' stages in every later call (all threads) until kwker_observe_stop, which writes the report as JSON into buf (NUL-terminated, cut to cap - 1 bytes; buf may be NULL with cap 0) and returns its full length: call it again with a larger buffer to get all of it. The report looks like {"isa":"avx512","traced":true,"stages":[{"id":40,"name":"r32.enter","about":"...","count":1,"cycles":0},...]}. start returns 0, or -2 while another observation runs; stop returns SIZE_MAX when none was started. Stages are counted on the x86 engines ("traced": false elsewhere).
int kwker_observe_start(void);
size_t kwker_observe_stop(char* buf, size_t cap);
kwker_version Page
The library version, for example "0.1.0".
const char* kwker_version(void);
kwker_precision_policies Page
Precision policy: which weights a model runs in, from the one rules table every Kwker integration shares (Python's
KwkDecoder and kwker serve read it through here, so integrations can't disagree).
policy: "preserve" (lossless choices only; NULL means it), "balanced" (int8, about +0.1% perplexity), or
"float32", "bf16", "int8", "int4" by name. kwker_precision_policies() lists them.
checkpoint: how the model's weight matrices are stored: "float32", "float32 (bf16 values)" (float32 numbers that
are all exact bf16 numbers), "bf16", "fp16" or "mixed".
flags: KWKER_MODEL_MOE for a mixture-of-experts model, else 0.
Writes *out: weights ("float32", "bf16", "int8" or "int4"), quality (what it costs, "lossless" or the perplexity
change), and a next choice to try - hint_policy plus hint, for example "balanced" + "(int8) decodes about 1.7x
faster at about +0.1% perplexity". All static strings.
Returns 0; 1 when the policy has no choice for this model (weights NULL; why says why, the hint what to pass
instead); -1 for an unknown policy or checkpoint name, or a NULL out.
#define KWKER_MODEL_MOE 1u
typedef struct kwker_precision_plan {
const char* weights;
const char* quality;
const char* hint_policy;
const char* hint;
const char* why;
} kwker_precision_plan;
int kwker_precision_resolve(const char* policy, const char* checkpoint, uint32_t flags, kwker_precision_plan* out);
kwker_precision_policies Page
The policies kwker_precision_resolve takes: "preserve,balanced,float32,bf16,int8,int4".
const char* kwker_precision_policies(void);
kwker_int4_sort_packed Page
Packed 4-bit keys: n keys two per byte ((n + 1) / 2 bytes), key i in byte i / 2, the low nibble first (the GGML / ONNX / quint4x2 order); is_signed 0 = 0..15, 1 = two's-complement -8..7; order: KWKER_DESCENDING or not. The nibble past an odd n is never touched.
int kwker_int4_sort_packed(uint8_t* data, size_t n, int is_signed, uint32_t order);
kwker_int4_argsort_packed Page
The stable argsort: indices[0..n) in key order, equal keys by index.
int kwker_int4_argsort_packed(const uint8_t* data, size_t n, int is_signed, uint32_t order, uint64_t* indices);
kwker_int4_top_k_packed Page
The indices of the min(k, n) first keys in order (ties by index, in key order) into indices[0..min(k, n)).
int kwker_int4_top_k_packed(const uint8_t* data, size_t n, size_t k, int is_signed, uint32_t order,
uint64_t* indices);
kwker_set_scratch_limit, kwker_scratch_limit Page
The calling thread's scratch-memory limit for later calls, in bytes (SIZE_MAX: none, the default; 0: no allocation). Results don't change; some inputs sort slower. Covers the in-place operations: sort, sort_order, select, partial_sort and sort_kv.
void kwker_set_scratch_limit(size_t bytes);
size_t kwker_scratch_limit(void);
Remarks: The scratch limit changes only the speed and memory use, never a result (rule 12).
Examples: Large data: Limit the extra memory
KWKER_ALG_ADAPTIVE, KWKER_ALG_COUNTING, KWKER_ALG_RADIX, ... Page
Algorithm classes (kwker_set_algorithms): the optional paths beyond the comparison sort, which always runs. ADAPTIVE: finishes early on sorted, reversed, all-equal or nearly sorted inputs, and sorts runs of equal keys as one entry per run. COUNTING: few distinct values, dominant values and narrow key ranges. RADIX: radix and value-bucket passes.
#define KWKER_ALG_ADAPTIVE 1u
#define KWKER_ALG_COUNTING 2u
#define KWKER_ALG_RADIX 4u
#define KWKER_ALG_ALL 7u
kwker_set_algorithms, kwker_algorithms Page
Permits only these classes in the calling thread's later calls (sorts, selection, partial sorts, key-value sorts, argsort; their helper threads take the caller's setting); returns the previous setting. Results are unchanged - including stable orders - only the time differs: predictable run time, or isolating a path. Default ALL.
uint32_t kwker_set_algorithms(uint32_t classes);
uint32_t kwker_algorithms(void);
kwker_set_scratch_policy, kwker_scratch_policy Page
Scratch policy (process-wide) for the buffers the library allocates for itself: cache_bytes of released buffers kept for later calls (default 1 GiB: repeated large calls take no page faults; 0 = every buffer returned when its call ends), mapped != 0 = large buffers from the library's own 2 MiB-aligned anonymous mappings (Linux, the default) / 0 = from the heap, huge_pages != 0 = MADV_HUGEPAGE on new mappings (default off; the environment variable KWKER_HUGEPAGE switches it on). A smaller cache releases the kept buffers above it at once. kwker_scratch_policy reads it back (any pointer may be NULL).
void kwker_set_scratch_policy(size_t cache_bytes, int mapped, int huge_pages);
void kwker_scratch_policy(size_t* cache_bytes, int* mapped, int* huge_pages);
kwker_scratch_use Page
Those buffers now (process-wide): bytes in use by running calls, kept in the cache, and the most in use at once since the last reset (reset != 0 restarts it after this reading). Any pointer may be NULL.
void kwker_scratch_use(int reset, size_t* in_use, size_t* cached, size_t* peak);
kwker_release_scratch Page
Unmaps the kept buffers and frees the calling thread's argsort / top-k buffers.
void kwker_release_scratch(void);
kwker_set_scratch_allocator Page
Routes those buffers to the host's allocator for later calls (process-wide) - a memory pool, an arena, an accounting wrapper: alloc(ctx, bytes, align) returns bytes (>= 1) aligned to align (a power of two, at most 4096) or NULL (the library then allocates that buffer itself; a scratch limit bounds it), free(ctx, p, bytes, align) takes one back. Both are called from any thread, concurrently. The library keeps none of the host's buffers between calls; buffers taken before a change go back to the allocator they came from. alloc = free = NULL: back to the library's own. -1 when only one of them is NULL (nothing changed).
typedef void* (*kwker_alloc_fn)(void* ctx, size_t bytes, size_t align);
typedef void (*kwker_free_fn)(void* ctx, void* p, size_t bytes, size_t align);
int kwker_set_scratch_allocator(kwker_alloc_fn alloc, kwker_free_fn free_fn, void* ctx);
kwker_scratch_bound Page
An upper bound of the scratch bytes an operation allocates for n keys of key_bytes (values of value_bytes) on this machine's engine, no limit set - the bounds SCRATCH.md documents (per-thread histograms included); SIZE_MAX for an unknown op.
#define KWKER_SCRATCH_SORT 0
#define KWKER_SCRATCH_SELECT 1
#define KWKER_SCRATCH_SORT_KV 2
#define KWKER_SCRATCH_TOP_K 3
#define KWKER_SCRATCH_SORT_KV_STABLE 4
#define KWKER_SCRATCH_ARGSORT 5
#define KWKER_SCRATCH_RANK 6
#define KWKER_SCRATCH_REDUCE_BY_KEY 7
#define KWKER_SCRATCH_SORT128 8
size_t kwker_scratch_bound(int op, size_t n, size_t key_bytes, size_t value_bytes);
kwker_set_default_threads, kwker_default_threads Page
The thread count the _mt functions use when called with threads = 0 (process-wide; default 1 - single-threaded; n = 0 sets the CPUs this process may run on).
void kwker_set_default_threads(size_t n);
size_t kwker_default_threads(void);
Remarks: Threads change only the speed: the result follows the same rules on any thread count (rule 10).
kwker_set_max_threads, kwker_max_threads, kwker_parallel_threads Page
The process-wide budget of threads running parallel phases (all callers together; n = 0: the CPUs the process may run on, the default): concurrent _mt calls share it instead of each starting its own threads, and a parallel call from inside a parallel task runs on that task's thread. kwker_parallel_threads: the threads running parallel phases now (*active) and at most since the last reset (*peak; reset != 0 restarts it).
void kwker_set_max_threads(size_t n);
size_t kwker_max_threads(void);
void kwker_parallel_threads(int reset, size_t* active, size_t* peak);
Remarks: Threads change only the speed: the result follows the same rules on any thread count (rule 10).
kwker_set_worker_cpus Page
Pins the worker threads of later parallel phases (worker w on cpus[w % n]; the calling thread untouched); n = 0 or cpus = NULL: no pinning (the default). Linux only (elsewhere ignored).
void kwker_set_worker_cpus(const size_t* cpus, size_t n);
kwker_capabilities_json Page
What Kwker does on this machine, one JSON object: version, isa, engines_built, engines_usable, features (the CPU features the engines use, detected), sve_vector_bits, l1d / l2 / l3 (bytes or null), cpus, default_threads, scratch_limit, build. A static string, computed at the first call.
const char* kwker_capabilities_json(void);
kwker_set_task_runner Page
Runs the library's parallel phases (the _mt functions, threads > 1) on the caller's thread pool - for example a framework's intra-op threads, which would otherwise spin-wait on the cores the library's own threads need: runner(ctx, n, task, arg) must call task(arg, i) once for every i in 0..n (on any threads, concurrently or not, in any order) and return when all have returned. NULL: the library's own threads (the default). Process-wide.
typedef void (*kwker_task_fn)(void* arg, size_t i);
typedef void (*kwker_runner_fn)(void* ctx, size_t n, kwker_task_fn task, void* arg);
void kwker_set_task_runner(kwker_runner_fn runner, void* ctx);
Per-type functions (kwker_<s>_...) Page
For each key type T with suffix s:
kwker_s_sort(T* a, size_t n) sort ascending (not stable: equal keys are identical)
kwker_s_sort_order(T* a, size_t n, uint32_t order) sort in `order`
kwker_s_select(T* a, size_t n, size_t k, order) a[k] = the key a full sort would put there, the keys
before it sorting before or equal, after it after or
equal; neither side sorted (k < n)
kwker_s_partial_sort(T* a, size_t n, size_t k, order) a[0..k) = the first k keys in order, the rest in
any order (k <= n)
kwker_s_argsort(const T* a, size_t n, order, uint64_t* indices)
the stable sorting permutation (n indices; equal
keys by index); a is not modified
kwker_s_argsort_ws(const T* a, size_t n, order, uint64_t* indices, kwker_workspace* ws)
argsort with a reusable workspace (NULL: as argsort)
kwker_s_argselect(const T* a, size_t n, size_t k, order, uint64_t* indices)
the indices of the stable order's first k keys, in
any order (k <= n)
kwker_s_top_k(const T* a, size_t n, size_t k, order, int sorted, T* values, uint64_t* indices)
the stable order's first k keys and their indices
(sorted != 0: in order); values or indices may be NULL
kwker_s_top_k_ws(..., kwker_workspace* ws) top_k with a reusable workspace (NULL: as top_k)
kwker_s_sort_kv_ws / _sort_kv_stable_ws / _select_kv_ws / _partial_sort_kv_ws(..., kwker_workspace* ws)
the key-value calls with a reusable workspace (NULL:
as without)
kwker_s_sort_kv(T* keys, void* values, size_t value_size, size_t n, order)
sort keys and move each value (value_size bytes, any
size) with its key; equal keys' values in any order
kwker_s_sort_kv_stable(T* keys, void* values, size_t value_size, size_t n, order)
sort_kv, stable: equal keys keep their values in input
order (allocates O(n))
kwker_s_select_kv(T* keys, void* values, size_t value_size, size_t n, size_t k, order)
select with the values: keys[k] = the key a full sort
would put there, with its value; neither side sorted
(k < n)
kwker_s_partial_sort_kv(T* keys, void* values, size_t value_size, size_t n, size_t k, order)
the first min(k, n) keys in order sorted, each with its
value (value sizes as sort_kv)
kwker_s_sort_kv_mt(T* keys, void* values, size_t value_size, size_t n, order, size_t threads)
sort_kv_stable on `threads` threads (0: the default)
kwker_s_sort_rows(T* a, size_t rows, size_t row_len, order)
sort each row of a row-major rows x row_len array
kwker_s_sort_segments(T* a, size_t n, const uint64_t* offsets, size_t count, order)
sort every a[offsets[i] .. offsets[i + 1]) (offsets
nondecreasing, the last <= n; keys outside untouched)
kwker_s_rank(const T* a, size_t n, order, int ties, uint64_t* ranks)
the 1-based rank of every key (ranks[i]: of a[i]);
ties: 0 ordinal (stable), 1 min, 2 max, 3 dense
kwker_s_rank_f64(const T* a, size_t n, order, int kind, double* ranks)
kind 0: average ranks (1-based, equal keys share the
mean), 1: percent rank (min rank - 1) / (n - 1)
kwker_s_argsort_rows(const T* a, size_t rows, size_t row_len, order, uint64_t* indices)
the stable permutation of each row (row-relative)
kwker_s_sort_rows_indexed(const T* a, size_t rows, size_t row_len, order, T* values, uint64_t* indices)
each row sorted into values and its stable permutation
(row-relative) into indices - one sort for both
kwker_s_kth_rows(const T* a, size_t rows, size_t row_len, size_t k, order, int nan_first, T* values,
uint64_t* indices) the k-th key (0-based, k < row_len) of each row's order
into values[row], its index (the stable order's k-th)
into indices[row]; nan_first != 0 (torch.median): a
row holding a NaN gives its first NaN
kwker_s_kth_axis(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, size_t axis, size_t k,
order, int nan_first, T* values, uint64_t* indices, const ptrdiff_t* out_strides)
the k-th key (stable order) of every lane along axis and
its lane-relative index, one result per lane (out_strides
for the input's shape, the axis entry unused);
nan_first as kth_rows
kwker_s_kth_mt(const T* a, size_t n, size_t k, order, int nan_first, size_t threads, T* value, uint64_t* index)
the k-th key of a (the stable order's k-th, 0-based, k < n)
into *value, its index into *index, on `threads` threads;
nan_first as kth_rows
kwker_s_sort_mt(T* a, size_t n, order, size_t threads)
sort_order on `threads` threads (0: the default), with
the same result
kwker_s_sort_indexed_mt(const T* a, size_t n, order, T* values, uint64_t* indices, size_t threads)
the stable permutation into indices and (values not NULL)
the sorted keys, on `threads` threads - argsort's result
kwker_s_sort_mt_progress / _sort_kv_mt_progress / _sort_indexed_mt_progress (..., threads, progress, ctx)
the same with progress and cancellation (-3)
kwker_s_unique(const T* a, size_t n, T* values, uint64_t* inverse, uint64_t* counts, size_t threads,
size_t* n_unique) the distinct keys ascending into values (room for n), the
group of every key into inverse (n; NULL: not wanted),
the groups' sizes into counts (room for n; NULL: not
wanted), *n_unique = their number; threads > 1: that
many threads. Floats equal as values (-0.0 = +0.0),
each NaN its own key (torch.unique)
kwker_s_top_k_rows(const T* a, size_t rows, size_t row_len, size_t k, order, int sorted, T* values,
uint64_t* indices) each row's first k keys and row-relative indices
kwker_s_top_k_segments(const T* a, size_t n, const uint64_t* offsets, size_t count, size_t k, order,
int sorted, T* values, int64_t* indices)
segment i = a[offsets[i] .. offsets[i + 1]) (offsets
nondecreasing, the last at most n; count - 1
segments): its first min(k, length) keys in order
(sorted != 0: in order) at values[i * k ..], their
indices within the segment at indices[i * k ..]; a
shorter segment's other index slots are -1 (its value
slots untouched); -1 for decreasing offsets
kwker_s_argpartition_rows(const T* a, size_t rows, size_t row_len, size_t kth, order, uint64_t* indices)
numpy.argpartition per row: position kth = the index of
the row's kth key (ties by index), the kth first before
it, the rest after it ascending
kwker_s_searchsorted(const T* sorted, size_t n, const T* queries, size_t m, order, int side, uint64_t* out)
insertion position of every query in sorted (sorted
in order, not checked): side 0 before equal keys
(lower bound), 1 after them (upper bound)
kwker_s_bucket_counts(const T* values, size_t n, const T* boundaries, size_t m, order, int right,
uint64_t* counts) values per bucket of the sorted boundaries into counts
(m + 1 entries): right 0 boundaries[i-1] < v <=
boundaries[i] (torch.bucketize), 1 boundaries[i-1] <=
v < boundaries[i]
kwker_s_set_op(const T* a, size_t n, const T* b, size_t m, order, int op, int multiset, T* out, size_t* out_len)
a and b sorted in order: op 0 intersection, 1 union,
2 difference (a - b), 3 symmetric difference; multiset 0:
each value once, else copy counts min / max / a-b / |a-b|;
out: room for n + m keys
kwker_s_intersection_indices(const T* a, size_t n, const T* b, size_t m, order, int multiset, uint64_t* ia,
uint64_t* ib, size_t* count)
the intersection's positions in a and b (room for
min(n, m) each)
kwker_s_isin(const T* a, size_t n, const T* test, size_t m, int invert, uint8_t* out)
out[i] = 1 when a[i] equals a value of test (any order;
-0.0 = +0.0, a NaN equals nothing), else 0; swapped
with invert (numpy.isin / torch.isin)
kwker_s_argsort_masked(const T* a, size_t n, const uint8_t* mask, int bitmap, order, uint64_t* indices,
size_t* count) the stable permutation of the selected positions only
kwker_s_sort_masked(T* a, size_t n, const uint8_t* mask, int bitmap, order) the selected keys sorted among
their positions, the others untouched
kwker_s_argsort_field(const void* records, size_t n, size_t stride, size_t offset, order, uint64_t* indices)
the stable permutation of n records of stride bytes by
the T at byte offset of each (any alignment): indices
only, the records never moved (n keys copied)
kwker_s_top_k_field(const void* records, size_t n, size_t stride, size_t offset, size_t k, order,
uint64_t* indices) the first min(k, n) records by that key (ties by index)
kwker_s_top_k_masked(const T* a, size_t n, const uint8_t* mask, int bitmap, size_t k, order, int sorted,
T* values, uint64_t* indices, size_t* count)
top k among the positions mask selects: bitmap 0 one
byte per key (nonzero = takes part), 1 an Arrow validity
bitmap (LSB first); room for min(k, n); *count written
kwker_s_top_k_by_group(const T* a, size_t n, const int64_t* groups, size_t k, order, int64_t* labels,
uint64_t* offsets, uint64_t* indices, size_t* ngroups)
top k per group label (any order of labels): distinct
labels ascending, group i at indices[offsets[i] ..
offsets[i + 1]); room: labels n, offsets n + 1, indices n
kwker_s_sort_axis(T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, size_t axis, order)
sort every 1-D lane along axis of an N-dimensional
array (1 <= ndim <= 64; strides in elements, any sign,
NULL = C order; a: the element at index (0, .., 0))
kwker_s_argsort_axis(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, size_t axis,
order, uint64_t* out, const ptrdiff_t* out_strides)
the stable permutation of every lane (lane-relative)
into out, of the same shape (out_strides: NULL = C order)
kwker_s_sort_axis_indexed(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, size_t axis,
order, T* values, uint64_t* indices, const ptrdiff_t* out_strides)
every lane sorted into values and its stable permutation
into indices (both of the input's shape, out_strides;
NULL = C order); indices NULL: the sorted values only
kwker_s_sort_axis_indexed8(same, uint8_t* indices, ..) the same with uint8_t indices (lanes of at most 256
keys, else -1): a permutation kept for later (autograd)
in an eighth of the bytes
Distributed sorting primitives. Every element has a position, base + its index in the array a call sees (base per
worker, for example worker << 40); elements are ordered by (key in order, position), and splitters are (key, position)
pairs held as two arrays sk / sp. Partition j holds the elements from splitter j - 1 (inclusive) to splitter j
(exclusive), so equal keys at a boundary are split by position (balanced parts on duplicate-heavy keys):
kwker_s_sample(const T* a, size_t n, size_t m, uint64_t base, uint64_t seed, T* keys, uint64_t* pos)
a stratified random sample: min(m, n) keys + positions
kwker_s_sample_sorted(const T* sorted, size_t n, size_t m, uint64_t base, T* keys, uint64_t* pos)
the regular sample of sorted keys (ranks (j + 1) n / (m + 1))
kwker_s_splitters(const T* keys, const uint64_t* pos, size_t m, size_t parts, order, T* sk, uint64_t* sp,
size_t* count) parts - 1 splitters from m gathered sample entries
(0 for an empty sample); room for parts - 1
kwker_s_splitters_exact(const T* a, size_t n, uint64_t base, size_t parts, order, T* sk, uint64_t* sp,
size_t* count) exact quantile splitters: parts of floor / ceil(n / parts)
kwker_s_partition_splitters(T* a, size_t n, uint64_t base, const T* sk, const uint64_t* sp, size_t ns,
order, size_t* offsets) a reordered by partition in place (unordered inside);
ns + 2 offsets (0 .. n); -1 for unordered splitters
kwker_s_partition_indices(const T* a, size_t n, uint64_t base, sk, sp, ns, order, uint64_t* indices,
size_t* offsets) the n indices grouped by partition, ascending inside
kwker_s_split_points(const T* sorted, size_t n, uint64_t base, sk, sp, ns, order, size_t* offsets)
the partition offsets of stably sorted keys
kwker_s_kway_merge(const T* const* runs, const size_t* lens, size_t k, order, T* out)
k sorted runs merged, equal keys by run then index
kwker_s_kway_merge_kv(const T* const* runs, const void* const* values, size_t value_size, const size_t* lens,
size_t k, order, T* out, void* out_values) values of value_size bytes move along
Strided arrays (sort_axis / argsort_axis): every element the shape and strides reach must be valid (writable for
sort_axis) and no two indices may address the same element (a stride 0 along axis excepted: such lanes are left as
they are).
The declarations:
int kwker_<s>_sort(T* a, size_t n);
int kwker_<s>_sort_order(T* a, size_t n, uint32_t order);
int kwker_<s>_select(T* a, size_t n, size_t k, uint32_t order);
int kwker_<s>_partial_sort(T* a, size_t n, size_t k, uint32_t order);
int kwker_<s>_argsort(const T* a, size_t n, uint32_t order, uint64_t* indices);
int kwker_<s>_argsort_ws(const T* a, size_t n, uint32_t order, uint64_t* indices, kwker_workspace* ws);
int kwker_<s>_argselect(const T* a, size_t n, size_t k, uint32_t order, uint64_t* indices);
int kwker_<s>_top_k(const T* a, size_t n, size_t k, uint32_t order, int sorted, T* values,
uint64_t* indices);
int kwker_<s>_top_k_ws(const T* a, size_t n, size_t k, uint32_t order, int sorted, T* values,
uint64_t* indices, kwker_workspace* ws);
int kwker_<s>_sort_kv(T* keys, void* values, size_t value_size, size_t n, uint32_t order);
int kwker_<s>_sort_kv_stable(T* keys, void* values, size_t value_size, size_t n, uint32_t order);
int kwker_<s>_sort_kv_ws(T* keys, void* values, size_t value_size, size_t n, uint32_t order,
kwker_workspace* ws);
int kwker_<s>_sort_kv_stable_ws(T* keys, void* values, size_t value_size, size_t n, uint32_t order,
kwker_workspace* ws);
int kwker_<s>_select_kv_ws(T* keys, void* values, size_t value_size, size_t n, size_t k, uint32_t order,
kwker_workspace* ws);
int kwker_<s>_partial_sort_kv_ws(T* keys, void* values, size_t value_size, size_t n, size_t k,
uint32_t order, kwker_workspace* ws);
int kwker_<s>_select_kv(T* keys, void* values, size_t value_size, size_t n, size_t k, uint32_t order);
int kwker_<s>_partial_sort_kv(T* keys, void* values, size_t value_size, size_t n, size_t k,
uint32_t order);
int kwker_<s>_sort_rows(T* a, size_t rows, size_t row_len, uint32_t order);
int kwker_<s>_sort_segments(T* a, size_t n, const uint64_t* offsets, size_t count, uint32_t order);
Declared for: u8 (uint8_t), i8 (int8_t), u16 (uint16_t), i16 (int16_t), u32 (uint32_t), i32 (int32_t), f32 (float), u64 (uint64_t), i64 (int64_t), f64 (double), f16 (uint16_t), bf16 (uint16_t), f8e5m2 (uint8_t), f8e4m3 (uint8_t).
Examples: Sorting: Every number type, Core concepts: Special float values, Quickstart: Kwker Core: The median, without a full sort, Top-k and selection: Sort only the beginning, Order and ranking: The order of an array: argsort, Sorting keys with values: Keep equal keys in order: the stable sort, Large data: Use several cores, Searching sorted data: Where does a value go? searchsorted, Groups, merges and sets: Set operations, Use Kwker from C and C++: The program
kwker_<s>_median3x3, kwker_<s>_median3x3_backward, kwker_<s>_rank_filter, ... Page
3 x 3 window medians (median filter / median pooling, stride 1) of planes x h x w row-major keys; s: the ten
integer and float types u8 .. f64 (backward: f32 / f64):
kwker_s_median3x3(const T* src, size_t planes, size_t h, size_t w, uint32_t pad, T* out)
out: planes x h x w (pad 3: planes x (h - 2) x (w - 2)); the window of
output (y, x) is centred on input (y, x); pad 0 reflect (F.pad reflect:
h, w >= 2), 1 replicate, 2 zeros, 3 valid (no padding: h, w >= 3). A
window holding a NaN gives its first NaN (rows, then columns), as
torch.median; otherwise the 5th smallest of the 9 keys
kwker_s_median3x3_backward(const T* src, const T* out, const T* grad_out, size_t planes, size_t h, size_t w,
uint32_t pad, T* grad_in)
grad_in (planes x h x w, overwritten): each output's gradient added at
the input key its median came from (the first window key equal to out,
for a NaN median its first NaN); padding keys fold back onto the keys
they mirror (zeros: dropped)
kwker_s_median5x5 / kwker_s_median5x5_backward the same for 5 x 5 windows: the 13th smallest of 25 keys; pad 3
gives planes x (h - 4) x (w - 4); reflect needs h, w >= 3, valid >= 5
kwker_s_median7x7 / kwker_s_median7x7_backward the same for 7 x 7 windows: the 25th smallest of 49 keys; pad 3
gives planes x (h - 6) x (w - 6); reflect needs h, w >= 4, valid >= 7
kwker_s_rank_filter(const T* src, size_t planes, size_t h, size_t w, size_t k, size_t rank, T* out)
rank filter (scipy.ndimage.rank_filter / percentile_filter, minimum and
maximum filters): out (planes x (h - k + 1) x (w - k + 1)) = the key of
rank `rank` (0 the smallest, k * k - 1 the largest) among the k x k keys of
the window whose top-left key is input (y, x); k 3, 5 or 7, h and w >= k;
a window holding a NaN gives an unspecified key; -1 for another k, rank
>= k * k or a plane smaller than the window
kwker_s_rolling_quantile(const T* src, size_t n, size_t window, double q, int interpolation, double* out)
rolling quantile of a series (pandas rolling(window).quantile(q)):
out[i] (n doubles) = the q quantile of src[i + 1 - window .. i]; the
first window - 1 outputs and every window holding a NaN are NaN;
interpolation 0 linear (pandas' quantile bit for bit), 1 lower, 2 higher,
3 midpoint (q 0.5: pandas' median, bottleneck move_median), 4 nearest
kwker_s_rolling_mad(const T* src, size_t n, size_t window, double* out)
rolling median absolute deviation (Hampel filters): out[i] = the
median of |x - m| over src[i + 1 - window .. i], m that window's
median (np.median: the mean of the two middle values for even
windows); NaN as rolling_quantile
kwker_s_expanding_quantile(const T* src, size_t n, double q, int interpolation, double* out)
expanding quantile (pandas expanding().quantile(q) / .median() with
interpolation 3 at q 0.5): out[i] = the q quantile of the values of
src[0 .. i] that are not NaN (NaN while there is none); O(n log n)
-1 for an unknown pad, planes too small for it, or a NULL pointer with planes > 0 (rolling: window 0, q outside
[0, 1], an unknown interpolation or a NULL pointer with n > 0).
int kwker_<s>_median3x3(const T* src, size_t planes, size_t h, size_t w, uint32_t pad, T* out);
int kwker_<s>_median5x5(const T* src, size_t planes, size_t h, size_t w, uint32_t pad, T* out);
int kwker_<s>_median7x7(const T* src, size_t planes, size_t h, size_t w, uint32_t pad, T* out);
int kwker_<s>_rank_filter(const T* src, size_t planes, size_t h, size_t w, size_t k, size_t rank, T* out);
int kwker_<s>_rolling_quantile(const T* src, size_t n, size_t window, double q, int interpolation, double* out);
int kwker_<s>_rolling_mad(const T* src, size_t n, size_t window, double* out);
int kwker_<s>_expanding_quantile(const T* src, size_t n, double q, int interpolation, double* out);
Declared for: u8 (uint8_t), i8 (int8_t), u16 (uint16_t), i16 (int16_t), u32 (uint32_t), i32 (int32_t), f32 (float), u64 (uint64_t), i64 (int64_t), f64 (double).
int kwker_<s>_median3x3_backward(const T* src, const T* out, const T* grad_out, size_t planes, size_t h,
size_t w, uint32_t pad, T* grad_in);
int kwker_<s>_median5x5_backward(const T* src, const T* out, const T* grad_out, size_t planes, size_t h,
size_t w, uint32_t pad, T* grad_in);
int kwker_<s>_median7x7_backward(const T* src, const T* out, const T* grad_out, size_t planes, size_t h,
size_t w, uint32_t pad, T* grad_in);
Declared for: f32 (float), f64 (double).
kwker_<s>_trim_mean, kwker_<s>_weighted_quantile, kwker_<s>_average_precision, ... Page
Robust statistics (s = u8, i8, u16, i16, u32, i32, u64, i64, f32, f64):
kwker_s_trim_mean(const T* a, size_t ndim, const size_t* shape, size_t axis, double proportion, double* out)
scipy.stats.trim_mean(a, proportion, axis) of the C-order array: for every
lane along axis (n values), the mean of its values without the
floor(proportion x n) smallest and as many largest, into out (one double a
lane, C order of the other dimensions); NaN sorts above every number, so a
lane keeps NaN only with more NaNs than are cut; nothing left (proportion
0.5, n even) or n 0 gives NaN; sums in double
kwker_s_weighted_quantile(const T* a, const double* weights, size_t n, const double* qs, size_t nq, T* out)
numpy.quantile(a, qs, weights=weights, method="inverted_cdf"): out[i] = the
first value in the stable sorted order whose cumulative weight over the
total reaches qs[i] - NumPy's element, bit for bit; a NaN in a: every
result NaN
kwker_s_average_precision(const T* scores, size_t n, const uint8_t* positive, double* out)
sklearn.metrics.average_precision_score of binary labels (positive[i]
nonzero: a positive): the recall gained at each distinct score, from the
highest, times the precision there (ties one threshold, -0.0 = +0.0);
NaN for a NaN score, 0.0 without a positive
kwker_s_roc_auc(const T* scores, size_t n, const uint8_t* positive, double* out)
sklearn.metrics.roc_auc_score of binary labels: P(a positive scores above
a negative), ties counting half; NaN for a NaN score or one class absent
-1 for a NULL pointer with work to do, axis >= ndim, ndim 0 or above 64, a negative or too large
proportion (2 x floor(proportion x n) > n), n 0 (weighted_quantile), a negative weight or a q outside [0, 1].
int kwker_<s>_trim_mean(const T* a, size_t ndim, const size_t* shape, size_t axis, double proportion,
double* out);
int kwker_<s>_weighted_quantile(const T* a, const double* weights, size_t n, const double* qs, size_t nq,
T* out);
int kwker_<s>_average_precision(const T* scores, size_t n, const uint8_t* positive, double* out);
int kwker_<s>_roc_auc(const T* scores, size_t n, const uint8_t* positive, double* out);
Declared for: u8 (uint8_t), i8 (int8_t), u16 (uint16_t), i16 (int16_t), u32 (uint32_t), i32 (int32_t), u64 (uint64_t), i64 (int64_t), f32 (float), f64 (double).
kwker_<s>_quantile_axis Page
Quantiles (f32 / f64 as s), torch.quantile / nanquantile's order statistics:
kwker_s_quantile_axis(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, size_t axis,
const double* qs, size_t nq, int ignore_nan, int interpolation, T* below, T* above,
double* weight, const ptrdiff_t* out_strides, size_t threads)
for every lane along axis and every q in qs (in [0, 1], rounded to T
as torch does) the keys of ranks floor(r) / ceil(r) of r = q * (n - 1)
(ignore_nan: q * (non-NaN count - 1)) into below / above and
r - floor(r) into weight (0.5 for midpoint), in rows of nq entries at
the lane's position in out_strides (the axis entry unused); r in f64 as
torch (interpolation | 16: r in f32, as older torch releases (2.12) compute it
for float32 inputs); interpolation 0 linear, 1 lower, 2 higher,
3 midpoint, 4 nearest (1, 2, 4 round r first: below = above); a lane holding a NaN (all NaN
with ignore_nan) gives NaN keys. lerp(below, above, (T)weight) = the
quantile. `threads`: threads for long lanes (0: the default). -1 for a q
outside [0, 1], an unknown interpolation or a NULL pointer with keys to read.
int kwker_<s>_quantile_axis(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides,
size_t axis, const double* qs, size_t nq, int ignore_nan, int interpolation,
T* below, T* above, double* weight, const ptrdiff_t* out_strides, size_t threads);
Declared for: f32 (float), f64 (double).
kwker_<s>_coo_coalesce, kwker_<s>_coo_to_csr, kwker_<s>_coo_to_csc Page
Sparse matrices (value types f32 / f64 / i32 / i64 / u32 / u64 as s; uint64_t indices):
kwker_s_coo_coalesce(const uint64_t* rows, const uint64_t* cols, const V* vals, size_t nnz, uint64_t nrows,
uint64_t ncols, int reduce, uint64_t* out_rows, uint64_t* out_cols, V* out_vals,
size_t* out_nnz)
the coordinates sorted row-major, each distinct (row, col) once with its
values combined - reduce 0 sum, 1 prod, 2 min, 3 max, 4 mean (integers:
wrapping sum / product, truncated mean; floats: min / max ignore NaNs
unless all are NaN); outputs: room for nnz; *out_nnz = the distinct count
kwker_s_coo_to_csr(same inputs, int reduce, uint64_t* indptr, uint64_t* indices, V* data, size_t* out_nnz)
CSR: indptr[nrows + 1], row i's column indices ascending in
indices[indptr[i] .. indptr[i + 1]), duplicates combined as above
kwker_s_coo_to_csc(same inputs, int reduce, uint64_t* indptr, uint64_t* indices, V* data, size_t* out_nnz)
CSC: indptr[ncols + 1], row indices ascending within each column
-1 when an index is out of range, bits(nrows - 1) + bits(ncols - 1) > 64 (one 64-bit key per coordinate), a
pointer is NULL (inputs may be NULL for nnz = 0) or reduce is unknown.
int kwker_<s>_coo_coalesce(const uint64_t* rows, const uint64_t* cols, const V* vals, size_t nnz,
uint64_t nrows, uint64_t ncols, int reduce, uint64_t* out_rows,
uint64_t* out_cols, V* out_vals, size_t* out_nnz);
int kwker_<s>_coo_to_csr(const uint64_t* rows, const uint64_t* cols, const V* vals, size_t nnz,
uint64_t nrows, uint64_t ncols, int reduce, uint64_t* indptr, uint64_t* indices,
V* data, size_t* out_nnz);
int kwker_<s>_coo_to_csc(const uint64_t* rows, const uint64_t* cols, const V* vals, size_t nnz,
uint64_t nrows, uint64_t ncols, int reduce, uint64_t* indptr, uint64_t* indices,
V* data, size_t* out_nnz);
Declared for: f32 (float), f64 (double), i32 (int32_t), i64 (int64_t), u32 (uint32_t), u64 (uint64_t).
CSR -> CSC / CSC -> CSR without a sort (minor indices ascending, duplicates kept; nnz = the last offset)
\
int kwker_##s##_csr_to_csc(const uint64_t* indptr, const uint64_t* indices, const V* data, uint64_t nrows, \
uint64_t ncols, uint64_t* out_colptr, uint64_t* out_rows, V* out_data); \
int kwker_##s##_csc_to_csr(const uint64_t* colptr, const uint64_t* rows, const V* data, uint64_t nrows, \
uint64_t ncols, uint64_t* out_indptr, uint64_t* out_cols, V* out_data); \
the same on threads threads (0: the default; the same output)
\
int kwker_##s##_csr_to_csc_mt(const uint64_t* indptr, const uint64_t* indices, const V* data, \
uint64_t nrows, uint64_t ncols, uint64_t* out_colptr, uint64_t* out_rows, \
V* out_data, size_t threads); \
int kwker_##s##_csc_to_csr_mt(const uint64_t* colptr, const uint64_t* rows, const V* data, uint64_t nrows, \
uint64_t ncols, uint64_t* out_indptr, uint64_t* out_cols, V* out_data, \
size_t threads); \
... with 32-bit offsets and indices (scipy's int32 arrays; nnz < 2^32), threads as above
\
int kwker_##s##_csr_to_csc32(const uint32_t* indptr, const uint32_t* indices, const V* data, uint64_t nrows, \
uint64_t ncols, uint32_t* out_colptr, uint32_t* out_rows, V* out_data, \
size_t threads); \
int kwker_##s##_csc_to_csr32(const uint32_t* colptr, const uint32_t* rows, const V* data, uint64_t nrows, \
uint64_t ncols, uint32_t* out_indptr, uint32_t* out_cols, V* out_data, \
size_t threads);
kwker_workspace_new, kwker_workspace_free, kwker_workspace_bytes, ... Page
A reusable workspace for repeated calls (kwker_<t>_argsort_ws, kwker_<t>_top_k_ws, kwker_<t>_sort_kv_ws / _select_kv_ws / _partial_sort_kv_ws): buffers kept between calls, so repeated argsorts, top-k and key-value calls (batched rows, a training loop) allocate nothing once it has grown. One per thread; free with kwker_workspace_free. reserve_kv grows it for key-value calls of up to n pairs of value_size-byte values, reserve_argsort for argsorts of up to n 64-bit keys (-1: NULL). A reserved workspace keeps those calls allocation-free under a scratch limit of 0 too.
typedef struct kwker_workspace kwker_workspace;
kwker_workspace* kwker_workspace_new(void);
void kwker_workspace_free(kwker_workspace* ws);
size_t kwker_workspace_bytes(const kwker_workspace* ws);
int kwker_workspace_reserve_kv(kwker_workspace* ws, size_t n, size_t value_size);
int kwker_workspace_reserve_argsort(kwker_workspace* ws, size_t n);
A progress callback: (ctx, keys done, keys in total); a nonzero return cancels the operation (it returns -3).
typedef int (*kwker_progress_fn)(void* ctx, uint64_t done, uint64_t total);
kwker_take, kwker_permute_in_place Page
Moving records by an order (any record size): record idx[j] of n records at src copied to record j of dst (m records, repeats allowed); -1 (nothing written) for an index >= n. In place: record j becomes the one at perm[j] (an argsort's result applied), no record buffer, n bits of scratch; -1 (nothing moved) unless perm is a permutation of 0..n.
int kwker_take(const void* src, size_t n, size_t record_size, const uint64_t* idx, size_t m, void* dst);
int kwker_permute_in_place(void* records, size_t n, size_t record_size, const uint64_t* perm);
Examples: Order and ranking: Reorder records in place
The Arrow C data interface (arrow/c/abi.h; the standard guard lets either definition come first).
#define ARROW_FLAG_DICTIONARY_ORDERED 1
#define ARROW_FLAG_NULLABLE 2
#define ARROW_FLAG_MAP_KEYS_SORTED 4
struct ArrowSchema {
const char* format;
const char* name;
const char* metadata;
int64_t flags;
int64_t n_children;
struct ArrowSchema** children;
struct ArrowSchema* dictionary;
void (*release)(struct ArrowSchema*);
void* private_data;
};
struct ArrowArray {
int64_t length;
int64_t null_count;
int64_t offset;
int64_t n_buffers;
int64_t n_children;
const void** buffers;
struct ArrowArray** children;
struct ArrowArray* dictionary;
void (*release)(struct ArrowArray*);
void* private_data;
};
kwker_arrow_argsort, kwker_arrow_top_k Page
The stable order of an Arrow array read in place (no conversion): primitive (int, uint, float16 / 32 / 64), temporal (date, time, timestamp, duration, month interval), decimal32 / 64 / 128 / 256, boolean, (large) string / binary and their views, fixed-size binary and dictionary-encoded arrays, structs (by fields), lists, list views and maps (by elements), run-end encoded arrays (by their runs) and sparse / dense unions (DuckDB's order: the member - the type id's position - then the value; null member values with the nulls), with validity bitmaps and offsets. Arrow's semantics (pyarrow.compute.array_sort_indices): -0.0 = +0.0, NaNs equal, after the values and next to the nulls (values, NaNs, nulls; with KWKER_ARROW_NULLS_FIRST nulls, NaNs, values - in both directions), equal values by index; strings as bytes; dictionaries by value (KWKER_ARROW_BY_CODES: by code). flags: KWKER_DESCENDING | KWKER_ARROW_NULLS_FIRST | KWKER_ARROW_BY_CODES. indices: room for length (top_k: min(k, length); *count written). 0, -1 invalid arguments or array, -2 a type without an order here (intervals other than months).
#define KWKER_ARROW_NULLS_FIRST 4u
#define KWKER_ARROW_BY_CODES 8u
int kwker_arrow_argsort(const struct ArrowSchema* schema, const struct ArrowArray* array, uint32_t flags,
uint64_t* indices);
int kwker_arrow_top_k(const struct ArrowSchema* schema, const struct ArrowArray* array, size_t k, uint32_t flags,
uint64_t* indices, size_t* count);
kwker_arrow_argsort_chunks, kwker_arrow_top_k_chunks Page
A chunked array - n_arrays arrays of schema's type, in order (a pyarrow ChunkedArray, a stream's batches) - ordered as one array of their summed length without combining it: indices into the concatenation (room for the summed length; top_k: min(k, summed length), *count written). Fixed-width types (integers, temporal, floats, booleans, decimals of 32 to 256 bits), strings / binaries and their views, dictionaries of any of these by value (each chunk with its own dictionary; equal values in different dictionaries tie) or by code (KWKER_ARROW_BY_CODES), run-end encoded arrays of those values (by their runs), structs, lists (list views, fixed-size lists, maps) and sparse / dense unions of all of these (each field / the elements / each member ranked across the chunks). -2: a type it does not read (combine the chunks, then kwker_arrow_argsort).
int kwker_arrow_argsort_chunks(const struct ArrowSchema* schema, const struct ArrowArray* const* arrays, size_t n_arrays,
uint32_t flags, uint64_t* indices);
int kwker_arrow_top_k_chunks(const struct ArrowSchema* schema, const struct ArrowArray* const* arrays, size_t n_arrays,
size_t k, uint32_t flags, uint64_t* indices, size_t* count);
kwker_argsort_strings Page
Strings in a collation: the stable order of n strings into n indices. KWKER_COLLATE_BYTES plain byte order,
_ASCII_CASELESS ASCII letters without case, _NATURAL runs of ASCII digits by numeric value ("file2" before
"file10", leading zeros ignored), _NATURAL_CASELESS both. Equal strings under the collation keep their input order.
kwker_argsort_strings: strings[i] with lens[i] bytes (lens NULL: NUL-terminated strings)
kwker_argsort_fixed_strings: n strings of width bytes each at data, trailing NUL bytes not part of a string
(NumPy 'S' arrays)
-1 for an unknown collation, a NULL string or a NULL output with n > 0.
#define KWKER_COLLATE_BYTES 0u
#define KWKER_COLLATE_ASCII_CASELESS 1u
#define KWKER_COLLATE_NATURAL 2u
#define KWKER_COLLATE_NATURAL_CASELESS 3u
int kwker_argsort_strings(const char* const* strings, const size_t* lens, size_t n, uint32_t collation, uint64_t* indices);
Examples: Strings: Sort a list of strings, Strings: The order of strings
kwker_unique_strings, kwker_argsort_fixed_strings Page
The distinct strings under a collation (as kwker_argsort_strings) in sorted order: the input index of each one's first occurrence into indices[0 .. *count) (indices: n entries).
int kwker_unique_strings(const char* const* strings, const size_t* lens, size_t n, uint32_t collation, uint64_t* indices,
size_t* count);
int kwker_argsort_fixed_strings(const char* data, size_t n, size_t width, uint32_t collation, uint64_t* indices);
kwker_argsort_fixed_strings_field Page
The same over the width-byte field at byte offset of n records of stride bytes (COBOL PIC X keys, C char[] members): n indices, the records are not moved (kwker_take / kwker_permute_in_place apply the order).
int kwker_argsort_fixed_strings_field(const void* records, size_t n, size_t stride, size_t offset, size_t width,
uint32_t collation, uint64_t* indices);
kwker_argsort_ucs4 Page
n fixed-width UCS-4 strings of width code points each (trailing zeros not part of a string: NumPy 'U' arrays).
int kwker_argsort_ucs4(const uint32_t* data, size_t n, size_t width, uint32_t collation, uint64_t* indices);
kwker_collation_table, kwker_argsort_strings_table, kwker_argsort_fixed_strings_table, ... Page
Collating sequences as 256 byte weights (weights[b] = byte b's weight): strings compare as their bytes' weight sequences, a prefix first; bytes of equal weight are equal characters (COBOL ALPHABET ... ALSO); stable. kwker_collation_table writes a built-in table: KWKER_TABLE_BYTES (byte order), _EBCDIC_037 (Latin-1 / ASCII text in IBM EBCDIC 037 order: space, punctuation, lowercase, uppercase, digits), _FROM_EBCDIC_037 (EBCDIC 037 bytes in Latin-1 order). The _field_table form compares every byte of the field (COBOL's fixed-length comparison); the fixed_strings form drops trailing NULs as above. -1 for an unknown table or a NULL pointer with n > 0.
#define KWKER_TABLE_BYTES 0u
#define KWKER_TABLE_EBCDIC_037 1u
#define KWKER_TABLE_FROM_EBCDIC_037 2u
int kwker_collation_table(uint32_t table, uint8_t* weights);
int kwker_argsort_strings_table(const char* const* strings, const size_t* lens, size_t n, const uint8_t* weights, uint64_t* indices);
int kwker_argsort_fixed_strings_table(const char* data, size_t n, size_t width, const uint8_t* weights, uint64_t* indices);
int kwker_argsort_fixed_strings_field_table(const void* records, size_t n, size_t stride, size_t offset, size_t width,
const uint8_t* weights, uint64_t* indices);
... with progress after each ~64K keys (NULL: none); cancelled: -3, rows / segments done so far sorted
\
int kwker_##s##_sort_rows_progress(T* a, size_t rows, size_t row_len, uint32_t order, \
kwker_progress_fn progress, void* ctx); \
int kwker_##s##_sort_segments_progress(T* a, size_t n, const uint64_t* offsets, size_t count, \
uint32_t order, kwker_progress_fn progress, void* ctx); \
int kwker_##s##_rank(const T* a, size_t n, uint32_t order, int ties, uint64_t* ranks); \
int kwker_##s##_rank_f64(const T* a, size_t n, uint32_t order, int kind, double* ranks); \
int kwker_##s##_argsort_rows(const T* a, size_t rows, size_t row_len, uint32_t order, uint64_t* indices); \
int kwker_##s##_sort_rows_indexed(const T* a, size_t rows, size_t row_len, uint32_t order, T* values, \
uint64_t* indices); \
int kwker_##s##_kth_rows(const T* a, size_t rows, size_t row_len, size_t k, uint32_t order, int nan_first, \
T* values, uint64_t* indices); \
int kwker_##s##_kth_axis(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, size_t axis, \
size_t k, uint32_t order, int nan_first, T* values, uint64_t* indices, \
const ptrdiff_t* out_strides); \
int kwker_##s##_kth_mt(const T* a, size_t n, size_t k, uint32_t order, int nan_first, size_t threads, \
T* value, uint64_t* index); \
int kwker_##s##_sort_mt(T* a, size_t n, uint32_t order, size_t threads); \
int kwker_##s##_sort_kv_mt(T* keys, void* values, size_t value_size, size_t n, uint32_t order, size_t threads); \
int kwker_##s##_sort_indexed_mt(const T* a, size_t n, uint32_t order, T* values, uint64_t* indices, \
size_t threads); \
... with a progress callback (NULL: none) after each bucket - from the worker threads, never two calls at once; \ a nonzero return cancels: -3; sort_mt's keys are then a permutation (the buckets done sorted), sort_kv_mt's keys \ and values unchanged, sort_indexed_mt's outputs unspecified
\
int kwker_##s##_sort_mt_progress(T* a, size_t n, uint32_t order, size_t threads, \
kwker_progress_fn progress, void* ctx); \
int kwker_##s##_sort_kv_mt_progress(T* keys, void* values, size_t value_size, size_t n, uint32_t order, \
size_t threads, kwker_progress_fn progress, void* ctx); \
int kwker_##s##_sort_indexed_mt_progress(const T* a, size_t n, uint32_t order, T* values, \
uint64_t* indices, size_t threads, \
kwker_progress_fn progress, void* ctx); \
int kwker_##s##_unique(const T* a, size_t n, T* values, uint64_t* inverse, uint64_t* counts, size_t threads, \
size_t* n_unique); \
int kwker_##s##_top_k_rows(const T* a, size_t rows, size_t row_len, size_t k, uint32_t order, int sorted, \
T* values, uint64_t* indices); \
int kwker_##s##_top_k_segments(const T* a, size_t n, const uint64_t* offsets, size_t count, size_t k, \
uint32_t order, int sorted, T* values, int64_t* indices); \
the batched row / segment operations on threads threads (0: the default; the same results): rows split \
into one part per thread, a single large row by the parallel sort, segments in parts of equal key counts
\
int kwker_##s##_sort_rows_mt(T* a, size_t rows, size_t row_len, uint32_t order, size_t threads); \
int kwker_##s##_sort_segments_mt(T* a, size_t n, const uint64_t* offsets, size_t count, uint32_t order, \
size_t threads); \
int kwker_##s##_argsort_rows_mt(const T* a, size_t rows, size_t row_len, uint32_t order, size_t threads, \
uint64_t* indices); \
int kwker_##s##_top_k_rows_mt(const T* a, size_t rows, size_t row_len, size_t k, uint32_t order, \
int sorted, size_t threads, T* values, uint64_t* indices); \
int kwker_##s##_sort_rows_indexed_mt(const T* a, size_t rows, size_t row_len, uint32_t order, \
size_t threads, T* values, uint64_t* indices); \
int kwker_##s##_argpartition_rows(const T* a, size_t rows, size_t row_len, size_t kth, uint32_t order, \
uint64_t* indices); \
int kwker_##s##_searchsorted(const T* sorted, size_t n, const T* queries, size_t m, uint32_t order, int side, \
uint64_t* out); \
int kwker_##s##_bucket_counts(const T* values, size_t n, const T* boundaries, size_t m, uint32_t order, \
int right, uint64_t* counts); \
int kwker_##s##_set_op(const T* a, size_t n, const T* b, size_t m, uint32_t order, int op, int multiset, \
T* out, size_t* out_len); \
int kwker_##s##_intersection_indices(const T* a, size_t n, const T* b, size_t m, uint32_t order, \
int multiset, uint64_t* ia, uint64_t* ib, size_t* count); \
int kwker_##s##_isin(const T* a, size_t n, const T* test, size_t m, int invert, uint8_t* out); \
int kwker_##s##_argsort_masked(const T* a, size_t n, const uint8_t* mask, int bitmap, uint32_t order, \
uint64_t* indices, size_t* count); \
int kwker_##s##_sort_masked(T* a, size_t n, const uint8_t* mask, int bitmap, uint32_t order); \
int kwker_##s##_argsort_field(const void* records, size_t n, size_t stride, size_t offset, uint32_t order, \
uint64_t* indices); \
int kwker_##s##_top_k_field(const void* records, size_t n, size_t stride, size_t offset, size_t k, \
uint32_t order, uint64_t* indices); \
int kwker_##s##_top_k_masked(const T* a, size_t n, const uint8_t* mask, int bitmap, size_t k, uint32_t order, \
int sorted, T* values, uint64_t* indices, size_t* count); \
int kwker_##s##_top_k_by_group(const T* a, size_t n, const int64_t* groups, size_t k, uint32_t order, \
int64_t* labels, uint64_t* offsets, uint64_t* indices, size_t* ngroups); \
int kwker_##s##_sort_axis(T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, size_t axis, \
uint32_t order); \
int kwker_##s##_argsort_axis(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, \
size_t axis, uint32_t order, uint64_t* out, const ptrdiff_t* out_strides); \
int kwker_##s##_sort_axis_indexed(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, \
size_t axis, uint32_t order, T* values, uint64_t* indices, \
const ptrdiff_t* out_strides); \
int kwker_##s##_sort_axis_indexed8(const T* a, size_t ndim, const size_t* shape, const ptrdiff_t* strides, \
size_t axis, uint32_t order, T* values, uint8_t* indices, \
const ptrdiff_t* out_strides); \
int kwker_##s##_sample(const T* a, size_t n, size_t m, uint64_t base, uint64_t seed, T* keys, uint64_t* pos); \
int kwker_##s##_sample_sorted(const T* a, size_t n, size_t m, uint64_t base, T* keys, uint64_t* pos); \
int kwker_##s##_splitters(const T* keys, const uint64_t* pos, size_t m, size_t parts, uint32_t order, \
T* sk, uint64_t* sp, size_t* count); \
int kwker_##s##_splitters_exact(const T* a, size_t n, uint64_t base, size_t parts, uint32_t order, T* sk, \
uint64_t* sp, size_t* count); \
int kwker_##s##_partition_splitters(T* a, size_t n, uint64_t base, const T* sk, const uint64_t* sp, \
size_t ns, uint32_t order, size_t* offsets); \
int kwker_##s##_partition_indices(const T* a, size_t n, uint64_t base, const T* sk, const uint64_t* sp, \
size_t ns, uint32_t order, uint64_t* indices, size_t* offsets); \
int kwker_##s##_split_points(const T* a, size_t n, uint64_t base, const T* sk, const uint64_t* sp, \
size_t ns, uint32_t order, size_t* offsets); \
int kwker_##s##_kway_merge(const T* const* runs, const size_t* lens, size_t k, uint32_t order, T* out); \
int kwker_##s##_kway_merge_kv(const T* const* runs, const void* const* values, size_t value_size, \
const size_t* lens, size_t k, uint32_t order, T* out, void* out_values);
#undef KWKER_DECLARE
#undef KWKER_SPARSE_DECLARE
#undef KWKER_QUANTILE_DECLARE
#undef KWKER_WINDOW_DECLARE
#undef KWKER_WINDOW_GRAD_DECLARE
#undef KWKER_ROBUST_DECLARE
kwker_<k>_reduce_by_key_v, kwker_<k>_reduce_by_key_mt_v, kwker_<k>_mean_by_key_v, ... Page
Reduce by key: the distinct keys of keys[0..n) in `order` into out_keys and one result per key; *out_groups = their
number (the outputs hold n elements - every key may be distinct). Groups are formed by sorting the pairs together.
kwker_k_reduce_by_key_v(const K* keys, const V* values, size_t n, int op, uint32_t order, K* out_keys,
V* out_values, size_t* out_groups)
op: KWKER_SUM (integers wrap; floats summed left to right in input order), KWKER_MIN / _MAX (in the
ascending sort order: -0.0 below +0.0, NaNs above all), KWKER_FIRST / _LAST (in input order)
kwker_k_reduce_by_key_mt_v(..., uint32_t order, size_t threads, K* out_keys, V* out_values, size_t* out_groups)
the same on `threads` threads (0: the default): chunks reduced in parallel, merged by key ranges; float sums add
the chunks' partial sums in chunk order (deterministic for a thread count)
kwker_k_mean_by_key_v(const K* keys, const V* values, size_t n, uint32_t order, K* out_keys, double* out_means,
size_t* out_groups)
kwker_k_count_by_key(const K* keys, size_t n, uint32_t order, K* out_keys, uint64_t* out_counts,
size_t* out_groups)
k: u8 i8 u16 i16 u32 i32 f32 u64 i64 f64; v: i32 i64 u32 u64 f32 f64.
#define KWKER_SUM 0
#define KWKER_MIN 1
#define KWKER_MAX 2
#define KWKER_FIRST 3
#define KWKER_LAST 4
int kwker_<ks>_reduce_by_key_<vs>(const K* keys, const V* values, size_t n, int op, uint32_t order,
K* out_keys, V* out_values, size_t* out_groups);
int kwker_<ks>_reduce_by_key_mt_<vs>(const K* keys, const V* values, size_t n, int op, uint32_t order,
size_t threads, K* out_keys, V* out_values, size_t* out_groups);
int kwker_<ks>_mean_by_key_<vs>(const K* keys, const V* values, size_t n, uint32_t order, K* out_keys,
double* out_means, size_t* out_groups);
int kwker_<ks>_count_by_key(const K* keys, size_t n, uint32_t order, K* out_keys, uint64_t* out_counts,
size_t* out_groups);
/* and kwker_<ks>_reduce_by_key_<vs>, _reduce_by_key_mt_<vs>, _mean_by_key_<vs> for vs = i32, i64, u32, u64, f32, f64 */
Declared for: u8 (uint8_t), i8 (int8_t), u16 (uint16_t), i16 (int16_t), u32 (uint32_t), i32 (int32_t), f32 (float), u64 (uint64_t), i64 (int64_t), f64 (double).
Examples: Groups, merges and sets: Totals per key: reduce_by_key
kwker_u128_sort, kwker_i128_sort Page
128-bit integer keys (unsigned __int128 / __int128 where the compiler has them - GCC, Clang: 16-byte little-endian
integers, 16-byte aligned), sorted in `order` (KWKER_DESCENDING or 0):
int kwker_u128_sort(void* a, size_t n, uint32_t order); int kwker_i128_sort(void* a, size_t n, uint32_t order);
int kwker_u128_sort(void* a, size_t n, uint32_t order);
int kwker_i128_sort(void* a, size_t n, uint32_t order);
Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
kwker_u128_select, kwker_i128_select, kwker_u128_partial_sort, ... Page
... and selection (k-th key at a[k], k < n), partial sort (the first min(k, n) keys sorted), top-k (the min(k, n) first keys and their indices, ties by index; values / indices may be NULL) and the stable argsort (n indices):
int kwker_u128_select(void* a, size_t n, size_t k, uint32_t order);
int kwker_i128_select(void* a, size_t n, size_t k, uint32_t order);
int kwker_u128_partial_sort(void* a, size_t n, size_t k, uint32_t order);
int kwker_i128_partial_sort(void* a, size_t n, size_t k, uint32_t order);
int kwker_u128_top_k(const void* a, size_t n, size_t k, uint32_t order, void* values, uint64_t* indices);
int kwker_i128_top_k(const void* a, size_t n, size_t k, uint32_t order, void* values, uint64_t* indices);
int kwker_u128_argsort(const void* a, size_t n, uint32_t order, uint64_t* indices);
int kwker_i128_argsort(const void* a, size_t n, uint32_t order, uint64_t* indices);
kwker_u128_sort_kv, kwker_i128_sort_kv Page
... and the stable key-value sort: each value_size-byte value moves with its key, equal keys' values in input order:
int kwker_u128_sort_kv(void* keys, void* values, size_t value_size, size_t n, uint32_t order);
int kwker_i128_sort_kv(void* keys, void* values, size_t value_size, size_t n, uint32_t order);
Remarks: Unless the stable form is asked for, pairs with equal keys may come out in any order; the stable form keeps their input order (rule 6). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
kwker_u32_sort_file, kwker_i32_sort_file, kwker_f32_sort_file, ... Page
Out-of-core sort of a file of native-endian keys of type <t> back to back (u8 i8 u16 i16 u32 i32 f32 u64 i64 f64 f16
bf16 f8e5m2 f8e4m3): sorted runs of about memory bytes (0: 256 MiB) spilled to a private directory in temp_dir (NULL:
the output's directory) and merged into output (may equal input); the run files are removed in every case.
Returns 0, -1 for invalid arguments, -2 for an I/O error or a length that is not a whole number of keys.
int kwker_u32_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_i32_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_f32_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_u64_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_i64_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_f64_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_u8_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_i8_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_u16_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_i16_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_f16_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_bf16_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_f8e5m2_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
int kwker_f8e4m3_sort_file(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order, size_t threads);
Examples: Large data: Sort a file larger than memory
kwker_u8_sort_file_records, kwker_i8_sort_file_records, kwker_u16_sort_file_records, ... Page
Out-of-core stable sort of a file of fixed-size records (record_size bytes each, back to back) by the native-endian <t> key at byte key_offset of every record: records with equal keys keep their file order; the record bytes move unchanged. memory, temp_dir and output as for kwker_<t>_sort_file. Returns 0, -1 for invalid arguments (a key that does not fit the record), -2 for an I/O error or a length that is not a whole number of records.
int kwker_u8_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_i8_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_u16_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_i16_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_u32_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_i32_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_f32_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_u64_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_i64_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_f64_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_f16_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_bf16_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_f8e5m2_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
int kwker_f8e4m3_sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, size_t memory, const char* temp_dir, uint32_t order);
kwker_u32_sort_file_progress, kwker_i32_sort_file_progress, kwker_f32_sort_file_progress, ... Page
... with a progress callback (NULL: none), called after each run and merge round with (ctx, keys done, keys in total over all phases); a nonzero return cancels: the call returns -3, the run files are removed, the output is incomplete.
int kwker_u32_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_i32_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_f32_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_u64_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_i64_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_f64_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_u8_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_i8_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_u16_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_i16_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_f16_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_bf16_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_f8e5m2_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
int kwker_f8e4m3_sort_file_progress(const char* input, const char* output, size_t memory, const char* temp_dir, uint32_t order,
size_t threads, kwker_progress_fn progress, void* ctx);
KWKER_TYPE_U8, KWKER_TYPE_I8, KWKER_TYPE_U16, ... Page
Lexicographic operations over several key columns of n rows (the first column most significant, each column in its
own order; equal tuples by row index - the stable order). A column: n keys of type at data (aligned to the type).
#define KWKER_TYPE_U8 1u
#define KWKER_TYPE_I8 2u
#define KWKER_TYPE_U16 3u
#define KWKER_TYPE_I16 4u
#define KWKER_TYPE_U32 5u
#define KWKER_TYPE_I32 6u
#define KWKER_TYPE_F32 7u
#define KWKER_TYPE_U64 8u
#define KWKER_TYPE_I64 9u
#define KWKER_TYPE_F64 10u
#define KWKER_TYPE_F16 11u
#define KWKER_TYPE_BF16 12u
#define KWKER_TYPE_F8E5M2 13u
#define KWKER_TYPE_F8E4M3 14u
typedef struct kwker_column {
const void* data;
uint32_t type; /* KWKER_TYPE_* */
uint32_t order; /* KWKER_DESCENDING | KWKER_NANS_FIRST, or 0 */
} kwker_column;
kwker_lexsort Page
The sorting permutation: perm[0..n) = the row indices in lexicographic order (ncols >= 1).
int kwker_lexsort(const kwker_column* cols, size_t ncols, size_t n, uint64_t* perm);
Examples: Order and ranking: Sort by several columns
kwker_lexsort_mt Page
... on threads threads (0: the default; the same permutation).
int kwker_lexsort_mt(const kwker_column* cols, size_t ncols, size_t n, uint64_t* perm, size_t threads);
kwker_lex_top_k Page
The first min(k, n) rows of that order into rows[0..min(k, n)) without sorting every row (ORDER BY .. LIMIT k).
int kwker_lex_top_k(const kwker_column* cols, size_t ncols, size_t n, size_t k, uint64_t* rows);
Examples: Order and ranking: Sort by several columns
kwker_lex_select Page
The row at position k (< n) of that order into *row, without sorting (O(n) per column).
int kwker_lex_select(const kwker_column* cols, size_t ncols, size_t n, size_t k, uint64_t* row);
kwker_f32_top_p, kwker_f64_top_p Page
Nucleus (top-p) sampling cut-off of rows of logits (LLM sampling: vLLM / Hugging Face's sort + softmax + cumsum rule,
without sorting the vocabulary): for each of rows rows of row_len logits, the indices of the most probable tokens
under softmax(row), most probable first (equal logits in index order), while the probability of the tokens before
each is below p (p > 0; p >= 1: every token with a nonzero probability). ids (rows * row_len uint32 entries) gets
the rows' indices one after another, ends[r] the end of row r's indices in ids. Probabilities: exp(logit - max) over
their sum in double (exponentials to ~1e-7 relative). NaN logits are never kept, a row of -inf / NaN keeps nothing,
+inf logits share the probability. -1: row_len 0 or >= 2^32, p <= 0 or NaN, a NULL pointer with rows > 0.
int kwker_f32_top_p(const float* logits, size_t rows, size_t row_len, double p, uint32_t* ids, uint64_t* ends);
int kwker_f64_top_p(const double* logits, size_t rows, size_t row_len, double p, uint32_t* ids, uint64_t* ends);
KWKER_NO_GROUP, KWKER_GROUP_SKIP_NAN, KWKER_GROUP_SUM, ... Page
Group-by. kwker_group_codes: each row's group into codes[0..n) - the groups numbered 0.. in the columns'
lexicographic order (equal order keys: one group) - and each group's first row and size into first / sizes (n entries
each; the first *groups written). kwker_<t>_group_reduce: one reduction per group over the rows' codes (below
groups, or KWKER_NO_GROUP = skipped) and values; valid: NULL or n bytes (nonzero = the row has a value); flags
KWKER_GROUP_SKIP_NAN: NaN is no value. op and the type of out[0..groups):
KWKER_GROUP_SUM double for float values, int64_t / uint64_t for signed / unsigned integers (wrapping)
KWKER_GROUP_MIN / _MAX the value type; NaN passed over unless the group holds NaNs only
KWKER_GROUP_FIRST_ROW / _LAST_ROW uint64_t: the group's first / last row with a value (UINT64_MAX: none)
KWKER_GROUP_COUNT uint64_t: rows with a value
KWKER_GROUP_MEDIAN double: the middle value, or the mean of the two middle values (NaN sorted largest)
counts: NULL or groups uint64_t - each group's rows with a value (sum, min, max, median; 0: out unspecified, NaN for
the median). threads: chunks of rows on that many threads (0: the default).
kwker_<t>_group_quantile: the q quantile (0 <= q <= 1) of each group's values into out[0..groups) as double - the
order statistics at q * (count - 1) combined by interpolation (0 linear: pandas groupby().quantile bit for bit with
KWKER_GROUP_SKIP_NAN, 1 lower, 2 higher, 3 midpoint, 4 nearest); NaN sorted largest; counts as for the median.
kwker_<t>_group_rank: each row's rank within its group into out[0..n) as double, 1-based - pandas
groupby().rank(method, ascending, pct) bit for bit: method KWKER_RANK_AVERAGE / _MIN / _MAX / _FIRST (row order among
equal values) / _DENSE; flags KWKER_RANK_PCT (divide by the group's count of values, of distinct values for dense),
KWKER_RANK_DESCENDING. Values compare as values (-0.0 = 0.0); a row without a value (valid 0, NaN, no group) gets
NaN and does not count.
#define KWKER_NO_GROUP 0xFFFFFFFFu
#define KWKER_GROUP_SKIP_NAN 1u
#define KWKER_GROUP_SUM 0u
#define KWKER_GROUP_MIN 1u
#define KWKER_GROUP_MAX 2u
#define KWKER_GROUP_FIRST_ROW 3u
#define KWKER_GROUP_LAST_ROW 4u
#define KWKER_GROUP_COUNT 5u
#define KWKER_GROUP_MEDIAN 6u
#define KWKER_RANK_AVERAGE 0u
#define KWKER_RANK_MIN 1u
#define KWKER_RANK_MAX 2u
#define KWKER_RANK_FIRST 3u
#define KWKER_RANK_DENSE 4u
#define KWKER_RANK_PCT 2u
#define KWKER_RANK_DESCENDING 4u
kwker_arrow_dense_ranks Page
Dense ranks of a (large) string / binary (or view), or fixed-size binary Arrow array (bytes order; null rows 0) into ranks[0..length), *distinct = the number of distinct values: one hash pass plus a sort of the distinct values. -2: another type.
int kwker_arrow_dense_ranks(const struct ArrowSchema* schema, const struct ArrowArray* array, uint32_t* ranks, size_t* distinct);
kwker_arrow_dense_ranks_mt, kwker_group_codes Page
kwker_arrow_dense_ranks on threads threads (0: the default; the same ranks): one hash table per row range, merged.
int kwker_arrow_dense_ranks_mt(const struct ArrowSchema* schema, const struct ArrowArray* array, size_t threads, uint32_t* ranks,
size_t* distinct);
int kwker_group_codes(const kwker_column* cols, size_t ncols, size_t n, size_t threads, uint32_t* codes, uint64_t* first,
uint64_t* sizes, size_t* groups);
Examples: Groups, merges and sets: Group several key columns: group_codes
kwker_group_cumcount Page
pandas groupby().cumcount(): each row's position among the rows of its group (codes as kwker_group_codes', below groups or KWKER_NO_GROUP) in row order into out[0..n), from 0 (ascending 0: counted from the group's last row); -1 for a row without a group.
int kwker_group_cumcount(const uint32_t* codes, size_t n, size_t groups, int ascending, int64_t* out);
int kwker_<ks>_group_reduce(const uint32_t* codes, size_t n, size_t groups, const V* values, const uint8_t* valid,
uint32_t op, uint32_t flags, size_t threads, void* out, uint64_t* counts);
Declared for: u8 (uint8_t), i8 (int8_t), u16 (uint16_t), i16 (int16_t), u32 (uint32_t), i32 (int32_t), f32 (float), u64 (uint64_t), i64 (int64_t), f64 (double).
sum (op SUM's type), count, min and max in one pass over the rows; any output NULL: not written
\
int kwker_##ks##_group_stats(const uint32_t* codes, size_t n, size_t groups, const V* values, const uint8_t* valid, \
uint32_t flags, size_t threads, void* sum, uint64_t* count, V* min, V* max); \
int kwker_##ks##_group_quantile(const uint32_t* codes, size_t n, size_t groups, const V* values, \
const uint8_t* valid, double q, int interpolation, uint32_t flags, size_t threads, \
double* out, uint64_t* counts); \
int kwker_##ks##_group_rank(const uint32_t* codes, size_t n, size_t groups, const V* values, const uint8_t* valid, \
uint32_t method, uint32_t flags, double* out); \
pandas groupby().cumsum(): each row's running sum of its group in row order into out[0..n) (the SUM type: double \ for floats, int64_t / uint64_t for integers, wrapping); flags bit 0: NaN is no value (skipna); a row without a \ value or group gets NaN (integers: 0) and leaves its group's sum as it is
\
int kwker_##ks##_group_cumsum(const uint32_t* codes, size_t n, size_t groups, const V* values, const uint8_t* valid, \
uint32_t flags, void* out); \
pandas groupby().shift(periods) / diff(periods) as double into out[0..n): the value periods rows earlier in \
the row's group (negative: later) / this value minus it; NaN where there is none or the row has no group
\
int kwker_##ks##_group_shift(const uint32_t* codes, size_t n, size_t groups, const V* values, int64_t periods, \
double* out); \
int kwker_##ks##_group_diff(const uint32_t* codes, size_t n, size_t groups, const V* values, int64_t periods, \
double* out); \
the inversions of a[0..n) in order into *out: pairs i < j whose keys stand the other way round (equal values \
none) - Kendall tau's discordant pairs
\
int kwker_##ks##_count_inversions(const V* a, size_t n, uint32_t order, uint64_t* out); \
per row r of a (rows x ka) and b (rows x kb): the adjacent equal pairs of row r's ka + kb keys sorted (|A_r & B_r| \ for distinct ids; values compare as values) into out[0..rows)
\
int kwker_##ks##_row_intersect_count(const V* a, size_t ka, const V* b, size_t kb, size_t rows, uint64_t* out); \
the number of distinct values in each row of a (rows x k, row-major; values compare as values: -0.0 = +0.0, every \ NaN one value) into out[0..rows)
\
int kwker_##ks##_row_unique_count(const V* a, size_t k, size_t rows, uint64_t* out);
#undef KWKER_GROUP_REDUCE
kwker_asof_indices Page
As-of join (point-in-time lookup; pandas merge_asof, Polars join_asof): for each of the n left rows the index of its match among the m right rows into out[0..n), -1 for none. direction 0 = backward (the right row with the largest time <= the left time; among equal times the last in input order), 1 = forward (the smallest time >= it; the first), 2 = nearest (the closer of the two; a tie takes the backward one). left_by / right_by: both NULL, or n / m int64 keys - then only rows of equal keys match. The rows need not be sorted.
int kwker_asof_indices(const int64_t* left_t, size_t n, const int64_t* right_t, size_t m, const int64_t* left_by,
const int64_t* right_by, uint32_t direction, int64_t* out);
kwker_f32_histogram, kwker_f64_histogram Page
np.histogram(x, bins, range=(lo, hi)) counts, bin for bin: x[0..n) in bins uniform bins over [lo, hi] (edges =
np.linspace(lo, hi, bins + 1) rounded to the value type; the last bin includes hi; values outside and NaNs not counted;
lo == hi widens the range by 0.5 each side) into out[0..bins). lo, hi finite, lo <= hi, bins > 0.
int kwker_f32_histogram(const float* x, size_t n, size_t bins, double lo, double hi, uint64_t* out);
int kwker_f64_histogram(const double* x, size_t n, size_t bins, double lo, double hi, uint64_t* out);
kwker_logit_filter Page
Sort-free logit filters of LLM sampling on rows x cols float32 logits, into out (the same shape; may not overlap x):
kind 0 = top-n-sigma (param n: logits below max - n x the row's sample std become fill), 1 = min-p (param p in
(0, 1]: logits below max + ln p - probability under p x the top one - become fill). A row holding a NaN keeps all.
int kwker_logit_filter(const float* x, size_t rows, size_t cols, uint32_t kind, double param, float fill, float* out);
kwker_buffer_free Page
Output memory for results made over and over (a binding's large arrays): at least bytes from the library's cache of
2 MB-aligned mappings, uninitialized; *capacity (if not NULL) gets the block's size. Freed blocks are kept and reused,
so a result rewritten every call does not page-fault its memory again. NULL - allocate as usual - below 4 MB, off
Linux, or with the mapped scratch cache off. Give it back with kwker_buffer_free(p, capacity).
void* kwker_buffer_alloc(size_t bytes, size_t* capacity);
void kwker_buffer_free(void* p, size_t capacity);
kwker_top_k_filter Page
Per-request top-k filter of LLM sampling (vLLM's per-row k) on rows x cols float32 logits, into out (the same shape; may
not overlap x): in row r, logits below its ks[r]-th largest become fill - logits equal to it stay, so ties keep more
than k. ks[r] <= 0 or >= cols keeps the row whole; NaN counts as the largest value (a NaN cut-off keeps the row).
int kwker_top_k_filter(const float* x, size_t rows, size_t cols, const int64_t* ks, float fill, float* out);
kwker_f64_cdf_distance, kwker_f32_cdf_distance Page
Distance between the empirical distributions of a[0..na) and b[0..nb) into *out (double): kind 0 = the two-sample Kolmogorov-Smirnov statistic (sup |F_a - F_b|), 1 = the 1-D Wasserstein (earth mover's) distance, 2 = the energy distance - SciPy's ks_2samp(a, b).statistic, wasserstein_distance, energy_distance (unweighted). Each sample sorted once (copies; the inputs are not changed), then one merge walk. NaN in either sample, or an empty one: NaN.
int kwker_f64_cdf_distance(const double* a, size_t na, const double* b, size_t nb, uint32_t kind, double* out);
int kwker_f32_cdf_distance(const float* a, size_t na, const float* b, size_t nb, uint32_t kind, double* out);
kwker_f64_cdf_terms Page
The arrays SciPy's wasserstein_distance / energy_distance reduce, for the pooled sorted values of a[0..na) and b[0..nb): terms[0..na + nb - 1) = |F_a - F_b| at each pooled value but the last (squared != 0: its square) and deltas = the gap from each to the next - the same double operations as SciPy, so np.vecdot(terms, deltas) is its result bit for bit. Each sample sorted once (copies). NaN in either sample or an empty one: a nonzero return.
int kwker_f64_cdf_terms(const double* a, size_t na, const double* b, size_t nb, int squared, double* terms, double* deltas);