Re: A qsort template

Hi,

I've run a few tests to get some feel for the effects of various
comparators on Datums containing int32. I've attached the full
results, as well as the (messy) patch which applies on top of 0012 to
run the tests. I'll excerpt some of those results as I go through them
here. For now, I only ran input orders of sorted, random, and
reversed.

1) Specializing

This is a win in all cases, including SQL-callable comparators (the
case here is for _bt_sort_array_elements).

NOTICE: [traditional qsort] size=8MB, order=random, cmp=arg, test=2,
time=0.140526
NOTICE: [inlined] size=8MB, order=random, cmp=inline, test=0, time=0.085023

NOTICE: [SQL arg] size=8MB, order=random, cmp=SQL-arg, test=2, time=0.256708
NOTICE: [SQL inlined] size=8MB, order=random, cmp=SQL-inline, test=0,
time=0.192063

2) Branchless operations

The int case is for how to perform the comparison, and the SQL case is
referring to how to reverse the sort order.Surprisingly, they don't
seem to help for direct comparisons, and in fact they seem worse. I'll
have to dig a bit deeper to be sure, but it's not looking good now.

NOTICE: [inlined] size=8MB, order=random, cmp=inline, test=2, time=0.084781
NOTICE: [branchless] size=8MB, order=random, cmp=branchless, test=0,
time=0.091837

NOTICE: [SQL inlined] size=8MB, order=random, cmp=SQL-inline, test=2,
time=0.192018
NOTICE: [SQL inlined reverse] size=8MB, order=random,
cmp=SQL-inline-rev, test=0, time=0.190797

When the effect is reversing a list, the direct comparisons seem much
worse, and the SQL ones aren't helped.

NOTICE: [inlined] size=8MB, order=decreasing, cmp=inline, test=2, time=0.024963
NOTICE: [branchless] size=8MB, order=decreasing, cmp=branchless,
test=0, time=0.036423

NOTICE: [SQL inlined] size=8MB, order=decreasing, cmp=SQL-inline,
test=0, time=0.125182
NOTICE: [SQL inlined reverse] size=8MB, order=increasing,
cmp=SQL-inline-rev, test=0, time=0.127051

--
Since I have a couple more planned tests, I'll keep a running tally on
the current state of the patch set so that summaries are not scattered
over many emails:

0001 - bsearch and unique is good to have, and we can keep the return
type pending further tests
0002/3 - I've yet to see a case where branchless comparators win, but
other than that, these are good. Notational improvement and not
performance sensitive.

0004/5 - Computing the arguments slows it down, but accessing the
underlying int16s gives an improvement. [1] Haven't done an in-situ
test on VACUUM. Could be worth it for pg15, since I imagine the
proposals for dead tuple storage won't be ready this cycle.
0006 - I expect this to be slower too. I also wonder if this could
also use the global function in 0004 once it's improved.

0007 - untested

0008 - Good performance in microbenchmarks, no in-situ testing.
Inlined reversal is not worth the binary space or notational overhead.

0009 - Based on 0004, I would guess that computing the arguments is
too slow. Not sure how to test in-situ to see if specializing helps.

0010 - Thresholds on my TODO list.

0011 - A simple correction -- I'll go ahead and commit this.

v3-0001 comparators for abbreviated keys - Clearly a win, especially
for the "unsigned" case [2]. There are still possible improvements,
but they seem like a pg16 project(s).

[1] https://www.postgresql.org/message-id/CA%2BhUKG%2BS5SMoG8Z2PHj0bsK70CxVLgqQR1orQJq6Cjgibu26vA%40mail.gmail.com
[2] https://www.postgresql.org/message-id/CAFBsxsEFGAJ9eBpQVb5a86BE93WER3497zn2OT5wbjm1HHcqgA%40mail.gmail.com
(I just realized in that message I didn't attach the script for that,
and also attached an extra draft spreadsheet. I'll improve the tests
and rerun later)

--
John Naylor
EDB: http://www.enterprisedb.com