64-bit Multi-Key Record Sort

Algorithms & Data

Records sorted by a primary 64-bit key, ties broken by a secondary 64-bit key — so each comparison runs the “spaceship” three-way compare (a>b)-(a<b) twice, both at 64 bits. This is compiler stress-test #100, the last of its cluster: the widest, densest form of the three-way-compare fix (llvm-mos patch 0016), stacked two deep in qsort’s hot loop.

loading core…

Self-running — left half = primary key, right half = secondary; rows resort.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

A multi-key sort orders records by one field, then resolves ties with another. Expressed with the spaceship compare, each comparison is a chained pair of three-way compares — and here both keys are 64-bit, the widest the operation gets.

// sort records by a PRIMARY 64-bit key, then break ties with a SECOND
int cmp(const void *a, const void *b) {
    const Rec *x = a, *y = b;
    int c = (x->k1 > y->k1) - (x->k1 < y->k1);   // 64-bit spaceship (primary)
    if (c != 0) return c;
    return (x->k2 > y->k2) - (x->k2 < y->k2);    // 64-bit spaceship (tie-break)
}
qsort(records, N, sizeof(Rec), cmp);             // two 64-bit three-way compares / call

The primary key collides often on purpose, so the secondary 64-bit compare truly runs. The gate folds the sorted (primary, secondary) pairs into a CRC. The picture is the proof: a wrong 64-bit three-way lowering — in either the primary or the tie-break — would misorder the records and change the CRC.

Compiler stress-test #100 — Round 6: hardening the fixes

Item	What it exercises
a chained comparator	Sorting by more than one key is everyday code: order by the primary field, and when two records match, fall back to a secondary field. Each comparison therefore runs the three-way compare twice — once on the primary 64-bit key, and again on the secondary — with the second only reached when the first ties.
64 bits, twice	Both keys are full 64-bit signed integers, so every comparator call can emit two 64-bit three-way compares. That is the widest, densest form of the operation in the whole battery — a compare-and-select over four 16-bit limbs, stacked two deep, inside qsort’s hot loop.
making the tie-break fire	The primary key is drawn from a deliberately small range so records collide often — 38 tie pairs among 24 records in the gate. That guarantees the second 64-bit compare is genuinely exercised rather than dead code, and the sort really does resolve ties by the secondary key.
the bug this guards (#46, patch 0016)	The three-way-compare idiom once crashed the 65816 backend, which had no rule to lower the generic opcode. Patch 0016 routes it through LLVM’s compare-and-select lowering. Earlier demos exercised it at single widths and as a sort key or a branch; this one stacks two 64-bit compares per call — the extreme case — and confirms the fix still holds.
why qsort	Inline, ((a>b)-(a<b)) folds back to ordinary comparisons and the three-way intrinsic vanishes — untested. Passing the comparator to qsort through its opaque function pointer forces it to return the −1/0/+1 value, keeping both 64-bit compares alive. An IR probe confirms the 64-bit three-way compare is present (and chained).
result: bit-exact, and the visual	Sorting is a pure reordering, so the sorted records are identical on host and SNES: host == default == +mos-a16 == +mos-xy16 on both MAME and bsnes-jg, -verify-machineinstrs clean. On screen each row is a sorted record — the left half coloured by the primary key (non-decreasing down the field), the right half by the secondary key (ordered within each tie group) — and the rows reshuffle as the data re-seeds.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg and MAME. Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0xB8AD — a fold of the sorted 64-bit key pairs) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean.