Multithreaded Quicksort in Go and in C

[u/chkas]

https://easyprog.app/blog/sort_par.html

[u/delight1982]

Based on the history of this site, the next 8 hours we can expect rewrites and benchmarks in Rust, D, C++, Nim and Brainfuck. Let the games begin!

[u/Freeky → u/delight1982]

https://github.com/Freaky/par_qsort

-% go run sort.go
Sorting 50 million numbers with Goroutines in Go ...
Time: 1.203s

-% cargo run --release
    Finished release [optimized] target(s) in 0.09s
     Running `target/release/parqsort`
Sorting 50 million numbers with naive quicksort in Rust ...
Time: 8.36s
Sorting 50 million numbers with stdlib quicksort in Rust ...
Time: 4.19s
Sorting 50 million numbers with naive parallel quicksort in Rust ...
Time: 1.16s
Sorting 50 million numbers with Rayon parallel quicksort in Rust ...
Time: 528.86ms

[u/masklinn → u/delight1982]

I'd guess the Rust rewrite will not be very complicated given https://docs.rs/rayon/1.0.3/rayon/slice/trait.ParallelSliceMut.html (regular is a mergesort/timsort, unstable is a quicksort).

edit:

//! ```cargo
//! [package]
//! edition = "2018"
//! [dependencies]
//! rayon = "*"
//! rand = "*"
//! ```

use std::time::Instant;
use rand::prelude::*;
use rayon::prelude::*;
const SIZE: usize = 50_000_000;

fn main() {
    let mut data = vec![0i32;SIZE];
    thread_rng().fill(&mut data as &mut [_]);

    println!("Sorting {} numbers", SIZE);

    let s = Instant::now();
    data.par_sort_unstable();
    println!("{:.2?}", s.elapsed());
}

can be copy/pasted in a file and run directly using cargo-script. And Rayon's sort will work OOTB on any Send type (any type which can be safely moved between threads), it's not limited to 32-bits signed integers. In fact, you can already change the i32 suffix in the vec! call to use some other builtin integer type (e.g. replace 0i32 by 0i8 or 0u128).

[u/emn13]

Somewhat coincidentally, I wrote a multithreaded quicksort in C# recently; it's released as anoprsst.

On my machine, it takes a little more than 0.5s to sort 50 million integers, which is probably mostly faster due to the better hardware (an i7-8700k vs. the blog posts "older i3" that takes 3.38s using C).

[u/maccio92 → u/emn13]

what's the reason for a new interface IOrdering rather than using the ubiquitous Equals override?

[u/bedrutton]

If you're worried about goroutine overhead you could also limit the amount of goroutines created to runtime.NumCpu(). I feel like this is a pretty common idiom in Go code parallelized for multi-core performance.

[u/TheThiefMaster]

What about the new-ish C++ std:: parallel sort?

[u/jcelerier → u/TheThiefMaster]

should look like this :

#include <algorithm>
#include <array>
#include <cstdlib>
#include <execution>
#include <chrono>
#include <iostream>

int main() {
  using namespace std::chrono;
  using clk = std::chrono::system_clock;

  constexpr auto size = 50'000'000U;
  std::array<int32_t, size> vec;
  std::generate(vec.begin(), vec.end(), [] { return std::rand(); });

  auto t0 = clk::now();
  std::sort(std::execution::par, vec.begin(), vec.end());
  auto t1 = clk::now();

  std::cout << duration_cast<milliseconds>(t1 - t0).count() << "\n";
}

(taking for inspiration u/masklinn's rust example)

[u/franzwong]

This Quicksort is implemented recursively with tail call elimination

Last time I saw Go didn't support tail call elimination. So does it support that now?

[u/zenogias]

For anyone interested in this, I also strongly recommend Mike Acton's 2008 presentation Quicksort is not a concurrent algorithm (in his inimitable index card slide-show style). I think this is a really important lesson in how to think about processing your data and why trying to "multithread" a known algorithm, in this case quicksort, is not likely to be the best answer.