What this measures
Produce the stable ascending order of the amount column as a permutation of row indices, without moving any other column. SQL engines have no such form, so DuckDB and Spark sit this one out.
How neo does it
neo turns each double into a sortable 64-bit key and runs an LSD radix sort on the pool: O(n), stable, with the JavaScript rule that NaN sorts as negative infinity and ties keep their order. The ledger's design levers show the step from std::stable_sort at 84 ms, to radix at 14 ms, to the pool at 1 ms.
The keys are partitioned on their top 16 bits in parallel, then each bucket is sorted on its low 48 bits on its own: insertion sort when tiny, LSD radix otherwise, the largest buckets first.
sort, as a permutation · neon-cpp/bench/lang/swift/main.swift:920 · show all 104 lines
/// MSD partition on the top 16 bits (parallel: per-part histograms → absolute write positions,
/// part-major inside each bucket keeps it stable), then buckets sorted independently on the low
/// 48 bits (insertion sort when tiny, LSD radix otherwise), largest buckets scheduled first.
func sortPermMSD(_ amt: UnsafePointer<Double>, _ n: Int, _ perm: UnsafeMutablePointer<UInt32>, pool: Pool?, parts: Int) {
let np = pool == nil ? 1 : max(1, min(parts, n / 4096))
let chunk = (n + np - 1) / np
let kBuckets = 1 << 16
let keys = alloc(n, UInt64.self)
let hist = alloc(np * kBuckets, UInt32.self) // [p * kBuckets + b]
// A: keys + per-part histograms of the top 16 bits
let phaseA: (Int) -> Void = { p in
let h = hist + p * kBuckets
memset(h, 0, kBuckets * 4)
var i = p * chunk
let hi = min(n, i + chunk)
while i < hi { let k = sortKey(amt[i]); keys[i] = k; h[Int(k >> 48)] &+= 1; i += 1 }
}
if let pool = pool { pool.run(np, phaseA) } else { phaseA(0) }
// B: turn histograms into absolute write positions (bucket-major, part-major within a bucket)
let bucketStart = alloc(kBuckets + 1, Int.self)
let ranges = max(1, min(64, np * 4))
let perRange = (kBuckets + ranges - 1) / ranges
let rangeTotal = alloc(ranges + 1, Int.self)
let phaseB1: (Int) -> Void = { r in
var total = 0
var b = r * perRange
let be = min(kBuckets, b + perRange)
while b < be { var p = 0; while p < np { total += Int(hist[p * kBuckets + b]); p += 1 }; b += 1 }
rangeTotal[r] = total
}
if let pool = pool { pool.run(ranges, phaseB1) } else { for r in 0..<ranges { phaseB1(r) } }
var running = 0
for r in 0..<ranges { let t = rangeTotal[r]; rangeTotal[r] = running; running += t }
rangeTotal[ranges] = running
let phaseB2: (Int) -> Void = { r in
var pos = rangeTotal[r]
var b = r * perRange
let be = min(kBuckets, b + perRange)
while b < be {
bucketStart[b] = pos
var p = 0
while p < np { let c = Int(hist[p * kBuckets + b]); hist[p * kBuckets + b] = UInt32(truncatingIfNeeded: pos); pos += c; p += 1 }
b += 1
}
}
if let pool = pool { pool.run(ranges, phaseB2) } else { for r in 0..<ranges { phaseB2(r) } }
bucketStart[kBuckets] = n
// C: scatter (key, idx) into bucket order
let part = alloc(n, KV.self)
let phaseC: (Int) -> Void = { p in
let h = hist + p * kBuckets
var i = p * chunk
let hi = min(n, i + chunk)
while i < hi {
let k = keys[i]
let b = Int(k >> 48)
let pos = Int(h[b]); h[b] &+= 1
part[pos] = KV(key: k, idx: UInt64(i))
i += 1
}
}
if let pool = pool { pool.run(np, phaseC) } else { phaseC(0) }
// D: sort each bucket on the low 48 bits. Tasks = runs of consecutive buckets, ~n/(4·parts) rows each.
var taskLo: [Int] = [], taskHi: [Int] = [], taskSize: [Int] = []
let target = max(1024, n / max(1, 4 * np))
var b = 0
while b < kBuckets {
let lo = b
var size = 0
while b < kBuckets && (size == 0 || size + (bucketStart[b + 1] - bucketStart[b]) <= target) {
size += bucketStart[b + 1] - bucketStart[b]; b += 1
}
if size > 0 { taskLo.append(lo); taskHi.append(b); taskSize.append(size) }
}
let order = (0..<taskLo.count).sorted { taskSize[$0] > taskSize[$1] }
let phaseD: (Int) -> Void = { t in
let ti = order[t]
var bk = taskLo[ti]
let bend = taskHi[ti]
var maxBucket = 0
var x = bk
while x < bend { maxBucket = max(maxBucket, bucketStart[x + 1] - bucketStart[x]); x += 1 }
let tmp = maxBucket > 32 ? alloc(maxBucket, KV.self) : nil
let scratch = maxBucket > 32 ? alloc(768, Int.self) : nil
while bk < bend {
let s = bucketStart[bk], e = bucketStart[bk + 1]
let cnt = e - s
if cnt > 1 {
if cnt <= 32 { insertionSort(part + s, cnt) }
else {
let r = lsdRadix(part + s, tmp!, cnt, shift0: 0, shift1: 48, scratch!, scratch! + 256, scratch! + 512)
if r != part + s { memcpy(part + s, r, cnt * 16) }
}
}
var i = s
while i < e { perm[i] = UInt32(truncatingIfNeeded: part[i].idx); i += 1 }
bk += 1
}
if let t = tmp { free(t) }
if let s = scratch { free(s) }
}
if let pool = pool { pool.run(order.count, phaseD) } else { for t in 0..<order.count { phaseD(t) } }
free(keys); free(hist); free(bucketStart); free(rangeTotal); free(part)
}