KMeans recorded benchmark study

The matching development runtime improves numerical accumulation and adds explicit local CPU execution. Published Aner 0.0.5 retains its legacy serial KMeans implementation. Updated serial and parallel results agree bitwise under the recorded binary/floating-point contract; updated arithmetic can differ from legacy results. Clustering quality on an external scientific problem was not measured here.

On the primary Batch workload, four reused workers reduce fit time from 5.209583 ms updated serial to 1.810625 ms: 2.88×, or 1.71× relative to legacy serial. On Wide, fit falls from 54.920042 to 15.143375 ms: 3.63× relative to updated serial, or 3.16× relative to legacy. Prediction reaches 3.65× and 3.53× relative to updated serial for Batch/Wide respectively.

The updated serial implementation is slower than legacy in these observations. Fitting changes numerical accumulation and adds checked execution infrastructure; prediction has no exact-mean/SSE reduction but adds numerical environment setup, workspace/cancellation/error checks and changed loop structure. This capture does not isolate those individual costs. Tiny calls regress under pools, and skewed fitting scales less well than the primary Wide case. The tables retain these outcomes.

Raw observations and source/binary identities · KMeans contract · implementation note

The figure uses zero origin axes, both serial baselines and reused pools. Bars/whiskers show median ± median absolute deviation (MAD); MAD describes observed spread, not a confidence interval. Tables below retain more displayed precision and every workload. Download the standalone SVG or inspect its reproduction script.

Machine and measurement scope

Recorded on an Apple M2 Max, macOS 26.7.2 arm64, with 12 reported logical CPUs and admitted contexts with 1, 2 and 4 workers. AppleClang 21, C++20 Release -O3 -DNDEBUG, ThinLTO, -mcpu=apple-m1, -fno-fast-math and -ffp-contract=off were used. The apple-m1 compiler target is an instruction baseline; the recorded physical CPU is M2 Max. Worker counts bound pool concurrency and do not establish core affinity, dedicated cores or CPU utilization.

Each mode retains seven observations after two excluded warmups. All configurations ran sequentially after builds and validation finished. Inputs were already materialized CPU Float64. Fit timing includes initialization, all Lloyd updates, final labels/inertia and workspace allocation. Prediction timing excludes its prerequisite fit. Parsing, fixture creation and independent correctness checks are outside the timers. Every updated timed result is checked afterward against its own updated serial reference.

Legacy and updated kernels use the same native harness and matched build defaults. The preserved legacy source is from revision 32e34b92ef103156c9919212999b97b020e65aba, SHA-256 12f9ef7d5175f0d3c29c7aa1c6b814980541d00c4bd3b322e88931ddc12b0e64. Its unchanged Tensor/NN dependencies and current executor library are shared; legacy KMeans invokes no executor. The updated kernel SHA-256 is 771881f0f79758509a2bf2e4b604591e067297d737367eba64bc0d1e64325686. Source/binary hashes and complete raw samples remain in the JSON.

Workloads and completed updates

N is fitting rows, Q query rows, D features, k clusters and M the requested update cap. All use initialization seed 42. The final three cases examine overlap, skew and a fixed one update budget. A capped fit is a valid result with converged=false.

The completed counts happen to match in these nine cases. Improved numerical means can change stopping on other inputs, so before/after elapsed time alone does not prove equal per update work. The one update case fixes that count explicitly.

Latency: all nine workloads

Every cell is median ± MAD in milliseconds. Pools are reused; Pool 1 is distinct from a serial call. Legacy has only a serial baseline. Values are rounded for display; the JSON retains raw seconds.

Fitting

Prediction

Speedups and their denominators

Each cell lists Pool 1 / Pool 2 / Pool 4, in that order, as ratios:

• Vs new serial: updated serial median divided by the shown reused pool median. This compares execution modes with the same updated arithmetic.
• Vs legacy serial: legacy median divided by the shown pool median. This includes numerical/kernel changes as well as parallel execution.
• Vs Pool 1: reused one worker median divided by the shown pool median. This compares scaling within the pool path.

A value below 1× means slower execution. These are ratios of medians; no uncertainty interval for a ratio is inferred from MAD.

Fitting speedups

Prediction speedups

Tiny fitting takes 0.014416 ms updated serial and 0.162333 ms with four reused workers; tiny prediction takes 0.000209 versus 0.012750 ms. Its one query supplies one prediction lane regardless of a larger pool. These timings are especially sensitive to clock/scheduling overhead; small MAD or zero displayed MAD is not a precision guarantee.

Skewed fitting achieves 2.672× relative to updated serial with four workers, versus 3.627× for primary Wide. The phase structure and membership distribution limit scaling. These are local observations, not GPU/cluster, cross platform or universal acceleration claims.

Cold pool calls

Cells are median ± MAD in milliseconds, including pool creation and destruction. Compare them with the reused rows above; their difference is not an isolated measurement of thread startup. All nine workloads and both operations are retained.

Charged workspace admission

Memory probes cover Batch and Wide only, separately for fit and prediction. Each reported byte budget is the minimum accepted budget, verified to accept exactly that value and reject one byte less. All 16 boundaries passed. Cells show bytes (KiB), using 1 KiB = 1,024 bytes.

The default 64 MiB (67,108,864 bytes) is a cap, not a fixed allocation. New fitting charges returned centers/labels, vector capacities, CSR/center buffers, lane accumulator variants, bounded controls and the explicit mean finalization temporary. Prediction charges its output/lane controls and excludes its already fitted model. This recorded macOS arm64 ABI uses 8 byte Float64 values and size indices. Accumulator payloads are 544 bytes for exact means or 528 bytes for exact squares, plus variant/lane metadata; each active mean lane additionally charges 272 bytes. These probes add 836 admitted bytes per additional fit lane and 16 bytes per additional prediction lane, with both workloads exposing the requested lanes.

Iteration storage uses two N index buffers and old/next k×D centers, with k+1 offsets and k cursors. A fit has no N×k distance matrix or P×k×D accumulator array. Obsolete iteration capacities are released before final labels are allocated. The same retained numerical model payload is 8(N+kD) bytes in old/new implementations: 33,024 bytes (32.25 KiB) for Batch and 18,432 bytes (18 KiB) for Wide, before fitted-state/ownership metadata.

The preserved legacy logical fit peak payload formula on this 64 bit ABI is 24N + 40kD + 8k bytes, excluding vector/owner controls and allocator/input storage. It describes a different accounting scope from the updated charged boundary; comparing the two as measured RSS or as identical allocation measurements would be invalid.

Charged workspace excludes input/host-conversion caches, existing executor/session internals and thread stacks, observer/context payloads and strings, opaque shared ownership bookkeeping, allocator overhead, ordinary call stack frames and process RSS. The bounded mean temporary is explicitly included despite local storage duration. Other workloads have timings but no additional workspace boundary/RSS measurement here.

Fresh process peak RSS

This is a separate full process lifetime measurement, using getrusage, outside timing processes. Each cell is the maximum of three independent fresh process lifetime peaks, in MiB (1 MiB = 1,048,576 bytes). The JSON retains all three raw peaks. macOS returns bytes directly; the harness converts Linux KiB when applicable.

These peaks include runtime startup, input/query Tensors, executor threads and the operation. Prediction RSS includes its prerequisite serial fit. RSS only processes omit oracle model copies and timing repetitions. No subtraction converts these peaks into a per call allocation estimate; close process peaks do not establish general memory savings or zero thread stack cost. Keep RSS and charged workspace as distinct observations.

Correctness and development boundaries

The recorded validation reports 136,733 native KMeans checks, plus the language/session and existing ML/KNN/tree/executor regressions. Independent exact rational arithmetic checked 14,584 primitive cases and 38 full fit fixtures across serial/1/2/4 workers: 152 observations. Exact centroid means and exact sums of squared supplied/computed binary64 distances matched the independent once rounded reference. Sanitizer runs were kept separate from measurement.

The numerical contract uses exact sums of stored Float64 coordinates divided once for means, and exact squares of computed Float64 hypot distances summed before one final rounding for inertia. Distance computation itself remains checked, coordinate ordered and rounded. The integration report contains a fixture where exact coordinate SSE differs from squared computed distance SSE, demonstrating why these claims must remain separate.

Updated serial/pool results agree bitwise for every recorded mode and all fitted readouts/metadata; legacy arithmetic is deliberately a distinct comparison. This does not establish clustering quality, a global optimum, or cross math library bitwise portability. Seed/row selection, lowest cluster distance ties, empty cluster retention, absolute tolerance and final readouts against returned centers retain their API policies. Native cancellation/observer failures join before any successful output publication; full fit session admission and memory details are in the implementation note.

Reproduce the study

Use a source checkout containing the preserved legacy source and the matching development toolchain. On the recorded macOS platform, both benchmark targets inherit the same project Release, CPU, LTO and strict floating point defaults. ANER_KMEANS_BASELINE selects only the preserved legacy kernel. The exact compiler/OS/hardware identities affect reproduced timings.

cmake -S . -B build/kmeans-study -G Ninja \
  -DCMAKE_BUILD_TYPE=Release -DBUILD_TESTING=ON \
  -DANER_USE_MPS=OFF -DANER_USE_ACCELERATE=ON \
  -DANER_ENABLE_LTO=ON -DANER_APPLE_CPU=apple-m1
cmake --build build/kmeans-study --target \
  aner_kmeans_legacy_benchmark aner_kmeans_benchmark -j3
cmake --build build/kmeans-study --target \
  aner_ml_exact_tests aner_kmeans_oracle_probe aner_kmeans_parallel_tests -j3

python3 tools/verify_kmeans_exact.py \
  --binary build/kmeans-study/aner_ml_exact_tests \
  --output build/kmeans-study/exact-oracle.json
python3 tools/verify_kmeans_numeric.py \
  --binary build/kmeans-study/aner_kmeans_oracle_probe \
  --build-root build/kmeans-study \
  --output build/kmeans-study/integration-oracle.json
build/kmeans-study/aner_kmeans_parallel_tests > build/kmeans-study/native-checks.log
KMEANS_NATIVE_CHECKS="$(python3 -c 'import pathlib,re; print(re.search(r"(\d+) checks passed", pathlib.Path("build/kmeans-study/native-checks.log").read_text()).group(1))')"

python3 tools/kmeans_benchmark.py \
  --baseline build/kmeans-study/aner_kmeans_legacy_benchmark \
  --corrected build/kmeans-study/aner_kmeans_benchmark \
  --source-root . \
  --baseline-source docs/benchmarks/kmeans_legacy_ml_32e.cpp \
  --oracle-report build/kmeans-study/exact-oracle.json \
  --integration-report build/kmeans-study/integration-oracle.json \
  --native-checks "$KMEANS_NATIVE_CHECKS" \
  --repeats 7 --rss-repeats 3 \
  --output build/kmeans-study/new-observations.json
python3 tools/plot_kmeans_benchmark.py \
  --input build/kmeans-study/new-observations.json \
  --output build/kmeans-study/new-observations.svg

The driver requires admission for four workers, preserves an existing output file rather than overwriting it, and runs configurations sequentially. Use another supported CPU profile/provider configuration on other platforms and retain those differences in the evidence. Finish builds, tests and other substantial CPU work before timing.

The figure tool recomputes median/MAD from raw samples and checks the stored summaries. It uses an optional plotting backend when available and a standards based dependency free SVG renderer otherwise; the committed figure uses the SVG renderer. To reproduce that figure from the committed evidence without running timings:

python3 tools/plot_kmeans_benchmark.py --renderer svg

Benchmark harness, measurement driver, exact arithmetic oracle, full fit numerical oracle, and runnable local example are available for inspection.

See the Machine learning module reference for the shared API.