Re: A qsort template

On Fri, Jul 2, 2021 at 4:39 AM John Naylor <john(dot)naylor(at)enterprisedb(dot)com> wrote:
> For item pointers, it made sense to try doing math to reduce the number of branches. That made things worse, so let's try the opposite: Increase the number of branches so we do less math. In the attached patch (applies on top of your 0012 and a .txt to avoid confusing the CF bot), I test a new comparator with this approach, and also try a wider range of thresholds. The thresholds don't seem to make any noticeable difference with this data type, but the new comparator (cmp=ids below) gives a nice speedup in this test:

> NOTICE: [traditional qsort] order=random, threshold=7, cmp=32, test=0, time=4.964657

> NOTICE: order=random, threshold=7, cmp=std, test=0, time=2.810627

> NOTICE: order=random, threshold=7, cmp=ids, test=0, time=1.692711

Oooh. So, the awkwardness of the 64 maths with unaligned inputs (even
though we obtain all inputs with 16 bit loads) was hurting, and you
realised the same sort of thing might be happening also with the 32
bit version and went the other way. (It'd be nice to understand
exactly why.)

I tried your 16 bit comparison version on Intel, AMD and Apple CPUs
and the results were all in the same ballpark. For random input, I
see something like ~1.7x speedup over traditional qsort from
specialising (cmp=std), and ~2.7x from going 16 bit (cmp=ids). For
increasing and decreasing input, it's ~2x speedup from specialising
and ~4x speedup from going 16 bit. Beautiful.

One thing I'm wondering about is whether it's worth having stuff to
support future experimentation like ST_SORT_SMALL_THRESHOLD and
ST_COMPARE_RET_TYPE in the tree, or whether we should pare it back to
the minimal changes that definitely produce results. I think I'd like
to keep those changes: even if it may be some time, possibly an
infinite amount, before we figure out how to tune the thresholds
profitably, giving them names instead of using magic numbers seems
like progress.

The Alexandrescu talk was extremely entertaining, thanks.