HackerPapers

arXiv:1008.2849cs.DS

Faster Radix Sort via Virtual Memory and Write-Combining

Jan Wassenberg, Peter Sanders

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms cs.PFPerformance

On Hacker News

Linked by 2 identifiable commenters in 4 comments across 4 threads, from Aug 2015 to Jun 2023.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. A performance analysis of Intel x86-SIMD-sort (AVX-512) 1 comment

    • > 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…

      janwasView on HNParent context

  2. Vectorized and performance-portable Quicksort 1 comment

    • 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…

      janwasView on HNParent context

  3. 10x Faster sort than C++ std:sort 1 comment

    • :) 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…

      janwasView on HNParent context

  4. Sorting out graph processing 1 comment

    • 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…

      frankmcsherryView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.