按年被提到
20102022 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:1008.2849 · cs.DS

Faster Radix Sort via Virtual Memory and Write-Combining

Jan Wassenberg, Peter Sanders · 2010
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2015-08-20 · 最近 2023-06-13
2不同的人
3活跃月份
4讨论串
2被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Sorting algorithms are the deciding factor for the performance of common operations such as removal of duplicates or database sort-merge joins. This work focuses on 32-bit integer keys, optionally paired with a 32-bit value. We present a fast radix sorting algorithm that builds upon a microarchitecture-aware variant of counting sort. Taking advantage of virtual memory and making use of write-combining yields a per-pass throughput corresponding to at least 88 % of the system's peak memory bandwidth. Our implementation outperforms Intel's recently published radix sort by a factor of 1.5. It also compares favorably to the reported performance of an algorithm for Fermi GPUs when data-transfer overhead is included. These results indicate that scalar, bandwidth-sensitive sorting algorithms remain competitive on current architectures. Various other memory-intensive applications can benefit from the techniques described herein.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论frankmcsherry · 2015-08

“There is this cool related work [0] that I wanted to talk about, but couldn't get to show an improvement on my laptop, which uses software write combining to mitigate cache limitations. In particular, they are worried about the fact that 8-way associative L1 doesn't like to hold 256 specific cache lines, so they manually buffer writes into 16k (= 256 cach…”

Sorting out graph processing原评论 ↗
评论janwas · 2022-06

“:) Are you thinking of ips4o (sample sort)? That's about 2-3x std::sort. There's also a pending patch to std::sort that replaces it with BlockQuicksort which would narrow that gap. We integrate vqsort into ips4o, calling it once subarrays fit in L2. That speeds up ips4o by 2.9x (single thread) and 1.6 (parallel - bandwidth limited). More details in the p…”

10x Faster sort than C++ std:sort原评论 ↗
评论janwas · 2022-06

“Actually we also support floating-point (32/64 bit, possibly even 16). I've previously also looked into radix sort: https://arxiv.org/abs/1008.2849 Radix sort may actually be faster if you know that only a few bytes are guaranteed to distinguish keys, but that's difficult to guarantee/assume at the library level.”

Vectorized and performance-portable Quicksort原评论 ↗
评论janwas · 2023-06

“> According to the benchmarks in the article, many are also doing better at low-cardinality data. VQSort handles low cardinality quite well. Unfortunately only a few benchmarks in the article (not including that one) were re-run after our performance bug fix. > it's very strange to compare to std::sort which does make some attempt to be adaptive. We ch…”

10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)原评论 ↗