C++ API reference
kwker.hpp, the header-only C++ API over the C library: every function and type, with its parameters and results
(Kwker 0.1.0).
kwker.hpp - the C++ API of Kwker: header-only templates in namespace kwker over the C library (kwker.h, libkwker_c), which picks the fastest engine for the CPU at run time. C++17; std::span overloads with C++20.
#include <kwker.hpp>
std::vector
Keys: uint8_t / int8_t / uint16_t / int16_t / uint32_t / int32_t / float / uint64_t / int64_t / double (and char,
short, int, long and long long of those widths); f16 / bf16 / f8e5m2 / f8e4m3 (the bits of the low-precision
floats; _Float16 and __bf16 directly); unsigned __int128 / __int128 for sort / select / partial_sort / top_k /
argsort / sort_kv. Invalid arguments throw std::invalid_argument, I/O errors std::runtime_error.
Also: rows, segments and N-d arrays sort_rows, sort_segments, argsort_rows, top_k_rows, sort_axis, argsort_axis, sort_rows_indexed, kth_rows, kth_axis, sort_axis_indexed(8), argpartition(_rows) selection and ranks argselect, top_k_masked, top_k_by_group, kth, rank (Ties), rank_average, percent_rank, quantile_axis, quantile (Interpolation) sets, groups and merges set_op, intersection_indices, unique, reduce_by_key, mean_by_key, count_by_key (Combine), kway_merge, kway_merge_kv threads and buffers sort_mt, argsort_mt, sort_indexed, sort_kv_mt, Workspace + argsort_into, scratch_bound, capabilities_json, progress callbacks and cancellation records and strings argsort_field, argsort_by, top_k_by, take, permute_in_place, argsort_strings, sort_strings (Collation) other data sort_file (larger than memory), sparse matrices (coo_coalesce, coo_to_csr, coo_to_csc, csr_to_csc, csc_to_csr; Reduce), arrow_argsort / arrow_top_k (ArrowOptions), median3x3 (Pad), packed int4 sorts, argsort_masked / sort_masked distributed sorting sample, sample_sorted, splitters, splitters_exact, partition, partition_indices, split_points (Splitters)
Declarations
enum class Order Page
The order of a call's result: direction (ascending, descending) and NaN placement (last by default, first with nans_first) - the C ABI's KWKER_DESCENDING / KWKER_NANS_FIRST bits.
enum class Order : uint32_t
struct f16 / struct bf16 / struct f8e5m2 / struct f8e4m3 Page
Low-precision float keys by their bits: IEEE binary16, bfloat16, OCP FP8 E5M2 and E4M3 (ordered as the floats they encode: -0 before +0, NaNs last). _Float16 / std::float16_t and __bf16 / std::bfloat16_t keys work directly.
struct f16
struct bf16
struct f8e5m2
struct f8e4m3
sort Page
Sorts a[0..n) in place (not stable: equal keys are identical).
Throws: std::invalid_argument
template <class T> void sort(T* a, size_t n, Order o = Order::ascending)
template <class T, class A> void sort(std::vector<T, A>& v, Order o = Order::ascending)
template <class T, size_t E> void sort(std::span<T, E> s, Order o = Order::ascending)
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.
Examples: Quickstart: Kwker Core: Sort an array, Core concepts: In place or a copy, Runtime controls: Fallback switches, Sorting: Sort in place
select Page
a[k] gets the key a full sort would put there; every key before it sorts before or equal to it, every key after it after or equal. Neither side is sorted.
Throws: std::invalid_argument
template <class T> void select(T* a, size_t n, size_t k, Order o = Order::ascending)
Remarks: Position k holds the key a full sort puts there; the keys before it are ordered before or equal to it, the keys after it after or equal (rule 7). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Quickstart: Kwker Core: The median, without a full sort, Top-k and selection: The median and other positions
partial_sort Page
The first min(k, n) keys in order, the rest in any order.
Throws: std::invalid_argument
template <class T> void partial_sort(T* a, size_t n, size_t k, Order o = Order::ascending)
Remarks: The first k positions hold exactly what a full sort puts there; the rest hold the other keys in any order (rule 8). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Top-k and selection: Sort only the beginning
argsort Page
The stable sorting permutation of a[0..n) (a unchanged).
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> argsort(const T* a, size_t n, Order o = Order::ascending)
Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Quickstart: Kwker Core: Get the order, not the sorted data, Order and ranking: The order of an array: argsort, Large data: Use several cores, Languages: The same calls in every language
top_k Page
The first min(k, n) keys of the stable order and their indices (ties by index); sorted = false: in any order.
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> top_k(const T* a, size_t n, size_t k, Order o = Order::ascending, bool sorted = true)
Remarks: The first k keys of the stable order and their positions; equal keys keep their input order (rule 9). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Quickstart: Kwker Core: Find the top results, Use Kwker from C and C++: The program, Top-k and selection: The k largest or smallest values, Languages: The same calls in every language
sort_kv Page
Sorts keys[0..n) in place and moves values[0..n) with them (V: any trivially copyable type, any size).
Throws: std::invalid_argument
template <class T, class V> void sort_kv(T* keys, V* values, size_t n, Order o = Order::ascending)
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.
Examples: Core concepts: In place or a copy, Sorting keys with values: Sort keys and values together
sort_kv_stable Page
sort_kv, stable: equal keys keep their values in input order (allocates O(n)).
Throws: std::invalid_argument
template <class T, class V> void sort_kv_stable(T* keys, V* values, size_t n, Order o = Order::ascending)
Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Sorting keys with values: Keep equal keys in order: the stable sort
select_kv Page
keys[k] gets the key a full sort would put there, with its value; every key before it sorts before or equal to it, every key after it after or equal. Neither side is sorted. (k < n)
Throws: std::invalid_argument
template <class T, class V> void select_kv(T* keys, V* values, size_t n, size_t k, Order o = Order::ascending)
Remarks: Position k holds the key a full sort puts there; the keys before it are ordered before or equal to it, the keys after it after or equal (rule 7). 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).
partial_sort_kv Page
The first min(k, n) keys in order sorted, each with its value.
Throws: std::invalid_argument
template <class T, class V> void partial_sort_kv(T* keys, V* values, size_t n, size_t k, Order o = Order::ascending)
Remarks: The first k positions hold exactly what a full sort puts there; the rest hold the other keys in any order (rule 8). 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).
Examples: Sorting keys with values: Only the first k pairs
struct Column Page
One key column of lexsort / lex_top_k / lex_select: n keys at data in their own order.
struct Column
lexsort Page
The stable permutation sorting the rows by the columns, the first most significant (numpy.lexsort with the keys in reading order, each column in its own order).
Throws: std::invalid_argument
inline std::vector<uint64_t> lexsort(const std::vector<Column>& cols, size_t threads = 1)
Examples: Order and ranking: Sort by several columns
lex_top_k Page
The first min(k, n) rows of that order, without sorting every row (ORDER BY .. LIMIT k).
Throws: std::invalid_argument
inline std::vector<uint64_t> lex_top_k(const std::vector<Column>& cols, size_t k)
Examples: Order and ranking: Sort by several columns
lex_select Page
The row at position k (< n) of that order, without sorting.
Throws: std::invalid_argument
inline uint64_t lex_select(const std::vector<Column>& cols, size_t k)
struct Groups / group_codes Page
The groups of equal key tuples of the columns: each row's group (the groups numbered in the columns' lexicographic order), each group's first row and size.
Throws: std::invalid_argument
struct Groups
inline Groups group_codes(const std::vector<Column>& cols, size_t threads = 1)
Examples: Groups, merges and sets: Group several key columns: group_codes
group_sum / group_min / group_max / group_first_rows / group_last_rows / group_count / group_median Page
Group reductions over values[0..g.codes.size()): valid = nullptr or one byte per row (nonzero: a value), skip_nan = NaN is no value; counts (optional): each group's number of values (0: the result is unspecified, NaN for medians). Sums: double for floats, int64_t / uint64_t for integers (wrapping); NaN passed over by min / max unless a group holds NaNs only; first / last rows: UINT64_MAX = none; medians exact (NaN sorted largest).
Throws: std::invalid_argument
template <class T> std::vector<typename detail::GroupApi<T>::sum_t> group_sum(const Groups& g, const T* values, const uint8_t* valid = nullptr, bool skip_nan = false, size_t threads = 1, std::vector<uint64_t>* counts = nullptr)
template <class T> std::vector<T> group_min(const Groups& g, const T* values, const uint8_t* valid = nullptr, bool skip_nan = false, size_t threads = 1, std::vector<uint64_t>* counts = nullptr)
template <class T> std::vector<T> group_max(const Groups& g, const T* values, const uint8_t* valid = nullptr, bool skip_nan = false, size_t threads = 1, std::vector<uint64_t>* counts = nullptr)
template <class T> std::vector<uint64_t> group_first_rows(const Groups& g, const T* values, const uint8_t* valid = nullptr, bool skip_nan = false, size_t threads = 1)
template <class T> std::vector<uint64_t> group_last_rows(const Groups& g, const T* values, const uint8_t* valid = nullptr, bool skip_nan = false, size_t threads = 1)
template <class T> std::vector<uint64_t> group_count(const Groups& g, const T* values, const uint8_t* valid = nullptr, bool skip_nan = false, size_t threads = 1)
template <class T> std::vector<double> group_median(const Groups& g, const T* values, const uint8_t* valid = nullptr, bool skip_nan = false, size_t threads = 1, std::vector<uint64_t>* counts = nullptr)
searchsorted Page
Insertion positions of queries[0..m) in sorted[0..n) (sorted in order o): lower bounds, or upper bounds with right.
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> searchsorted(const T* sorted, size_t n, const T* queries, size_t m, bool right = false, Order o = Order::ascending)
Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).
Examples: Searching sorted data: Where does a value go? searchsorted, Searching sorted data: Which bucket? bucketize
bucket_counts Page
Values per bucket of the sorted boundaries[0..m) (sorted in order o): m + 1 counts; bucket i holds boundaries[i - 1] < v <= boundaries[i] (torch.bucketize), or boundaries[i - 1] <= v < boundaries[i] with right.
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> bucket_counts(const T* values, size_t n, const T* boundaries, size_t m, bool right = false, Order o = Order::ascending)
Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).
Examples: Searching sorted data: How many in each bucket? bucket_counts
argselect Page
The indices of the stable order's first min(k, n) keys, in any order.
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> argselect(const T* a, size_t n, size_t k, Order o = Order::ascending)
Remarks: The positions of the stable order's first k keys, in any 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.
Examples: Top-k and selection: Only the positions
sort_rows Page
Sorts each row of the row-major rows x row_len array a.
Throws: std::invalid_argument
template <class T> void sort_rows(T* a, size_t rows, size_t row_len, Order o = Order::ascending)
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.
Examples: Sorting: Sort each row
sort_segments Page
Sorts every a[offsets[i] .. offsets[i + 1]) (offsets nondecreasing, the last <= n; keys outside them untouched).
Throws: std::invalid_argument
template <class T> void sort_segments(T* a, size_t n, const uint64_t* offsets, size_t count, Order o = Order::ascending)
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.
argsort_rows Page
The stable permutation of each row (row-relative indices, rows x row_len).
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> argsort_rows(const T* a, size_t rows, size_t row_len, Order o = Order::ascending)
Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
top_k_rows Page
Each row's first k keys and their row-relative indices (row i's at [i * k, (i + 1) * k)); k <= row_len.
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> top_k_rows(const T* a, size_t rows, size_t row_len, size_t k, Order o = Order::ascending, bool sorted = true)
Remarks: The first k keys of the stable order and their positions; equal keys keep their input order (rule 9). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
sort_rows_mt / sort_segments_mt / argsort_rows_mt / top_k_rows_mt Page
sort_rows / sort_segments / argsort_rows / top_k_rows on threads threads (0: the default; the same results).
Throws: std::invalid_argument
template <class T> void sort_rows_mt(T* a, size_t rows, size_t row_len, Order o, size_t threads)
template <class T> void sort_segments_mt(T* a, size_t n, const uint64_t* offsets, size_t count, Order o, size_t threads)
template <class T> std::vector<uint64_t> argsort_rows_mt(const T* a, size_t rows, size_t row_len, Order o, size_t threads)
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> top_k_rows_mt(const T* a, size_t rows, size_t row_len, size_t k, Order o, bool sorted, size_t threads)
enum class Ties Page
How equal keys rank: ordinal (stable, by index), min, max or dense (consecutive ranks per distinct key).
enum class Ties : int
rank Page
The 1-based rank of every key (ranks[i]: of a[i]).
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> rank(const T* a, size_t n, Order o = Order::ascending, Ties t = Ties::ordinal)
Remarks: Ordinal ranks give equal keys increasing ranks in input order (rule 6). Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).
Examples: Order and ranking: Ranks
rank_average Page
Average ranks (1-based; equal keys share their mean rank).
Throws: std::invalid_argument
template <class T> std::vector<double> rank_average(const T* a, size_t n, Order o = Order::ascending)
Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).
Examples: Order and ranking: Ranks
percent_rank Page
Percent ranks: (min rank - 1) / (n - 1).
Throws: std::invalid_argument
template <class T> std::vector<double> percent_rank(const T* a, size_t n, Order o = Order::ascending)
Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).
Examples: Order and ranking: Ranks
enum class SetOp Page
The set operation of set_op / set_op_indices.
enum class SetOp : int
set_op Page
a op b; multiset = false: each value once, true: copy counts min / max / a - b / |a - b|.
Throws: std::invalid_argument
template <class T> std::vector<T> set_op(const T* a, size_t n, const T* b, size_t m, SetOp op, bool multiset = false, Order o = Order::ascending)
Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).
Examples: Groups, merges and sets: Set operations
intersection_indices Page
The positions of the intersection's keys in a and in b.
Throws: std::invalid_argument
template <class T> std::pair<std::vector<uint64_t>, std::vector<uint64_t>> intersection_indices(const T* a, size_t n, const T* b, size_t m, bool multiset = false, Order o = Order::ascending)
top_k_masked Page
The first k keys (and indices) among the positions mask selects: bitmap = false one byte per key (nonzero takes part), true an Arrow validity bitmap (LSB first).
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> top_k_masked(const T* a, size_t n, const uint8_t* mask, bool bitmap, size_t k, Order o = Order::ascending, bool sorted = true)
Examples: Top-k and selection: Top-k with a filter
struct GroupTopK / top_k_by_group Page
Top k per group label: the distinct labels ascending, group i's indices at indices[offsets[i] .. offsets[i + 1]).
Throws: std::invalid_argument
struct GroupTopK
template <class T> GroupTopK top_k_by_group(const T* a, size_t n, const int64_t* groups, size_t k, Order o = Order::ascending)
Examples: Top-k and selection: Top-k per group
sort_axis Page
Sorts every lane along axis of the array at a (the element at index (0, .., 0)) with the given shape; strides in elements (any sign; empty = C order). Strided lanes are gathered, sorted and scattered back (see kwker.h).
Throws: std::invalid_argument
template <class T> void sort_axis(T* a, const std::vector<size_t>& shape, size_t axis, Order o = Order::ascending, const std::vector<ptrdiff_t>& strides = {})
argsort_axis Page
The stable permutation of every lane along axis (lane-relative indices), as a C-order array of the same shape.
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> argsort_axis(const T* a, const std::vector<size_t>& shape, size_t axis, Order o = Order::ascending, const std::vector<ptrdiff_t>& strides = {})
enum class Reduce Page
How duplicate coordinates combine: sum, product, min, max or mean (integers wrap; the mean truncates).
enum class Reduce : int
struct Coo / struct Compressed Page
A sparse matrix in coordinates (COO): parallel rows / cols / vals; Compressed: CSR (indptr over rows, indices = columns) or CSC (indptr over columns, indices = rows), the layout named by the function that returns it.
template <class V> struct Coo
template <class V> struct Compressed
coo_coalesce Page
The coordinates sorted row-major, each distinct (row, col) once with its duplicates' values combined.
Throws: std::invalid_argument
template <class V> Coo<V> coo_coalesce(const uint64_t* rows, const uint64_t* cols, const V* vals, size_t nnz, uint64_t nrows, uint64_t ncols, Reduce r = Reduce::sum)
coo_to_csr Page
COO -> CSR: indptr[nrows + 1], each row's column indices ascending, duplicates combined.
Throws: std::invalid_argument
template <class V> Compressed<V> coo_to_csr(const uint64_t* rows, const uint64_t* cols, const V* vals, size_t nnz, uint64_t nrows, uint64_t ncols, Reduce r = Reduce::sum)
csr_to_csc Page
CSR -> CSC without a sort (a.indptr: nrows + 1 entries): colptr[ncols + 1], each column's rows ascending, duplicates kept. threads: 1, 0 for the default count, or a count - the same output.
Throws: std::invalid_argument
template <class V> Compressed<V> csr_to_csc(const Compressed<V>& a, uint64_t nrows, uint64_t ncols, size_t threads = 1)
csc_to_csr Page
CSC -> CSR without a sort (a.indptr: ncols + 1 entries): indptr[nrows + 1], each row's columns ascending.
Throws: std::invalid_argument
template <class V> Compressed<V> csc_to_csr(const Compressed<V>& a, uint64_t nrows, uint64_t ncols, size_t threads = 1)
coo_to_csc Page
COO -> CSC: indptr[ncols + 1], each column's row indices ascending, duplicates combined.
Throws: std::invalid_argument
template <class V> Compressed<V> coo_to_csc(const uint64_t* rows, const uint64_t* cols, const V* vals, size_t nnz, uint64_t nrows, uint64_t ncols, Reduce r = Reduce::sum)
argsort_masked Page
The stable permutation of the selected positions only (their indices in key order; the others left out).
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> argsort_masked(const T* a, size_t n, const uint8_t* mask, bool bitmap, Order o = Order::ascending)
sort_masked Page
Sorts the selected keys among their own positions; the other keys stay where they are.
Throws: std::invalid_argument
template <class T> void sort_masked(T* a, size_t n, const uint8_t* mask, bool bitmap, Order o = Order::ascending)
argsort_field Page
The stable permutation of n records of stride bytes at records by the K at byte offset of each (any alignment): the records are not moved (n keys are copied into a buffer).
Throws: std::invalid_argument
template <class Kt> std::vector<uint64_t> argsort_field(const void* records, size_t n, size_t stride, size_t offset, Order o = Order::ascending)
top_k_field Page
The indices of the first min(k, n) records by that key (ties by index, in key order).
Throws: std::invalid_argument
template <class Kt> std::vector<uint64_t> top_k_field(const void* records, size_t n, size_t stride, size_t offset, size_t k, Order o = Order::ascending)
argsort_by Page
The stable permutation of recs[0..n) by a numeric data member: argsort_by(trades, n, &Trade::price).
Throws: std::invalid_argument
template <class R, class Kt> std::vector<uint64_t> argsort_by(const R* recs, size_t n, Kt R::*member, Order o = Order::ascending)
top_k_by Page
The indices of the first min(k, n) records by a data member.
Throws: std::invalid_argument
template <class R, class Kt> std::vector<uint64_t> top_k_by(const R* recs, size_t n, Kt R::*member, size_t k, Order o = Order::ascending)
enum class Collation Page
How strings compare: bytes (unsigned, lexicographic), ASCII case-insensitive, natural (digit runs by value) or both.
enum class Collation : uint32_t
argsort_strings Page
The stable order of the strings (anything with data() and size(): std::string, std::string_view).
Throws: std::invalid_argument
template <class S> std::vector<uint64_t> argsort_strings(const std::vector<S>& v, Collation c = Collation::bytes)
Examples: Strings: The order of strings
argsort_fixed_strings_field Page
The stable order of n records of stride bytes by the width-byte string field at byte offset (trailing NULs not part of it; COBOL PIC X keys, char[] members): the records are not moved.
Throws: std::invalid_argument
inline std::vector<uint64_t> argsort_fixed_strings_field(const void* records, size_t n, size_t stride, size_t offset, size_t width, Collation c = Collation::bytes)
char Page
The stable permutation of recs[0..n) by a char[W] data member: argsort_by_string(people, n, &Person::name).
template <class R, size_t W> std::vector<uint64_t> argsort_by_string(const R* recs, size_t n, char (R::*member)[W], Collation c = Collation::bytes)
sort_strings Page
Sorts the strings in place under the collation (moved, not copied).
Throws: std::invalid_argument
template <class S> void sort_strings(std::vector<S>& v, Collation c = Collation::bytes)
Examples: Strings: Sort a list of strings
using Weights / enum class Table Page
A collating sequence as 256 byte weights (w[b] = byte b's weight; equal weights = equal characters).
using Weights = std::array<uint8_t, 256>
enum class Table : uint32_t
collation_table Page
A built-in collating sequence's weights: Table::ebcdic_037 orders ASCII / Latin-1 text as EBCDIC 037 does.
Throws: std::invalid_argument
inline Weights collation_table(Table t)
argsort_strings Page
The stable order of the strings under byte weights (a prefix first).
Throws: std::invalid_argument
template <class S> std::vector<uint64_t> argsort_strings(const std::vector<S>& v, const Weights& w)
Examples: Strings: The order of strings
argsort_fixed_strings_field Page
The order of n records by their width-byte field at byte offset under byte weights (every byte of the field counts, as COBOL compares fixed-length fields): the records are not moved.
Throws: std::invalid_argument
inline std::vector<uint64_t> argsort_fixed_strings_field(const void* records, size_t n, size_t stride, size_t offset, size_t width, const Weights& w)
char Page
argsort_by_string under byte weights (every byte of the member counts).
template <class R, size_t W> std::vector<uint64_t> argsort_by_string(const R* recs, size_t n, char (R::*member)[W], const Weights& w)
sort_strings Page
Sorts the strings in place under byte weights (moved, not copied).
Throws: std::invalid_argument
template <class S> void sort_strings(std::vector<S>& v, const Weights& w)
Examples: Strings: Sort a list of strings
struct Splitters Page
Keys with positions: a sample, or splitters (parts() = keys.size() + 1 partitions).
template <class T> struct Splitters
sample Page
A stratified random sample of min(m, n) keys with their positions (deterministic for a seed).
Throws: std::invalid_argument
template <class T> Splitters<T> sample(const T* a, size_t n, size_t m, uint64_t base = 0, uint64_t seed = 0)
sample_sorted Page
The regular sample of sorted keys: min(m, n) keys at ranks (j + 1) n / (m + 1) with their positions.
Throws: std::invalid_argument
template <class T> Splitters<T> sample_sorted(const T* sorted, size_t n, size_t m, uint64_t base = 0)
splitters Page
parts - 1 splitters from a sample gathered from every worker (an empty sample: one part).
Throws: std::invalid_argument
template <class T> Splitters<T> splitters(const Splitters<T>& sample, size_t parts, Order o = Order::ascending)
splitters_exact Page
Exact quantile splitters of n keys: parts of floor / ceil(n / parts), whatever the duplicates.
Throws: std::invalid_argument
template <class T> Splitters<T> splitters_exact(const T* a, size_t n, size_t parts, uint64_t base = 0, Order o = Order::ascending)
partition Page
Reorders a by partition in place (unordered inside a part); the parts() + 1 offsets.
Throws: std::invalid_argument
template <class T> std::vector<size_t> partition(T* a, size_t n, const Splitters<T>& s, uint64_t base = 0, Order o = Order::ascending)
partition_indices Page
The indices of a grouped by partition (ascending inside a part) and the parts() + 1 offsets.
Throws: std::invalid_argument
template <class T> std::pair<std::vector<uint64_t>, std::vector<size_t>> partition_indices(const T* a, size_t n, const Splitters<T>& s, uint64_t base = 0, Order o = Order::ascending)
split_points Page
The parts() + 1 partition offsets of stably sorted keys.
Throws: std::invalid_argument
template <class T> std::vector<size_t> split_points(const T* sorted, size_t n, const Splitters<T>& s, uint64_t base = 0, Order o = Order::ascending)
kway_merge Page
Sorted runs (pointer, length) merged, equal keys by run then index.
Throws: std::invalid_argument
template <class T> std::vector<T> kway_merge(const std::vector<std::pair<const T*, size_t>>& runs, Order o = Order::ascending)
Examples: Groups, merges and sets: Merge sorted lists: kway_merge
kway_merge_kv Page
Sorted key runs with their values (trivially copyable), merged: keys into out_keys, values into out_values.
Throws: std::invalid_argument
template <class T, class V> void kway_merge_kv(const std::vector<std::pair<const T*, size_t>>& runs, const std::vector<const V*>& values, std::vector<T>& out_keys, std::vector<V>& out_values, Order o = Order::ascending)
take Page
The records at idx (any indices < n, repeats allowed), copied in that order.
Throws: std::invalid_argument
template <class R> std::vector<R> take(const R* recs, size_t n, const std::vector<uint64_t>& idx)
permute_in_place Page
Rearranges recs[0..n) in place so that record j becomes the one at perm[j] (an argsort's result applied): no record buffer. Throws std::invalid_argument (nothing moved) unless perm is a permutation of 0..n.
Throws: std::invalid_argument
template <class R> void permute_in_place(R* recs, size_t n, const std::vector<uint64_t>& perm)
Examples: Order and ranking: Reorder records in place
struct ArrowOptions Page
Arrow sort options: descending, nulls first, by_codes (dictionary arrays by their codes instead of their values).
struct ArrowOptions
arrow_argsort Page
The stable sorting permutation of an Arrow array (pyarrow.compute.array_sort_indices's result).
Throws: std::invalid_argument
inline std::vector<uint64_t> arrow_argsort(const ArrowSchema& schema, const ArrowArray& array, ArrowOptions o = {})
arrow_top_k Page
The first min(k, length) rows of that order (ORDER BY .. LIMIT k).
Throws: std::invalid_argument
inline std::vector<uint64_t> arrow_top_k(const ArrowSchema& schema, const ArrowArray& array, size_t k, ArrowOptions o = {})
arrow_argsort_chunks Page
A chunked array - chunks of schema's type, in order (a ChunkedArray, a stream's batches) - ordered as one array of their summed length without combining it (indices into the concatenation): every type arrow_argsort reads (see kwker_arrow_argsort_chunks); another throws std::invalid_argument (combine the chunks, then arrow_argsort).
Throws: std::invalid_argument
inline std::vector<uint64_t> arrow_argsort_chunks(const ArrowSchema& schema, const std::vector<const ArrowArray*>& chunks, ArrowOptions o = {})
arrow_top_k_chunks Page
The first min(k, summed length) rows of that order.
Throws: std::invalid_argument
inline std::vector<uint64_t> arrow_top_k_chunks(const ArrowSchema& schema, const std::vector<const ArrowArray*>& chunks, size_t k, ArrowOptions o = {})
set_default_threads / default_threads Page
The thread count threads = 0 means (process-wide; default 1; n = 0: the CPUs this process may run on).
inline void set_default_threads(size_t n)
inline size_t default_threads()
Remarks: Threads change only the speed: the result follows the same rules on any thread count (rule 10).
set_max_threads / max_threads Page
The process-wide budget of threads running parallel phases (0: the CPUs the process may run on; see kwker.h).
inline void set_max_threads(size_t n)
inline size_t max_threads()
Remarks: Threads change only the speed: the result follows the same rules on any thread count (rule 10).
parallel_threads Page
(threads running parallel phases now, at most since the last reset); reset restarts the peak.
inline std::pair<size_t, size_t> parallel_threads(bool reset = false)
set_worker_cpus Page
Pins later parallel phases' worker threads (worker w on cpus[w % size]); an empty list: no pinning.
inline void set_worker_cpus(const std::vector<size_t>& cpus)
set_task_runner Page
Runs the parallel phases on the caller's thread pool (runner(ctx, n, task, arg) calls task(arg, i) for every i in 0..n and returns when all have returned); nullptr: the library's own threads.
inline void set_task_runner(kwker_runner_fn runner, void* ctx = nullptr)
sort_mt Page
sort on threads threads from 256K keys (4- / 8-byte keys: sorted chunks merged; others: a sample sort).
Throws: std::invalid_argument
template <class T> void sort_mt(T* a, size_t n, size_t threads = 0, Order o = Order::ascending)
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. Threads change only the speed: the result follows the same rules on any thread count (rule 10).
Examples: Sorting: Big arrays: use more cores
argsort_mt Page
argsort (the stable permutation) on threads threads.
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> argsort_mt(const T* a, size_t n, size_t threads = 0, Order o = Order::ascending)
Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for. Threads change only the speed: the result follows the same rules on any thread count (rule 10).
Examples: Large data: Use several cores
sort_indexed Page
The sorted keys and the stable permutation from one sort (a unchanged).
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> sort_indexed(const T* a, size_t n, Order o = Order::ascending, size_t threads = 1)
sort_kv_mt Page
sort_kv_stable on threads threads.
Throws: std::invalid_argument
template <class T, class V> void sort_kv_mt(T* keys, V* values, size_t n, size_t threads = 0, Order o = Order::ascending)
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. Threads change only the speed: the result follows the same rules on any thread count (rule 10).
kth Page
The k-th key of the stable order (0-based, k < n) and its index, without sorting, on threads threads. nan_first: a NaN anywhere gives the first NaN (torch.median).
Throws: std::invalid_argument
template <class T> std::pair<T, uint64_t> kth(const T* a, size_t n, size_t k, Order o = Order::ascending, bool nan_first = false, size_t threads = 1)
class Workspace Page
A reusable workspace: buffers kept between calls (argsort_into, sort_kv / top-k with a workspace), so repeated calls stop allocating once it has grown; one per thread at a time.
class Workspace
argsort_into Page
argsort into indices[0..n) (no allocation of its own); ws: buffers kept between calls (nullptr: none). One Workspace per thread.
Throws: std::invalid_argument
template <class T> void argsort_into(const T* a, size_t n, uint64_t* indices, Order o = Order::ascending, Workspace* ws = nullptr)
Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
top_k_into Page
top_k into values[0..k) / indices[0..k) (either may be nullptr; no result vectors), the candidate buffers kept in ws between calls (nullptr: the thread's). One Workspace per thread.
Throws: std::invalid_argument
template <class T> void top_k_into(const T* a, size_t n, size_t k, T* values, uint64_t* indices, Order o = Order::ascending, bool sorted = true, Workspace* ws = nullptr)
Remarks: The first k keys of the stable order and their positions; equal keys keep their input order (rule 9). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
sort_kv / sort_kv_stable / select_kv / partial_sort_kv Page
sort_kv / select_kv / partial_sort_kv that keep their buffers in ws between calls, so repeated calls don't allocate. One Workspace per thread.
Throws: std::invalid_argument
template <class T, class V> void sort_kv(T* keys, V* values, size_t n, Order o, Workspace& ws)
template <class T, class V> void sort_kv_stable(T* keys, V* values, size_t n, Order o, Workspace& ws)
template <class T, class V> void select_kv(T* keys, V* values, size_t n, size_t k, Order o, Workspace& ws)
template <class T, class V> void partial_sort_kv(T* keys, V* values, size_t n, size_t k, Order o, Workspace& ws)
Examples: Core concepts: In place or a copy, Sorting keys with values: Keep equal keys in order: the stable sort, Sorting keys with values: Only the first k pairs, Sorting keys with values: Sort keys and values together
struct Unique / unique Page
The distinct keys ascending, the group of every key (inverse = true) and each group's size (counts = true); floats equal as values (-0.0 = +0.0), every NaN its own key (torch.unique).
Throws: std::invalid_argument
template <class T> struct Unique
template <class T> Unique<T> unique(const T* a, size_t n, bool inverse = false, bool counts = false, size_t threads = 1)
Remarks: -0.0 and +0.0 are one value; every NaN is a value of its own, listed last (rule 15).
argpartition_rows / argpartition Page
numpy.argpartition of each row (kth < row_len): position kth holds the index of the row's kth key (ties by index), the kth first before it, the rest after it.
Throws: std::invalid_argument
template <class T> std::vector<uint64_t> argpartition_rows(const T* a, size_t rows, size_t row_len, size_t kth, Order o = Order::ascending)
template <class T> std::vector<uint64_t> argpartition(const T* a, size_t n, size_t kth, Order o = Order::ascending)
sort_rows_indexed Page
Each row sorted and its stable permutation (row-relative), from one sort per row.
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> sort_rows_indexed(const T* a, size_t rows, size_t row_len, Order o = Order::ascending)
kth_rows Page
Each row's k-th key of the stable order (k < row_len) and its row-relative index (nan_first as kth).
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> kth_rows(const T* a, size_t rows, size_t row_len, size_t k, Order o = Order::ascending, bool nan_first = false)
kth_axis Page
The k-th key and its lane-relative index of every lane along axis: C-order results of the shape without axis.
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> kth_axis(const T* a, const std::vector<size_t>& shape, size_t axis, size_t k, Order o = Order::ascending, bool nan_first = false, const std::vector<ptrdiff_t>& strides = {})
sort_axis_indexed Page
Every lane along axis sorted and its stable permutation, both C-order arrays of the input's shape.
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint64_t>> sort_axis_indexed(const T* a, const std::vector<size_t>& shape, size_t axis, Order o = Order::ascending, const std::vector<ptrdiff_t>& strides = {})
sort_axis_indexed8 Page
sort_axis_indexed with uint8_t indices (lanes of at most 256 keys).
Throws: std::invalid_argument
template <class T> std::pair<std::vector<T>, std::vector<uint8_t>> sort_axis_indexed8(const T* a, const std::vector<size_t>& shape, size_t axis, Order o = Order::ascending, const std::vector<ptrdiff_t>& strides = {})
sort_rows Page
sort_rows reporting progress about every 64K keys; false when cancelled (the rows done so far sorted).
Throws: std::invalid_argument
template <class T, class F> bool sort_rows(T* a, size_t rows, size_t row_len, Order o, F&& progress)
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.
Examples: Sorting: Sort each row
sort_segments Page
sort_segments reporting progress; false when cancelled.
Throws: std::invalid_argument
template <class T, class F> bool sort_segments(T* a, size_t n, const uint64_t* offsets, size_t count, Order o, F&& progress)
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.
sort_mt Page
sort_mt reporting progress after each bucket (from the worker threads, never two calls at once); false when cancelled - the keys then a permutation of themselves (the buckets done sorted).
Throws: std::invalid_argument
template <class T, class F> bool sort_mt(T* a, size_t n, size_t threads, Order o, F&& progress)
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. Threads change only the speed: the result follows the same rules on any thread count (rule 10).
Examples: Sorting: Big arrays: use more cores
argsort_mt Page
argsort_mt into indices (n entries) reporting progress, as sort_mt; false when cancelled (indices unspecified).
Throws: std::invalid_argument
template <class T, class F> bool argsort_mt(const T* a, size_t n, uint64_t* indices, size_t threads, Order o, F&& progress)
Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for. Threads change only the speed: the result follows the same rules on any thread count (rule 10).
Examples: Large data: Use several cores
sort_kv_mt Page
sort_kv_mt reporting progress while the keys sort; false when cancelled (keys and values unchanged).
Throws: std::invalid_argument
template <class T, class V, class F> bool sort_kv_mt(T* keys, V* values, size_t n, size_t threads, Order o, F&& progress)
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. Threads change only the speed: the result follows the same rules on any thread count (rule 10).
sort_file Page
Sorts a file of native-endian T keys back to back into output (may equal input): sorted runs of about memory bytes (0: 256 MiB) spilled to a private directory in temp_dir (nullptr: the output's directory) and merged; the run files are removed in every case. Throws std::runtime_error on an I/O error or a length that is not whole keys.
... reporting progress after each run and merge round; false when cancelled (the output incomplete).
Throws: std::invalid_argument, std::runtime_error
template <class T> void sort_file(const char* input, const char* output, Order o = Order::ascending, size_t memory = 0, const char* temp_dir = nullptr, size_t threads = 1)
template <class T, class F> bool sort_file(const char* input, const char* output, Order o, size_t memory, const char* temp_dir, size_t threads, F&& progress)
Examples: Large data: Sort a file larger than memory
sort_file_records Page
Sorts a file of fixed-size records (record_size bytes each) by the native-endian T key at byte key_offset of every record, stably (equal keys keep their file order), into output (may equal input); memory and temp_dir as for sort_file. Throws std::invalid_argument for a key that does not fit the record, std::runtime_error on an I/O error or partial record.
Throws: std::invalid_argument, std::runtime_error
template <class T> void sort_file_records(const char* input, const char* output, size_t record_size, size_t key_offset, Order o = Order::ascending, size_t memory = 0, const char* temp_dir = nullptr)
enum class Combine Page
How reduce_by_key combines a key's values: sum (integers wrap; floats left to right in input order), min / max (in the ascending order: -0 below +0, NaNs above all), first / last (in input order).
enum class Combine : int
struct Grouped / reduce_by_key Page
The distinct keys in order and one result per key.
Throws: std::invalid_argument
template <class Kt, class V> struct Grouped
template <class Kt, class V> Grouped<Kt, V> reduce_by_key(const Kt* keys, const V* values, size_t n, Combine op = Combine::sum, Order o = Order::ascending, size_t threads = 1)
Examples: Groups, merges and sets: Totals per key: reduce_by_key
mean_by_key Page
Each distinct key's mean value.
Throws: std::invalid_argument
template <class Kt, class V> Grouped<Kt, double> mean_by_key(const Kt* keys, const V* values, size_t n, Order o = Order::ascending)
count_by_key Page
Each distinct key's number of occurrences.
Throws: std::invalid_argument
template <class Kt> Grouped<Kt, uint64_t> count_by_key(const Kt* keys, size_t n, Order o = Order::ascending)
Examples: Groups, merges and sets: Totals per key: reduce_by_key
enum class Pad Page
Padding of the 3 x 3 window: reflect (h, w >= 2), replicate, zeros, or valid (no padding: h, w >= 3; smaller output).
enum class Pad : uint32_t
median3x3 Page
3 x 3 window medians of planes x h x w row-major keys (median filter / median pooling, stride 1): planes x h x w, or planes x (h - 2) x (w - 2) for Pad::valid; a window holding a NaN gives its first NaN (torch.median).
Throws: std::invalid_argument
template <class T> std::vector<T> median3x3(const T* src, size_t planes, size_t h, size_t w, Pad pad = Pad::reflect)
median3x3_backward Page
The gradient of median3x3 (float / double): each output's gradient added at the input key its median came from.
Throws: std::invalid_argument
template <class T> std::vector<T> median3x3_backward(const T* src, const T* out, const T* grad_out, size_t planes, size_t h, size_t w, Pad pad = Pad::reflect)
median5x5 Page
5 x 5 window medians, as median3x3 (the 13th smallest of 25 keys): planes x h x w, or planes x (h - 4) x (w - 4) for Pad::valid (h, w >= 5; reflect h, w >= 3).
Throws: std::invalid_argument
template <class T> std::vector<T> median5x5(const T* src, size_t planes, size_t h, size_t w, Pad pad = Pad::reflect)
median5x5_backward Page
The gradient of median5x5 (float / double).
Throws: std::invalid_argument
template <class T> std::vector<T> median5x5_backward(const T* src, const T* out, const T* grad_out, size_t planes, size_t h, size_t w, Pad pad = Pad::reflect)
enum class Interpolation Page
How a quantile between two keys is taken (torch.quantile's interpolation).
enum class Interpolation : int
struct QuantileKeys / quantile_axis Page
The order statistics of every lane along axis (float / double) for every q in qs (in [0, 1]): the keys of ranks floor(r) / ceil(r) of r = q * (n - 1) and r - floor(r), in C-order lanes (the shape without axis) x qs.size(); ignore_nan: ranks among the non-NaN keys (torch.nanquantile); a lane holding a NaN gives NaN keys.
Throws: std::invalid_argument
template <class T> struct QuantileKeys
template <class T> QuantileKeys<T> quantile_axis(const T* a, const std::vector<size_t>& shape, size_t axis, const std::vector<double>& qs, Interpolation in = Interpolation::linear, bool ignore_nan = false, const std::vector<ptrdiff_t>& strides = {}, size_t threads = 1)
quantile Page
The quantiles of a[0..n) (float / double) as torch.quantile computes them (torch.lerp of the two order statistics).
Throws: std::invalid_argument
template <class T> std::vector<T> quantile(const T* a, size_t n, const std::vector<double>& qs, Interpolation in = Interpolation::linear, bool ignore_nan = false, size_t threads = 1)
sort_int4_packed Page
Sorts n packed nibbles in place (counting passes; the nibble past an odd n is never touched).
Throws: std::invalid_argument
inline void sort_int4_packed(uint8_t* data, size_t n, bool is_signed, Order o = Order::ascending)
argsort_int4_packed Page
The stable argsort of n packed nibbles.
Throws: std::invalid_argument
inline std::vector<uint64_t> argsort_int4_packed(const uint8_t* data, size_t n, bool is_signed, Order o = Order::ascending)
top_k_int4_packed / select / partial_sort / argsort / top_k / sort_kv / sort_kv_stable / select_kv / partial_sort_kv / searchsorted / bucket_counts / argselect / sort_rows / sort_segments / rank / set_op / coo_coalesce / coo_to_csr / coo_to_csc / argsort_masked / sort_masked / argsort_by / top_k_by / take / permute_in_place / sort_mt / argsort_mt / sort_indexed / sort_kv_mt / kth Page
The indices of the first min(k, n) packed nibbles in order (ties by index).
Throws: std::invalid_argument
inline std::vector<uint64_t> top_k_int4_packed(const uint8_t* data, size_t n, size_t k, bool is_signed, Order o = Order::ascending)
template <class T, class A> void select(std::vector<T, A>& v, size_t k, Order o = Order::ascending)
template <class T, class A> void partial_sort(std::vector<T, A>& v, size_t k, Order o = Order::ascending)
template <class T, class A> std::vector<uint64_t> argsort(const std::vector<T, A>& v, Order o = Order::ascending)
template <class T, class A> std::pair<std::vector<T>, std::vector<uint64_t>> top_k(const std::vector<T, A>& v, size_t k, Order o = Order::ascending, bool sorted = true)
template <class T, class A, class V, class B> void sort_kv(std::vector<T, A>& keys, std::vector<V, B>& values, Order o = Order::ascending)
template <class T, class A, class V, class B> void sort_kv_stable(std::vector<T, A>& keys, std::vector<V, B>& values, Order o = Order::ascending)
template <class T, class A, class V, class B> void select_kv(std::vector<T, A>& keys, std::vector<V, B>& values, size_t k, Order o = Order::ascending)
template <class T, class A, class V, class B> void partial_sort_kv(std::vector<T, A>& keys, std::vector<V, B>& values, size_t k, Order o = Order::ascending)
template <class T, class A> std::vector<uint64_t> searchsorted(const std::vector<T, A>& sorted, const std::vector<T, A>& queries, bool right = false, Order o = Order::ascending)
template <class T, class A> std::vector<uint64_t> bucket_counts(const std::vector<T, A>& values, const std::vector<T, A>& boundaries, bool right = false, Order o = Order::ascending)
template <class T, class A> std::vector<uint64_t> argselect(const std::vector<T, A>& v, size_t k, Order o = Order::ascending)
template <class T, class A> void sort_rows(std::vector<T, A>& v, size_t row_len, Order o = Order::ascending)
template <class T, class A> void sort_segments(std::vector<T, A>& v, const std::vector<uint64_t>& offsets, Order o = Order::ascending)
template <class T, class A> std::vector<uint64_t> rank(const std::vector<T, A>& v, Order o = Order::ascending, Ties t = Ties::ordinal)
template <class T, class A> std::vector<T> set_op(const std::vector<T, A>& a, const std::vector<T, A>& b, SetOp op, bool multiset = false, Order o = Order::ascending)
template <class V, class A> Coo<V> coo_coalesce(const std::vector<uint64_t>& rows, const std::vector<uint64_t>& cols, const std::vector<V, A>& vals, uint64_t nrows, uint64_t ncols, Reduce r = Reduce::sum)
template <class V, class A> Compressed<V> coo_to_csr(const std::vector<uint64_t>& rows, const std::vector<uint64_t>& cols, const std::vector<V, A>& vals, uint64_t nrows, uint64_t ncols, Reduce r = Reduce::sum)
template <class V, class A> Compressed<V> coo_to_csc(const std::vector<uint64_t>& rows, const std::vector<uint64_t>& cols, const std::vector<V, A>& vals, uint64_t nrows, uint64_t ncols, Reduce r = Reduce::sum)
template <class T, class A> std::vector<uint64_t> argsort_masked(const std::vector<T, A>& v, const std::vector<uint8_t>& mask, bool bitmap = false, Order o = Order::ascending)
template <class T, class A> void sort_masked(std::vector<T, A>& v, const std::vector<uint8_t>& mask, bool bitmap = false, Order o = Order::ascending)
template <class R, class A, class Kt> std::vector<uint64_t> argsort_by(const std::vector<R, A>& recs, Kt R::*member, Order o = Order::ascending)
template <class R, class A, class Kt> std::vector<uint64_t> top_k_by(const std::vector<R, A>& recs, Kt R::*member, size_t k, Order o = Order::ascending)
template <class R, class A> std::vector<R> take(const std::vector<R, A>& recs, const std::vector<uint64_t>& idx)
template <class R, class A> void permute_in_place(std::vector<R, A>& recs, const std::vector<uint64_t>& perm)
template <class T, class A> void sort_mt(std::vector<T, A>& v, size_t threads = 0, Order o = Order::ascending)
template <class T, class A> std::vector<uint64_t> argsort_mt(const std::vector<T, A>& v, size_t threads = 0, Order o = Order::ascending)
template <class T, class A> std::pair<std::vector<T>, std::vector<uint64_t>> sort_indexed(const std::vector<T, A>& v, Order o = Order::ascending, size_t threads = 1)
template <class T, class A, class V, class B> void sort_kv_mt(std::vector<T, A>& keys, std::vector<V, B>& values, size_t threads = 0, Order o = Order::ascending)
template <class T, class A> std::pair<T, uint64_t> kth(const std::vector<T, A>& v, size_t k, Order o = Order::ascending, bool nan_first = false, size_t threads = 1)
Examples: Quickstart: Kwker Core: The median, without a full sort, Top-k and selection: Sort only the beginning, Core concepts: In place or a copy, Sorting keys with values: Keep equal keys in order: the stable sort
argsort_into / unique / argpartition / reduce_by_key / mean_by_key / count_by_key / quantile / select / partial_sort / argsort Page
argsort into indices (resized to v.size(): no allocation once it is large enough).
Throws: std::invalid_argument
template <class T, class A> void argsort_into(const std::vector<T, A>& v, std::vector<uint64_t>& indices, Order o = Order::ascending, Workspace* ws = nullptr)
template <class T, class A> Unique<T> unique(const std::vector<T, A>& v, bool inverse = false, bool counts = false, size_t threads = 1)
template <class T, class A> std::vector<uint64_t> argpartition(const std::vector<T, A>& v, size_t kth, Order o = Order::ascending)
template <class Kt, class A, class V, class B> Grouped<Kt, V> reduce_by_key(const std::vector<Kt, A>& keys, const std::vector<V, B>& values, Combine op = Combine::sum, Order o = Order::ascending, size_t threads = 1)
template <class Kt, class A, class V, class B> Grouped<Kt, double> mean_by_key(const std::vector<Kt, A>& keys, const std::vector<V, B>& values, Order o = Order::ascending)
template <class Kt, class A> Grouped<Kt, uint64_t> count_by_key(const std::vector<Kt, A>& keys, Order o = Order::ascending)
template <class T, class A> std::vector<T> quantile(const std::vector<T, A>& v, const std::vector<double>& qs, Interpolation in = Interpolation::linear, bool ignore_nan = false, size_t threads = 1)
template <class T, size_t E> void select(std::span<T, E> s, size_t k, Order o = Order::ascending)
template <class T, size_t E> void partial_sort(std::span<T, E> s, size_t k, Order o = Order::ascending)
template <class T, size_t E> std::vector<uint64_t> argsort(std::span<const T, E> s, Order o = Order::ascending)
Examples: Groups, merges and sets: Totals per key: reduce_by_key, 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
isa Page
The engine in use: "avx512", "avx2", "sse42", "neon", "simd128" or "portable".
inline const char* isa()
Remarks: The engine changes only the speed, never a result (rule 11).
Examples: Runtime controls: Fallback switches
observe Page
Runs f() with the engines' path trace on and returns the report as JSON (kwker_observe_stop's).
Throws: std::runtime_error
template <class F> std::string observe(F&& f)
set_isa Page
Caps the engine of later calls (process-wide, as KWKER_ISA): "avx512", "avx2", "sse42", "neon", "simd128", "portable", or nullptr 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; an unknown name throws. Results never depend on the engine.
Throws: std::invalid_argument
inline const char* set_isa(const char* name = nullptr)
Remarks: The engine changes only the speed, never a result (rule 11).
Examples: Runtime controls: Fallback switches
version Page
The library version.
inline const char* version()
precision_resolve Page
The weights a model runs in for a precision policy, from the rules table every Kwker integration shares. policy: "preserve" (lossless only), "balanced" (int8), or "float32", "bf16", "int8", "int4" by name; checkpoint: how the weight matrices are stored ("float32", "float32 (bf16 values)", "bf16", "fp16", "mixed"); moe: a mixture-of-experts model. Returns the plan; its weights is nullptr when the policy has no choice for the model (why and the hint say what to pass instead). An unknown name throws. auto p = kwker::precision_resolve("preserve", "bf16"); // p.weights == "bf16", p.quality == "lossless"
Throws: std::invalid_argument
inline kwker_precision_plan precision_resolve(const char* policy, const char* checkpoint, bool moe = false)
set_scratch_limit / scratch_limit Page
The calling thread's scratch-memory limit for later calls (bytes; SIZE_MAX: none; 0: no allocation).
inline void set_scratch_limit(size_t bytes)
inline size_t scratch_limit()
Remarks: The scratch limit changes only the speed and memory use, never a result (rule 12).
Examples: Large data: Limit the extra memory
enum class Algorithms / operator| / operator& / operator~ Page
Algorithm classes the calls may use beyond the comparison core (kwker_set_algorithms); combine with | and &.
enum class Algorithms : uint32_t
inline constexpr Algorithms operator|(Algorithms a, Algorithms b)
inline constexpr Algorithms operator&(Algorithms a, Algorithms b)
inline constexpr Algorithms operator~(Algorithms a)
set_algorithms / algorithms Page
Permits only these classes in this thread's later calls; returns the previous setting (results unchanged).
inline Algorithms set_algorithms(Algorithms a)
inline Algorithms algorithms()
class AlgorithmsScope Page
RAII: the classes for one scope (restored at its end).
class AlgorithmsScope
struct ScratchPolicy / set_scratch_policy / scratch_policy Page
The scratch policy (process-wide) for the buffers the library allocates for itself (kwker_set_scratch_policy): released bytes kept for later calls, the library's own mappings or the heap, huge-page advice.
struct ScratchPolicy
inline void set_scratch_policy(const ScratchPolicy& p)
inline ScratchPolicy scratch_policy()
struct ScratchUse / scratch_use Page
Those buffers now (process-wide): bytes in use by running calls, kept for later calls, the most in use at once since the last reset (reset_peak: restart it after this reading).
struct ScratchUse
inline ScratchUse scratch_use(bool reset_peak = false)
release_scratch Page
Unmaps the kept buffers and frees the calling thread's argsort / top-k buffers.
inline void release_scratch()
set_scratch_allocator Page
Routes those buffers to a host allocator (kwker_set_scratch_allocator; both nullptr: the library's own again).
Throws: std::invalid_argument
inline void set_scratch_allocator(kwker_alloc_fn alloc, kwker_free_fn free_fn, void* ctx = nullptr)
enum class ScratchOp Page
The operations scratch_bound knows.
enum class ScratchOp : int
scratch_bound Page
An upper bound of the scratch bytes op allocates for n keys of key_bytes (values of value_bytes) on this machine's engine, no limit set (SCRATCH.md); SIZE_MAX for an unknown op.
inline size_t scratch_bound(ScratchOp op, size_t n, size_t key_bytes, size_t value_bytes = 0)
capabilities_json Page
What Kwker does on this machine: one JSON object (version, isa, engines, CPU features, caches, threads, ...).
inline const char* capabilities_json()