Performance

Kwker is fastest when each call does only the work you need, on data it can use as it is. Five habits cover most programs. Then measure on your own machine: the commands at the end take a few seconds.

Ask only for what you need

The largest few values, a median or the first page of a ranking need much less work than a full sort. top_k returns the k largest or smallest values and their positions; select puts one value of a given rank in place, as numpy.partition does.

import numpy as np
import kwker

scores = np.array([0.2, 0.9, 0.4, 0.7, 0.1, 0.8])
values, positions = kwker.top_k(scores, 3, descending=True)
print(values, positions)

a = np.array([7, 1, 9, 4, 3])
kwker.select(a, 2)        # the median of 5 values: rank 2
print(a[2])

[0.9 0.8 0.7] [1 5 3]
4

Sort in place

sort(a) sorts the array itself, views and strided arrays included, without a copy. sorted(a) makes a new array: use it only when you still need the original order.

import numpy as np
import kwker

a = np.array([3.5, 1.0, 2.25])
kwker.sort(a)             # no new array
print(a)

[1.   2.25 3.5 ]

One call per matrix

To sort every row, pass the whole matrix with axis=1. One call sorts all rows; a Python loop pays the call overhead once per row, which dominates for short rows.

import numpy as np
import kwker

m = np.array([[3, 1, 2],
              [9, 7, 8]])
kwker.sort(m, axis=1)
print(m)

[[1 2 3]
 [7 8 9]]

Threads for big arrays

Calls run on one thread unless you pass threads=. From about a million values, more cores help; below that, one thread is usually fastest. threads=0 uses every CPU the process may use.

import numpy as np
import kwker

big = np.random.default_rng(0).random(2_000_000)
kwker.sort(big, threads=4)
print(bool(np.all(big[:-1] <= big[1:])))

True

Reuse buffers in a loop

Some calls need working memory. Kwker keeps its own buffers for reuse, so most programs need nothing here. In a hot loop of argsort or top_k calls, a Plan holds one set of buffers and your settings (order, threads) for the whole loop: once it has grown, its calls allocate nothing.

import numpy as np
import kwker

rng = np.random.default_rng(1)
with kwker.Plan() as plan:
    for _ in range(3):
        batch = rng.random(10_000)
        order = plan.argsort(batch)
print(bool(np.all(np.diff(batch[order]) >= 0)))

True

How the speed comes about

• An engine for your CPU. When Kwker loads, it picks the fastest code it has for your processor: AVX-512 or AVX2 on x86, NEON or SVE on ARM, or a portable version. python -m kwker doctor shows which one.
• An algorithm for each call. Small arrays use sorting networks; larger ones use vector partitioning, and large integer and float keys use radix passes. Data that is already sorted, reversed or full of repeats is noticed and takes a shortcut.
• Few passes over memory. Large sorts are limited by how fast memory moves, so Kwker reads and writes each value as few times as it can.

Runtime controls lists the switches for each of these: the engine cap, the algorithm classes, threads and scratch memory.

Measure on your machine

Evaluate on your machine walks through the three. The benchmarks page has the published results against x86-simd-sort, VQSort and the model runtimes, with the raw data and the method.

Notes

• Timings depend on the CPU, the memory and where the threads run. Compare on the machine you deploy on.
• The first call in a process loads the library and picks the engine; time a few calls, not the first one.
• Under PyTorch, parallel calls use torch's own thread pool.

Related

• Command-line reference: every option of doctor, bench and audit.
• Large data: several cores and a memory limit for one call.
• Top-k and selection: the partial-result calls in detail.