Hello,
Inspired by the recent discussions[1][2] around sort improvements, I took a look around the code and noticed the use of
asomewhat naive version of insertion sort within the broader quicksort code.
The current implementation (see sort_template.h) is practically the textbook version of insertion sort:
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP; pm += ST_POINTER_STEP)
for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0; pl -= ST_POINTER_STEP)
DO_SWAP(pl, pl - ST_POINTER_STEP);
I propose to rather use the slightly more efficient variant of insertion sort where only a single assignment instead of
afully-fledged swap is performed in the inner loop:
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP; pm += ST_POINTER_STEP) {
DO_COPY(pm_temp, pm); /* pm_temp <- copy of pm */
pl = pm - ST_POINTER_STEP;
for (; pl >= a && DO_COMPARE(pl, pm_temp) > 0; pl -= ST_POINTER_STEP)
DO_ASSIGN(pl + ST_POINTER_STEP, pl); /* pl + 1 <- pl */
DO_COPY(pl + ST_POINTER_STEP, pm_temp); /* pl + 1 <- copy of pm_temp */
}
DO_ASSIGN and DO_COPY macros would have to be declared analogue to DO_SWAP via the template.
There is obviously a trade-off involved here as O(1) extra memory is required to hold the temporary variable and
DO_COPYmight be expensive if the sort element is large. In case of single datum sort with trivial data types this would
notbe a big issue. For large tuples on the other hand it could mean a significant overhead that might not be made up
forby the improved inner loop. One might want to limit this algorithm to a certain maximum tuple size and use the
originalinsertion sort version for larger elements (this could be decided at compile-time via sort_template.h).
Anyways, there might be some low hanging fruit here. If it turns out to be significantly faster one might even consider
increasingthe insertion sort threshold from < 7 to < 10 sort elements. But that is a whole other discussion for another
day.
Has anyone tested such an approach before? Please let me know your thoughts.
Cheers,
Benjamin
[1] https://www.postgresql.org/message-id/flat/CAFBsxsHanJTsX9DNJppXJxwg3bU%2BYQ6pnmSfPM0uvYUaFdwZdQ%40mail.gmail.com
[2] https://www.postgresql.org/message-id/flat/CAApHDvoTTtoQYfp3d0kTPF6y1pjexgLwquzKmjzvjC9NCw4RGw%40mail.gmail.com
--
Benjamin Coutu
http://www.zeyos.com
