DeepSeek总结的一种带宽高效的压缩基数排序FractalSortCPU

来源https://github.com/mikdangana/fractalsort_cpuFractalSortCPU一种带宽高效的压缩基数排序在各大平台上均优于最先进的排序算法。在 16GB 数据集规模下FractalSortCPU 实现了 0.92 的带宽效率——相比之下Bonsai 为 0.34Timsort 为 0.25PARADIS 为 0.11HRS/SampleSort 为 0.05。这意味着根据基线不同带宽利用率提高了 2-18 倍与先前规模最大的 CPU 结果相比提升了 6 倍。论文:FractalSortCPU: 基于 CPU 的带宽高效压缩基数排序 (arXiv:2605.10390v2, 2026 年 5 月)主要结果平台先前最佳工作FractalSortCPU提升CPUHRS, SampleSort, PARADISFractalSortCPU最高 6 倍GPU设备级基数排序FractalSortCPU最高 3 倍FPGA定制加速器FractalSortCPU最高 2.5 倍已在 16 位精度、512MB 至 32GB 的数据集上得到验证。关于项目FractalSort 算法最初为 FPGA/硬件加速器设计此为 FractalSort 的 CPU 适配版本旨在将其引入 CPU 以提高可访问性并便于更广泛的实验。它使用直方图合并树索引进行排序和查询/检索通过将键分解为基于 MSB 的容器并包含紧凑条目和每批排序运行实现了比基数排序更低的 DRAM 带宽。架构FractalSort 将每个 p 位键分解为两个部分key (p bits): ├─ top (ln-lb) bits → bin_id (MSB, 决定属于哪个容器) └─ bottom entry_bits → entry (lb (p-ln) bits, 每个键存储)其中ln ceil(log2(n))lb控制容器大小entry_bits lb (p - ln)。对于小精度 (p 20)使用直接直方图模式——不使用容器或分散只是一个具有O(n 2^p)重建的计数直方图。阶段处理单次直接分散。对于每个键从 MSB 提取bin_id从剩余位提取entry。将entry写入sbatch_mem中该容器对应的区域。键按批次处理每批为每个容器生成一个排序后的运行。排序对每批中每个容器内的entry进行基数排序对于小型容器也可用插入排序。排序后的运行被连接起来——不需要全局索引数组。获取项在容器计数上通过线段树查找找到目标容器O(log n_bins)。通过二分搜索在排序后的运行中进行 K 路选择以找到目标排名位置的entry。将键重建为(bin_id entry_bits) | entry。全部重建对所有容器中的排序后运行进行 K 路合并以生成完整的排序输出。最优lb选择lb参数控制容器数量和条目大小之间的权衡。规则容器数使用场景lb e - 101024当e 20时的默认值lb e - 664当e 20时的默认值容器数更少要求Python 3.8NumPyNumbapipinstallnumpy numba使用方法排序和访问fromfractalsort_cpuimportfractalsortimportnumpyasnp# 生成随机的 32 位键keysnp.random.randint(0,2**32,size1_000_000,dtypenp.uint32)# 排序 (首次调用包含 JIT 编译)resultfractalsort(keys,p32,lb12)# 按位置访问排序后的键smallestresult[0]largestresult[-1]medianresult[len(result)//2]# 重建所有排序后的键sorted_keysresult.reconstruct_all()assertnp.array_equal(sorted_keys,np.sort(keys))参数resultfractalsort(keys,# uint32 类型的键数组p32,# 键的精度位数lbNone,# log2(容器大小), 默认值: e-10 (当 e20) 或 e-6 (当 e20)n_batches4,# 处理批次 (用于流式处理))结果对象result.get_item(position)# 点查询: O(log bins k*log(bin_size))result[i]# 通过 __getitem__ 实现相同功能result[10:20]# 切片访问len(result)# 键的总数result.reconstruct_all()# 按排序顺序返回所有键内部数组供高级使用result.sbatch_mem# 条目数组 (每个容器的区域排序后的运行)result.bin_counts# 每个容器的条目数result.bin_cumulative# 每个容器的累积起始位置result.batch_boundaries# [n_bins, n_batches1] 每个容器的每批运行边界result.n_batches# 批次数量result.ln# 树深度result.lb# log2(容器大小)result.entry_bits# 每个条目的位数result.n_bins# 容器数量result.seg_tree# 用于 O(log n_bins) 容器查找的线段树测试python test_fractalsort.py[e][lb]示例:python test_fractalsort.py# e18, 自动 lbpython test_fractalsort.py20# e20, 自动 lbpython test_fractalsort.py2012# e20, lb12性能吞吐量 (单核, Numba JIT, p32)数据集nFractalSort (百万键/秒)基数排序 (百万键/秒)加速比1 MB262K124572.2 倍16 MB4.2M76591.3 倍64 MB16.8M98671.5 倍256 MB67.1M122711.7 倍4 GB1.07B78431.8 倍在这个单核 Python/Numba 配置中FractalSortCPU 在所有数据集大小上均更快。其带宽效率优势在更大规模下进一步增长——有关高达 32GB 的完整多平台基准测试请参阅论文。复现基准测试pipinstallnumpy numba python bench_frmw_io.py许可证MIT——详见 LICENSE 文件。