Kwker

Behavior specification

These rules hold for every operation, every key type, every engine (AVX-512, AVX2, ARM NEON and SVE, portable) and every language binding. Each rule names the test in the repository that checks it. If Kwker ever breaks one of them, that is a bug: please report it.

Key order

  1. Integer keys compare by their numeric value: signed types as signed numbers, unsigned types as unsigned numbers. Tested by typed.rs and unsigned.rs.
  2. Floating-point keys sort in this ascending order: negative infinity, negative numbers, -0.0, +0.0, positive numbers (subnormals by value), positive infinity, then NaN. -0.0 and +0.0 are distinct keys, so a result never depends on which zero arrived first. Tested by doc_order in typed.rs.
  3. Every NaN, whatever its sign or payload, belongs to one NaN block: at the end by default, at the start with the NaNs-first order. A NaN keeps its exact bits; plain sorts may reorder NaNs with different bits among themselves. Tested by order.rs and tiny.rs.
  4. Descending order reverses the order of the numbers. It does not move the NaN block: NaNs stay last unless NaNs-first is asked for. Tested by order.rs.

Operations

  1. sort returns a permutation of its input in the requested order. It is not stable, which only matters when equal keys can be told apart (NaNs with different bits). Tested by ops.rs.
  2. argsort, the positions of top_k, ordinal ranks and the stable key-value sort are stable: equal keys keep their input order, so the same input always gives the same positions. Tested by ops.rs, topk.rs and kv.rs.
  3. select(k) puts at position k the key a full sort puts there. Keys before it are ordered before or equal to it, keys after it are ordered after or equal. Tested by select.rs.
  4. partial_sort(k) leaves the first k positions exactly as a full sort would. The rest hold the other keys in any order. Tested by select.rs.
  5. top_k(k) returns the first k keys of the stable order and their positions, in that order when sorted output is asked for. Tested by topk.rs.

Execution

  1. The number of threads never changes a result: a multithreaded sort, argsort or stable key-value sort returns exactly what the single-threaded call returns. A multithreaded key-value sort is always stable. Tested by ops.rs (each multithreaded form against the single-threaded one) and concurrent.rs (many calls at once).
  2. Every engine returns the same result for the same call; the engine changes only the speed. Tested by engine_matches_fallback in fallback.rs.
  3. The scratch limit never changes a result. With a limit of 0, sort, select, partial_sort and sort_kv allocate no memory. Tested by scratch.rs.

Equal keys

  1. Ranks, multi-column sorts (lexsort), group codes and set operations compare values, as NumPy, SciPy, pandas and Polars do: -0.0 and +0.0 are equal, and every NaN equals every other NaN. So equal values share a rank, keep their row order in a multi-column sort and form one group. The sorts themselves still put -0.0 before +0.0 (rule 2). Tested by eq_values in ops.rs.
  2. searchsorted and bucketize compare -0.0 and +0.0 as equal, as NumPy does: a query of either zero finds the same position. Tested by search in ops.rs.
  3. unique treats -0.0 and +0.0 as one value, given as the zero that comes first in the input. Every NaN is a value of its own, listed last in input order (the rule of torch.unique). Python's kwker.unique follows numpy.unique instead: all NaNs are one value, sorted last. Tested by unique_inv in ops.rs and the unique cases of kwker-py/tests/test_kwker.py.

Drop-in replacements

  1. Every call a drop-in integration takes over - kwker.numpy_ops.install(), kwker.torch_ops.install(), and the kwker.frame calls that stand in for pandas, Polars and pyarrow sorts - makes one of three promises: exact (the host library's result, NaN equal to NaN), equivalent (a result the host could return too where it leaves a choice open, such as the order of equal keys in an unstable sort) or approximate (within a tolerance you chose by asking for a lower precision). kwker.contract lists each call with its promise, and kwker.contract.run(routes) checks them on generated inputs. Tested by contract_fuzz.py.