在 i9-13980HX 上，使用无分支 Rust 实现，20 毫秒内对 100 万个 u64 键值对进行排序
1 分•作者: EfurDec•4 个月前
我开发了一个零抖动排序 DLL（用 Rust 编写），针对 100 万个 u64 KV 对（u32+u32）的排序，始终保持在 20 毫秒以内，不受数据分布的影响。与 SkaSort 或其他自适应算法不同，我的实现完全与数据无关，并且对通常会将性能拖垮至 40-50 毫秒的“毒化”数据集免疫。
该方法受到 FPGA 的启发，专为 x86-64-v3 (AVX2/BMI2) 架构实现。它在我的 i9-13980HX 上达到了物理 L3 缓存带宽的极限 (~50GB/s)。虽然纯 FPGA 硬件可能达到 15 毫秒，但这很可能是单线程 CPU 实现的理论极限。可在任何现代台式机上运行。
查看原文
I’ve developed a zero-jitter sorting DLL (written in Rust) that consistently hits 20ms for 1M u64 KV-pairs (u32+u32), regardless of data distribution. Unlike SkaSort or other adaptive algorithms, my implementation is entirely data-independent and immune to 'poisoned' datasets that typically tank performance to 40-50ms.
The approach is FPGA-inspired, implemented for x86-64-v3 (AVX2/BMI2). It hits the physical L3 bandwidth limit on my i9-13980HX (~50GB/s). While pure FPGA hardware might hit 15ms, this is likely the theoretical limit for a single-threaded CPU implementation. Works on any modern desktop.