HackerPapers

arXiv:1705.02257cs.DC

In-place Parallel Super Scalar Samplesort (IPS$^4$o)

Michael Axtmann, Sascha Witt, Daniel Ferizovic, Peter Sanders

Abstract

We present a sorting algorithm that works in-place, executes in parallel, is cache-efficient, avoids branch-mispredictions, and performs work O(n log n) for arbitrary inputs with high probability. The main algorithmic contributions are new ways to make distribution-based algorithms in-place: On the practical side, by using coarse-grained block-based permutations, and on the theoretical side, we show how to eliminate the recursion stack. Extensive experiments show that our algorithm IPS$^4$o scales well on a variety of multi-core machines. We outperform our closest in-place competitor by a factor of up to 3. Even as a sequential algorithm, we are up to 1.5 times faster than the closest sequential competitor, BlockQuicksort.

arXiv comments
Journal reference
DOI
Subjects
cs.DCDistributed, Parallel, and Cluster Computing

On Hacker News

Linked by 2 identifiable commenters in 4 comments across 3 threads, from Jun 2017 to May 2020.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Lomuto's Comeback 1 comment

    • There's an even better branch-free (super scalar) sorting algorithm: "In-place Parallel Super Scalar Samplesort (IPS4o)" which we started using: https://github.com/SaschaWitt/ips4o https://arxiv.org/abs/1705.02257 As an example, to sort 10 million random longs on my computer it…

      ipsofactoView on HNParent context

  2. On the Worst-Case Complexity of TimSort 1 comment

    • Especially when targeting realistic machine models, there are a lot of things that are suboptimal about the classical sorting algorithms like quicksort or mergesort. For example, a quicksort with perfect choice of pivot will incur a branch miss with probability 50% for every…

      lorenzhsView on HNParent context

  3. Pattern-defeating quicksort 2 comments

    • To illustrate the point about branch misprediction, I implemented quicksort with intentionally skewed pivot selection. You can see the results here: https://github.com/lorenzhs/quicksort-pivot-imbalance For this demo I'm sorting a permutation of the range 1 to n, so obtaining…

      lorenzhsView on HNParent context

    • Don't count out sample-sort just yet, it lends itself to parallelisation very well and is blazingly fast. See https://arxiv.org/abs/1705.02257 (to be presented at ESA in September) for an in-place parallel implementation that overcomes the most important downsides of previous…

      lorenzhsView on HNParent context

Submitted to Hacker News

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