A Fast Quicksort blqsort - A C++ Quicksort Faster Than std::sort blqsort is a very fast quicksort algorithm. I am not aware of any other general-purpose comparison-based sorting algorithm that is faster on random data. Only specialized SIMD-based algorithms are generally faster when dealing with small primitive data types. The implementation is available on GitHub under the MIT license.
There is also a C version of it, including multithreaded versions, each as a single header file. blqsort on Github The following benchmarks show the execution times for sorting 50 million random doubles using different sorting implementations. The measurements were taken on an Apple M1 system using Clang and on an Intel i5-9300H Linux system using GCC, both compiled with the -O3 option. random data Apple M1 Intel i5-9300H std::sort 1.33s 4.02s ipnsort ClickHouse C++ port 1.00s 2.11s blqsort 0.68s 1.32s Real-world data is often partially sorted. Here are benchmark results for 90% sorted input: partially sorted Apple M1 Intel i5-9300H std::sort 1.25s 1.84 ipnsort ClickHouse C++ port 0.94s 1.72s blqsort 0.72s 1.41 Execution times for sorting 50 million of these structs with random id values. struct entry { int id; int value; bool operator<(const entry& other) const { return id < other.id; } }; custom objects Apple M1 Intel i5 std::sort 3.45s 3.71s ipnsort ClickHouse C++ port 0.98s 2.04s blqsort 0.75s 1.60s For a fair comparison, the single-threaded version of blqsort was used here. On the M1, the multithreaded versions are roughly another factor of 3 faster.
In terms of runtime, the C versions differ only very little from the C++ version. Already sorted and reverse-sorted inputs are detected and handled efficiently. Inputs with many duplicate keys are optimized as well. The key concepts of blqsort are branchless partitioning, sorting networks for small partitions, and good pivot selection.
From a basic quicksort to blqsort The execution times, unless otherwise specified, apply to an Apple M1 system. A small, elegant, recursive quicksort: #include <cstdio> #include <cstdlib> #include <chrono> constexpr int SIZE = 50000000; double data[SIZE]; double time() { static auto time0 = std::chrono::high_resolution_clock::now(); auto t = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> diff = t - time0; return diff.count(); } void sortq(double ar[], int len) { if (len < 2) return; double piv = ar[0]; int mid = 0; for (int i = 1; i < len; i++) { if (ar[i] < piv) { mid += 1; std::swap(ar[mid], ar[i]); } } std::swap(ar[mid], ar[0]); sortq(ar + mid + 1, len - mid - 1); sortq(ar, mid); } int main() { double t0; printf("Sorting %d million doubles\n", SIZE / 1000000); for (int i = 0; i < SIZE; i++) data[i] = rand() / 1024.0; t0 = time(); sortq(data, SIZE); printf("sortq: %.2fs\n", time() - t0); } c++ -O1 main.cpp && ./a.out Sorting 50 million doubles sortq: 4.61s If you sort the sorted data again, all elements in the partition are greater than or equal to the pivot element. The second partition becomes only one element smaller each time, and the function is called recursively millions of times, which leads to a stack overflow after a few hours. You can prevent this with tail call elimination.
That is, the first recursive call remains, while the second is replaced by a loop iteration. You now need to ensure that the smaller partition is called recursively. So swap them if necessary. void sortq(double* ar, int len) { while (len >= 2) { double piv = ar[0]; int mid = 0; for (int i = 1; i < len; i++) { if (ar[i] < piv) { mid += 1; std::swap(ar[mid], ar[i]); } } std::swap(ar[mid], ar[0]); double* ar2 = ar + mid + 1; int len2 = len - mid - 1; len = mid; if (len2 > len) { std::swap(len, len2); std::swap(ar, ar2); } sortq(ar2, len2); } } Now the program no longer crashes, but it will take a few days to finish. Because of this unfavorable partitioning, the worst-case scenario of O(n²) has become a reality.
However, insertion sort would not make it any faster either. Let’s just use the middle element as the pivot - then the problem of sorting already sorted data will be gone. . while (len >= 2) { std::swap(ar[len / 2], ar[0]); double piv = ar[0]; . The only remaining risk is that someone intentionally sends specially crafted data to trigger this behavior. To eliminate this threat, the pivot point should be selected randomly.
This implementation is sufficient for many purposes and is also reasonably fast. By the way, “Lomuto” partitioning is used here. “Hoare” partitioning performs fewer comparisons and swaps, but on modern CPUs its cache behavior can be less favorable. But why write your own implementation when std::sort exists? . #include <algorithm> . . t0 = time(); std::sort(data, data + SIZE); printf("std::sort: %.2fs\n", time() - t0); . std::sort: 1.31s That’s on ARM Mac - on a x86 system, std::sort is only about 10% faster. How can you make a quicksort run faster than std::sort?
Sorting networks For partitions with up to about 20 elements, insertion sort is faster than quicksort. But there is something even faster for small partitions: sorting networks. Each partition size is handled in its own program branch. For a partition size of two, the two elements are simply compared and swapped if necessary.
However, as the number of elements increases, the logic becomes increasingly complex. inline void sort2(double& a, double& b) { if (a < b) std::swap(a, b); } inline void sort3(double& a, double& b, double& c) { sort2(a, b); sort2(b, c); sort2(a, b); } inline void sort4(double& a, double& b, double& c, double& d) { sort2(a, b); sort2(c, d); sort2(a, c); sort2(b, d); sort2(b, c); } inline void sort5(double& a, double& b, double& c, double& d, double& e) { sort2(b, c); sort2(d, e); sort2(b, d); sort2(a, c); sort2(a, d); sort2(c, e); sort2(a, b); sort2(c, d); sort2(b, c); } . while (len >= 6) { . . } if (len == 5) sort5(ar[0], ar[1], ar[2], ar[3], ar[4]); else if (len == 4) sort4(ar[0], ar[1], ar[2], ar[3]); else if (len == 3) sort3(ar[0], ar[1], ar[2]); else if (len == 2) sort2(ar[0], ar[1]); } When if slows you down, avoid it Let’s consider a simple task: Iterate through an array and copy all numbers less than 500 into a new array. A straightforward implementation in C looks like this: smlen = 0; for (int i = 0; i < 1000; i++) { if (numbers[i] < 500) { small_numbers[smlen] = numbers[i]; smlen += 1; } } If the numbers are randomly distributed, the result of the if condition becomes unpredictable for the branch predictor. This results in a high misprediction rate, which severely impacts performance because the processor must constantly flush its pipeline and restart execution. We can avoid this problem by using a branchless approach: smlen = 0; for (int i = 0; i < 1000; i++) { small_numbers[smlen] = numbers[i]; smlen += (numbers[i] < 500); } Although this version introduces an unconditional write operation (writing to memory even if the condition is not met), the associated overhead is generally much lower than the performance loss resulting from a branch misprediction.
Branchless does not mean that there are no jumps at all. The term refers only to the comparison, which is difficult to predict. Obviously, the loop jump remains, but that is not a problem because it is easily predictable - it is skipped only once. Performance Comparison To get meaningful results, we run both routines for 1000 iterations using 100,000 random numbers. #include <stdio.h> #include <stdlib.h> #include <sys/time.h> #define SIZE 100000 int numbers[SIZE]; int small_numbers[SIZE]; int smlen; double ts(void) { static double t0; struct timeval tv; gettimeofday(&tv, NULL); double h = t0; t0 = tv.tv_sec + tv.tv_usec / 1000000.0; return t0 - h; } void init(void) { srand(1); for (int i = 0; i < SIZE; i++) numbers[i] = rand() % 1000; ts(); } void small_if(void) { smlen = 0; for (int i = 0; i < SIZE; i++) { if (numbers[i] < 500) { small_numbers[smlen] = numbers[i]; smlen += 1; } } } void small_bl(void) { smlen = 0; for (int i = 0; i < SIZE; i++) { small_numbers[smlen] = numbers[i]; smlen += (numbers[i] < 500); } } int main(void) { init(); for (int i = 0; i < 1000; i++) small_if(); printf("Time if: %.3f\n", ts()); init(); for (int i = 0; i < 1000; i++) small_bl(); printf("Time bl: %.3f\n", ts()); } Benchmark results were obtained on an Apple M1 with -O1 optimization.
On this benchmark, -O3 did not yield additional speedup, only larger generated code. Time if: 0.345 Time bl: 0.036 Assembly Analysis Using objdump -d, we can see the difference in how the CPU processes these loops. With the if version, the compiler generates a conditional branch b.gt. ldr w13, [x10], #0x4 ; load numbers[i] cmp w13, #0x1f3 ; compare with 499 (0x1f3) b.gt 0x100000678 ; branch if greater (The bottleneck) str w13, [x12, w8, sxtw #2] ; store value in small_numbers[j] add w8, w8, #0x1 ; j += 1 With the branchless version the compiler uses the cinc (conditional increment) instruction. ldr w13, [x10], #0x4 ; load numbers[i] str w13, [x12, w8, uxtw #2] ; unconditional store to small_numbers[j] cmp w13, #0x1f4 ; compare with 500 cinc w8, w8, lt ; conditional increment (No branch) In this version, there is no jump based on the data. The control flow is perfectly linear, allowing the CPU to use its full pipeline width.
Why doesn’t the compiler optimize the if case automatically? The compiler doesn’t know the nature of your data. If only a small fraction of numbers were less than 500, the branch version might actually be faster because the predictor would almost always be right. The branchless version performs a write operation (str) every single time.
The compiler cannot safely assume that it is permitted to write to memory if a write operation in the original source code was intended to occur only under a specific condition - for example, to avoid writing past the end of an allocated buffer. Since quicksort essentially works by dividing the data into large and small numbers, it should be possible to speed it up using this technique. Branchless quicksort (explicit version) So, as described above, we can make the partitioning step branchless. (comp is the comparison function): int h = comp(*left, piv); *lwr = *rwr = *left++; lwr += h; rwr -= !h; We can also make sort2 - the basic operation for the sorting network - branchless: inline static void sort2(double& a, double& b) { double x = a; double y = b; bool m = x < y; a = m ? x : y; b = m ? y : x; } Here’s how it works (in short) : First, about 250 elements are copied from one page into an auxiliary buffer to make room for subsequent operations. We then alternately copy a block to the left and to the right, without using any branches.
The pivot element is also carefully selected. Several medians are determined from various elements of the partition, and the final median is then calculated from these medians. This results in a much more even distribution of the data. Some randomness is added to the pivot selection process to prevent inputs from consistently triggering worst-case behavior.
If the distribution is still very uneven, however, the algorithm switches to heap sort for these partitions as a precaution. Uneven distribution often occurs when there are many identical elements; in this case, they are identified and grouped together. In addition, the code includes the sorting networks, which are used for partition sizes up to 16. And with a for (int i = 16; i--;) { ... } loop, the compiler unrolls the loop, generating 16 copies of the loop body.
This version consists of a single C++ header file that can be easily included. It can sort any data type, and the comparison function can be supplied by the user, just like with std::sort. blqs.h #ifndef BLQS_H #define BLQS_H #include <cstddef> #include <cstdint> #include <cstring> #include <functional> #include <utility> #ifndef BLQS_RAND #define BLQS_RAND #include <random> static thread_local uint64_t blqs_seed; stat
Texto de tiki.li tal como lo publicó, leído de su página y mostrado aquí con el formato de El Autómata. El original, en tiki.li · Volver a la noticia de El Autómata