HackerPapers

arXiv:2205.05982cs.IR

Vectorized and performance-portable Quicksort

Mark Blacher, Joachim Giesen, Peter Sanders, Jan Wassenberg

Abstract

Recent works showed that implementations of Quicksort using vector CPU instructions can outperform the non-vectorized algorithms in widespread use. However, these implementations are typically single-threaded, implemented for a particular instruction set, and restricted to a small set of key types. We lift these three restrictions: our proposed 'vqsort' algorithm integrates into the state-of-the-art parallel sorter 'ips4o', with a geometric mean speedup of 1.59. The same implementation works on seven instruction sets (including SVE and RISC-V V) across four platforms. It also supports floating-point and 16-128 bit integer keys. To the best of our knowledge, this is the fastest sort for non-tuple keys on CPUs, up to 20 times as fast as the sorting algorithms implemented in standard libraries. This paper focuses on the practical engineering aspects enabling the speed and portability, which we have not yet seen demonstrated for a Quicksort implementation. Furthermore, we introduce compact and transpose-free sorting networks for in-register sorting of small arrays, and a vector-friendly pivot sampling strategy that is robust against adversarial input.

arXiv comments
21 pages
Journal reference
DOI
Subjects
cs.IRInformation Retrieval cs.DCDistributed, Parallel, and Cluster Computing

On Hacker News

Linked by 5 identifiable commenters in 6 comments across 5 threads, from Jun 2022 to Mar 2024. Found in 1 HN submission from Feb 2024 to Feb 2024. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. JPEG XL and the Pareto Front 1 comment

    • [0] for those interested in Highway. It's also mentioned in [1], which starts off > Today we're sharing open source code that can sort arrays of numbers about ten times as fast as the C++ std::sort, and outperforms state of the art architecture-specific algorithms, while being…

      jhalsteadView on HNParent context

  2. Efficient and performance-portable vector software 1 comment

    • That linked quicksort paper is pretty cool: https://arxiv.org/abs/2205.05982 - for sorting floats/integers the speedup against std::qsort is around 10x. Considering climate change more focus should be put on making fast and efficient software. Every watt not wasted on bad…

      nisaView on HNParent context

  3. Sorting with SIMD 1 comment

    • Yes indeed. IIRC std::sort's sorting network is only 3-7 elements wide. With SIMD we can handle 256. The trick is to minimize shuffling by reshaping 1D input to 2D and first sorting the columns. Previously one would then transpose (expensive) and then again sort columns. We…

      janwasView on HNParent context

  4. Apple M2 Die Shot and Architecture Analysis – Big Cost Increase and A15 Based IP 1 comment

    • > Stuff like SVE2 is really marginal when looking at whole system performance. It is not. A recent paper (https://arxiv.org/pdf/2205.05982.pdf) from Google engineering has compared performance of a vectorised (SIMD) vs non-vectorised implementation of the quick sort in the…

      inkyotoView on HNParent context

  5. Vectorized and performance-portable Quicksort 2 comments

    • The paper goes into a lot more details: https://arxiv.org/pdf/2205.05982.pdf

      slackerIIIView on HNParent context

    • Yes, this is discussed in section 4.2 of our paper: https://arxiv.org/pdf/2205.05982.pdf In short, it turns out not to help for single core with vectors, but a few initial passes of ips4o (with 64..256-way partitioning) is faster for parallel sorts.

      janwasView on HNParent context

Submitted to Hacker News

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