Re: A qsort template

I wrote:

> > 0010 - Thresholds on my TODO list.
>
> I did some basic tests on the insertion sort thresholds, and it looks
> like we could safely and profitably increase the current value from 7
> to 20 or so, in line with other more recent implementations. I've
> attached an addendum on top of 0012 and the full test results on an
> Intel Coffee Lake machine with gcc 11.1. I found that the object test
> setup in 0012 had some kind of bug that was comparing the pointer of
> the object array. Rather than fix that, I decided to use Datums, but
> with the two extremes in comparator: simple branching with machine
> instructions vs. a SQL-callable function. The papers I've read
> indicate the results for Datum sizes would not be much different for
> small structs. The largest existing sort element is SortTuple, but
> that's only 24 bytes and has a bulky comparator as well.
>
> The first thing to note is that I rejected outright any testing of a
> "middle value" where the pivot is simply the middle of the array. Even
> the Bently and McIlroy paper which is the reference for our
> implementation says "The range that consists of the single integer 7
> could be eliminated, but has been left adjustable because on some
> machines larger ranges are a few percent better".
>
> I tested thresholds up to 64, which is where I guessed results to get
> worse (most implementations are smaller than that). Here are the best
> thresholds at a quick glance:
>
> - elementary comparator:
>
> random: 16 or greater
> decreasing, rotate: get noticeably better all the way up to 64
> organ: little difference, but seems to get better all the way up to 64
> 0/1: seems to get worse above 20
>
> - SQL-callable comparator:
>
> random: between 12 and 20, but slight differences until 32
> decreasing, rotate: get noticeably better all the way up to 64
> organ: seems best at 12, but slight differences until 32
> 0/1: slight differences
>
> Based on these tests and this machine, it seems 20 is a good default
> value. I'll repeat this test on one older Intel and one non-Intel
> platform with older compilers.

The above was an Intel Comet Lake / gcc 11, and I've run the same test
on a Haswell-era Xeon / gcc 8 and a Power8 machine / gcc 4.8. The
results on those machines are pretty close to the above (full results
attached). The noticeable exception is the Power8 on random input with
a slow comparator -- those measurements there are more random than
others so we can't draw conclusions from them, but the deviations are
small in any case. I'm still thinking 20 or so is about right.

I've put a lot out here recently, so I'll take a break now and come
back in a few weeks.

(no running tally here because the conclusions haven't changed since
last message)
-- 
John Naylor
EDB: http://www.enterprisedb.com