Re: A qsort template

On Fri, Jul 30, 2021 at 12:34 PM John Naylor
<john.naylor@enterprisedb.com> wrote:
> I got around to getting a benchmark together to serve as a starting point. I based it off something I got from the archives, but don't remember where (I seem to remember Tomas Vondra wrote the original, but not sure). To start I just used types that were there already -- int, text, numeric. The latter two won't be helped by this patch, but I wanted to keep something like that so we can see what kind of noise variation there is. I'll probably cut text out in the future and just keep numeric for that purpose.

Thanks, that's very useful.

> I've attached both the script and a crude spreadsheet. I'll try to figure out something nicer for future tests, and maybe some graphs. The "comparison" sheet has the results side by side (min of five). There are 6 distributions of values:
> - random
> - sorted
> - "almost sorted"
> - reversed
> - organ pipe (first half ascending, second half descending)
> - rotated (sorted but then put the smallest at the end)
> - random 0s/1s
>
> I included both "select a" and "select *" to make sure we have the recent datum sort optimization represented. The results look pretty good for ints -- about the same speed up master gets going from tuple sorts to datum sorts, and those got faster in turn also.

Great!  I saw similar sorts of numbers.  It's really just a few
crumbs, nothing compared to the gains David just found over in the
thread "Use generation context to speed up tuplesorts", but on the
bright side, these crumbs will be magnified by that work.

> Next I think I'll run microbenchmarks on int64s with the test harness you attached earlier, and experiment with the qsort parameters a bit.

Cool.  I haven't had much luck experimenting with that yet, though I
consider the promotion from magic numbers to names as an improvement
in any case.

> I'm also attaching your tuplesort patch so others can see what exactly I'm comparing.

We've been bouncing around quite a few different ideas and patches in
this thread; soon I'll try to bring it back to one patch set with the
ideas that are looking good so far in a more tidied up form.  For the
tupesort.c part, I added some TODO notes in
v3-0001-WIP-Accelerate-tuple-sorting-for-common-types.patch's commit
message (see reply to Peter).