18 ms·

Qsort.h – Quicksort as a C macro (2019)

85 points by olitech 3y ago

greenyoda 3y ago
The link to Sedgewick's 1978 paper no longer works, but an archive of it can be found here: http://web.archive.org/web/20190713031319/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/Sedgewick.pdf http://web.archive.org/web/20190713031319/http://penguin.ewu...
- kazinator 3y ago
  The paper says that more detailed discussion of partition methods is given in [15]. That looks like Sedwicks's Ph. D thesis which was on Quicksort? I found this: https://sedgewick.io/wp-content/themes/sedgewick/papers/1975Quicksort.pdf https://sedgewick.io/wp-content/themes/sedgewick/papers/1975... Basically a longer book on Quicksort with a lot more analysis. He doesn't discuss any partitioning methods that do not move two indices toward each other from opposite ends of the subarray. It's not even on the table.
  - metadat 3y ago
    Of course the logo on the paper title page is a sequence of 8 lines with each doubling on thickness. Though it'd be more visually and intuitively accurate if the lines started large and cut in half each step. :P
    - _the_inflator 3y ago
      Nice catch, yes!
kazinator 3y ago
This is very good: it uses the original Hoare partitioning algorithm which moves two indices at opposite ends of the array partition toward each other, rather than the ill-considered Lomuto partitioning: while (1) { \ do q_i++; while (Q_LESS(q_i, q_l)); \ do q_j--; while (Q_LESS(q_l, q_j)); \ if (q_i >= q_j) break; /* Sedgewick says "until j < i" */ \ Q_SWAP(q_i, q_j); \ } \ Lomuto is that algorithm that moves one index, swapping lower-than-pivot elements into a growing lower partition. Lomuto ends up performing more comparisons. What's more, Lomuto has quadratic behavior for sequences that are just repetitions of a value: every partitioning and sub-partitioning is a degenerate case. Hoare's algorithm deftly avoids this problem. You can explain that using the above snippet. If all elements are the same, then Q_LESS(q_i, q_l) is always false. Thus each of the two do/while loops executes one unconditional iteration, so that the two indices q_i and q_j march toward each other and meet in the middle. The repeating sequence thus nicely cut in half, and recursively so, ensuring O(N log N) behavior. You can't easily banish the worst case from Quicksort, but implementations should not exhibit worst case behavior on inputs that have some obvious pattern, like a repeated value.
- nwallin 3y ago
  Lomuto partitioning has one major advantage over Hoare: Lomuto can be implemented in such that the inner loop is branchless, while the inner loops in Hoare are branchy and wreck the branch predictor. Lomuto typically fixes the Dutch National Flag problem by keeping two 'midpoints'; left of the left midpoint is less than the pivot, right of the right midpoint is greater than the pivot, between the two midpoints is equal to the pivot. This makes most data inputs that result in the O(n^2) worst case of quicksort give O(n) performance instead. Unfortunately the code is horrific looking. It's not something I'd ever want to do in a C macro.
  - orlp 3y ago
    And my algorithm pdqsort uses Hoare-style partitioning, is branchless, and properly solves the Dutch National Flag problem by being 0(n log k) for k unique values on average using only a single extra comparison per partitioning. https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort
WalterBright 3y ago
If you're doing metaprogramming using the C preprocessor, it's time to move to a more advanced language.
- FpUser 3y ago
  I knew someone would come up with this kind of "wisdom". For starters you do not know what other languages they might be using for development. And whatever they do they definitely do not need patronizing.
  - WalterBright 3y ago
    I've done a share of C metaprogramming with the preprocessor myself, and have dealt a lot with other peoples' C metaprogramming. I've also seen people use pages of algrebra as a substitute for a couple lines of calculus. I struggled for years with a soldering iron, always frustrated by bad solder joints. Then, I discovered a Weller thermostat controlled iron, and get a perfect joint every time. Not everyone knows there are better ways to do things.
    - webstrand 3y ago
      Your experience soldering is a much better response. You present a concrete suggestion for use a weller thermostat controlled iron. But you did not present a concrete suggestion for an alternative to the C pre-processor. You could do this with C++ templates, for instance. But the LESS and SWAP operations may or may not get inlined. With the C pre-processor you can be certain that the operations get inlined, since no other alternative interpretation is available to the compiler.
      - WalterBright 3y ago
        > But you did not present a concrete suggestion for an alternative to the C pre-processor. If someone asked, I would. But since I do have a dog in that hunt, I felt it would be more appropriate for others to make a suggestion, as there are several.
eesmith 3y ago
Along the same lines, I use Christopher Swenson's sort.h at https://github.com/swenson/sort/ https://github.com/swenson/sort/ You get the choice of many sorting routines, including: Timsort (stable) Quicksort Merge sort (stable) In-place merge sort (not stable) Shellsort Binary insertion sort Heapsort Selection sort (this is really only here for comparison) Grail sort (stable) Sqrt Sort (stable, based on Grail sort, also by Andrey Astrelin).
syockit 3y ago
Today I learned that for modern processors, quicksort code is small enough that the compiler can inline them if the definition is visible during compilation. See here for comparison of isort function implemented using plain static functions vs the macro in TFA: https://godbolt.org/z/arGjPGhKE https://godbolt.org/z/arGjPGhKE . It's not as flexible as the macro form (not being able to pass two arrays at once like the sortByAge example in TFA), but I figure it should be friendlier to debuggers (though with all the inlining the experience is not going to be that great either). IIRC, if LTO is enabled the calls to the less and swap functions can also be inlined even if the generic function is compiled to a separate translation unit. Haven't tried it for the quick sort code above, but I found that out for some other thing I experimented with.
- uecker 3y ago
  Did you try inline as well? Why are they not as flexible as the macro? Couldn't the swap not also process two arrays?
  - syockit 3y ago
    The function is already inlined because the implementation is visible. You can check the assembly, it has no calls to the compare and swap functions. I guess you're right, since the function accepts a void pointer, it could also point to an array of two array pointers. So yes, it can also process two arrays.
vrglvrglvrgl 3y ago
[dead]
dale_glass 3y ago
On one hand, neat. On the other hand, I think it's sad that so much time and brainpower is going on contriving ways to get bad tooling to do something, rather than on the actual meat of the problem solving. You'd think that in 50 years somebody could have invented a better preprocessor, and save the need for all the while(0) and other trickery needed for macros.
nuancebydefault 3y ago
I like C a lot. One big advantage of the language is that its complete syntax and standard runtime functions can fit in one brain. That said, I hate the way a lot of programmers use the preprocessor. For me, macros should be just simple expressions or functions (i mean they sohould be invokeable like functions) . But very often, there's a lot of magic inside macros, making them hard to use, let alone understand.

85 points by olitech 3y ago

The link to Sedgewick's 1978 paper no longer works, but an archive of it can be found here: http://web.archive.org/web/20190713031319/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/Sedgewick.pdf http://web.archive.org/web/20190713031319/http://penguin.ewu...

kazinator 3y ago
The paper says that more detailed discussion of partition methods is given in [15]. That looks like Sedwicks's Ph. D thesis which was on Quicksort? I found this: https://sedgewick.io/wp-content/themes/sedgewick/papers/1975Quicksort.pdf https://sedgewick.io/wp-content/themes/sedgewick/papers/1975... Basically a longer book on Quicksort with a lot more analysis. He doesn't discuss any partitioning methods that do not move two indices toward each other from opposite ends of the subarray. It's not even on the table.
- metadat 3y ago
  Of course the logo on the paper title page is a sequence of 8 lines with each doubling on thickness. Though it'd be more visually and intuitively accurate if the lines started large and cut in half each step. :P
  - _the_inflator 3y ago
    Nice catch, yes!

kazinator 3y ago

This is very good: it uses the original Hoare partitioning algorithm which moves two indices at opposite ends of the array partition toward each other, rather than the ill-considered Lomuto partitioning: while (1) { \ do q_i++; while (Q_LESS(q_i, q_l)); \ do q_j--; while (Q_LESS(q_l, q_j)); \ if (q_i >= q_j) break; /* Sedgewick says "until j < i" */ \ Q_SWAP(q_i, q_j); \ } \ Lomuto is that algorithm that moves one index, swapping lower-than-pivot elements into a growing lower partition. Lomuto ends up performing more comparisons. What's more, Lomuto has quadratic behavior for sequences that are just repetitions of a value: every partitioning and sub-partitioning is a degenerate case. Hoare's algorithm deftly avoids this problem. You can explain that using the above snippet. If all elements are the same, then Q_LESS(q_i, q_l) is always false. Thus each of the two do/while loops executes one unconditional iteration, so that the two indices q_i and q_j march toward each other and meet in the middle. The repeating sequence thus nicely cut in half, and recursively so, ensuring O(N log N) behavior. You can't easily banish the worst case from Quicksort, but implementations should not exhibit worst case behavior on inputs that have some obvious pattern, like a repeated value.

nwallin 3y ago
Lomuto partitioning has one major advantage over Hoare: Lomuto can be implemented in such that the inner loop is branchless, while the inner loops in Hoare are branchy and wreck the branch predictor. Lomuto typically fixes the Dutch National Flag problem by keeping two 'midpoints'; left of the left midpoint is less than the pivot, right of the right midpoint is greater than the pivot, between the two midpoints is equal to the pivot. This makes most data inputs that result in the O(n^2) worst case of quicksort give O(n) performance instead. Unfortunately the code is horrific looking. It's not something I'd ever want to do in a C macro.
- orlp 3y ago
  And my algorithm pdqsort uses Hoare-style partitioning, is branchless, and properly solves the Dutch National Flag problem by being 0(n log k) for k unique values on average using only a single extra comparison per partitioning. https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort

WalterBright 3y ago

If you're doing metaprogramming using the C preprocessor, it's time to move to a more advanced language.

FpUser 3y ago
I knew someone would come up with this kind of "wisdom". For starters you do not know what other languages they might be using for development. And whatever they do they definitely do not need patronizing.
- WalterBright 3y ago
  I've done a share of C metaprogramming with the preprocessor myself, and have dealt a lot with other peoples' C metaprogramming. I've also seen people use pages of algrebra as a substitute for a couple lines of calculus. I struggled for years with a soldering iron, always frustrated by bad solder joints. Then, I discovered a Weller thermostat controlled iron, and get a perfect joint every time. Not everyone knows there are better ways to do things.
  - webstrand 3y ago
    Your experience soldering is a much better response. You present a concrete suggestion for use a weller thermostat controlled iron. But you did not present a concrete suggestion for an alternative to the C pre-processor. You could do this with C++ templates, for instance. But the LESS and SWAP operations may or may not get inlined. With the C pre-processor you can be certain that the operations get inlined, since no other alternative interpretation is available to the compiler.
    - WalterBright 3y ago
      > But you did not present a concrete suggestion for an alternative to the C pre-processor. If someone asked, I would. But since I do have a dog in that hunt, I felt it would be more appropriate for others to make a suggestion, as there are several.

eesmith 3y ago

Along the same lines, I use Christopher Swenson's sort.h at https://github.com/swenson/sort/ https://github.com/swenson/sort/ You get the choice of many sorting routines, including: Timsort (stable) Quicksort Merge sort (stable) In-place merge sort (not stable) Shellsort Binary insertion sort Heapsort Selection sort (this is really only here for comparison) Grail sort (stable) Sqrt Sort (stable, based on Grail sort, also by Andrey Astrelin).

syockit 3y ago

Today I learned that for modern processors, quicksort code is small enough that the compiler can inline them if the definition is visible during compilation. See here for comparison of isort function implemented using plain static functions vs the macro in TFA: https://godbolt.org/z/arGjPGhKE https://godbolt.org/z/arGjPGhKE . It's not as flexible as the macro form (not being able to pass two arrays at once like the sortByAge example in TFA), but I figure it should be friendlier to debuggers (though with all the inlining the experience is not going to be that great either). IIRC, if LTO is enabled the calls to the less and swap functions can also be inlined even if the generic function is compiled to a separate translation unit. Haven't tried it for the quick sort code above, but I found that out for some other thing I experimented with.

uecker 3y ago
Did you try inline as well? Why are they not as flexible as the macro? Couldn't the swap not also process two arrays?
- syockit 3y ago
  The function is already inlined because the implementation is visible. You can check the assembly, it has no calls to the compare and swap functions. I guess you're right, since the function accepts a void pointer, it could also point to an array of two array pointers. So yes, it can also process two arrays.

vrglvrglvrgl 3y ago

[dead]

dale_glass 3y ago

On one hand, neat. On the other hand, I think it's sad that so much time and brainpower is going on contriving ways to get bad tooling to do something, rather than on the actual meat of the problem solving. You'd think that in 50 years somebody could have invented a better preprocessor, and save the need for all the while(0) and other trickery needed for macros.

nuancebydefault 3y ago

I like C a lot. One big advantage of the language is that its complete syntax and standard runtime functions can fit in one brain. That said, I hate the way a lot of programmers use the preprocessor. For me, macros should be just simple expressions or functions (i mean they sohould be invokeable like functions) . But very often, there's a lot of magic inside macros, making them hard to use, let alone understand.