5 ms·

looks awesome. making this the default sort would surely save lots of co_2.

SideQuark 4y ago
Not if it does lots more memory accesses, which is not clear from the page. For example, mergesort has nicer lower bound than quicksort, but quicksort has significantly better constant value hidden in the O(n log n), so quicksort is much lower energy cost (in general - both can be fiddled with, but if I recall, quicksort is still better after all the shenanigans you can apply). From a quick look at the code, line 248 of quidsort.c looks like an 8 way switch per 4 elements - this will likely destroy branch prediction, making pipeline refills cost significantly more CPU cycles than quicksort or merge sort. The code throughout looks like this type of large branching situations. If you want to save CO2, disregard standard complexity and actually measure energy usage - many things can have nice complexities and hide terrible behavior on modern hardware.
- tuukkah 4y ago
  > 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...

Not if it does lots more memory accesses, which is not clear from the page. For example, mergesort has nicer lower bound than quicksort, but quicksort has significantly better constant value hidden in the O(n log n), so quicksort is much lower energy cost (in general - both can be fiddled with, but if I recall, quicksort is still better after all the shenanigans you can apply). From a quick look at the code, line 248 of quidsort.c looks like an 8 way switch per 4 elements - this will likely destroy branch prediction, making pipeline refills cost significantly more CPU cycles than quicksort or merge sort. The code throughout looks like this type of large branching situations. If you want to save CO2, disregard standard complexity and actually measure energy usage - many things can have nice complexities and hide terrible behavior on modern hardware.

tuukkah 4y ago
> 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...