4 ms·

> Not if it does lots more memory accesses, which is not clear from the page. They say it reduces comparisons, moves and temporary allocation. To me this sound

> Not if it does lots more memory accesses, which is not clear from the page. They say it reduces comparisons, moves and temporary allocation. To me this sounds like fewer memory accesses, although they note that quicksort can use L1 cache more optimally. > quicksort is still better after all the shenanigans you can apply According to the benchmarks, this is better than the quicksorts (qsort and Timsort). > this will likely destroy branch prediction But this is branchless where it matters, which is confirmed by the benchmarks. I do agree it would be interesting to measure the actual energy efficiency to see how well it matches the benchmark results.

scandum 4y ago
Quadsort makes more comparisons than timsort, but it has far better branch prediction for random data and far less overhead under the hood. While a switch might seem bad, in the case of random data quadsort turns 1.5 branch mispredictions into 0.84 branch mispredictions. My upcoming release of quadsort 1.1.5.4 will improve that further. This is a difficult topic to comment on for someone who isn't 100% in the know, and I often make incorrect assumptions myself. It would be interesting indeed to get the actual energy efficiency, but quadsort being 2-3x faster than timsort on random data pretty much guarantees it is. I'm not aware of an easy method to measure energy consumption, but it would be a better metric in this day and age. As for mergesort vs quicksort, this is pretty much a draw and it heavily depends on data type and comparison type. Fluxsort so far appears to confirm that a hybrid mergesort/quicksort is the best overall by taking advantage of the strengths of both algorithms. Adaptation is coming along slowly but steadily. Several people have started incorporating my branchless bidirectional merge and branchless stable partition concepts, among other things, as fluxsort contains quite a few novelties. My work on binary searching and array rotations could be even more important to reducing the energy footprint.
- tuukkah 4y ago
  Thank you for these insights! To measure the energy efficiency as simply as possible, I wonder if it could be sufficient to run a big-enough benchmark on a laptop and check the battery charge level before and after.
- SideQuark 4y ago
  I'd be surprised if this is so good - it's a small instance of a sorting network [1], which has been analyzed to death for around 70 years. I first read about them from TAOCP decades ago, and have used pieces of them in algorithm design before. There's still progress in the field, but I don't see much in quadsort that isn't a direction beat to death decades ago. But if so, it would be cool. It's always interesting to see stuff pushed to the edge. Maybe if I get time I'll build instrumentation to measure all the pieces and see what I find :) >so in any instance where data is more likely to be orderly than disorderly this shift in probability will give an advantage This is pretty hand wavy - for example, standard sorting networks sorts 4 values in 5 compare-and-swaps always (AB,CD,AC,BD,BC). Quadsort over the 24 possible input orders averages 5.17, but with much worse locality and branch patterns (the 5 CAS can be done with zero branches, for many data types, for example). I've not found good empirical evidence on what happens in practice to tell if, for whatever distribution of things occur in practice, if quadsort is better even at expected number of compares. And, if quadsort is better, you can easily do any number of n-sort, and using something like Z3 theorem prover to find optimal code for just about any set of conditions you want to model. But all this stuff has been done forever, and in practice such results end up worse enough that the algorithms don't get widespread or published at all. https://en.wikipedia.org/wiki/Sorting_network https://en.wikipedia.org/wiki/Sorting_network https://ieeexplore.ieee.org/document/53587 https://ieeexplore.ieee.org/document/53587
  - tuukkah 4y ago
    Here you can see how an older version of quadsort beats some benchmarks that include the number of comparisons: https://www.raygard.net/2022/03/09/Re-engineering-a-qsort-part-5/ https://www.raygard.net/2022/03/09/Re-engineering-a-qsort-pa...
    - SideQuark 4y ago
      I agree one can make data for which quadsort has less compares. But one can also make data where it's worse. It's provably worse over each of the 24 orderings of possible data when uniformly weighted. When your benchmarks are weighted to cases where it's better, you'll conclude it's better. But that doesn't really cover what will happen in the real world. That distribution is what will matter. As I pointed out, this line you're chasing was done decades ago. I posted one paper along this line. Things it cites and things citing it likely cover the method you're working on. Theres significant literature on your method and lots of generalizations. I'd be surprised if somehow all those researchers missed this.

scandum 4y ago

Quadsort makes more comparisons than timsort, but it has far better branch prediction for random data and far less overhead under the hood. While a switch might seem bad, in the case of random data quadsort turns 1.5 branch mispredictions into 0.84 branch mispredictions. My upcoming release of quadsort 1.1.5.4 will improve that further. This is a difficult topic to comment on for someone who isn't 100% in the know, and I often make incorrect assumptions myself. It would be interesting indeed to get the actual energy efficiency, but quadsort being 2-3x faster than timsort on random data pretty much guarantees it is. I'm not aware of an easy method to measure energy consumption, but it would be a better metric in this day and age. As for mergesort vs quicksort, this is pretty much a draw and it heavily depends on data type and comparison type. Fluxsort so far appears to confirm that a hybrid mergesort/quicksort is the best overall by taking advantage of the strengths of both algorithms. Adaptation is coming along slowly but steadily. Several people have started incorporating my branchless bidirectional merge and branchless stable partition concepts, among other things, as fluxsort contains quite a few novelties. My work on binary searching and array rotations could be even more important to reducing the energy footprint.

tuukkah 4y ago
Thank you for these insights! To measure the energy efficiency as simply as possible, I wonder if it could be sufficient to run a big-enough benchmark on a laptop and check the battery charge level before and after.
SideQuark 4y ago
I'd be surprised if this is so good - it's a small instance of a sorting network [1], which has been analyzed to death for around 70 years. I first read about them from TAOCP decades ago, and have used pieces of them in algorithm design before. There's still progress in the field, but I don't see much in quadsort that isn't a direction beat to death decades ago. But if so, it would be cool. It's always interesting to see stuff pushed to the edge. Maybe if I get time I'll build instrumentation to measure all the pieces and see what I find :) >so in any instance where data is more likely to be orderly than disorderly this shift in probability will give an advantage This is pretty hand wavy - for example, standard sorting networks sorts 4 values in 5 compare-and-swaps always (AB,CD,AC,BD,BC). Quadsort over the 24 possible input orders averages 5.17, but with much worse locality and branch patterns (the 5 CAS can be done with zero branches, for many data types, for example). I've not found good empirical evidence on what happens in practice to tell if, for whatever distribution of things occur in practice, if quadsort is better even at expected number of compares. And, if quadsort is better, you can easily do any number of n-sort, and using something like Z3 theorem prover to find optimal code for just about any set of conditions you want to model. But all this stuff has been done forever, and in practice such results end up worse enough that the algorithms don't get widespread or published at all. https://en.wikipedia.org/wiki/Sorting_network https://en.wikipedia.org/wiki/Sorting_network https://ieeexplore.ieee.org/document/53587 https://ieeexplore.ieee.org/document/53587
- tuukkah 4y ago
  Here you can see how an older version of quadsort beats some benchmarks that include the number of comparisons: https://www.raygard.net/2022/03/09/Re-engineering-a-qsort-part-5/ https://www.raygard.net/2022/03/09/Re-engineering-a-qsort-pa...
  - SideQuark 4y ago
    I agree one can make data for which quadsort has less compares. But one can also make data where it's worse. It's provably worse over each of the 24 orderings of possible data when uniformly weighted. When your benchmarks are weighted to cases where it's better, you'll conclude it's better. But that doesn't really cover what will happen in the real world. That distribution is what will matter. As I pointed out, this line you're chasing was done decades ago. I posted one paper along this line. Things it cites and things citing it likely cover the method you're working on. Theres significant literature on your method and lots of generalizations. I'd be surprised if somehow all those researchers missed this.