Following on from Go 1.18’s support for generics, Go’s support for the pdqsort sorting algorithm in the next release has once again generated a lot of buzz among developers.
A feature description for pdqsort has now been committed to the latest commit of the Go repository.
pdqsort has not shown to be slower than other previous algorithms in all benchmark tests.
in common patterns, pdqsort is typically faster (i.e. 10x faster in sorted slices)
So what is pdqsort?
pdqsort, which stands for Pattern-defeating quicksort, is a new sorting algorithm that combines the fast average case of randomized quick sort with the fast worst case of heap sort, while achieving linear time on inputs with a particular pattern. pdqsort is an extension and improvement of David Mussers introsort. All code is free under the zlib licence.
There are currently implementations in C++ and Rust, and a number of developers have tested it and found that pdqsort gives a large performance gain over the commonly used introsort.
C++ implementation: https://github.com/orlp/pdqsort
Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/
C++ code demo.
#include <algorithm>
#include <functional>
#include <array>
#include <iostream>
#include <string_view>
int main()
{
std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
auto print = [&s](std::string_view const rem) {
for (auto a : s) {
std::cout << a << ‘ ‘;
}
std::cout << “: ” << rem << ‘\n’;
};
std::sort(s.begin(), s.end());
print(“sorted with the default operator<“);
std::sort(s.begin(), s.end(), std::greater<int>());
print(“sorted with the standard library compare function object”);
struct {
bool operator()(int a, int b) const { return a < b; }
} customLess;
std::sort(s.begin(), s.end(), customLess);
print(“sorted with a custom function object”);
std::sort(s.begin(), s.end(), [](int a, int b) {
return a > b;
});
print(“sorted with a lambda expression”);
}
Execution results.
0 1 2 3 4 5 6 7 8 9 : sorted with the default operator<
9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object
0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object
9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression
Rust Code Demo: extern crate pdqs
extern crate pdqsort;
let mut v = [-5i32, 4, 1, -3, 2];
pdqsort::sort(&mut v);
assert!(v == [-5, -3, 1, 2, 4]);
pdqsort::sort_by(&mut v, |a, b| b.cmp(a));
assert!(v == [4, 2, 1, -3, -5]);
pdqsort::sort_by_key(&mut v, |k| k.abs());
assert!(v == [1, 2, -3, 4, -5]);
And there’s been a lot of discussion on HN about Go’s support for the pdqsort algorithm, with some saying that we’ve been working on sorting algorithms for so long that it’s surprising we can still come up with optimisations that produce real improvements. What do you think about this, get your hands on it and experience it.
