vector-quicksort 0.1 → 0.2
raw patch · 20 files changed
+1501/−920 lines, 20 filesdep +tasty-hunitdep −atomic-counterdep −paralleldep ~basedep ~tasty
Dependencies added: tasty-hunit
Dependencies removed: atomic-counter, parallel
Dependency ranges changed: base, tasty
Files
- Changelog.md +8/−0
- Readme.md +698/−589
- bench/BenchMain.hs +206/−38
- bench/ForeignSorting.hs +0/−18
- bench/ForeignSorting.hsc +56/−0
- cbits/sort.cpp +171/−1
- cbits/sort.h +14/−0
- src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/AveragingMedian.hs +0/−68
- src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/PIntSequentialAveragingMedianST.hs +0/−24
- src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/PTripleSequentialMedian3ST.hs +30/−0
- src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/PTripleSequentialMedian3or5ST.hs +24/−0
- src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/SortTriple.hs +143/−0
- src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/UPairSequentialAveragingMedianST.hs +0/−23
- src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/UTripleSequentialMedian3ST.hs +30/−0
- src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/UTripleSequentialMedian3or5ST.hs +24/−0
- src/Data/Vector/Algorithms/Quicksort.hs +9/−8
- src/Data/Vector/Algorithms/Quicksort/Median.hs +49/−68
- src/Data/Vector/Algorithms/Quicksort/Parameterised.hs +0/−36
- test/Data/Vector/Algorithms/Quicksort/Tests.hs +0/−18
- vector-quicksort.cabal +39/−29
+ Changelog.md view
@@ -0,0 +1,8 @@+# 0.2++- Improve performance+- Remove median guessing: remove `Guess` case from `MedianResult` type. Now custom median selection algorithms always have to pick existing value from array to be sorted (shouldn’t really be a limitation in practice)++# 0.1++- Initial release
Readme.md view
@@ -1,591 +1,700 @@-[](https://github.com/sergv/atomic-counter/actions/workflows/haskell-ci.yaml)--# Synopsis--This package features reasonable sort function that is a good default-for sorting mutable vectors using well-known quicksort algorithm.-During development one of the goals was making it perform on par with-C++’s `std::sort`, i.e. fast.--While providing reasonably good single-threaded default sorting, the-algorithm in this package is also parallelisable and can provides ways-to run on multiple cores using either threads or sparks, so bigger-vectors can be sorted even faster.--# Algorithm details--Technically it’s an (introsort)[https://en.wikipedia.org/wiki/Introsort], i.e.-pathological `O(N^2)` quicksort case will get delegated to heapsort when recursion-gets too deep, thus making algorithm reliably `O(N * log(N))`.--# Benchmarks--The benchmark is to generate some random arrays of different length-and sort them. For each array size N two versions are generated: one-from range [0, N] (`with few duplicates` below),-another from [0, N / 1000] (`with many duplicates` below) to-introduce duplicates. And there’s one reasonably big array (around-40,000 elements) with lots of duplicates that I managed to come by in-the real world under `Sorting fuzzy matching scores vector` that comes-from `test.txt` file in this repository. with--Test setup: Intel i5-9600K CPU @ 3.70GHz, 6 cores, no hyperthreading, GHC 9.6.1.--The default sort exported in `Data.Vector.Algorithms.Quicksort` is `Sequential` and `Median3or5`.--```-$ cabal run bench -- -j1 --time-mode wall --timeout 300-All- Sorting fuzzy matching scores vector- C++: OK (0.54s)- 377 μs ± 30 μs- Sequential ST Median3: OK (0.36s)- 315 μs ± 17 μs, 0.83x- Sequential IO Median3: OK (0.31s)- 288 μs ± 17 μs, 0.76x- ParStrategies ST Median3: OK (0.15s)- 285 μs ± 23 μs, 0.76x- ParStrategies IO Median3: OK (0.16s)- 306 μs ± 22 μs, 0.81x- Sequential ST Median3or5: OK (0.28s)- 261 μs ± 13 μs, 0.69x- Sequential IO Median3or5: OK (0.28s)- 264 μs ± 25 μs, 0.70x- ParStrategies ST Median3or5: OK (0.14s)- 268 μs ± 21 μs, 0.71x- ParStrategies IO Median3or5: OK (0.15s)- 272 μs ± 27 μs, 0.72x- Sequential ST AveragingMedian: OK (0.16s)- 2.47 ms ± 191 μs, 6.55x- Threads IO Median3: OK (0.31s)- 295 μs ± 28 μs, 0.78x- Threads IO Median3or5: OK (0.24s)- 230 μs ± 12 μs, 0.61x- vector-algorithms heapsort: OK (0.27s)- 2.06 ms ± 97 μs, 5.45x- fallback heapsort: OK (0.25s)- 1.91 ms ± 106 μs, 5.07x- Sorting 10 random arrays of length 16 with few duplicates- C++: OK (0.36s)- 654 ns ± 24 ns- Sequential ST Median3: OK (0.31s)- 554 ns ± 23 ns, 0.85x- Sequential IO Median3: OK (0.16s)- 559 ns ± 44 ns, 0.85x- ParStrategies ST Median3: OK (0.16s)- 578 ns ± 58 ns, 0.88x- ParStrategies IO Median3: OK (0.32s)- 578 ns ± 26 ns, 0.88x- Sequential ST Median3or5: OK (0.16s)- 569 ns ± 50 ns, 0.87x- Sequential IO Median3or5: OK (0.16s)- 571 ns ± 50 ns, 0.87x- ParStrategies ST Median3or5: OK (0.17s)- 580 ns ± 42 ns, 0.89x- ParStrategies IO Median3or5: OK (0.16s)- 577 ns ± 49 ns, 0.88x- Sequential ST AveragingMedian: OK (0.31s)- 557 ns ± 27 ns, 0.85x- Threads IO Median3: OK (0.24s)- 1.71 μs ± 128 ns, 2.62x- Threads IO Median3or5: OK (0.24s)- 1.73 μs ± 120 ns, 2.64x- vector-algorithms heapsort: OK (0.20s)- 1.41 μs ± 117 ns, 2.16x- fallback heapsort: OK (0.62s)- 1.15 μs ± 29 ns, 1.76x- Sorting 10 random arrays of length 17 with few duplicates- C++: OK (0.21s)- 758 ns ± 73 ns- Sequential ST Median3: OK (0.38s)- 701 ns ± 35 ns, 0.92x- Sequential IO Median3: OK (0.20s)- 728 ns ± 60 ns, 0.96x- ParStrategies ST Median3: OK (0.22s)- 773 ns ± 49 ns, 1.02x- ParStrategies IO Median3: OK (0.21s)- 766 ns ± 44 ns, 1.01x- Sequential ST Median3or5: OK (0.39s)- 727 ns ± 55 ns, 0.96x- Sequential IO Median3or5: OK (0.20s)- 724 ns ± 47 ns, 0.95x- ParStrategies ST Median3or5: OK (0.22s)- 793 ns ± 68 ns, 1.05x- ParStrategies IO Median3or5: OK (0.22s)- 791 ns ± 63 ns, 1.04x- Sequential ST AveragingMedian: OK (0.30s)- 2.18 μs ± 92 ns, 2.88x- Threads IO Median3: OK (0.14s)- 1.89 μs ± 182 ns, 2.49x- Threads IO Median3or5: OK (0.14s)- 1.99 μs ± 176 ns, 2.63x- vector-algorithms heapsort: OK (0.21s)- 1.52 μs ± 114 ns, 2.01x- fallback heapsort: OK (0.18s)- 1.23 μs ± 116 ns, 1.62x- Sorting 10 random arrays of length 100 with few duplicates- C++: OK (0.16s)- 4.33 μs ± 413 ns- Sequential ST Median3: OK (0.38s)- 5.56 μs ± 371 ns, 1.29x- Sequential IO Median3: OK (0.20s)- 5.55 μs ± 333 ns, 1.28x- ParStrategies ST Median3: OK (0.21s)- 6.03 μs ± 345 ns, 1.39x- ParStrategies IO Median3: OK (0.50s)- 7.24 μs ± 287 ns, 1.67x- Sequential ST Median3or5: OK (0.20s)- 5.57 μs ± 337 ns, 1.29x- Sequential IO Median3or5: OK (0.20s)- 5.59 μs ± 329 ns, 1.29x- ParStrategies ST Median3or5: OK (0.22s)- 6.28 μs ± 371 ns, 1.45x- ParStrategies IO Median3or5: OK (0.22s)- 6.52 μs ± 621 ns, 1.51x- Sequential ST AveragingMedian: OK (0.26s)- 30.5 μs ± 2.8 μs, 7.05x- Threads IO Median3: OK (0.13s)- 7.28 μs ± 686 ns, 1.68x- Threads IO Median3or5: OK (0.49s)- 7.22 μs ± 296 ns, 1.67x- vector-algorithms heapsort: OK (0.32s)- 18.8 μs ± 1.4 μs, 4.35x- fallback heapsort: OK (0.20s)- 22.9 μs ± 1.5 μs, 5.30x- Sorting 10 random arrays of length 256 with few duplicates- C++: OK (0.19s)- 44.7 μs ± 2.9 μs- Sequential ST Median3: OK (0.45s)- 54.6 μs ± 2.8 μs, 1.22x- Sequential IO Median3: OK (0.20s)- 46.9 μs ± 3.5 μs, 1.05x- ParStrategies ST Median3: OK (0.22s)- 51.3 μs ± 3.9 μs, 1.15x- ParStrategies IO Median3: OK (0.23s)- 53.7 μs ± 4.1 μs, 1.20x- Sequential ST Median3or5: OK (0.21s)- 48.1 μs ± 3.1 μs, 1.07x- Sequential IO Median3or5: OK (0.21s)- 47.8 μs ± 2.9 μs, 1.07x- ParStrategies ST Median3or5: OK (0.23s)- 54.0 μs ± 4.0 μs, 1.21x- ParStrategies IO Median3or5: OK (0.24s)- 54.3 μs ± 5.0 μs, 1.21x- Sequential ST AveragingMedian: OK (0.13s)- 119 μs ± 11 μs, 2.67x- Threads IO Median3: OK (0.24s)- 56.3 μs ± 5.6 μs, 1.26x- Threads IO Median3or5: OK (0.24s)- 56.1 μs ± 4.6 μs, 1.25x- vector-algorithms heapsort: OK (0.23s)- 110 μs ± 6.6 μs, 2.47x- fallback heapsort: OK (0.21s)- 95.2 μs ± 6.5 μs, 2.13x- Sorting 10 random arrays of length 1,000 with few duplicates- C++: OK (0.15s)- 274 μs ± 24 μs- Sequential ST Median3: OK (0.13s)- 471 μs ± 46 μs, 1.72x- Sequential IO Median3: OK (0.23s)- 428 μs ± 28 μs, 1.56x- ParStrategies ST Median3: OK (0.19s)- 350 μs ± 27 μs, 1.27x- ParStrategies IO Median3: OK (0.24s)- 451 μs ± 42 μs, 1.65x- Sequential ST Median3or5: OK (0.18s)- 333 μs ± 31 μs, 1.22x- Sequential IO Median3or5: OK (0.12s)- 428 μs ± 42 μs, 1.56x- ParStrategies ST Median3or5: OK (0.25s)- 460 μs ± 42 μs, 1.68x- ParStrategies IO Median3or5: OK (0.19s)- 363 μs ± 27 μs, 1.32x- Sequential ST AveragingMedian: OK (0.20s)- 742 μs ± 64 μs, 2.71x- Threads IO Median3: OK (0.25s)- 469 μs ± 25 μs, 1.71x- Threads IO Median3or5: OK (0.25s)- 457 μs ± 37 μs, 1.67x- vector-algorithms heapsort: OK (0.18s)- 667 μs ± 65 μs, 2.43x- fallback heapsort: OK (0.17s)- 618 μs ± 46 μs, 2.25x- Sorting 10 random arrays of length 10,000 with few duplicates- C++: OK (0.29s)- 4.50 ms ± 269 μs- Sequential ST Median3: OK (0.19s)- 6.00 ms ± 586 μs, 1.33x- Sequential IO Median3: OK (0.28s)- 4.31 ms ± 260 μs, 0.96x- ParStrategies ST Median3: OK (0.18s)- 5.73 ms ± 514 μs, 1.27x- ParStrategies IO Median3: OK (0.20s)- 6.06 ms ± 375 μs, 1.35x- Sequential ST Median3or5: OK (0.14s)- 4.35 ms ± 353 μs, 0.97x- Sequential IO Median3or5: OK (0.18s)- 5.57 ms ± 524 μs, 1.24x- ParStrategies ST Median3or5: OK (0.15s)- 4.62 ms ± 340 μs, 1.03x- ParStrategies IO Median3or5: OK (0.38s)- 5.89 ms ± 520 μs, 1.31x- Sequential ST AveragingMedian: OK (0.31s)- 9.89 ms ± 437 μs, 2.20x- Threads IO Median3: OK (0.60s)- 4.65 ms ± 291 μs, 1.03x- Threads IO Median3or5: OK (0.37s)- 5.77 ms ± 183 μs, 1.28x- vector-algorithms heapsort: OK (0.14s)- 8.79 ms ± 718 μs, 1.95x- fallback heapsort: OK (0.26s)- 8.34 ms ± 568 μs, 1.85x- Sorting 10 random arrays of length 100,000 with few duplicates- C++: OK (0.17s)- 55.6 ms ± 3.2 ms- Sequential ST Median3: OK (0.24s)- 78.1 ms ± 3.7 ms, 1.41x- Sequential IO Median3: OK (0.21s)- 69.3 ms ± 3.7 ms, 1.25x- ParStrategies ST Median3: OK (0.18s)- 59.5 ms ± 4.5 ms, 1.07x- ParStrategies IO Median3: OK (3.66s)- 56.6 ms ± 5.3 ms, 1.02x- Sequential ST Median3or5: OK (0.16s)- 54.0 ms ± 3.5 ms, 0.97x- Sequential IO Median3or5: OK (0.21s)- 67.3 ms ± 5.7 ms, 1.21x- ParStrategies ST Median3or5: OK (0.19s)- 62.3 ms ± 5.6 ms, 1.12x- ParStrategies IO Median3or5: OK (0.45s)- 65.3 ms ± 4.7 ms, 1.17x- Sequential ST AveragingMedian: OK (0.38s)- 127 ms ± 4.5 ms, 2.28x- Threads IO Median3: OK (0.34s)- 48.3 ms ± 2.7 ms, 0.87x- Threads IO Median3or5: OK (0.34s)- 47.7 ms ± 2.4 ms, 0.86x- vector-algorithms heapsort: OK (0.37s)- 124 ms ± 8.9 ms, 2.23x- fallback heapsort: OK (0.81s)- 113 ms ± 5.4 ms, 2.04x- Sorting 10 random arrays of length 1,000,000 with few duplicates- C++: OK (2.05s)- 682 ms ± 15 ms- Sequential ST Median3: OK (2.18s)- 727 ms ± 7.5 ms, 1.06x- Sequential IO Median3: OK (2.44s)- 812 ms ± 9.6 ms, 1.19x- ParStrategies ST Median3: OK (1.44s)- 204 ms ± 13 ms, 0.30x- ParStrategies IO Median3: OK (0.81s)- 268 ms ± 20 ms, 0.39x- Sequential ST Median3or5: OK (2.00s)- 664 ms ± 45 ms, 0.97x- Sequential IO Median3or5: OK (1.95s)- 645 ms ± 43 ms, 0.95x- ParStrategies ST Median3or5: OK (1.49s)- 209 ms ± 4.9 ms, 0.31x- ParStrategies IO Median3or5: OK (1.46s)- 208 ms ± 21 ms, 0.30x- Sequential ST AveragingMedian: OK (4.05s)- 1.348 s ± 8.5 ms, 1.98x- Threads IO Median3: OK (1.53s)- 508 ms ± 7.1 ms, 0.74x- Threads IO Median3or5: OK (1.36s)- 452 ms ± 6.2 ms, 0.66x- vector-algorithms heapsort: OK (3.94s)- 1.309 s ± 53 ms, 1.92x- fallback heapsort: OK (3.67s)- 1.220 s ± 27 ms, 1.79x- Sorting 10 random arrays of length 10,000,000 with few duplicates- C++: OK (18.62s)- 6.188 s ± 240 ms- Sequential ST Median3: OK (25.26s)- 8.422 s ± 49 ms, 1.36x- Sequential IO Median3: OK (21.91s)- 7.295 s ± 118 ms, 1.18x- ParStrategies ST Median3: OK (6.01s)- 2.010 s ± 110 ms, 0.32x- ParStrategies IO Median3: OK (6.16s)- 2.044 s ± 100 ms, 0.33x- Sequential ST Median3or5: OK (21.85s)- 7.284 s ± 4.9 ms, 1.18x- Sequential IO Median3or5: OK (21.94s)- 7.311 s ± 38 ms, 1.18x- ParStrategies ST Median3or5: OK (6.05s)- 2.010 s ± 72 ms, 0.32x- ParStrategies IO Median3or5: OK (6.27s)- 2.090 s ± 2.8 ms, 0.34x- Sequential ST AveragingMedian: OK (81.58s)- 27.074 s ± 1.60 s, 4.38x- Threads IO Median3: OK (15.86s)- 5.283 s ± 29 ms, 0.85x- Threads IO Median3or5: OK (12.85s)- 4.283 s ± 7.3 ms, 0.69x- vector-algorithms heapsort: OK (71.14s)- 23.711 s ± 33 ms, 3.83x- fallback heapsort: OK (96.39s)- 32.157 s ± 355 ms, 5.20x- Sorting 10 random arrays of length 16 with many duplicates- C++: OK (0.37s)- 673 ns ± 36 ns- Sequential ST Median3: OK (0.17s)- 576 ns ± 53 ns, 0.86x- Sequential IO Median3: OK (0.16s)- 560 ns ± 49 ns, 0.83x- ParStrategies ST Median3: OK (0.17s)- 576 ns ± 49 ns, 0.86x- ParStrategies IO Median3: OK (0.17s)- 575 ns ± 42 ns, 0.85x- Sequential ST Median3or5: OK (0.17s)- 575 ns ± 57 ns, 0.85x- Sequential IO Median3or5: OK (0.17s)- 568 ns ± 47 ns, 0.84x- ParStrategies ST Median3or5: OK (0.33s)- 596 ns ± 50 ns, 0.89x- ParStrategies IO Median3or5: OK (0.33s)- 593 ns ± 30 ns, 0.88x- Sequential ST AveragingMedian: OK (0.32s)- 571 ns ± 26 ns, 0.85x- Threads IO Median3: OK (0.24s)- 1.71 μs ± 85 ns, 2.54x- Threads IO Median3or5: OK (0.24s)- 1.71 μs ± 118 ns, 2.53x- vector-algorithms heapsort: OK (0.20s)- 1.39 μs ± 90 ns, 2.06x- fallback heapsort: OK (0.17s)- 1.17 μs ± 83 ns, 1.73x- Sorting 10 random arrays of length 17 with many duplicates- C++: OK (0.22s)- 763 ns ± 56 ns- Sequential ST Median3: OK (0.41s)- 752 ns ± 22 ns, 0.99x- Sequential IO Median3: OK (0.21s)- 744 ns ± 64 ns, 0.98x- ParStrategies ST Median3: OK (0.23s)- 798 ns ± 44 ns, 1.05x- ParStrategies IO Median3: OK (0.22s)- 782 ns ± 46 ns, 1.03x- Sequential ST Median3or5: OK (0.21s)- 738 ns ± 44 ns, 0.97x- Sequential IO Median3or5: OK (0.21s)- 749 ns ± 52 ns, 0.98x- ParStrategies ST Median3or5: OK (0.22s)- 786 ns ± 42 ns, 1.03x- ParStrategies IO Median3or5: OK (0.44s)- 796 ns ± 29 ns, 1.04x- Sequential ST AveragingMedian: OK (0.30s)- 2.16 μs ± 88 ns, 2.83x- Threads IO Median3: OK (0.14s)- 1.92 μs ± 173 ns, 2.51x- Threads IO Median3or5: OK (0.27s)- 1.98 μs ± 116 ns, 2.59x- vector-algorithms heapsort: OK (0.22s)- 1.52 μs ± 97 ns, 1.99x- fallback heapsort: OK (0.18s)- 1.26 μs ± 85 ns, 1.65x- Sorting 10 random arrays of length 100 with many duplicates- C++: OK (0.19s)- 5.12 μs ± 401 ns- Sequential ST Median3: OK (0.21s)- 5.85 μs ± 409 ns, 1.14x- Sequential IO Median3: OK (0.21s)- 5.85 μs ± 527 ns, 1.14x- ParStrategies ST Median3: OK (0.22s)- 6.26 μs ± 395 ns, 1.22x- ParStrategies IO Median3: OK (0.28s)- 7.89 μs ± 461 ns, 1.54x- Sequential ST Median3or5: OK (0.21s)- 5.71 μs ± 458 ns, 1.11x- Sequential IO Median3or5: OK (0.20s)- 5.70 μs ± 404 ns, 1.11x- ParStrategies ST Median3or5: OK (0.23s)- 6.45 μs ± 381 ns, 1.26x- ParStrategies IO Median3or5: OK (0.23s)- 6.47 μs ± 499 ns, 1.26x- Sequential ST AveragingMedian: OK (0.13s)- 29.0 μs ± 2.6 μs, 5.65x- Threads IO Median3: OK (0.14s)- 7.34 μs ± 671 ns, 1.43x- Threads IO Median3or5: OK (0.26s)- 7.48 μs ± 455 ns, 1.46x- vector-algorithms heapsort: OK (0.17s)- 18.6 μs ± 1.3 μs, 3.63x- fallback heapsort: OK (0.20s)- 23.2 μs ± 2.2 μs, 4.52x- Sorting 10 random arrays of length 256 with many duplicates- C++: OK (0.20s)- 46.3 μs ± 3.2 μs- Sequential ST Median3: OK (0.25s)- 55.6 μs ± 5.0 μs, 1.20x- Sequential IO Median3: OK (0.42s)- 49.5 μs ± 3.0 μs, 1.07x- ParStrategies ST Median3: OK (0.23s)- 53.0 μs ± 2.7 μs, 1.14x- ParStrategies IO Median3: OK (0.13s)- 55.7 μs ± 5.3 μs, 1.20x- Sequential ST Median3or5: OK (0.22s)- 49.2 μs ± 2.9 μs, 1.06x- Sequential IO Median3or5: OK (0.42s)- 49.3 μs ± 2.0 μs, 1.06x- ParStrategies ST Median3or5: OK (0.24s)- 55.2 μs ± 4.2 μs, 1.19x- ParStrategies IO Median3or5: OK (0.47s)- 55.0 μs ± 1.5 μs, 1.19x- Sequential ST AveragingMedian: OK (0.13s)- 121 μs ± 11 μs, 2.60x- Threads IO Median3: OK (0.13s)- 56.1 μs ± 5.4 μs, 1.21x- Threads IO Median3or5: OK (0.25s)- 56.6 μs ± 3.4 μs, 1.22x- vector-algorithms heapsort: OK (0.22s)- 102 μs ± 5.2 μs, 2.21x- fallback heapsort: OK (0.21s)- 94.9 μs ± 5.4 μs, 2.05x- Sorting 10 random arrays of length 1,000 with many duplicates- C++: OK (0.30s)- 279 μs ± 14 μs- Sequential ST Median3: OK (0.20s)- 367 μs ± 22 μs, 1.31x- Sequential IO Median3: OK (0.18s)- 335 μs ± 33 μs, 1.20x- ParStrategies ST Median3: OK (0.19s)- 344 μs ± 22 μs, 1.23x- ParStrategies IO Median3: OK (0.19s)- 359 μs ± 24 μs, 1.28x- Sequential ST Median3or5: OK (0.18s)- 336 μs ± 25 μs, 1.20x- Sequential IO Median3or5: OK (0.18s)- 336 μs ± 21 μs, 1.20x- ParStrategies ST Median3or5: OK (0.38s)- 358 μs ± 14 μs, 1.28x- ParStrategies IO Median3or5: OK (0.19s)- 363 μs ± 26 μs, 1.30x- Sequential ST AveragingMedian: OK (0.16s)- 583 μs ± 43 μs, 2.09x- Threads IO Median3: OK (0.19s)- 357 μs ± 23 μs, 1.28x- Threads IO Median3or5: OK (0.19s)- 358 μs ± 28 μs, 1.28x- vector-algorithms heapsort: OK (0.15s)- 536 μs ± 42 μs, 1.92x- fallback heapsort: OK (0.13s)- 494 μs ± 46 μs, 1.77x- Sorting 10 random arrays of length 10,000 with many duplicates- C++: OK (0.21s)- 3.25 ms ± 184 μs- Sequential ST Median3: OK (0.14s)- 4.23 ms ± 347 μs, 1.30x- Sequential IO Median3: OK (0.24s)- 3.65 ms ± 329 μs, 1.12x- ParStrategies ST Median3: OK (0.12s)- 3.76 ms ± 362 μs, 1.15x- ParStrategies IO Median3: OK (0.13s)- 3.98 ms ± 360 μs, 1.22x- Sequential ST Median3or5: OK (0.24s)- 3.72 ms ± 254 μs, 1.14x- Sequential IO Median3or5: OK (0.12s)- 3.71 ms ± 344 μs, 1.14x- ParStrategies ST Median3or5: OK (0.13s)- 3.96 ms ± 344 μs, 1.22x- ParStrategies IO Median3or5: OK (0.27s)- 4.10 ms ± 315 μs, 1.26x- Sequential ST AveragingMedian: OK (0.12s)- 7.81 ms ± 724 μs, 2.40x- Threads IO Median3: OK (0.13s)- 3.92 ms ± 338 μs, 1.20x- Threads IO Median3or5: OK (0.13s)- 4.05 ms ± 347 μs, 1.24x- vector-algorithms heapsort: OK (0.12s)- 7.85 ms ± 674 μs, 2.41x- fallback heapsort: OK (0.21s)- 6.58 ms ± 434 μs, 2.02x- Sorting 10 random arrays of length 100,000 with many duplicates- C++: OK (0.24s)- 33.0 ms ± 1.5 ms- Sequential ST Median3: OK (0.12s)- 38.8 ms ± 2.7 ms, 1.18x- Sequential IO Median3: OK (0.10s)- 33.1 ms ± 2.9 ms, 1.00x- ParStrategies ST Median3: OK (0.23s)- 32.9 ms ± 1.9 ms, 1.00x- ParStrategies IO Median3: OK (0.13s)- 41.5 ms ± 3.3 ms, 1.26x- Sequential ST Median3or5: OK (0.23s)- 32.8 ms ± 2.3 ms, 1.00x- Sequential IO Median3or5: OK (0.10s)- 33.4 ms ± 3.1 ms, 1.01x- ParStrategies ST Median3or5: OK (0.23s)- 32.9 ms ± 1.5 ms, 1.00x- ParStrategies IO Median3or5: OK (0.23s)- 33.0 ms ± 2.0 ms, 1.00x- Sequential ST AveragingMedian: OK (0.31s)- 102 ms ± 7.6 ms, 3.08x- Threads IO Median3: OK (0.48s)- 32.2 ms ± 982 μs, 0.98x- Threads IO Median3or5: OK (0.48s)- 31.3 ms ± 1.6 ms, 0.95x- vector-algorithms heapsort: OK (0.31s)- 103 ms ± 5.2 ms, 3.12x- fallback heapsort: OK (0.27s)- 89.0 ms ± 4.7 ms, 2.70x- Sorting 10 random arrays of length 1,000,000 with many duplicates- C++: OK (1.03s)- 339 ms ± 32 ms- Sequential ST Median3: OK (1.16s)- 387 ms ± 5.5 ms, 1.14x- Sequential IO Median3: OK (0.99s)- 329 ms ± 5.0 ms, 0.97x- ParStrategies ST Median3: OK (0.59s)- 198 ms ± 15 ms, 0.58x- ParStrategies IO Median3: OK (0.60s)- 198 ms ± 5.8 ms, 0.58x- Sequential ST Median3or5: OK (0.99s)- 329 ms ± 8.3 ms, 0.97x- Sequential IO Median3or5: OK (1.00s)- 331 ms ± 3.6 ms, 0.98x- ParStrategies ST Median3or5: OK (1.39s)- 199 ms ± 5.0 ms, 0.59x- ParStrategies IO Median3or5: OK (0.60s)- 199 ms ± 3.0 ms, 0.59x- Sequential ST AveragingMedian: OK (3.82s)- 1.273 s ± 25 ms, 3.76x- Threads IO Median3: OK (0.88s)- 294 ms ± 27 ms, 0.87x- Threads IO Median3or5: OK (1.92s)- 274 ms ± 15 ms, 0.81x- vector-algorithms heapsort: OK (11.77s)- 1.664 s ± 6.3 ms, 4.91x- fallback heapsort: OK (4.08s)- 1.357 s ± 23 ms, 4.00x- Sorting 10 random arrays of length 10,000,000 with many duplicates- C++: OK (16.77s)- 5.595 s ± 88 ms- Sequential ST Median3: OK (15.18s)- 5.059 s ± 9.0 ms, 0.90x- Sequential IO Median3: OK (16.64s)- 5.541 s ± 75 ms, 0.99x- ParStrategies ST Median3: OK (4.50s)- 1.499 s ± 4.0 ms, 0.27x- ParStrategies IO Median3: OK (4.60s)- 1.534 s ± 14 ms, 0.27x- Sequential ST Median3or5: OK (12.89s)- 4.287 s ± 114 ms, 0.77x- Sequential IO Median3or5: OK (12.81s)- 4.267 s ± 46 ms, 0.76x- ParStrategies ST Median3or5: OK (4.19s)- 1.399 s ± 70 ms, 0.25x- ParStrategies IO Median3or5: OK (4.28s)- 1.430 s ± 43 ms, 0.26x- Sequential ST AveragingMedian: OK (72.72s)- 24.214 s ± 367 ms, 4.33x- Threads IO Median3: OK (10.38s)- 3.450 s ± 125 ms, 0.62x- Threads IO Median3or5: OK (8.70s)- 2.886 s ± 191 ms, 0.52x- vector-algorithms heapsort: OK (68.36s)- 22.767 s ± 265 ms, 4.07x- fallback heapsort: OK (65.38s)- 21.792 s ± 5.9 ms, 3.90x+[](https://github.com/sergv/vector-quicksort/actions/workflows/haskell-ci.yaml)++# Synopsis++This package features reasonable sort function that is a good default+for sorting mutable vectors using well-known quicksort algorithm.+During development one of the goals was making it perform on par with+C++’s `std::sort`, i.e. fast.++While providing reasonably good single-threaded default sorting, the+algorithm in this package is also parallelisable and can provide ways+to run on multiple cores using either threads or sparks, so bigger+vectors can be sorted even faster.++# Algorithm details++Technically it’s an [introsort](https://en.wikipedia.org/wiki/Introsort), i.e.+pathological `O(N^2)` quicksort case will get delegated to heapsort when recursion+gets too deep, thus making algorithm reliably `O(N * log(N))`.++# Benchmarks++The benchmark is to generate some random arrays of different length+and sort them. For each array size N two versions are generated: one+from range [0, N] (`with few duplicates` below),+another from [0, N / 1000] (`with many duplicates` below) to+introduce duplicates. And there’s one reasonably big array (around+40,000 elements) with lots of duplicates that I managed to come by in+the real world under `Sorting fuzzy matching scores vector` that comes+from `test.txt` file in this repository. with++Test setup: AMD Ryzen 9 7950X3D 16-Core Processor, Intel i5-9600K CPU @ 3.70GHz, GHC 9.10.1.++The default sort exported in `Data.Vector.Algorithms.Quicksort` is+`Sequential` and `Median3or5`.++NB `vector-algorithms` benchmark is not included below (but it’s still+there and will run for you locally) because it doesn’t specialise by+default and in that case takes around 100 times more time than C++.+That’s not representative, when this library doesn’t specialise it+suffers similar slowdown (please refer to the docs on how to alleviate+that).++```+$ cabal run bench -- -j1 --time-mode wall --timeout 300 -p '!/vector-algorithms heapsort/'+All+ Sorting fuzzy matching scores vector+ C++: OK+ 228 μs ± 22 μs+ Sequential ST Median3: OK+ 104 μs ± 6.1 μs, 0.45x+ Sequential IO Median3: OK+ 104 μs ± 6.0 μs, 0.46x+ ParStrategies ST Median3: OK+ 102 μs ± 5.6 μs, 0.45x+ ParStrategies IO Median3: OK+ 104 μs ± 5.6 μs, 0.46x+ Sequential ST Median3or5: OK+ 94.6 μs ± 5.7 μs, 0.41x+ Sequential IO Median3or5: OK+ 96.7 μs ± 5.5 μs, 0.42x+ ParStrategies ST Median3or5: OK+ 95.0 μs ± 5.6 μs, 0.42x+ ParStrategies IO Median3or5: OK+ 95.9 μs ± 5.9 μs, 0.42x+ Threads IO Median3: OK+ 104 μs ± 8.2 μs, 0.45x+ Threads IO Median3or5: OK+ 98.0 μs ± 5.5 μs, 0.43x+ fallback heapsort: OK+ 1.53 ms ± 97 μs, 6.70x+ Int64+ Sorting 10 random arrays of length 16 with few duplicates+ C++: OK+ 673 ns ± 65 ns+ Sequential ST Median3: OK+ 442 ns ± 21 ns, 0.66x+ Sequential IO Median3: OK+ 432 ns ± 37 ns, 0.64x+ ParStrategies ST Median3: OK+ 437 ns ± 38 ns, 0.65x+ ParStrategies IO Median3: OK+ 450 ns ± 21 ns, 0.67x+ Sequential ST Median3or5: OK+ 439 ns ± 7.4 ns, 0.65x+ Sequential IO Median3or5: OK+ 439 ns ± 26 ns, 0.65x+ ParStrategies ST Median3or5: OK+ 460 ns ± 43 ns, 0.68x+ ParStrategies IO Median3or5: OK+ 454 ns ± 35 ns, 0.67x+ Threads IO Median3: OK+ 1.23 μs ± 103 ns, 1.83x+ Threads IO Median3or5: OK+ 1.22 μs ± 95 ns, 1.81x+ fallback heapsort: OK+ 911 ns ± 66 ns, 1.35x+ Sorting 10 random arrays of length 17 with few duplicates+ C++: OK+ 688 ns ± 66 ns+ Sequential ST Median3: OK+ 561 ns ± 45 ns, 0.82x+ Sequential IO Median3: OK+ 566 ns ± 55 ns, 0.82x+ ParStrategies ST Median3: OK+ 690 ns ± 55 ns, 1.00x+ ParStrategies IO Median3: OK+ 679 ns ± 62 ns, 0.99x+ Sequential ST Median3or5: OK+ 588 ns ± 38 ns, 0.85x+ Sequential IO Median3or5: OK+ 590 ns ± 48 ns, 0.86x+ ParStrategies ST Median3or5: OK+ 646 ns ± 64 ns, 0.94x+ ParStrategies IO Median3or5: OK+ 645 ns ± 24 ns, 0.94x+ Threads IO Median3: OK+ 1.45 μs ± 133 ns, 2.11x+ Threads IO Median3or5: OK+ 1.40 μs ± 129 ns, 2.03x+ fallback heapsort: OK+ 989 ns ± 59 ns, 1.44x+ Sorting 10 random arrays of length 100 with few duplicates+ C++: OK+ 4.48 μs ± 368 ns+ Sequential ST Median3: OK+ 5.05 μs ± 444 ns, 1.13x+ Sequential IO Median3: OK+ 5.02 μs ± 367 ns, 1.12x+ ParStrategies ST Median3: OK+ 5.49 μs ± 464 ns, 1.23x+ ParStrategies IO Median3: OK+ 5.72 μs ± 171 ns, 1.28x+ Sequential ST Median3or5: OK+ 4.86 μs ± 485 ns, 1.08x+ Sequential IO Median3or5: OK+ 5.20 μs ± 350 ns, 1.16x+ ParStrategies ST Median3or5: OK+ 5.62 μs ± 442 ns, 1.25x+ ParStrategies IO Median3or5: OK+ 5.64 μs ± 473 ns, 1.26x+ Threads IO Median3: OK+ 6.15 μs ± 413 ns, 1.37x+ Threads IO Median3or5: OK+ 6.27 μs ± 217 ns, 1.40x+ fallback heapsort: OK+ 8.02 μs ± 409 ns, 1.79x+ Sorting 10 random arrays of length 256 with few duplicates+ C++: OK+ 14.9 μs ± 1.2 μs+ Sequential ST Median3: OK+ 16.5 μs ± 1.4 μs, 1.11x+ Sequential IO Median3: OK+ 16.5 μs ± 1.6 μs, 1.11x+ ParStrategies ST Median3: OK+ 17.4 μs ± 1.4 μs, 1.17x+ ParStrategies IO Median3: OK+ 18.1 μs ± 1.7 μs, 1.22x+ Sequential ST Median3or5: OK+ 15.6 μs ± 1.4 μs, 1.05x+ Sequential IO Median3or5: OK+ 16.4 μs ± 1.5 μs, 1.10x+ ParStrategies ST Median3or5: OK+ 17.4 μs ± 1.5 μs, 1.17x+ ParStrategies IO Median3or5: OK+ 18.2 μs ± 1.6 μs, 1.22x+ Threads IO Median3: OK+ 17.6 μs ± 1.7 μs, 1.18x+ Threads IO Median3or5: OK+ 18.1 μs ± 1.4 μs, 1.21x+ fallback heapsort: OK+ 24.8 μs ± 1.5 μs, 1.67x+ Sorting 10 random arrays of length 1,000 with few duplicates+ C++: OK+ 109 μs ± 5.4 μs+ Sequential ST Median3: OK+ 89.8 μs ± 2.7 μs, 0.83x+ Sequential IO Median3: OK+ 131 μs ± 7.5 μs, 1.21x+ ParStrategies ST Median3: OK+ 125 μs ± 11 μs, 1.15x+ ParStrategies IO Median3: OK+ 163 μs ± 15 μs, 1.50x+ Sequential ST Median3or5: OK+ 120 μs ± 2.6 μs, 1.10x+ Sequential IO Median3or5: OK+ 118 μs ± 4.2 μs, 1.09x+ ParStrategies ST Median3or5: OK+ 132 μs ± 6.4 μs, 1.22x+ ParStrategies IO Median3or5: OK+ 181 μs ± 18 μs, 1.67x+ Threads IO Median3: OK+ 126 μs ± 7.8 μs, 1.16x+ Threads IO Median3or5: OK+ 133 μs ± 11 μs, 1.23x+ fallback heapsort: OK+ 360 μs ± 26 μs, 3.31x+ Sorting 10 random arrays of length 10,000 with few duplicates+ C++: OK+ 3.02 ms ± 170 μs+ Sequential ST Median3: OK+ 3.69 ms ± 337 μs, 1.22x+ Sequential IO Median3: OK+ 3.64 ms ± 356 μs, 1.21x+ ParStrategies ST Median3: OK+ 3.73 ms ± 336 μs, 1.23x+ ParStrategies IO Median3: OK+ 3.87 ms ± 354 μs, 1.28x+ Sequential ST Median3or5: OK+ 3.63 ms ± 350 μs, 1.20x+ Sequential IO Median3or5: OK+ 3.64 ms ± 350 μs, 1.20x+ ParStrategies ST Median3or5: OK+ 3.76 ms ± 336 μs, 1.24x+ ParStrategies IO Median3or5: OK+ 3.80 ms ± 367 μs, 1.26x+ Threads IO Median3: OK+ 3.67 ms ± 339 μs, 1.21x+ Threads IO Median3or5: OK+ 3.68 ms ± 358 μs, 1.22x+ fallback heapsort: OK+ 5.09 ms ± 391 μs, 1.68x+ Sorting 10 random arrays of length 100,000 with few duplicates+ C++: OK+ 36.8 ms ± 1.6 ms+ Sequential ST Median3: OK+ 45.3 ms ± 3.4 ms, 1.23x+ Sequential IO Median3: OK+ 44.6 ms ± 2.8 ms, 1.21x+ ParStrategies ST Median3: OK+ 39.3 ms ± 2.6 ms, 1.07x+ ParStrategies IO Median3: OK+ 42.4 ms ± 3.8 ms, 1.15x+ Sequential ST Median3or5: OK+ 44.3 ms ± 2.7 ms, 1.20x+ Sequential IO Median3or5: OK+ 44.4 ms ± 2.8 ms, 1.21x+ ParStrategies ST Median3or5: OK+ 42.5 ms ± 3.5 ms, 1.15x+ ParStrategies IO Median3or5: OK+ 42.0 ms ± 2.7 ms, 1.14x+ Threads IO Median3: OK+ 27.6 ms ± 1.8 ms, 0.75x+ Threads IO Median3or5: OK+ 27.1 ms ± 2.1 ms, 0.74x+ fallback heapsort: OK+ 65.0 ms ± 2.9 ms, 1.77x+ Sorting 10 random arrays of length 1,000,000 with few duplicates+ C++: OK+ 449 ms ± 35 ms+ Sequential ST Median3: OK+ 544 ms ± 11 ms, 1.21x+ Sequential IO Median3: OK+ 540 ms ± 11 ms, 1.20x+ ParStrategies ST Median3: OK+ 191 ms ± 15 ms, 0.42x+ ParStrategies IO Median3: OK+ 193 ms ± 10 ms, 0.43x+ Sequential ST Median3or5: OK+ 535 ms ± 11 ms, 1.19x+ Sequential IO Median3or5: OK+ 537 ms ± 8.4 ms, 1.20x+ ParStrategies ST Median3or5: OK+ 190 ms ± 12 ms, 0.42x+ ParStrategies IO Median3or5: OK+ 197 ms ± 20 ms, 0.44x+ Threads IO Median3: OK+ 249 ms ± 16 ms, 0.55x+ Threads IO Median3or5: OK+ 245 ms ± 13 ms, 0.55x+ fallback heapsort: OK+ 851 ms ± 30 ms, 1.90x+ Sorting 10 random arrays of length 16 with many duplicates+ C++: OK+ 690 ns ± 22 ns+ Sequential ST Median3: OK+ 452 ns ± 33 ns, 0.66x+ Sequential IO Median3: OK+ 446 ns ± 43 ns, 0.65x+ ParStrategies ST Median3: OK+ 450 ns ± 42 ns, 0.65x+ ParStrategies IO Median3: OK+ 457 ns ± 29 ns, 0.66x+ Sequential ST Median3or5: OK+ 442 ns ± 42 ns, 0.64x+ Sequential IO Median3or5: OK+ 443 ns ± 42 ns, 0.64x+ ParStrategies ST Median3or5: OK+ 458 ns ± 45 ns, 0.66x+ ParStrategies IO Median3or5: OK+ 459 ns ± 43 ns, 0.67x+ Threads IO Median3: OK+ 1.23 μs ± 109 ns, 1.79x+ Threads IO Median3or5: OK+ 1.22 μs ± 92 ns, 1.77x+ fallback heapsort: OK+ 904 ns ± 52 ns, 1.31x+ Sorting 10 random arrays of length 17 with many duplicates+ C++: OK+ 689 ns ± 57 ns+ Sequential ST Median3: OK+ 593 ns ± 28 ns, 0.86x+ Sequential IO Median3: OK+ 603 ns ± 41 ns, 0.87x+ ParStrategies ST Median3: OK+ 656 ns ± 48 ns, 0.95x+ ParStrategies IO Median3: OK+ 724 ns ± 59 ns, 1.05x+ Sequential ST Median3or5: OK+ 599 ns ± 53 ns, 0.87x+ Sequential IO Median3or5: OK+ 606 ns ± 51 ns, 0.88x+ ParStrategies ST Median3or5: OK+ 657 ns ± 46 ns, 0.95x+ ParStrategies IO Median3or5: OK+ 664 ns ± 44 ns, 0.96x+ Threads IO Median3: OK+ 1.40 μs ± 92 ns, 2.02x+ Threads IO Median3or5: OK+ 1.39 μs ± 85 ns, 2.02x+ fallback heapsort: OK+ 985 ns ± 51 ns, 1.43x+ Sorting 10 random arrays of length 100 with many duplicates+ C++: OK+ 4.31 μs ± 357 ns+ Sequential ST Median3: OK+ 4.93 μs ± 361 ns, 1.15x+ Sequential IO Median3: OK+ 4.94 μs ± 390 ns, 1.15x+ ParStrategies ST Median3: OK+ 5.27 μs ± 416 ns, 1.22x+ ParStrategies IO Median3: OK+ 5.47 μs ± 363 ns, 1.27x+ Sequential ST Median3or5: OK+ 4.61 μs ± 436 ns, 1.07x+ Sequential IO Median3or5: OK+ 4.93 μs ± 419 ns, 1.15x+ ParStrategies ST Median3or5: OK+ 5.33 μs ± 329 ns, 1.24x+ ParStrategies IO Median3or5: OK+ 5.45 μs ± 352 ns, 1.27x+ Threads IO Median3: OK+ 5.79 μs ± 360 ns, 1.34x+ Threads IO Median3or5: OK+ 5.87 μs ± 384 ns, 1.36x+ fallback heapsort: OK+ 8.00 μs ± 331 ns, 1.86x+ Sorting 10 random arrays of length 256 with many duplicates+ C++: OK+ 15.1 μs ± 1.2 μs+ Sequential ST Median3: OK+ 16.9 μs ± 1.7 μs, 1.12x+ Sequential IO Median3: OK+ 17.0 μs ± 1.5 μs, 1.13x+ ParStrategies ST Median3: OK+ 17.9 μs ± 795 ns, 1.19x+ ParStrategies IO Median3: OK+ 18.4 μs ± 1.6 μs, 1.22x+ Sequential ST Median3or5: OK+ 15.6 μs ± 1.4 μs, 1.04x+ Sequential IO Median3or5: OK+ 16.7 μs ± 1.4 μs, 1.11x+ ParStrategies ST Median3or5: OK+ 17.8 μs ± 1.7 μs, 1.18x+ ParStrategies IO Median3or5: OK+ 18.6 μs ± 1.6 μs, 1.24x+ Threads IO Median3: OK+ 17.9 μs ± 670 ns, 1.19x+ Threads IO Median3or5: OK+ 18.7 μs ± 1.6 μs, 1.24x+ fallback heapsort: OK+ 24.9 μs ± 1.3 μs, 1.65x+ Sorting 10 random arrays of length 1,000 with many duplicates+ C++: OK+ 60.7 μs ± 1.3 μs+ Sequential ST Median3: OK+ 162 μs ± 3.1 μs, 2.67x+ Sequential IO Median3: OK+ 130 μs ± 4.7 μs, 2.13x+ ParStrategies ST Median3: OK+ 179 μs ± 7.1 μs, 2.94x+ ParStrategies IO Median3: OK+ 159 μs ± 3.8 μs, 2.62x+ Sequential ST Median3or5: OK+ 126 μs ± 12 μs, 2.07x+ Sequential IO Median3or5: OK+ 139 μs ± 7.3 μs, 2.29x+ ParStrategies ST Median3or5: OK+ 127 μs ± 8.9 μs, 2.09x+ ParStrategies IO Median3or5: OK+ 151 μs ± 6.1 μs, 2.49x+ Threads IO Median3: OK+ 86.0 μs ± 5.6 μs, 1.42x+ Threads IO Median3or5: OK+ 83.4 μs ± 7.7 μs, 1.37x+ fallback heapsort: OK+ 352 μs ± 25 μs, 5.80x+ Sorting 10 random arrays of length 10,000 with many duplicates+ C++: OK+ 2.69 ms ± 173 μs+ Sequential ST Median3: OK+ 3.09 ms ± 276 μs, 1.15x+ Sequential IO Median3: OK+ 2.98 ms ± 190 μs, 1.11x+ ParStrategies ST Median3: OK+ 3.06 ms ± 212 μs, 1.14x+ ParStrategies IO Median3: OK+ 3.19 ms ± 186 μs, 1.19x+ Sequential ST Median3or5: OK+ 3.02 ms ± 191 μs, 1.12x+ Sequential IO Median3or5: OK+ 3.01 ms ± 186 μs, 1.12x+ ParStrategies ST Median3or5: OK+ 3.11 ms ± 187 μs, 1.16x+ ParStrategies IO Median3or5: OK+ 3.14 ms ± 192 μs, 1.17x+ Threads IO Median3: OK+ 3.05 ms ± 171 μs, 1.14x+ Threads IO Median3or5: OK+ 3.08 ms ± 270 μs, 1.15x+ fallback heapsort: OK+ 4.97 ms ± 337 μs, 1.85x+ Sorting 10 random arrays of length 100,000 with many duplicates+ C++: OK+ 26.6 ms ± 1.4 ms+ Sequential ST Median3: OK+ 27.7 ms ± 1.3 ms, 1.04x+ Sequential IO Median3: OK+ 27.2 ms ± 1.4 ms, 1.02x+ ParStrategies ST Median3: OK+ 26.0 ms ± 1.1 ms, 0.98x+ ParStrategies IO Median3: OK+ 27.2 ms ± 2.5 ms, 1.02x+ Sequential ST Median3or5: OK+ 27.1 ms ± 1.6 ms, 1.02x+ Sequential IO Median3or5: OK+ 27.6 ms ± 1.9 ms, 1.04x+ ParStrategies ST Median3or5: OK+ 26.7 ms ± 2.1 ms, 1.00x+ ParStrategies IO Median3or5: OK+ 26.2 ms ± 2.1 ms, 0.98x+ Threads IO Median3: OK+ 18.2 ms ± 900 μs, 0.68x+ Threads IO Median3or5: OK+ 17.9 ms ± 1.3 ms, 0.67x+ fallback heapsort: OK+ 64.5 ms ± 2.8 ms, 2.42x+ Sorting 10 random arrays of length 1,000,000 with many duplicates+ C++: OK+ 281 ms ± 25 ms+ Sequential ST Median3: OK+ 274 ms ± 2.9 ms, 0.98x+ Sequential IO Median3: OK+ 269 ms ± 5.3 ms, 0.96x+ ParStrategies ST Median3: OK+ 189 ms ± 8.9 ms, 0.67x+ ParStrategies IO Median3: OK+ 194 ms ± 11 ms, 0.69x+ Sequential ST Median3or5: OK+ 263 ms ± 3.2 ms, 0.94x+ Sequential IO Median3or5: OK+ 266 ms ± 2.9 ms, 0.95x+ ParStrategies ST Median3or5: OK+ 188 ms ± 14 ms, 0.67x+ ParStrategies IO Median3or5: OK+ 194 ms ± 11 ms, 0.69x+ Threads IO Median3: OK+ 151 ms ± 7.5 ms, 0.54x+ Threads IO Median3or5: OK+ 147 ms ± 12 ms, 0.53x+ fallback heapsort: OK+ 784 ms ± 11 ms, 2.79x+ (Double, Double, Int64)+ Sorting 10 random arrays of length 16 with few duplicates+ Sanity: OK+ C++ single vector: OK+ 841 ns ± 57 ns+ C++ three vectors: OK+ 2.35 μs ± 176 ns+ Sequential ST Median3 Unbox: OK+ 1.34 μs ± 128 ns+ Sequential ST Median3or5 Unbox: OK+ 1.36 μs ± 91 ns+ Sequential ST Median3 Prim: OK+ 1.23 μs ± 103 ns+ Sequential ST Median3or5 Prim: OK+ 1.22 μs ± 112 ns+ Sorting 10 random arrays of length 17 with few duplicates+ Sanity: OK+ C++ single vector: OK+ 901 ns ± 26 ns+ C++ three vectors: OK+ 2.60 μs ± 207 ns+ Sequential ST Median3 Unbox: OK+ 1.59 μs ± 126 ns+ Sequential ST Median3or5 Unbox: OK+ 1.70 μs ± 167 ns+ Sequential ST Median3 Prim: OK+ 1.44 μs ± 103 ns+ Sequential ST Median3or5 Prim: OK+ 1.46 μs ± 113 ns+ Sorting 10 random arrays of length 100 with few duplicates+ Sanity: OK+ C++ single vector: OK+ 7.72 μs ± 581 ns+ C++ three vectors: OK+ 14.5 μs ± 1.1 μs+ Sequential ST Median3 Unbox: OK+ 10.4 μs ± 959 ns+ Sequential ST Median3or5 Unbox: OK+ 10.2 μs ± 745 ns+ Sequential ST Median3 Prim: OK+ 12.3 μs ± 809 ns+ Sequential ST Median3or5 Prim: OK+ 12.5 μs ± 795 ns+ Sorting 10 random arrays of length 256 with few duplicates+ Sanity: OK+ C++ single vector: OK+ 14.6 μs ± 682 ns+ C++ three vectors: OK+ 42.7 μs ± 4.2 μs+ Sequential ST Median3 Unbox: OK+ 34.3 μs ± 1.7 μs+ Sequential ST Median3or5 Unbox: OK+ 33.5 μs ± 1.4 μs+ Sequential ST Median3 Prim: OK+ 30.7 μs ± 2.6 μs+ Sequential ST Median3or5 Prim: OK+ 32.0 μs ± 2.1 μs+ Sorting 10 random arrays of length 1,000 with few duplicates+ Sanity: OK+ C++ single vector: OK+ 69.4 μs ± 4.4 μs+ C++ three vectors: OK+ 212 μs ± 16 μs+ Sequential ST Median3 Unbox: OK+ 265 μs ± 23 μs+ Sequential ST Median3or5 Unbox: OK+ 294 μs ± 26 μs+ Sequential ST Median3 Prim: OK+ 299 μs ± 27 μs+ Sequential ST Median3or5 Prim: OK+ 305 μs ± 23 μs+ Sorting 10 random arrays of length 10,000 with few duplicates+ Sanity: OK+ C++ single vector: OK+ 3.27 ms ± 195 μs+ C++ three vectors: OK+ 3.62 ms ± 352 μs+ Sequential ST Median3 Unbox: OK+ 5.11 ms ± 338 μs+ Sequential ST Median3or5 Unbox: OK+ 5.17 ms ± 398 μs+ Sequential ST Median3 Prim: OK+ 5.70 ms ± 369 μs+ Sequential ST Median3or5 Prim: OK+ 5.64 ms ± 370 μs+ Sorting 10 random arrays of length 100,000 with few duplicates+ Sanity: OK+ C++ single vector: OK+ 40.7 ms ± 1.6 ms+ C++ three vectors: OK+ 43.8 ms ± 1.4 ms+ Sequential ST Median3 Unbox: OK+ 62.2 ms ± 2.7 ms+ Sequential ST Median3or5 Unbox: OK+ 62.9 ms ± 3.0 ms+ Sequential ST Median3 Prim: OK+ 70.7 ms ± 1.8 ms+ Sequential ST Median3or5 Prim: OK+ 69.7 ms ± 3.4 ms+ Sorting 10 random arrays of length 1,000,000 with few duplicates+ Sanity: OK+ C++ single vector: OK+ 510 ms ± 3.0 ms+ C++ three vectors: OK+ 542 ms ± 18 ms+ Sequential ST Median3 Unbox: OK+ 752 ms ± 14 ms+ Sequential ST Median3or5 Unbox: OK+ 757 ms ± 35 ms+ Sequential ST Median3 Prim: OK+ 848 ms ± 73 ms+ Sequential ST Median3or5 Prim: OK+ 823 ms ± 20 ms+ Sorting 10 random arrays of length 16 with many duplicates+ Sanity: OK+ C++ single vector: OK+ 876 ns ± 54 ns+ C++ three vectors: OK+ 2.40 μs ± 181 ns+ Sequential ST Median3 Unbox: OK+ 1.45 μs ± 132 ns+ Sequential ST Median3or5 Unbox: OK+ 1.44 μs ± 115 ns+ Sequential ST Median3 Prim: OK+ 1.39 μs ± 102 ns+ Sequential ST Median3or5 Prim: OK+ 1.41 μs ± 94 ns+ Sorting 10 random arrays of length 17 with many duplicates+ Sanity: OK+ C++ single vector: OK+ 889 ns ± 57 ns+ C++ three vectors: OK+ 2.63 μs ± 181 ns+ Sequential ST Median3 Unbox: OK+ 1.64 μs ± 120 ns+ Sequential ST Median3or5 Unbox: OK+ 1.65 μs ± 130 ns+ Sequential ST Median3 Prim: OK+ 1.47 μs ± 107 ns+ Sequential ST Median3or5 Prim: OK+ 1.47 μs ± 119 ns+ Sorting 10 random arrays of length 100 with many duplicates+ Sanity: OK+ C++ single vector: OK+ 7.62 μs ± 597 ns+ C++ three vectors: OK+ 13.8 μs ± 693 ns+ Sequential ST Median3 Unbox: OK+ 10.8 μs ± 790 ns+ Sequential ST Median3or5 Unbox: OK+ 10.5 μs ± 839 ns+ Sequential ST Median3 Prim: OK+ 12.7 μs ± 814 ns+ Sequential ST Median3or5 Prim: OK+ 12.9 μs ± 910 ns+ Sorting 10 random arrays of length 256 with many duplicates+ Sanity: OK+ C++ single vector: OK+ 14.8 μs ± 978 ns+ C++ three vectors: OK+ 38.7 μs ± 2.7 μs+ Sequential ST Median3 Unbox: OK+ 34.0 μs ± 3.4 μs+ Sequential ST Median3or5 Unbox: OK+ 34.0 μs ± 3.0 μs+ Sequential ST Median3 Prim: OK+ 31.6 μs ± 3.1 μs+ Sequential ST Median3or5 Prim: OK+ 32.5 μs ± 2.3 μs+ Sorting 10 random arrays of length 1,000 with many duplicates+ Sanity: OK+ C++ single vector: OK+ 69.2 μs ± 4.9 μs+ C++ three vectors: OK+ 151 μs ± 11 μs+ Sequential ST Median3 Unbox: OK+ 256 μs ± 17 μs+ Sequential ST Median3or5 Unbox: OK+ 291 μs ± 15 μs+ Sequential ST Median3 Prim: OK+ 303 μs ± 26 μs+ Sequential ST Median3or5 Prim: OK+ 292 μs ± 7.8 μs+ Sorting 10 random arrays of length 10,000 with many duplicates+ Sanity: OK+ C++ single vector: OK+ 2.98 ms ± 193 μs+ C++ three vectors: OK+ 3.48 ms ± 182 μs+ Sequential ST Median3 Unbox: OK+ 4.30 ms ± 345 μs+ Sequential ST Median3or5 Unbox: OK+ 4.50 ms ± 446 μs+ Sequential ST Median3 Prim: OK+ 4.80 ms ± 339 μs+ Sequential ST Median3or5 Prim: OK+ 4.87 ms ± 407 μs+ Sorting 10 random arrays of length 100,000 with many duplicates+ Sanity: OK+ C++ single vector: OK+ 30.2 ms ± 1.8 ms+ C++ three vectors: OK+ 41.1 ms ± 1.8 ms+ Sequential ST Median3 Unbox: OK+ 40.8 ms ± 1.9 ms+ Sequential ST Median3or5 Unbox: OK+ 41.6 ms ± 1.7 ms+ Sequential ST Median3 Prim: OK+ 43.7 ms ± 1.5 ms+ Sequential ST Median3or5 Prim: OK+ 43.6 ms ± 3.0 ms+ Sorting 10 random arrays of length 1,000,000 with many duplicates+ Sanity: OK+ C++ single vector: OK+ 337 ms ± 11 ms+ C++ three vectors: OK+ 420 ms ± 5.0 ms+ Sequential ST Median3 Unbox: OK+ 389 ms ± 3.3 ms+ Sequential ST Median3or5 Unbox: OK+ 398 ms ± 3.4 ms+ Sequential ST Median3 Prim: OK+ 452 ms ± 27 ms+ Sequential ST Median3or5 Prim: OK+ 428 ms ± 2.9 ms+ ```
bench/BenchMain.hs view
@@ -12,7 +12,7 @@ {-# OPTIONS_GHC -Wno-orphans #-} -module BenchmarkMain (main) where+module BenchMain (main) where import Prelude hiding (pi, last) @@ -22,8 +22,9 @@ import Control.Monad import Control.Monad.ST import Data.ByteString.Char8 qualified as C8+import Data.Coerce+import Data.Foldable import Data.Int-import Data.Ord import Data.Text (Text) import Data.Text qualified as T import Data.Text.Builder.Linear qualified as TBL@@ -33,11 +34,20 @@ import Data.Vector.Primitive.Mutable qualified as PM import Data.Vector.Storable qualified as S import Data.Vector.Storable.Mutable qualified as SM+import Data.Vector.Unboxed qualified as U+import Data.Vector.Unboxed.Mutable qualified as UM+import Data.Word import Foreign.C.Types+import System.Exit import System.Random.Stateful +import Test.Tasty import Test.Tasty.Bench+import Test.Tasty.HUnit+import Test.Tasty.Ingredients.ConsoleReporter (MinDurationToReport(MinDurationToReport))+import Test.Tasty.Options import Test.Tasty.Patterns.Printer (printAwkExpr)+import Test.Tasty.Runners import ForeignSorting @@ -47,7 +57,6 @@ import Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelStrategiesMedian3ST import Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelStrategiesMedian3or5IO import Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelStrategiesMedian3or5ST-import Data.Vector.Algorithms.Quicksort.Predefined.PIntSequentialAveragingMedianST import Data.Vector.Algorithms.Quicksort.Predefined.PIntSequentialMedian3IO import Data.Vector.Algorithms.Quicksort.Predefined.PIntSequentialMedian3ST import Data.Vector.Algorithms.Quicksort.Predefined.PIntSequentialMedian3or5IO@@ -56,13 +65,12 @@ import Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelMedian3IO import Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelMedian3or5IO -newtype SortKey v = SortKey { _unSortKey :: (Int32, Int, v) } -instance Eq (SortKey v) where- SortKey (a, b, _) == SortKey (a', b', _) = a == a' && b == b'--instance Ord (SortKey v) where- SortKey (a, b, _) `compare` SortKey (a', b', _) = Down a `compare` Down a' <> b `compare` b'+import Data.Vector.Algorithms.Quicksort.Predefined.SortTriple+import Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3ST+import Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3or5ST+import Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3ST+import Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3or5ST {-# NOINLINE qsortSeq3 #-} qsortSeq3 :: P.Vector Int64 -> ST s (PM.MVector s Int64)@@ -99,13 +107,6 @@ sortPIntSequentialMedian3or5ST ys pure ys -{-# NOINLINE qsortSeqAvgST #-}-qsortSeqAvgST :: P.Vector Int64 -> ST s (PM.MVector s Int64)-qsortSeqAvgST xs = do- ys <- P.thaw xs- sortPIntSequentialAveragingMedianST ys- pure ys- {-# NOINLINE qsortSeq3or5IO #-} qsortSeq3or5IO :: P.Vector Int64 -> IO (PM.MVector RealWorld Int64) qsortSeq3or5IO xs = do@@ -162,6 +163,68 @@ SM.unsafeWith ys $ \ptr -> cppSortInt64 ptr (CInt (fromIntegral (SM.length ys))) pure ys +{-# NOINLINE cppStorableTriple #-}+cppStorableTriple :: S.Vector CPoint -> IO (SM.MVector RealWorld CPoint)+cppStorableTriple xs = do+ ys <- S.thaw xs+ SM.unsafeWith ys $ \ptr -> cppSortCPoint ptr (CInt (fromIntegral (SM.length ys)))+ pure ys++{-# NOINLINE cppStorableTripleUnpacked #-}+cppStorableTripleUnpacked+ :: (S.Vector CDouble, S.Vector CDouble, S.Vector Word64)+ -> IO (SM.MVector RealWorld CDouble, SM.MVector RealWorld CDouble, SM.MVector RealWorld Word64)+cppStorableTripleUnpacked (as, bs, cs) = do+ as' <- S.thaw as+ bs' <- S.thaw bs+ cs' <- S.thaw cs+ SM.unsafeWith as' $ \as'' ->+ SM.unsafeWith bs' $ \bs'' ->+ SM.unsafeWith cs' $ \cs'' -> cppSortCPointUnboxed as'' bs'' cs'' (CInt (fromIntegral (SM.length as')))+ pure (as', bs', cs')++{-# NOINLINE qsortSeq3STTripleUnbox #-}+qsortSeq3STTripleUnbox+ :: forall s.+ U.Vector (Double, Double, Word64)+ -> ST s (UM.MVector s (Double, Double, Word64))+qsortSeq3STTripleUnbox xs = do+ (ys :: UM.MVector s (Double, Double, Word64)) <- U.thaw xs+ sortUTripleSequentialMedian3ST (coerce ys :: UM.MVector s SortTriple)+ pure ys++{-# NOINLINE qsortSeq3or5STTripleUnbox #-}+qsortSeq3or5STTripleUnbox+ :: forall s.+ U.Vector (Double, Double, Word64)+ -> ST s (UM.MVector s (Double, Double, Word64))+qsortSeq3or5STTripleUnbox xs = do+ (ys :: UM.MVector s (Double, Double, Word64)) <- U.thaw xs+ sortUTripleSequentialMedian3or5ST (coerce ys :: UM.MVector s SortTriple)+ pure ys+++{-# NOINLINE qsortSeq3STTriplePrim #-}+qsortSeq3STTriplePrim+ :: forall s.+ P.Vector SortTriple+ -> ST s (PM.MVector s SortTriple)+qsortSeq3STTriplePrim xs = do+ (ys :: PM.MVector s SortTriple) <- P.thaw xs+ sortPTripleSequentialMedian3ST ys+ pure ys++{-# NOINLINE qsortSeq3or5STTriplePrim #-}+qsortSeq3or5STTriplePrim+ :: forall s.+ P.Vector SortTriple+ -> ST s (PM.MVector s SortTriple)+qsortSeq3or5STTriplePrim xs = do+ (ys :: PM.MVector s SortTriple) <- P.thaw xs+ sortPTripleSequentialMedian3or5ST ys+ pure ys++ main :: IO () main = do (fuzzyMatchScores :: P.Vector Int64) <-@@ -169,38 +232,77 @@ putStrLn $ "P.length fuzzyMatchScores = " ++ show (P.length fuzzyMatchScores) - let generate :: Int -> Int -> IOGenM StdGen -> IO (P.Vector Int64)- generate n k g = P.fromList <$> replicateM n (uniformRM (1 :: Int64, fromIntegral k) g)+ let generateInt64 :: Int -> Int -> IOGenM StdGen -> IO (P.Vector Int64)+ generateInt64 n k g = P.replicateM n (uniformRM (1 :: Int64, fromIntegral k) g) + let generateTriple :: Int -> Int -> IOGenM StdGen -> IO (U.Vector (Double, Double, Word64))+ generateTriple n k g =+ U.replicateM n $+ (,,)+ <$> uniformDouble01M g+ <*> uniformDouble01M g+ <*> uniformRM (1 :: Word64, fromIntegral k) g+ gen <- newIOGenM $ mkStdGen 1 let sizes :: [(Int, Int)]- sizes = map (10, ) [16, 17, 100, 256, 1000, 10_000, 100_000, 1_000_000, 10_000_000]+ sizes = map (10, ) [16, 17, 100, 256, 1000, 10_000, 100_000, 1_000_000] -- [, 10_000_000] - xsssNoDup <- traverse (\(n, k) -> replicateM n $ generate k k gen) sizes- xsssDup <- traverse (\(n, k) -> replicateM n $ generate k (max 1000 (k `quot` 1000)) gen) sizes+ (xsssNoDup :: [[P.Vector Int64]]) <- traverse (\(n, k) -> replicateM n $ generateInt64 k k gen) sizes+ (xsssDup :: [[P.Vector Int64]]) <- traverse (\(n, k) -> replicateM n $ generateInt64 k (max 1000 (k `quot` 1000)) gen) sizes + (ysssNoDup :: [[U.Vector (Double, Double, Word64)]]) <- traverse (\(n, k) -> replicateM n $ generateTriple k k gen) sizes+ (ysssDup :: [[U.Vector (Double, Double, Word64)]]) <- traverse (\(n, k) -> replicateM n $ generateTriple k (max 1000 (k `quot` 1000)) gen) sizes+ evaluate $ rnf xsssNoDup evaluate $ rnf xsssDup+ evaluate $ rnf ysssNoDup+ evaluate $ rnf ysssDup - defaultMain $- [ mkBenches "Sorting fuzzy matching scores vector" (MkSolo fuzzyMatchScores)- ] ++- [ mkBenches ("Sorting " ++ show (length xss) ++ " random arrays of length " ++ T.unpack (formatNumber (P.length (head xss))) ++ " with few duplicates") xss- | xss <- xsssNoDup- ] ++- [ mkBenches ("Sorting " ++ show (length xss) ++ " random arrays of length " ++ T.unpack (formatNumber (P.length (head xss))) ++ " with many duplicates") xss- | xss <- xsssDup- ]+ let ingredients = benchIngredients + let benchmark = bgroup "All" $ map (localOption WallTime) $+ [ mkBenchesInt64 "Sorting fuzzy matching scores vector" (MkSolo fuzzyMatchScores)+ ] +++ [ bgroup "Int64" $+ [ mkBenchesInt64 ("Sorting " ++ show (length xss) ++ " random arrays of length " ++ T.unpack (formatNumber (P.length (head' xss))) ++ " with few duplicates") xss+ | xss <- xsssNoDup+ ] +++ [ mkBenchesInt64 ("Sorting " ++ show (length xss) ++ " random arrays of length " ++ T.unpack (formatNumber (P.length (head' xss))) ++ " with many duplicates") xss+ | xss <- xsssDup+ ]+ , bgroup "(Double, Double, Int64)" $+ [ mkBenchesTriple ("Sorting " ++ show (length yss) ++ " random arrays of length " ++ T.unpack (formatNumber (U.length (head' yss))) ++ " with few duplicates") yss+ | yss <- ysssNoDup+ ] +++ [ mkBenchesTriple ("Sorting " ++ show (length yss) ++ " random arrays of length " ++ T.unpack (formatNumber (U.length (head' yss))) ++ " with many duplicates") yss+ | yss <- ysssDup+ ]+ ]++ installSignalHandlers+ opts <- parseOptions ingredients benchmark+ let opts' = setOption (MinDurationToReport 1000000000000) $ setOption (NumThreads 1) opts++ case tryIngredients ingredients opts' benchmark of+ Nothing -> die+ "No ingredients agreed to run. Something is wrong either with your ingredient set or the options."+ Just act -> do+ ok <- act+ if ok then exitSuccess else exitFailure++head' :: [a] -> a+head' (x:_) = x+head' [] = error "oops, empty head"+ instance NFData (TVar a) where rnf x = x `seq` () -{-# INLINE mkBenches #-}-mkBenches+{-# INLINE mkBenchesInt64 #-}+mkBenchesInt64 :: forall f. (Traversable f, forall a. NFData a => NFData (f a)) => String -> f (P.Vector Int64) -> Benchmark-mkBenches name xssPrim = mapLeafBenchmarks addCompare $ bgroup name- [ bench cppBenchName $ nfAppIO (traverse cppUnboxedInt64) xsStorable+mkBenchesInt64 name xssPrim = mapLeafBenchmarks addCompare $ bgroup name+ [ bench cppBenchName $ nfAppIO (traverse cppUnboxedInt64) xssStorable , bench "Sequential ST Median3" $ nfAppIO (stToIO . traverse qsortSeq3) xssPrim , bench "Sequential IO Median3" $ nfAppIO (traverse qsortSeqIO3) xssPrim@@ -212,8 +314,6 @@ , bench "ParStrategies ST Median3or5" $ nfAppIO (stToIO . traverse qsortParStrategies3or5ST) xssPrim , bench "ParStrategies IO Median3or5" $ nfAppIO (traverse qsortParStrategies3or5IO) xssPrim - , bench "Sequential ST AveragingMedian" $ nfAppIO (stToIO . traverse qsortSeqAvgST) xssPrim- , bench "Threads IO Median3" $ nfAppIO (traverse qsortParallel3IO) xssPrim , bench "Threads IO Median3or5" $ nfAppIO (traverse qsortParallel3or5IO) xssPrim @@ -221,8 +321,76 @@ , bench "fallback heapsort" $ nfAppIO (stToIO . traverse fallbackHeapsortInt64) xssPrim ] where- xsStorable :: f (S.Vector Int64)- xsStorable = P.convert <$> xssPrim+ xssStorable :: f (S.Vector Int64)+ xssStorable = P.convert <$> xssPrim++isSorted :: Ord a => [a] -> Bool+isSorted = \case+ [] -> True+ x : xs -> go x xs+ where+ go _ [] = True+ go x (y : ys) = x <= y && go y ys++assertSorted :: (Show a, Ord a) => String -> [a] -> IO ()+assertSorted label xs =+ assertBool (label ++ " not sorted: " ++ show xs) $ isSorted xs++{-# INLINE mkBenchesTriple #-}+mkBenchesTriple+ :: forall f. (Traversable f, forall a. NFData a => NFData (f a))+ => String -> f (U.Vector (Double, Double, Word64)) -> Benchmark+mkBenchesTriple name xssUnbox = bgroup name+ [ testCase "Sanity" $+ for_ xssUnbox $ \xs -> do+ xsUnboxed <- U.unsafeFreeze =<< stToIO (qsortSeq3STTripleUnbox xs)+ xsStorable <- S.unsafeFreeze =<< cppStorableTriple (mkStorable xs)+ xsUnpacked <-+ (\(a, b, c) -> (,,) <$> S.unsafeFreeze a <*> S.unsafeFreeze b <*> S.unsafeFreeze c) =<<+ cppStorableTripleUnpacked (mkUnpacked xs)+ xsPrim <- P.unsafeFreeze =<< stToIO (qsortSeq3STTriplePrim (mkPrim xs))+ assertSorted "Unboxed" $ map (\(_, _, c) -> c) $ U.toList xsUnboxed+ assertSorted "Storabale" $ map (\(CPoint _ _ z) -> z) $ S.toList xsStorable+ assertSorted "Unpacked" $ S.toList $ (\(_, _, c) -> c) xsUnpacked+ assertSorted "Prim" $ map (\(SortTriple _ _ c) -> c) $ P.toList $ xsPrim++ , bench "C++ single vector" $ nfAppIO (traverse cppStorableTriple) xssStorable+ , bench "C++ three vectors" $ nfAppIO (traverse cppStorableTripleUnpacked) xssUnpacked++ , bench "Sequential ST Median3 Unbox" $ nfAppIO (stToIO . traverse qsortSeq3STTripleUnbox) xssUnbox+ , bench "Sequential ST Median3or5 Unbox" $ nfAppIO (stToIO . traverse qsortSeq3or5STTripleUnbox) xssUnbox++ , bench "Sequential ST Median3 Prim" $ nfAppIO (stToIO . traverse qsortSeq3STTriplePrim) xssPrim+ , bench "Sequential ST Median3or5 Prim" $ nfAppIO (stToIO . traverse qsortSeq3or5STTriplePrim) xssPrim+ ]+ where+ mkStorable+ :: U.Vector (Double, Double, Word64)+ -> S.Vector CPoint+ mkStorable = S.fromList . map (\(a, b, c) -> CPoint (CDouble a) (CDouble b) c) . U.toList++ mkPrim+ :: U.Vector (Double, Double, Word64)+ -> P.Vector SortTriple+ mkPrim = U.convert . U.map (\(a, b, c) -> SortTriple a b c)++ mkUnpacked+ :: U.Vector (Double, Double, Word64)+ -> (S.Vector CDouble, S.Vector CDouble, S.Vector Word64)+ mkUnpacked xs =+ ( S.fromList . map (\(a, _, _) -> CDouble a) . U.toList $ xs+ , S.fromList . map (\(_, b, _) -> CDouble b) . U.toList $ xs+ , U.convert . U.map (\(_, _, c) -> c) $ xs+ )++ xssStorable :: f (S.Vector CPoint)+ xssStorable = mkStorable <$> xssUnbox++ xssUnpacked :: f (S.Vector CDouble, S.Vector CDouble, S.Vector Word64)+ xssUnpacked = mkUnpacked <$> xssUnbox++ xssPrim :: f (P.Vector SortTriple)+ xssPrim = mkPrim <$> xssUnbox cppBenchName :: String cppBenchName = "C++"
− bench/ForeignSorting.hs
@@ -1,18 +0,0 @@--- |--- Module: ForeignSorting--- Copyright: (c) Sergey Vinokurov 2023--- License: Apache-2.0 (see LICENSE)--- Maintainer: serg.foo@gmail.com--module ForeignSorting- ( cppSortInt64- ) where--import Data.Int-import Foreign-import Foreign.C.Types--foreign import ccall unsafe "cplusplus_sort" cppSortInt64- :: Ptr Int64- -> CInt- -> IO ()
+ bench/ForeignSorting.hsc view
@@ -0,0 +1,56 @@+-- |+-- Module: ForeignSorting+-- Copyright: (c) Sergey Vinokurov 2023+-- License: Apache-2.0 (see LICENSE)+-- Maintainer: serg.foo@gmail.com++{-# LANGUAGE ForeignFunctionInterface #-}++module ForeignSorting+ ( cppSortInt64+ , cppSortCPoint+ , cppSortCPointUnboxed+ , CPoint(..)+ ) where++import Data.Int+import Data.Word+import Foreign+import Foreign.C.Types++#include <sort.h>++foreign import ccall unsafe "cplusplus_sort_int64" cppSortInt64+ :: Ptr Int64+ -> CInt+ -> IO ()++data CPoint = CPoint !CDouble !CDouble !Word64+ deriving (Eq, Show)++++instance Storable CPoint where+ sizeOf _ = (#size struct Point)+ alignment _ = (#alignment struct Point)+ peek p =+ CPoint+ <$> (#peek struct Point, x) p+ <*> (#peek struct Point, y) p+ <*> (#peek struct Point, id) p+ poke p (CPoint x y n) = do+ (#poke struct Point, x) p x+ (#poke struct Point, y) p y+ (#poke struct Point, id) p n++foreign import ccall unsafe "cplusplus_sort_point" cppSortCPoint+ :: Ptr CPoint+ -> CInt+ -> IO ()++foreign import ccall unsafe "cplusplus_sort_point_unboxed" cppSortCPointUnboxed+ :: Ptr CDouble+ -> Ptr CDouble+ -> Ptr Word64+ -> CInt+ -> IO ()
cbits/sort.cpp view
@@ -1,8 +1,178 @@ #include <algorithm> #include <cstdint>+#include <iterator> +#include <sort.h>++inline bool operator<(Point x, Point y) {+ return x.id < y.id;+}++namespace std {++namespace sort_helper {++template <typename _Data1, typename _Data2, typename _Order>+struct value_reference_t;++template <typename _Data1, typename _Data2, typename _Order>+struct value_t {+ _Data1 data1;+ _Data2 data2;+ _Order val;+ inline value_t(_Data1 _data1, _Data2 _data2, _Order _val) : data1(_data1), data2(_data2), val(_val) {}+ inline value_t(const value_reference_t<_Data1, _Data2, _Order>& rhs);++ inline bool operator < (const value_t<_Data1, _Data2, _Order>& rhs) const { return val < rhs.val; }+};++template <typename _Data1, typename _Data2, typename _Order>+struct value_reference_t {+ _Data1* pdata1;+ _Data2* pdata2;+ _Order* pval;+ value_reference_t(_Data1* _itData1, _Data2* _itData2, _Order* _itVal)+ : pdata1(_itData1)+ , pdata2(_itData2)+ , pval(_itVal)+ {}+ inline value_reference_t& operator = (const value_reference_t& rhs) {+ *pdata1 = *rhs.pdata1;+ *pdata2 = *rhs.pdata2;+ *pval = *rhs.pval;+ return *this;+ }+ inline value_reference_t& operator = (const value_t<_Data1, _Data2, _Order>& rhs) {+ *pdata1 = rhs.data1;+ *pdata2 = rhs.data2;+ *pval = rhs.val;+ return *this;+ }+ inline bool operator < (const value_reference_t& rhs) { return *pval < *rhs.pval; }+};++template <typename _Data1, typename _Data2, typename _Order>+struct value_iterator_t :+ std::iterator<+ random_access_iterator_tag,+ value_t<_Data1, _Data2, _Order>,+ ptrdiff_t,+ value_t<_Data1, _Data2, _Order>*,+ value_reference_t<_Data1, _Data2, _Order>+ >+{+ _Data1* itData1;+ _Data2* itData2;+ _Order* itVal;++ value_iterator_t(_Data1* _itData1, _Data2* _itData2, _Order* _itVal)+ : itData1(_itData1)+ , itData2(_itData2)+ , itVal(_itVal)+ {}++ inline ptrdiff_t operator - (const value_iterator_t& rhs) const { return itVal - rhs.itVal; }+ inline value_iterator_t operator + (ptrdiff_t off) const {+ return value_iterator_t(itData1 + off, itData2 + off, itVal + off);+ }+ inline value_iterator_t operator - (ptrdiff_t off) const {+ return value_iterator_t(itData1 - off, itData2 - off, itVal - off);+ }++ inline value_iterator_t& operator += (ptrdiff_t off) {+ itData1 += off;+ itData2 += off;+ itVal += off;+ return *this;+ }+ inline value_iterator_t& operator -= (ptrdiff_t off) {+ itData1 -= off;+ itData2 -= off;+ itVal -= off;+ return *this;+ }++ inline value_iterator_t& operator ++ () { ++itData1; ++itData2; ++itVal; return *this; }+ inline value_iterator_t& operator -- () { --itData1; --itData2; --itVal; return *this; }+ inline value_iterator_t operator ++ (int) { return value_iterator_t(itData1++, itData2++, itVal++); }+ inline value_iterator_t operator -- (int) { return value_iterator_t(itData1--, itData2--, itVal--); }+ inline value_t<_Data1, _Data2, _Order> operator * () const {+ return value_t<_Data1, _Data2, _Order>(*itData1, *itData2, *itVal);+ }+ inline value_reference_t<_Data1, _Data2, _Order> operator * () {+ return value_reference_t<_Data1, _Data2, _Order>(itData1, itData2, itVal);+ }++ inline bool operator < (const value_iterator_t& rhs) const { return itVal < rhs.itVal; }+ inline bool operator <= (const value_iterator_t& rhs) const { return itVal <= rhs.itVal; }+ inline bool operator > (const value_iterator_t& rhs) const { return itVal > rhs.itVal; }+ inline bool operator >= (const value_iterator_t& rhs) const { return itVal >= rhs.itVal; }+ inline bool operator == (const value_iterator_t& rhs) const { return itVal == rhs.itVal; }+ inline bool operator != (const value_iterator_t& rhs) const { return itVal != rhs.itVal; }+};++template <typename _Data1, typename _Data2, typename _Order>+inline value_t<_Data1, _Data2, _Order>::value_t(const value_reference_t<_Data1, _Data2, _Order>& rhs)+ : data1(*rhs.pdata1), data2(*rhs.pdata2), val(*rhs.pval) {}++template <typename _Data1, typename _Data2, typename _Order>+bool operator < (+ const value_t<_Data1, _Data2, _Order>& lhs,+ const value_reference_t<_Data1, _Data2, _Order>& rhs+ )+{+ return lhs.val < *rhs.pval;+}++template <typename _Data1, typename _Data2, typename _Order>+bool operator < (+ const value_reference_t<_Data1, _Data2, _Order>& lhs,+ const value_t<_Data1, _Data2, _Order>& rhs+ )+{+ return *lhs.pval < rhs.val;+}++template <typename _Data1, typename _Data2, typename _Order>+bool operator < (+ const value_reference_t<_Data1, _Data2, _Order>& lhs,+ const value_reference_t<_Data1, _Data2, _Order>& rhs+ )+{+ return *lhs.pval < *rhs.pval;+}++template <typename _Data1, typename _Data2, typename _Order>+void swap(+ value_reference_t<_Data1, _Data2, _Order> lhs,+ value_reference_t<_Data1, _Data2, _Order> rhs+ )+{+ std::swap(*lhs.pdata1, *rhs.pdata1);+ std::swap(*lhs.pdata2, *rhs.pdata2);+ std::swap(*lhs.pval, *rhs.pval);+}+++} // namespace sort_helper++} // namespace std+ extern "C" {- void cplusplus_sort(int64_t* xs, int len) {++ void cplusplus_sort_int64(int64_t* xs, int len) { std::sort(xs, xs + len); }++ void cplusplus_sort_point(Point* xs, int len) {+ std::sort(xs, xs + len);+ }++ void cplusplus_sort_point_unboxed(double* xs, double* ys, uint64_t* ids, int len) {+ typedef std::sort_helper::value_iterator_t<double, double, uint64_t> PointIterator;++ PointIterator i = PointIterator(xs, ys, ids);+ std::sort(i, i + len);+ }+ }
+ cbits/sort.h view
@@ -0,0 +1,14 @@+#ifndef SORT_H_+#define SORT_H_ 1++/* Created: 14 June 2023 */++#include <stdint.h>++struct Point {+ double x;+ double y;+ uint64_t id;+};++#endif /* #ifndef SORT_H_ */
− src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/AveragingMedian.hs
@@ -1,68 +0,0 @@--- |--- Module: Data.Vector.Algorithms.Quicksort.Predefined.AveragingMedian--- Copyright: (c) Sergey Vinokurov 2023--- License: Apache-2.0 (see LICENSE)--- Maintainer: serg.foo@gmail.com--{-# LANGUAGE TypeFamilies #-}-{-# LANGUAGE UndecidableInstances #-}--module Data.Vector.Algorithms.Quicksort.Predefined.AveragingMedian- ( AveragingMedian(..)- ) where--import Control.Monad.Primitive-import Data.Bits-import Data.Int-import Data.Kind-import Data.Vector.Generic.Mutable qualified as GM--import Data.Vector.Algorithms.Quicksort.Median-import Data.Vector.Algorithms.Quicksort.Predefined.Pair--data AveragingMedian a = AveragingMedian--instance (PrimMonad m, s ~ PrimState m) => Median (AveragingMedian Int64) Int64 m s where- {-# INLINE selectMedian #-}- selectMedian- :: forall (v :: Type -> Type -> Type).- GM.MVector v Int64- => AveragingMedian Int64- -> v s Int64- -> m (MedianResult Int64)- selectMedian _ !v = do- let len :: Int- !len = GM.length v- pi0, pi1, pi2 :: Int- !pi0 = 0- !pi1 = halve len- !pi2 = len - 1- !pv0 <- GM.unsafeRead v pi0- !pv1 <- GM.unsafeRead v pi1- !pv2 <- GM.unsafeRead v pi2- pure $! Guess $ pv0 + pv1 + pv2 `quot` 3--instance (PrimMonad m, s ~ PrimState m) => Median (AveragingMedian (TestPair Int32 b)) (TestPair Int32 b) m s where- {-# INLINE selectMedian #-}- selectMedian- :: forall (v :: Type -> Type -> Type).- GM.MVector v (TestPair Int32 b)- => AveragingMedian (TestPair Int32 b)- -> v s (TestPair Int32 b)- -> m (MedianResult (TestPair Int32 b))- selectMedian _ !v = do- let len :: Int- !len = GM.length v- pi0, pi1, pi2 :: Int- !pi0 = 0- !pi1 = halve len- !pi2 = len - 1- !(TestPair !pv0 pv0') <- GM.unsafeRead v pi0- !pv1 <- fst . toTuple <$> GM.unsafeRead v pi1- !pv2 <- fst . toTuple <$> GM.unsafeRead v pi2- pure $! Guess $ TestPair (pv0 + pv1 + pv2 `quot` 3) pv0'--{-# INLINE halve #-}-halve :: Int -> Int-halve x = x `unsafeShiftR` 1-
− src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/PIntSequentialAveragingMedianST.hs
@@ -1,24 +0,0 @@--- |--- Module: Data.Vector.Algorithms.Quicksort.Predefined.VIntSequentialMedian3ST--- Copyright: (c) Sergey Vinokurov 2023--- License: Apache-2.0 (see LICENSE)--- Maintainer: serg.foo@gmail.com--module Data.Vector.Algorithms.Quicksort.Predefined.PIntSequentialAveragingMedianST- ( sortPIntSequentialAveragingMedianST- ) where--import Control.Monad.ST-import Data.Int-import Data.Vector.Primitive qualified as P--import Data.Vector.Algorithms.Quicksort.Parameterised--import Data.Vector.Algorithms.Quicksort.Predefined.AveragingMedian-import Data.Vector.Algorithms.Quicksort.Predefined.PIntSequentialMedian3ST ()--{-# NOINLINE sortPIntSequentialAveragingMedianST #-}-sortPIntSequentialAveragingMedianST :: P.MVector s Int64 -> ST s ()-sortPIntSequentialAveragingMedianST = sortInplaceFM Sequential (AveragingMedian @Int64)--
+ src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/PTripleSequentialMedian3ST.hs view
@@ -0,0 +1,30 @@+-- |+-- Module: Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3ST+-- Copyright: (c) Sergey Vinokurov 2023+-- License: Apache-2.0 (see LICENSE)+-- Maintainer: serg.foo@gmail.com++{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3ST+ ( sortPTripleSequentialMedian3ST+ ) where++import Control.Monad.ST+import Data.Vector.Primitive qualified as P++import Data.Vector.Algorithms.Quicksort.Parameterised++import Data.Vector.Algorithms.FixedSort+import Data.Vector.Algorithms.Heapsort++import Data.Vector.Algorithms.Quicksort.Predefined.SortTriple++{-# SPECIALIZE heapSort :: P.MVector s SortTriple -> ST s () #-}+{-# SPECIALIZE bitonicSort :: Int -> P.MVector s SortTriple -> ST s () #-}++{-# NOINLINE sortPTripleSequentialMedian3ST #-}+sortPTripleSequentialMedian3ST :: P.MVector s SortTriple -> ST s ()+sortPTripleSequentialMedian3ST = sortInplaceFM Sequential (Median3 @SortTriple)++
+ src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/PTripleSequentialMedian3or5ST.hs view
@@ -0,0 +1,24 @@+-- |+-- Module: Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3or5ST+-- Copyright: (c) Sergey Vinokurov 2023+-- License: Apache-2.0 (see LICENSE)+-- Maintainer: serg.foo@gmail.com++module Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3or5ST+ ( sortPTripleSequentialMedian3or5ST+ ) where++import Control.Monad.ST+import Data.Vector.Primitive qualified as P++import Data.Vector.Algorithms.Quicksort.Parameterised++import Data.Vector.Algorithms.Quicksort.Predefined.SortTriple++import Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3ST ()++{-# NOINLINE sortPTripleSequentialMedian3or5ST #-}+sortPTripleSequentialMedian3or5ST :: P.MVector s SortTriple -> ST s ()+sortPTripleSequentialMedian3or5ST = sortInplaceFM Sequential (Median3or5 @SortTriple)++
+ src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/SortTriple.hs view
@@ -0,0 +1,143 @@+-- |+-- Module: Data.Vector.Algorithms.Quicksort.Predefined.SortTriple+-- Copyright: (c) Sergey Vinokurov 2023+-- License: Apache-2.0 (see LICENSE)+-- Maintainer: serg.foo@gmail.com++{-# LANGUAGE DerivingVia #-}+{-# LANGUAGE InstanceSigs #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE UnboxedTuples #-}++module Data.Vector.Algorithms.Quicksort.Predefined.SortTriple+ ( SortTriple(..)+ , U.MVector(..)+ , U.Vector(..)+ ) where++import Data.Word+import Data.Vector.Generic qualified as G+import Data.Vector.Generic.Mutable qualified as GM+import Data.Vector.Unboxed qualified as U++import Data.Primitive.Types+import GHC.Exts+import GHC.Word++data SortTriple = SortTriple !Double !Double !Word64++instance Eq SortTriple where+ SortTriple _ _ c == SortTriple _ _ c' = c == c'++instance Ord SortTriple where+ SortTriple _ _ c `compare` SortTriple _ _ c' = compare c c'++instance U.IsoUnbox SortTriple (Double, Double, Word64) where+ toURepr (SortTriple a b c) = (a, b, c)+ fromURepr (a, b, c) = SortTriple a b c+ {-# INLINE toURepr #-}+ {-# INLINE fromURepr #-}++newtype instance U.MVector s SortTriple = MV_TestPair (U.MVector s (Double, Double, Word64))+newtype instance U.Vector SortTriple = V_TestPair (U.Vector (Double, Double, Word64))+deriving via (SortTriple `U.As` (Double, Double, Word64)) instance GM.MVector U.MVector SortTriple+deriving via (SortTriple `U.As` (Double, Double, Word64)) instance G.Vector U.Vector SortTriple+instance U.Unbox SortTriple++idxs :: Int# -> (# Int#, Int#, Int# #)+idxs idx =+ (# start+ , start +# sizeOf# (undefined :: Double)+ , start +# sizeOf# (undefined :: Double) +# sizeOf# (undefined :: Double)+ #)+ where+ start = idx *# sizeOf# (undefined :: SortTriple)++instance Prim SortTriple where+ sizeOf# _+ = sizeOf# (undefined :: Double)+ +# sizeOf# (undefined :: Double)+ +# sizeOf# (undefined :: Word64)++ alignment# _+ = alignment# (undefined :: Word64)++ indexByteArray# :: ByteArray# -> Int# -> SortTriple+ indexByteArray# arr idx =+ SortTriple+ (D# (indexWord8ArrayAsDouble# arr ia))+ (D# (indexWord8ArrayAsDouble# arr ib))+ (W64# (indexWord8ArrayAsWord64# arr ic))+ where+ !(# ia, ib, ic #) = idxs idx++ readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, SortTriple #)+ readByteArray# arr idx s1 =+ case readWord8ArrayAsDouble# arr ia s1 of+ (# s2, a #) ->+ case readWord8ArrayAsDouble# arr ib s2 of+ (# s3, b #) ->+ case readWord8ArrayAsWord64# arr ic s3 of+ (# s4, c #) -> (# s4, SortTriple (D# a) (D# b) (W64# c) #)+ where+ !(# ia, ib, ic #) = idxs idx++ writeByteArray# :: MutableByteArray# s -> Int# -> SortTriple -> State# s -> State# s+ writeByteArray# arr idx (SortTriple (D# a) (D# b) (W64# c)) s1 =+ case writeWord8ArrayAsDouble# arr ia a s1 of+ s2 ->+ case writeWord8ArrayAsDouble# arr ib b s2 of+ s3 ->+ writeWord8ArrayAsWord64# arr ic c s3+ where+ !(# ia, ib, ic #) = idxs idx++ setByteArray#+ :: MutableByteArray# s+ -> Int# -- ^ offset+ -> Int# -- ^ length+ -> SortTriple+ -> State# s+ -> State# s+ setByteArray# = defaultSetByteArray#++ indexOffAddr# :: Addr# -> Int# -> SortTriple+ indexOffAddr# addr idx =+ SortTriple+ (D# (indexDoubleOffAddr# addr ia))+ (D# (indexDoubleOffAddr# addr ib))+ (W64# (indexWord64OffAddr# addr ic))+ where+ !(# ia, ib, ic #) = idxs idx++ readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, SortTriple #)+ readOffAddr# addr idx s1 =+ case readDoubleOffAddr# addr ia s1 of+ (# s2, a #) ->+ case readDoubleOffAddr# addr ib s2 of+ (# s3, b #) ->+ case readWord64OffAddr# addr ic s3 of+ (# s4, c #) -> (# s4, SortTriple (D# a) (D# b) (W64# c) #)+ where+ !(# ia, ib, ic #) = idxs idx++ writeOffAddr# :: Addr# -> Int# -> SortTriple -> State# s -> State# s+ writeOffAddr# addr idx (SortTriple (D# a) (D# b) (W64# c)) s1 =+ case writeDoubleOffAddr# addr ia a s1 of+ s2 ->+ case writeDoubleOffAddr# addr ib b s2 of+ s3 ->+ writeWord64OffAddr# addr ic c s3+ where+ !(# ia, ib, ic #) = idxs idx++ setOffAddr#+ :: Addr#+ -> Int# -- ^ offset+ -> Int# -- ^ length+ -> SortTriple+ -> State# s+ -> State# s+ setOffAddr# = defaultSetOffAddr#+
− src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/UPairSequentialAveragingMedianST.hs
@@ -1,23 +0,0 @@--- |--- Module: Data.Vector.Algorithms.Quicksort.Predefined.UPairSequentialAveragingMedianST--- Copyright: (c) Sergey Vinokurov 2023--- License: Apache-2.0 (see LICENSE)--- Maintainer: serg.foo@gmail.com--module Data.Vector.Algorithms.Quicksort.Predefined.UPairSequentialAveragingMedianST- ( sortUPairSequentialAveragingMedianST- ) where--import Control.Monad.ST-import Data.Int-import Data.Vector.Unboxed qualified as U--import Data.Vector.Algorithms.Quicksort.Parameterised--import Data.Vector.Algorithms.Quicksort.Predefined.AveragingMedian-import Data.Vector.Algorithms.Quicksort.Predefined.Pair-import Data.Vector.Algorithms.Quicksort.Predefined.UPairSequentialMedian3ST ()--{-# NOINLINE sortUPairSequentialAveragingMedianST #-}-sortUPairSequentialAveragingMedianST :: U.MVector s (TestPair Int32 Int32) -> ST s ()-sortUPairSequentialAveragingMedianST = sortInplaceFM Sequential (AveragingMedian @(TestPair Int32 Int32))
+ src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/UTripleSequentialMedian3ST.hs view
@@ -0,0 +1,30 @@+-- |+-- Module: Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3ST+-- Copyright: (c) Sergey Vinokurov 2023+-- License: Apache-2.0 (see LICENSE)+-- Maintainer: serg.foo@gmail.com++{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3ST+ ( sortUTripleSequentialMedian3ST+ ) where++import Control.Monad.ST+import Data.Vector.Unboxed qualified as U++import Data.Vector.Algorithms.Quicksort.Parameterised++import Data.Vector.Algorithms.FixedSort+import Data.Vector.Algorithms.Heapsort++import Data.Vector.Algorithms.Quicksort.Predefined.SortTriple++{-# SPECIALIZE heapSort :: U.MVector s SortTriple -> ST s () #-}+{-# SPECIALIZE bitonicSort :: Int -> U.MVector s SortTriple -> ST s () #-}++{-# NOINLINE sortUTripleSequentialMedian3ST #-}+sortUTripleSequentialMedian3ST :: U.MVector s SortTriple -> ST s ()+sortUTripleSequentialMedian3ST = sortInplaceFM Sequential (Median3 @SortTriple)++
+ src-predefined/Data/Vector/Algorithms/Quicksort/Predefined/UTripleSequentialMedian3or5ST.hs view
@@ -0,0 +1,24 @@+-- |+-- Module: Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3or5ST+-- Copyright: (c) Sergey Vinokurov 2023+-- License: Apache-2.0 (see LICENSE)+-- Maintainer: serg.foo@gmail.com++module Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3or5ST+ ( sortUTripleSequentialMedian3or5ST+ ) where++import Control.Monad.ST+import Data.Vector.Unboxed qualified as U++import Data.Vector.Algorithms.Quicksort.Parameterised++import Data.Vector.Algorithms.Quicksort.Predefined.SortTriple++import Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3ST ()++{-# NOINLINE sortUTripleSequentialMedian3or5ST #-}+sortUTripleSequentialMedian3or5ST :: U.MVector s SortTriple -> ST s ()+sortUTripleSequentialMedian3or5ST = sortInplaceFM Sequential (Median3or5 @SortTriple)++
src/Data/Vector/Algorithms/Quicksort.hs view
@@ -38,10 +38,10 @@ -- to make sure that this function doesn't take any class -- dictionaries. If it does then performance will be very bad since -- either comparisons will go via indirection, vector reads/writes,--- monadic bind, or any combinatior of those will go through+-- monadic bind, or any combination of those will go through -- dictionary indirection. This can be avoided either by compiling--- with @-fspecialise-aggressively@ flag or by using via @SPECIALIZE@--- pragmas, like so:+-- with @-fspecialise-aggressively@ flag or by issuing @SPECIALIZE@+-- pragmas manually, like so: -- -- > -- Either use the flag to specialize everything, ... -- > {-# OPTIONS_GHC -fspecialise-aggressively #-}@@ -63,6 +63,10 @@ -- > {-# SPECIALIZE heapSort :: U.MVector RealWorld Int -> IO () #-} -- > {-# SPECIALIZE bitonicSort :: Int -> U.MVector RealWorld Int -> IO () #-} -- > {-# SPECIALIZE sort :: U.MVector RealWorld Int -> IO () #-}+--+-- Please note that since GHC 9.6 SPECIALIZE may not do anything for+-- the @ST@ monad unless -fpolymorphic-specialisation flag is also+-- enabled. {-# OPTIONS_GHC -Wno-orphans #-} @@ -80,10 +84,7 @@ import Data.Vector.Algorithms.Quicksort.Parameterised -{-# SPECIALIZE sortInplaceFM- :: (PrimMonad m, Ord a, GM.MVector v a) => Sequential -> Median3or5 a -> v (PrimState m) a -> m () #-}--{-# INLINABLE sort #-}+{-# INLINE sort #-} -- | Good default sort. Returns sorted copy. -- -- This function takes generic vectors so will work with any vectors@@ -98,7 +99,7 @@ sortInplaceFM Sequential (Median3or5 @a) ys G.unsafeFreeze ys -{-# INLINABLE sortInplace #-}+{-# INLINE sortInplace #-} -- | Good default sort for mutable vectors. -- -- This function takes generic mutable vectors so will work with any
src/Data/Vector/Algorithms/Quicksort/Median.hs view
@@ -8,6 +8,7 @@ {-# LANGUAGE MagicHash #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE UnboxedTuples #-} module Data.Vector.Algorithms.Quicksort.Median ( Median(..)@@ -20,25 +21,17 @@ import Control.Monad.Primitive import Data.Bits-import Data.Function import Data.Kind (Type) import Data.Vector.Generic.Mutable qualified as GM+import GHC.Exts (Int(..), Int#) -- | Median selection result. data MedianResult a -- | Value that was located at specific index in the original array. = ExistingValue !a {-# UNPACK #-} !Int- -- | Value that is a good guess for a real median but may not be- -- present in the array (or we don't know where it's exactly).- --- -- Good example is to pick first, last, and middle element and- -- average them, which restricts us to dealing with numeric values- -- but may yield good results depending on distribution of values in- -- the array to be sorted.- | Guess !a -existingValue :: CmpFst a Int -> MedianResult a-existingValue (CmpFst (x, n)) = ExistingValue x n+existingValue :: (# a, Int# #) -> MedianResult a+existingValue (# !x, n #) = ExistingValue x (I# n) -- | Median selection algorithm that, given a vector, should come up -- with an elements that has good chances to be median (i.e to be@@ -76,8 +69,8 @@ {-# INLINE pick3 #-} -- Pick median among 3 values.-pick3 :: Ord a => a -> a -> a -> a-pick3 a b c =+pick3 :: Ord a => a -> Int# -> a -> Int# -> a -> Int# -> (# a, Int# #)+pick3 !a ai !b bi !c ci = if b < a then -- ... b < a ...@@ -86,13 +79,13 @@ if c < b then -- c < b < a- b+ (# b, bi #) else -- b <= c < a- c+ (# c, ci #) else -- b < a <= c- a+ (# a, ai #) else -- ... a <= b ... if c < b@@ -100,18 +93,18 @@ if c < a then -- c < a <= b- a+ (# a, ai #) else -- a <= c <= b- c+ (# c, ci #) else -- a <= b <= c- b+ (# b, bi #) {-# INLINE sort3 #-} -- Establish sortered order among 3 values.-sort3 :: Ord a => a -> a -> a -> (a, a, a)-sort3 a b c =+sort3 :: Ord a => a -> Int# -> a -> Int# -> a -> Int# -> (# a, Int#, a, Int#, a, Int# #)+sort3 !a ai !b bi !c ci = if b < a then -- ... b < a ...@@ -120,13 +113,13 @@ if c < b then -- c < b < a- (c, b, a)+ (# c, ci, b, bi, a, ai #) else -- b <= c < a- (b, c, a)+ (# b, bi, c, ci, a, ai #) else -- b < a <= c- (b, a, c)+ (# b, bi, a, ai, c, ci #) else -- ... a <= b ... if c < b@@ -134,25 +127,13 @@ if c < a then -- c < a <= b- (c, a, b)+ (# c, ci, a, ai, b, bi #) else -- a <= c <= b- (a, c, b)+ (# a, ai, c, ci, b, bi #) else -- a <= b <= c- (a, b, c)--newtype CmpFst a b = CmpFst { unCmpFst :: (a, b) }--instance Eq a => Eq (CmpFst a b) where- (==) = (==) `on` fst . unCmpFst--instance Ord a => Ord (CmpFst a b) where- compare = compare `on` fst . unCmpFst--{-# INLINE readAt #-}-readAt :: (PrimMonad m, GM.MVector v a) => v (PrimState m) a -> Int -> m (CmpFst a Int)-readAt xs n = (\x -> CmpFst (x, n)) <$> GM.unsafeRead xs n+ (# a, ai, b, bi, c, ci #) instance (PrimMonad m, s ~ PrimState m) => Median (Median3 a) a m s where {-# INLINE selectMedian #-}@@ -165,14 +146,14 @@ selectMedian _ !v = do let len :: Int !len = GM.length v- pi0, pi1, pi2 :: Int- !pi0 = 0- !pi1 = halve len- !pi2 = len - 1- !pv0 <- readAt v pi0- !pv1 <- readAt v pi1- !pv2 <- readAt v pi2- pure $! existingValue $ pick3 pv0 pv1 pv2+ pi0, pi1, pi2 :: Int#+ !(I# pi0) = 0+ !(I# pi1) = halve len+ !(I# pi2) = len - 1+ !pv0 <- GM.unsafeRead v (I# pi0)+ !pv1 <- GM.unsafeRead v (I# pi1)+ !pv2 <- GM.unsafeRead v (I# pi2)+ pure $! existingValue (pick3 pv0 pi0 pv1 pi1 pv2 pi2) instance (PrimMonad m, s ~ PrimState m) => Median (Median3or5 a) a m s where {-# INLINE selectMedian #-}@@ -185,34 +166,34 @@ selectMedian _ !v = do let len :: Int !len = GM.length v- pi0, pi1, pi2 :: Int- !pi0 = 0- !pi1 = halve len- !pi2 = len - 1- !pv0 <- readAt v pi0- !pv1 <- readAt v pi1- !pv2 <- readAt v pi2+ pi0, pi1, pi2 :: Int#+ !(I# pi0) = 0+ !(I# pi1) = halve len+ !(I# pi2) = len - 1+ !pv0 <- GM.unsafeRead v (I# pi0)+ !pv1 <- GM.unsafeRead v (I# pi1)+ !pv2 <- GM.unsafeRead v (I# pi2) -- If median of 3 has chances to be good enough if pv0 /= pv1 && pv1 /= pv2 && pv2 /= pv0- then pure $! existingValue $ pick3 pv0 pv1 pv2+ then pure $! existingValue (pick3 pv0 pi0 pv1 pi1 pv2 pi2) else do- let pi01, pi12 :: Int- !pi01 = halve pi1- !pi12 = pi1 + pi01+ let pi01, pi12 :: Int#+ !(I# pi01) = halve (I# pi1)+ !(I# pi12) = I# pi1 + I# pi01 - !pv01 <- readAt v pi01- !pv12 <- readAt v pi12+ !pv01 <- GM.unsafeRead v (I# pi01)+ !pv12 <- GM.unsafeRead v (I# pi12) - let (!mn, !med, !mx) = sort3 pv0 pv1 pv2- (!mn', !mx')- | pv01 < pv12 = (pv01, pv12)- | otherwise = (pv12, pv01)+ let !(# !mn, !mni, !med, !medi, !mx, !mxi #) = sort3 pv0 pi0 pv1 pi1 pv2 pi2+ !(# !mn', !mni', !mx', !mxi' #)+ | pv01 < pv12 = (# pv01, pi01, pv12, pi12 #)+ | otherwise = (# pv12, pi12, pv01, pi01 #) - !med'- | mn' > mx = mx- | mx' < mn = mn- | otherwise = pick3 mn' med mx'+ !med'@(# !_, !_ #)+ | mn' > mx = (# mx, mxi #)+ | mx' < mn = (# mn, mni #)+ | otherwise = pick3 mn' mni' med medi mx' mxi' pure $! existingValue med'
src/Data/Vector/Algorithms/Quicksort/Parameterised.hs view
@@ -140,10 +140,6 @@ res <- selectMedian med v' (!pi', !pv) <- case res of- Guess pv -> do- (_, !pi') <- partitionTwoWaysGuessedPivot pv last v- pure (pi', pv)- ExistingValue pv pi -> do when (pi /= last) $ do GM.unsafeWrite v pi =<< GM.unsafeRead v last@@ -169,38 +165,6 @@ where !len = GM.length v !depthDiff = depth - logLen--{-# INLINE partitionTwoWaysGuessedPivot #-}-partitionTwoWaysGuessedPivot- :: (PrimMonad m, Ord a, GM.MVector v a)- => a -> Int -> v (PrimState m) a -> m (a, Int)-partitionTwoWaysGuessedPivot !pv !lastIdx !v =- go 0 lastIdx- where- go !i !j = do- !(i', xi) <- goLT i- !(j', xj) <- goGT j- if i' < j'- then do- GM.unsafeWrite v j' xi- GM.unsafeWrite v i' xj- go (i' + 1) (j' - 1)- else pure (xi, i')- where- goLT !k = do- if k <= j- then do- !x <- GM.unsafeRead v k- if x < pv- then goLT (k + 1)- else pure (k, x)- -- Be careful not to write this pv into array - pv may not exsit there.- else pure (k, pv)- goGT !k = do- !x <- GM.unsafeRead v k- if x >= pv && i < k- then goGT (k - 1)- else pure (k, x) {-# INLINE partitionTwoWaysPivotAtEnd #-} partitionTwoWaysPivotAtEnd
test/Data/Vector/Algorithms/Quicksort/Tests.hs view
@@ -31,9 +31,6 @@ import Data.Vector.Algorithms.Quicksort.Predefined.Pair -import Data.Vector.Algorithms.Quicksort.Predefined.PIntSequentialAveragingMedianST-import Data.Vector.Algorithms.Quicksort.Predefined.UPairSequentialAveragingMedianST- import Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelMedian3IO import Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelMedian3or5IO @@ -178,9 +175,6 @@ sortsAndDoesNotLoseItemsST @U.Vector sortUPairParallelStrategiesMedian3ST , QC.testProperty "Data.Vector.Unboxed (TestPair Int32 Int32) sorting ParallelStrategies Median3or5" $ sortsAndDoesNotLoseItemsST @U.Vector sortUPairParallelStrategiesMedian3or5ST-- , QC.testProperty "Data.Vector.Unboxed (TestPair Int32 Int32) sorting Sequential AveragingMedian" $- sortsAndDoesNotLoseItemsST @U.Vector sortUPairSequentialAveragingMedianST ] , testGroup "IO" [ QC.testProperty "Data.Vector (TestPair Int32 Int32) sorting Sequential Median3" $@@ -219,9 +213,6 @@ sortsAndDoesNotLoseItemsSTtoIO @U.Vector sortUPairParallelStrategiesMedian3ST , QC.testProperty "Data.Vector.Unboxed (TestPair Int32 Int32) sorting ParallelStrategies Median3or5" $ sortsAndDoesNotLoseItemsSTtoIO @U.Vector sortUPairParallelStrategiesMedian3or5ST-- , QC.testProperty "Data.Vector.Unboxed (TestPair Int32 Int32) sorting Sequential AveragingMedian" $- sortsAndDoesNotLoseItemsSTtoIO @U.Vector sortUPairSequentialAveragingMedianST ] ] where@@ -307,10 +298,6 @@ , QC.testProperty "Data.Vector.Unboxed (Int32, Int32) sorting ParStrategies Median3or5" $ \(xs :: [(Int32, Int32)]) -> runST (runSort @U.Vector sortUTupleParallelStrategiesMedian3or5ST xs) === L.sort xs-- , QC.testProperty "Data.Vector.Primitive Int64 sorting Sequential AveragingMedian" $- \(xs :: [Int64]) ->- runST (runSort @P.Vector sortPIntSequentialAveragingMedianST xs) === L.sort xs ] sortTestsIO :: TestTree@@ -427,11 +414,6 @@ , QC.testProperty "Data.Vector.Unboxed (Int32, Int32) sorting ParStrategies Median3or5" $ \(xs :: [(Int32, Int32)]) -> ioProperty $ do ys <- runSortSTtoIO @U.Vector sortUTupleParallelStrategiesMedian3or5ST xs- pure $ ys === L.sort xs-- , QC.testProperty "Data.Vector.Primitive Int64 sorting Sequential AveragingMedian" $- \(xs :: [Int64]) -> ioProperty $ do- ys <- runSortSTtoIO @P.Vector sortPIntSequentialAveragingMedianST xs pure $ ys === L.sort xs ]
vector-quicksort.cabal view
@@ -3,7 +3,7 @@ name: vector-quicksort version:- 0.1+ 0.2 synopsis: Fast and flexible quicksort implementation for mutable vectors@@ -41,6 +41,9 @@ extra-source-files: Readme.md+ Changelog.md+ cbits/sort.cpp+ cbits/sort.h homepage: https://github.com/sergv/vector-quicksort@@ -54,7 +57,6 @@ GHC2021 default-extensions:- ImportQualifiedPost LambdaCase ghc-options:@@ -67,7 +69,6 @@ -Wno-missing-local-signatures -Wno-missing-safe-haskell-mode -Wno-safe- -Wno-type-defaults -Wno-unsafe -Wno-unused-packages @@ -79,6 +80,11 @@ ghc-options: -Wno-missing-kind-signatures + if impl(ghc >= 9.8)+ ghc-options:+ -Wno-missing-role-annotations+ -Wno-missing-poly-kind-signatures+ library import: ghc-options exposed-modules:@@ -91,17 +97,24 @@ hs-source-dirs: src build-depends:- , base >= 4.14 && < 5+ , base >= 4.15 && < 5 , primitive , stm , vector -library vector-quicksort-predefined+library test-predefined-sorts import: ghc-options + visibility:+ private++ if impl(ghc >= 9.6)+ ghc-options:+ -fpolymorphic-specialisation+ exposed-modules:- Data.Vector.Algorithms.Quicksort.Predefined.AveragingMedian Data.Vector.Algorithms.Quicksort.Predefined.Pair+ Data.Vector.Algorithms.Quicksort.Predefined.SortTriple Data.Vector.Algorithms.Quicksort.Predefined.BitonicIntST @@ -117,9 +130,6 @@ Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelStrategiesMedian3or5ST Data.Vector.Algorithms.Quicksort.Predefined.PIntParallelStrategiesMedian3or5IO - Data.Vector.Algorithms.Quicksort.Predefined.PIntSequentialAveragingMedianST- Data.Vector.Algorithms.Quicksort.Predefined.UPairSequentialAveragingMedianST- Data.Vector.Algorithms.Quicksort.Predefined.VIntSequentialMedian3ST Data.Vector.Algorithms.Quicksort.Predefined.VIntSequentialMedian3IO Data.Vector.Algorithms.Quicksort.Predefined.VPairSequentialMedian3ST@@ -173,15 +183,18 @@ Data.Vector.Algorithms.Quicksort.Predefined.UTupleParallelStrategiesMedian3or5ST Data.Vector.Algorithms.Quicksort.Predefined.UTupleParallelStrategiesMedian3or5IO + Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3ST+ Data.Vector.Algorithms.Quicksort.Predefined.PTripleSequentialMedian3or5ST+ Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3ST+ Data.Vector.Algorithms.Quicksort.Predefined.UTripleSequentialMedian3or5ST+ hs-source-dirs: src-predefined build-depends:- , base >= 4.14- , parallel+ , base >= 4.15 , primitive- , stm- , vector+ , vector >= 0.13 , vector-quicksort test-suite test@@ -197,21 +210,23 @@ test build-depends: , QuickCheck- , base >= 4.14+ , base >= 4.15 , containers , tasty , tasty-quickcheck , vector- , vector-quicksort-predefined+ , test-predefined-sorts ghc-options: -rtsopts -threaded "-with-rtsopts=-N -A16m -n1m -qg -qb" -main-is TestMain -library vector-quicksort-cpp+library test-foreign-sort default-language: GHC2021+ visibility:+ private include-dirs: cbits cxx-sources:@@ -235,12 +250,6 @@ elif os(linux) extra-libraries: stdc++ else- -- This is supposed to be under arch(wasm32), but we can't do that yet- -- since cabal check would fail with unrecognized arch, see- -- https://github.com/haskell/cabal/pull/8096 for the fix.- -- TODO: when a new cabal release is out with that fix, bump cabal in CI- -- and add proper arch(wasm32) declaration here.- cpp-options: -DSIMDUTF_NO_THREADS cxx-options: -fno-exceptions extra-libraries: c++ c++abi @@ -254,26 +263,27 @@ ForeignSorting hs-source-dirs: bench+ build-tool-depends:+ , hsc2hs:hsc2hs build-depends:- , atomic-counter- , base >= 4.14+ , base >= 4.15 , bytestring , deepseq- , primitive , random , stm- , tasty+ , tasty >= 1.5 , tasty-bench >= 0.3.2+ , tasty-hunit , text , text-builder-linear , vector , vector-algorithms , vector-quicksort- , vector-quicksort-cpp- , vector-quicksort-predefined+ , vector-quicksort:test-foreign-sort+ , vector-quicksort:test-predefined-sorts ghc-options: -fno-spec-constr -rtsopts -threaded "-with-rtsopts=-N -A16m -n1m -qg -qb"- -main-is BenchmarkMain+ -main-is BenchMain