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.
--
Running tally of patchset:
0001 - bsearch and unique is good to have, and we can keep the return
type pending further tests -- if none happen this cycle, suggest
committing this without the return type symbol.
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 - Suggest leaving out the middle threshold and setting the
insertion sort threshold to ~20. Might also name them
ST_INSERTION_SORT_THRESHOLD and ST_NINTHER_THRESHOLD. (TODO: test on
other platforms)
0011 - Committed.
v3-0001 comparators for abbreviated keys - Clearly a win in this state
already, especially
for the "unsigned" case [2]. (gist untested) There are additional
possible improvements mentioned,
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
(TODO: refine test)
--
John Naylor
EDB: http://www.enterprisedb.com
NOTICE: [direct] size=8MB, order=random, threshold=7, test=0, time=0.084503
NOTICE: [direct] size=8MB, order=random, threshold=7, test=1, time=0.087980
NOTICE: [direct] size=8MB, order=random, threshold=7, test=2, time=0.084299
NOTICE: [direct] size=8MB, order=random, threshold=12, test=0, time=0.081893
NOTICE: [direct] size=8MB, order=random, threshold=12, test=1, time=0.081907
NOTICE: [direct] size=8MB, order=random, threshold=12, test=2, time=0.081943
NOTICE: [direct] size=8MB, order=random, threshold=16, test=0, time=0.080810
NOTICE: [direct] size=8MB, order=random, threshold=16, test=1, time=0.080793
NOTICE: [direct] size=8MB, order=random, threshold=16, test=2, time=0.080922
NOTICE: [direct] size=8MB, order=random, threshold=20, test=0, time=0.080399
NOTICE: [direct] size=8MB, order=random, threshold=20, test=1, time=0.080433
NOTICE: [direct] size=8MB, order=random, threshold=20, test=2, time=0.080413
NOTICE: [direct] size=8MB, order=random, threshold=24, test=0, time=0.080342
NOTICE: [direct] size=8MB, order=random, threshold=24, test=1, time=0.080446
NOTICE: [direct] size=8MB, order=random, threshold=24, test=2, time=0.080339
NOTICE: [direct] size=8MB, order=random, threshold=28, test=0, time=0.080168
NOTICE: [direct] size=8MB, order=random, threshold=28, test=1, time=0.080215
NOTICE: [direct] size=8MB, order=random, threshold=28, test=2, time=0.080134
NOTICE: [direct] size=8MB, order=random, threshold=32, test=0, time=0.079902
NOTICE: [direct] size=8MB, order=random, threshold=32, test=1, time=0.080090
NOTICE: [direct] size=8MB, order=random, threshold=32, test=2, time=0.080099
NOTICE: [direct] size=8MB, order=random, threshold=64, test=0, time=0.080887
NOTICE: [direct] size=8MB, order=random, threshold=64, test=1, time=0.080847
NOTICE: [direct] size=8MB, order=random, threshold=64, test=2, time=0.080806
NOTICE: [direct] size=8MB, order=decreasing, threshold=7, test=0, time=0.026983
NOTICE: [direct] size=8MB, order=decreasing, threshold=7, test=1, time=0.027058
NOTICE: [direct] size=8MB, order=decreasing, threshold=7, test=2, time=0.027052
NOTICE: [direct] size=8MB, order=decreasing, threshold=12, test=0,
time=0.024109
NOTICE: [direct] size=8MB, order=decreasing, threshold=12, test=1,
time=0.024440
NOTICE: [direct] size=8MB, order=decreasing, threshold=12, test=2,
time=0.024165
NOTICE: [direct] size=8MB, order=decreasing, threshold=16, test=0,
time=0.023262
NOTICE: [direct] size=8MB, order=decreasing, threshold=16, test=1,
time=0.023237
NOTICE: [direct] size=8MB, order=decreasing, threshold=16, test=2,
time=0.023260
NOTICE: [direct] size=8MB, order=decreasing, threshold=20, test=0,
time=0.022600
NOTICE: [direct] size=8MB, order=decreasing, threshold=20, test=1,
time=0.022614
NOTICE: [direct] size=8MB, order=decreasing, threshold=20, test=2,
time=0.022609
NOTICE: [direct] size=8MB, order=decreasing, threshold=24, test=0,
time=0.024397
NOTICE: [direct] size=8MB, order=decreasing, threshold=24, test=1,
time=0.020750
NOTICE: [direct] size=8MB, order=decreasing, threshold=24, test=2,
time=0.020817
NOTICE: [direct] size=8MB, order=decreasing, threshold=28, test=0,
time=0.018351
NOTICE: [direct] size=8MB, order=decreasing, threshold=28, test=1,
time=0.018369
NOTICE: [direct] size=8MB, order=decreasing, threshold=28, test=2,
time=0.018357
NOTICE: [direct] size=8MB, order=decreasing, threshold=32, test=0,
time=0.016055
NOTICE: [direct] size=8MB, order=decreasing, threshold=32, test=1,
time=0.016049
NOTICE: [direct] size=8MB, order=decreasing, threshold=32, test=2,
time=0.016084
NOTICE: [direct] size=8MB, order=decreasing, threshold=64, test=0,
time=0.013842
NOTICE: [direct] size=8MB, order=decreasing, threshold=64, test=1,
time=0.013862
NOTICE: [direct] size=8MB, order=decreasing, threshold=64, test=2,
time=0.013839
NOTICE: [direct] size=8MB, order=organ, threshold=7, test=0, time=0.033074
NOTICE: [direct] size=8MB, order=organ, threshold=7, test=1, time=0.033080
NOTICE: [direct] size=8MB, order=organ, threshold=7, test=2, time=0.033043
NOTICE: [direct] size=8MB, order=organ, threshold=12, test=0, time=0.032984
NOTICE: [direct] size=8MB, order=organ, threshold=12, test=1, time=0.032922
NOTICE: [direct] size=8MB, order=organ, threshold=12, test=2, time=0.032658
NOTICE: [direct] size=8MB, order=organ, threshold=16, test=0, time=0.032258
NOTICE: [direct] size=8MB, order=organ, threshold=16, test=1, time=0.032123
NOTICE: [direct] size=8MB, order=organ, threshold=16, test=2, time=0.031859
NOTICE: [direct] size=8MB, order=organ, threshold=20, test=0, time=0.031229
NOTICE: [direct] size=8MB, order=organ, threshold=20, test=1, time=0.031656
NOTICE: [direct] size=8MB, order=organ, threshold=20, test=2, time=0.031333
NOTICE: [direct] size=8MB, order=organ, threshold=24, test=0, time=0.031113
NOTICE: [direct] size=8MB, order=organ, threshold=24, test=1, time=0.031015
NOTICE: [direct] size=8MB, order=organ, threshold=24, test=2, time=0.031010
NOTICE: [direct] size=8MB, order=organ, threshold=28, test=0, time=0.031000
NOTICE: [direct] size=8MB, order=organ, threshold=28, test=1, time=0.031003
NOTICE: [direct] size=8MB, order=organ, threshold=28, test=2, time=0.031086
NOTICE: [direct] size=8MB, order=organ, threshold=32, test=0, time=0.030584
NOTICE: [direct] size=8MB, order=organ, threshold=32, test=1, time=0.030645
NOTICE: [direct] size=8MB, order=organ, threshold=32, test=2, time=0.030505
NOTICE: [direct] size=8MB, order=organ, threshold=64, test=0, time=0.030736
NOTICE: [direct] size=8MB, order=organ, threshold=64, test=1, time=0.030655
NOTICE: [direct] size=8MB, order=organ, threshold=64, test=2, time=0.030575
NOTICE: [direct] size=8MB, order=rotate, threshold=7, test=0, time=0.036208
NOTICE: [direct] size=8MB, order=rotate, threshold=7, test=1, time=0.036199
NOTICE: [direct] size=8MB, order=rotate, threshold=7, test=2, time=0.036066
NOTICE: [direct] size=8MB, order=rotate, threshold=12, test=0, time=0.034699
NOTICE: [direct] size=8MB, order=rotate, threshold=12, test=1, time=0.034268
NOTICE: [direct] size=8MB, order=rotate, threshold=12, test=2, time=0.034179
NOTICE: [direct] size=8MB, order=rotate, threshold=16, test=0, time=0.033336
NOTICE: [direct] size=8MB, order=rotate, threshold=16, test=1, time=0.033413
NOTICE: [direct] size=8MB, order=rotate, threshold=16, test=2, time=0.033532
NOTICE: [direct] size=8MB, order=rotate, threshold=20, test=0, time=0.032425
NOTICE: [direct] size=8MB, order=rotate, threshold=20, test=1, time=0.032118
NOTICE: [direct] size=8MB, order=rotate, threshold=20, test=2, time=0.032819
NOTICE: [direct] size=8MB, order=rotate, threshold=24, test=0, time=0.026697
NOTICE: [direct] size=8MB, order=rotate, threshold=24, test=1, time=0.026226
NOTICE: [direct] size=8MB, order=rotate, threshold=24, test=2, time=0.026693
NOTICE: [direct] size=8MB, order=rotate, threshold=28, test=0, time=0.023723
NOTICE: [direct] size=8MB, order=rotate, threshold=28, test=1, time=0.023759
NOTICE: [direct] size=8MB, order=rotate, threshold=28, test=2, time=0.023900
NOTICE: [direct] size=8MB, order=rotate, threshold=32, test=0, time=0.021496
NOTICE: [direct] size=8MB, order=rotate, threshold=32, test=1, time=0.021579
NOTICE: [direct] size=8MB, order=rotate, threshold=32, test=2, time=0.021648
NOTICE: [direct] size=8MB, order=rotate, threshold=64, test=0, time=0.019228
NOTICE: [direct] size=8MB, order=rotate, threshold=64, test=1, time=0.019275
NOTICE: [direct] size=8MB, order=rotate, threshold=64, test=2, time=0.019456
NOTICE: [direct] size=8MB, order=0_1, threshold=7, test=0, time=0.004430
NOTICE: [direct] size=8MB, order=0_1, threshold=7, test=1, time=0.004445
NOTICE: [direct] size=8MB, order=0_1, threshold=7, test=2, time=0.004439
NOTICE: [direct] size=8MB, order=0_1, threshold=12, test=0, time=0.004465
NOTICE: [direct] size=8MB, order=0_1, threshold=12, test=1, time=0.004493
NOTICE: [direct] size=8MB, order=0_1, threshold=12, test=2, time=0.004500
NOTICE: [direct] size=8MB, order=0_1, threshold=16, test=0, time=0.004462
NOTICE: [direct] size=8MB, order=0_1, threshold=16, test=1, time=0.004480
NOTICE: [direct] size=8MB, order=0_1, threshold=16, test=2, time=0.004507
NOTICE: [direct] size=8MB, order=0_1, threshold=20, test=0, time=0.004491
NOTICE: [direct] size=8MB, order=0_1, threshold=20, test=1, time=0.004467
NOTICE: [direct] size=8MB, order=0_1, threshold=20, test=2, time=0.004442
NOTICE: [direct] size=8MB, order=0_1, threshold=24, test=0, time=0.004447
NOTICE: [direct] size=8MB, order=0_1, threshold=24, test=1, time=0.004803
NOTICE: [direct] size=8MB, order=0_1, threshold=24, test=2, time=0.005271
NOTICE: [direct] size=8MB, order=0_1, threshold=28, test=0, time=0.005306
NOTICE: [direct] size=8MB, order=0_1, threshold=28, test=1, time=0.005252
NOTICE: [direct] size=8MB, order=0_1, threshold=28, test=2, time=0.005264
NOTICE: [direct] size=8MB, order=0_1, threshold=32, test=0, time=0.005273
NOTICE: [direct] size=8MB, order=0_1, threshold=32, test=1, time=0.005278
NOTICE: [direct] size=8MB, order=0_1, threshold=32, test=2, time=0.005268
NOTICE: [direct] size=8MB, order=0_1, threshold=64, test=0, time=0.005260
NOTICE: [direct] size=8MB, order=0_1, threshold=64, test=1, time=0.005257
NOTICE: [direct] size=8MB, order=0_1, threshold=64, test=2, time=0.005264
NOTICE: [direct] size=8MB, order=increasing, threshold=7, test=0, time=0.000729
NOTICE: [direct] size=8MB, order=increasing, threshold=7, test=1, time=0.000731
NOTICE: [direct] size=8MB, order=increasing, threshold=7, test=2, time=0.000734
NOTICE: [direct] size=8MB, order=increasing, threshold=12, test=0,
time=0.000731
NOTICE: [direct] size=8MB, order=increasing, threshold=12, test=1,
time=0.000734
NOTICE: [direct] size=8MB, order=increasing, threshold=12, test=2,
time=0.000728
NOTICE: [direct] size=8MB, order=increasing, threshold=16, test=0,
time=0.000732
NOTICE: [direct] size=8MB, order=increasing, threshold=16, test=1,
time=0.000752
NOTICE: [direct] size=8MB, order=increasing, threshold=16, test=2,
time=0.000732
NOTICE: [direct] size=8MB, order=increasing, threshold=20, test=0,
time=0.000732
NOTICE: [direct] size=8MB, order=increasing, threshold=20, test=1,
time=0.000738
NOTICE: [direct] size=8MB, order=increasing, threshold=20, test=2,
time=0.000730
NOTICE: [direct] size=8MB, order=increasing, threshold=24, test=0,
time=0.000728
NOTICE: [direct] size=8MB, order=increasing, threshold=24, test=1,
time=0.000734
NOTICE: [direct] size=8MB, order=increasing, threshold=24, test=2,
time=0.000735
NOTICE: [direct] size=8MB, order=increasing, threshold=28, test=0,
time=0.000734
NOTICE: [direct] size=8MB, order=increasing, threshold=28, test=1,
time=0.000730
NOTICE: [direct] size=8MB, order=increasing, threshold=28, test=2,
time=0.000732
NOTICE: [direct] size=8MB, order=increasing, threshold=32, test=0,
time=0.000739
NOTICE: [direct] size=8MB, order=increasing, threshold=32, test=1,
time=0.000732
NOTICE: [direct] size=8MB, order=increasing, threshold=32, test=2,
time=0.000762
NOTICE: [direct] size=8MB, order=increasing, threshold=64, test=0,
time=0.000735
NOTICE: [direct] size=8MB, order=increasing, threshold=64, test=1,
time=0.000735
NOTICE: [direct] size=8MB, order=increasing, threshold=64, test=2,
time=0.000758
NOTICE: [SQL inlined] size=8MB, order=random, threshold=7, test=0,
time=0.168111
NOTICE: [SQL inlined] size=8MB, order=random, threshold=7, test=1,
time=0.159677
NOTICE: [SQL inlined] size=8MB, order=random, threshold=7, test=2,
time=0.155916
NOTICE: [SQL inlined] size=8MB, order=random, threshold=12, test=0,
time=0.152520
NOTICE: [SQL inlined] size=8MB, order=random, threshold=12, test=1,
time=0.152567
NOTICE: [SQL inlined] size=8MB, order=random, threshold=12, test=2,
time=0.152824
NOTICE: [SQL inlined] size=8MB, order=random, threshold=16, test=0,
time=0.153694
NOTICE: [SQL inlined] size=8MB, order=random, threshold=16, test=1,
time=0.153925
NOTICE: [SQL inlined] size=8MB, order=random, threshold=16, test=2,
time=0.153429
NOTICE: [SQL inlined] size=8MB, order=random, threshold=20, test=0,
time=0.152774
NOTICE: [SQL inlined] size=8MB, order=random, threshold=20, test=1,
time=0.152820
NOTICE: [SQL inlined] size=8MB, order=random, threshold=20, test=2,
time=0.152595
NOTICE: [SQL inlined] size=8MB, order=random, threshold=24, test=0,
time=0.154290
NOTICE: [SQL inlined] size=8MB, order=random, threshold=24, test=1,
time=0.154215
NOTICE: [SQL inlined] size=8MB, order=random, threshold=24, test=2,
time=0.154039
NOTICE: [SQL inlined] size=8MB, order=random, threshold=28, test=0,
time=0.157061
NOTICE: [SQL inlined] size=8MB, order=random, threshold=28, test=1,
time=0.153073
NOTICE: [SQL inlined] size=8MB, order=random, threshold=28, test=2,
time=0.153240
NOTICE: [SQL inlined] size=8MB, order=random, threshold=32, test=0,
time=0.156380
NOTICE: [SQL inlined] size=8MB, order=random, threshold=32, test=1,
time=0.156445
NOTICE: [SQL inlined] size=8MB, order=random, threshold=32, test=2,
time=0.156319
NOTICE: [SQL inlined] size=8MB, order=random, threshold=64, test=0,
time=0.168079
NOTICE: [SQL inlined] size=8MB, order=random, threshold=64, test=1,
time=0.167869
NOTICE: [SQL inlined] size=8MB, order=random, threshold=64, test=2,
time=0.167722
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=7, test=0,
time=0.100694
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=7, test=1,
time=0.100685
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=7, test=2,
time=0.100688
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=12, test=0,
time=0.095798
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=12, test=1,
time=0.095959
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=12, test=2,
time=0.095818
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=16, test=0,
time=0.096971
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=16, test=1,
time=0.096709
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=16, test=2,
time=0.100766
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=20, test=0,
time=0.088509
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=20, test=1,
time=0.088457
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=20, test=2,
time=0.088391
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=24, test=0,
time=0.085213
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=24, test=1,
time=0.085320
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=24, test=2,
time=0.085160
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=28, test=0,
time=0.074377
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=28, test=1,
time=0.074210
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=28, test=2,
time=0.076532
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=32, test=0,
time=0.070267
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=32, test=1,
time=0.070133
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=32, test=2,
time=0.070070
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=64, test=0,
time=0.065675
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=64, test=1,
time=0.065708
NOTICE: [SQL inlined] size=8MB, order=decreasing, threshold=64, test=2,
time=0.065403
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=7, test=0, time=0.104277
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=7, test=1, time=0.104239
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=7, test=2, time=0.104218
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=12, test=0,
time=0.102053
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=12, test=1,
time=0.102026
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=12, test=2,
time=0.102196
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=16, test=0,
time=0.104658
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=16, test=1,
time=0.106226
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=16, test=2,
time=0.106289
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=20, test=0,
time=0.108680
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=20, test=1,
time=0.104593
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=20, test=2,
time=0.104575
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=24, test=0,
time=0.106359
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=24, test=1,
time=0.106307
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=24, test=2,
time=0.106543
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=28, test=0,
time=0.105146
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=28, test=1,
time=0.105170
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=28, test=2,
time=0.105120
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=32, test=0,
time=0.108710
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=32, test=1,
time=0.108658
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=32, test=2,
time=0.108695
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=64, test=0,
time=0.122257
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=64, test=1,
time=0.122182
NOTICE: [SQL inlined] size=8MB, order=organ, threshold=64, test=2,
time=0.122325
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=7, test=0,
time=0.179572
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=7, test=1,
time=0.179514
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=7, test=2,
time=0.179475
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=12, test=0,
time=0.174136
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=12, test=1,
time=0.170401
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=12, test=2,
time=0.170497
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=16, test=0,
time=0.168404
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=16, test=1,
time=0.168415
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=16, test=2,
time=0.168518
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=20, test=0,
time=0.156971
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=20, test=1,
time=0.156866
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=20, test=2,
time=0.156613
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=24, test=0,
time=0.148548
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=24, test=1,
time=0.148574
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=24, test=2,
time=0.149027
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=28, test=0,
time=0.132972
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=28, test=1,
time=0.136334
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=28, test=2,
time=0.132893
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=32, test=0,
time=0.123577
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=32, test=1,
time=0.123669
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=32, test=2,
time=0.121909
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=64, test=0,
time=0.113562
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=64, test=1,
time=0.113854
NOTICE: [SQL inlined] size=8MB, order=rotate, threshold=64, test=2,
time=0.113732
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=7, test=0, time=0.010306
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=7, test=1, time=0.010328
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=7, test=2, time=0.010335
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=12, test=0, time=0.010329
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=12, test=1, time=0.010323
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=12, test=2, time=0.010340
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=16, test=0, time=0.010488
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=16, test=1, time=0.010485
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=16, test=2, time=0.010505
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=20, test=0, time=0.010319
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=20, test=1, time=0.010352
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=20, test=2, time=0.010361
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=24, test=0, time=0.010502
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=24, test=1, time=0.010510
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=24, test=2, time=0.010487
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=28, test=0, time=0.010336
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=28, test=1, time=0.010313
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=28, test=2, time=0.010312
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=32, test=0, time=0.010492
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=32, test=1, time=0.010486
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=32, test=2, time=0.010499
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=64, test=0, time=0.010674
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=64, test=1, time=0.010691
NOTICE: [SQL inlined] size=8MB, order=0_1, threshold=64, test=2, time=0.010668
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=7, test=0,
time=0.003660
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=7, test=1,
time=0.003659
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=7, test=2,
time=0.003658
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=12, test=0,
time=0.003660
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=12, test=1,
time=0.003661
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=12, test=2,
time=0.003660
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=16, test=0,
time=0.003657
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=16, test=1,
time=0.003659
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=16, test=2,
time=0.003658
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=20, test=0,
time=0.003655
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=20, test=1,
time=0.003656
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=20, test=2,
time=0.003655
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=24, test=0,
time=0.003659
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=24, test=1,
time=0.003659
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=24, test=2,
time=0.003658
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=28, test=0,
time=0.003658
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=28, test=1,
time=0.003660
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=28, test=2,
time=0.003661
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=32, test=0,
time=0.003659
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=32, test=1,
time=0.003660
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=32, test=2,
time=0.003658
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=64, test=0,
time=0.003659
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=64, test=1,
time=0.003659
NOTICE: [SQL inlined] size=8MB, order=increasing, threshold=64, test=2,
time=0.003657
diff --git a/src/test/modules/test_sort_perf/Makefile
b/src/test/modules/test_sort_perf/Makefile
index ab7f8e24b0..c99fac0845 100644
--- a/src/test/modules/test_sort_perf/Makefile
+++ b/src/test/modules/test_sort_perf/Makefile
@@ -6,12 +6,17 @@ DATA = test_sort_perf--1.0.sql
first: all
-test_sort_perf.o: test_sort_object_include.c test_sort_itemptr_include.c
+test_sort_perf.o: test_sort_object_include.c test_sort_itemptr_include.c
test_sort_datum_include.c test_sort_threshold_include.c
test_sort_object_include.c: make-object-tests.sh
./make-object-tests.sh > test_sort_object_include.c
test_sort_itemptr_include.c: make-itemptr-tests.sh
./make-itemptr-tests.sh > test_sort_itemptr_include.c
+test_sort_datum_include.c: make-datum-tests.sh
+ ./make-datum-tests.sh > test_sort_datum_include.c
+test_sort_threshold_include.c: make-threshold-tests.sh
+ ./make-threshold-tests.sh > test_sort_threshold_include.c
+
ifdef USE_PGXS
PG_CONFIG = pg_config
diff --git a/src/test/modules/test_sort_perf/make-datum-tests.sh
b/src/test/modules/test_sort_perf/make-datum-tests.sh
new file mode 100755
index 0000000000..69a04b18ab
--- /dev/null
+++ b/src/test/modules/test_sort_perf/make-datum-tests.sh
@@ -0,0 +1,146 @@
+#!/bin/sh
+
+# generate the function that runs all the tests
+echo "static void"
+echo "do_sort_datum(int nmegs)"
+echo "{"
+echo " size_t nobjects = (nmegs * 1024 * 1024) / sizeof(Datum);"
+echo " Datum *unsorted = malloc(sizeof(Datum) * nobjects);"
+echo " Datum *sorted = malloc(sizeof(Datum) * nobjects);"
+echo
+
+# for btree
+cat <<EOF
+
+ BTSortArrayContext cxt;
+ RegProcedure cmp_proc ;
+
+ // to keep from pulling in nbtree.h
+#define BTORDER_PROC 1
+
+ cmp_proc = get_opfamily_proc(INTEGER_BTREE_FAM_OID,
+ INT4OID,
+ INT4OID,
+ BTORDER_PROC);
+
+ fmgr_info(cmp_proc, &cxt.flinfo);
+ cxt.collation = DEFAULT_COLLATION_OID;
+ // we set cxt.reverse later
+
+EOF
+
+for order in random increasing decreasing ; do
+ echo " for (size_t i = 0; i < nobjects; ++i)"
+ echo " {"
+ if [ "$order" = "random" ] ; then
+ echo " int v = random();"
+ elif [ "$order" = "increasing" ] ; then
+ echo " int v = i + 16;"
+ elif [ "$order" = "decreasing" ] ; then
+ echo " int v = INT_MAX - i;"
+ fi
+ echo " unsorted[i] = Int32GetDatum(v);"
+echo " }"
+echo
+
+# traditional qsort
+echo " for (int i = 0; i < 3; ++i)"
+echo " {"
+echo " instr_time start_time, end_time;"
+echo " memcpy(sorted, unsorted, sizeof(Datum) * nobjects);"
+echo " INSTR_TIME_SET_CURRENT(start_time);"
+echo " qsort(sorted, nobjects, sizeof(Datum), btint4fastcmp);"
+echo " INSTR_TIME_SET_CURRENT(end_time);"
+echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+echo " elog(NOTICE, \"[traditional qsort] size=%dMB, order=$order,
cmp=arg, test=%d, time=%f\", nmegs, i, INSTR_TIME_GET_DOUBLE(end_time));"
+echo " }"
+
+# inlined
+echo " for (int i = 0; i < 3; ++i)"
+echo " {"
+echo " instr_time start_time, end_time;"
+echo " memcpy(sorted, unsorted, sizeof(Datum) * nobjects);"
+echo " INSTR_TIME_SET_CURRENT(start_time);"
+echo " qsort_int32(sorted, nobjects);"
+echo " INSTR_TIME_SET_CURRENT(end_time);"
+echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+echo " elog(NOTICE, \"[inlined] size=%dMB, order=$order,
cmp=inline, test=%d, time=%f\", nmegs, i, INSTR_TIME_GET_DOUBLE(end_time));"
+echo " }"
+
+# inlined and branchless
+echo " for (int i = 0; i < 3; ++i)"
+echo " {"
+echo " instr_time start_time, end_time;"
+echo " memcpy(sorted, unsorted, sizeof(Datum) * nobjects);"
+echo " INSTR_TIME_SET_CURRENT(start_time);"
+echo " qsort_int32_branchless(sorted, nobjects);"
+echo " INSTR_TIME_SET_CURRENT(end_time);"
+echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+echo " elog(NOTICE, \"[branchless] size=%dMB, order=$order,
cmp=branchless, test=%d, time=%f\", nmegs, i, INSTR_TIME_GET_DOUBLE(end_time));"
+echo " }"
+
+### B-tree forward
+
+echo "cxt.reverse = false;"
+
+# B-tree SQL-callable qsort arg
+echo " for (int i = 0; i < 3; ++i)"
+echo " {"
+echo " instr_time start_time, end_time;"
+echo " memcpy(sorted, unsorted, sizeof(Datum) * nobjects);"
+echo " INSTR_TIME_SET_CURRENT(start_time);"
+echo " qsort_arg((void *) sorted, nobjects, sizeof(Datum),
_bt_compare_array_elements, (void *) &cxt);"
+echo " INSTR_TIME_SET_CURRENT(end_time);"
+echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+echo " elog(NOTICE, \"[SQL arg] size=%dMB, order=$order,
cmp=SQL-arg, test=%d, time=%f\", nmegs, i, INSTR_TIME_GET_DOUBLE(end_time));"
+echo " }"
+
+# B-tree SQL-callable inlined
+echo " for (int i = 0; i < 3; ++i)"
+echo " {"
+echo " instr_time start_time, end_time;"
+echo " memcpy(sorted, unsorted, sizeof(Datum) * nobjects);"
+echo " INSTR_TIME_SET_CURRENT(start_time);"
+echo " qsort_bt_array_elements(sorted, nobjects, &cxt);"
+echo " INSTR_TIME_SET_CURRENT(end_time);"
+echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+echo " elog(NOTICE, \"[SQL inlined] size=%dMB, order=$order,
cmp=SQL-inline, test=%d, time=%f\", nmegs, i, INSTR_TIME_GET_DOUBLE(end_time));"
+echo " }"
+echo
+
+### Btree reversed
+
+echo "cxt.reverse = true;"
+
+# B-tree SQL-callable qsort arg (same as above, but with reversed comparator)
+echo " for (int i = 0; i < 3; ++i)"
+echo " {"
+echo " instr_time start_time, end_time;"
+echo " memcpy(sorted, unsorted, sizeof(Datum) * nobjects);"
+echo " INSTR_TIME_SET_CURRENT(start_time);"
+echo " qsort_arg((void *) sorted, nobjects, sizeof(Datum),
_bt_compare_array_elements, (void *) &cxt);"
+echo " INSTR_TIME_SET_CURRENT(end_time);"
+echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+echo " elog(NOTICE, \"[SQL arg reverse] size=%dMB, order=$order,
cmp=SQL-arg-rev, test=%d, time=%f\", nmegs, i,
INSTR_TIME_GET_DOUBLE(end_time));"
+echo " }"
+
+# B-tree SQL-callable inlined reversed
+echo " for (int i = 0; i < 3; ++i)"
+echo " {"
+echo " instr_time start_time, end_time;"
+echo " memcpy(sorted, unsorted, sizeof(Datum) * nobjects);"
+echo " INSTR_TIME_SET_CURRENT(start_time);"
+echo " qsort_bt_array_elements_reverse(sorted, nobjects, &cxt);"
+echo " INSTR_TIME_SET_CURRENT(end_time);"
+echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+echo " elog(NOTICE, \"[SQL inlined reverse] size=%dMB,
order=$order, cmp=SQL-inline-rev, test=%d, time=%f\", nmegs, i,
INSTR_TIME_GET_DOUBLE(end_time));"
+echo " }"
+echo
+
+
+
+done;
+
+echo " free(sorted);"
+echo " free(unsorted);"
+echo "}"
diff --git a/src/test/modules/test_sort_perf/make-threshold-tests.sh
b/src/test/modules/test_sort_perf/make-threshold-tests.sh
new file mode 100755
index 0000000000..633ab239d3
--- /dev/null
+++ b/src/test/modules/test_sort_perf/make-threshold-tests.sh
@@ -0,0 +1,142 @@
+#!/bin/sh
+
+# different values to test for insertion sorts
+#THRESHOLDS="7 12"
+THRESHOLDS="7 12 16 20 24 28 32 64"
+
+ORDERS="random decreasing organ rotate 0_1 increasing"
+
+
+for threshold in $THRESHOLDS ; do
+ cat << EOF
+
+#define ST_SORT qsort_int4direct_$threshold
+#define ST_ELEMENT_TYPE Datum
+#define ST_COMPARE(a, b) (btint4fastcmp(a, b))
+#define ST_SORT_SMALL_THRESHOLD $threshold
+#define ST_SCOPE static
+#define ST_DEFINE
+#define ST_DECLARE
+#include "lib/sort_template.h"
+
+#define ST_SORT qsort_bt_array_elements_$threshold
+#define ST_ELEMENT_TYPE Datum
+#define ST_COMPARE(a, b, cxt) \
+ DatumGetInt32(FunctionCall2Coll(&cxt->flinfo, cxt->collation, *a, *b))
+#define ST_COMPARE_ARG_TYPE BTSortArrayContext
+#define ST_SORT_SMALL_THRESHOLD $threshold
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+EOF
+done
+
+
+# generate the function that runs all the tests
+
+cat <<EOF
+static void
+do_sort_threshold(int nmegs)
+{
+ size_t nobjects = (nmegs * 1024 * 1024) / sizeof(Datum);
+ Datum *sorted = malloc(sizeof(Datum) * nobjects);
+
+ BTSortArrayContext cxt;
+ RegProcedure cmp_proc ;
+
+ // to keep from pulling in nbtree.h
+#define BTORDER_PROC 1
+
+ cmp_proc = get_opfamily_proc(INTEGER_BTREE_FAM_OID,
+ INT4OID,
+ INT4OID,
+ BTORDER_PROC);
+
+ fmgr_info(cmp_proc, &cxt.flinfo);
+ cxt.collation = DEFAULT_COLLATION_OID;
+ cxt.reverse = false;
+
+EOF
+
+# hard-code these
+for order in increasing random decreasing; do
+ echo " Datum *arr_$order = malloc(sizeof(Datum) * nobjects);"
+ echo " for (size_t i = 0; i < nobjects; ++i)"
+ echo " {"
+ if [ "$order" = "random" ] ; then
+ echo " int v = random();"
+ elif [ "$order" = "increasing" ] ; then
+ echo " int v = i + 1;"
+ elif [ "$order" = "decreasing" ] ; then
+ echo " int v = nobjects - i;"
+ fi
+ echo " arr_$order[i] = Int32GetDatum(v);"
+ echo " }"
+ echo
+done;
+
+# more complex orders
+cat <<EOF
+ /* organ pipe: first half increasing, second half decreasing */
+ Datum *arr_organ = malloc(sizeof(Datum) * nobjects);
+ for (size_t i = 0; i < nobjects / 2; ++i)
+ arr_organ[i] = Int32GetDatum(i + 1);
+ for (size_t i = nobjects / 2; i < nobjects; ++i)
+ arr_organ[i] = Int32GetDatum(nobjects - i);
+
+ /* rotate: increasing, then last element is the smallest */
+ Datum *arr_rotate = malloc(sizeof(Datum) * nobjects);
+ for (size_t i = 0; i < nobjects; ++i)
+ arr_rotate[i] = Int32GetDatum(i + 1);
+
+ arr_rotate[nobjects - 1] = Int32GetDatum(0);
+
+ /* random 0/1 */
+ Datum *arr_0_1 = malloc(sizeof(Datum) * nobjects);
+ for (size_t i = 0; i < nobjects; ++i)
+ arr_0_1[i] = arr_random[i] % 2;
+
+
+EOF
+
+# direct comp
+for order in $ORDERS ; do
+ for threshold in $THRESHOLDS ; do
+
+ echo " for (int i = 0; i < 3; ++i)"
+ echo " {"
+ echo " instr_time start_time, end_time;"
+ echo " memcpy(sorted, arr_$order, sizeof(Datum) * nobjects);"
+ echo " INSTR_TIME_SET_CURRENT(start_time);"
+ echo " qsort_int4direct_$threshold(sorted, nobjects);"
+ echo " INSTR_TIME_SET_CURRENT(end_time);"
+ echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+ echo " elog(NOTICE, \"[direct] size=%dMB, order=$order,
threshold=$threshold, test=%d, time=%f\", nmegs, i,
INSTR_TIME_GET_DOUBLE(end_time));"
+ echo " }"
+
+ done;
+done;
+
+# SQL-callable comp
+for order in $ORDERS ; do
+ for threshold in $THRESHOLDS ; do
+
+ echo " for (int i = 0; i < 3; ++i)"
+ echo " {"
+ echo " instr_time start_time, end_time;"
+ echo " memcpy(sorted, arr_$order, sizeof(Datum) * nobjects);"
+ echo " INSTR_TIME_SET_CURRENT(start_time);"
+ echo " qsort_bt_array_elements_$threshold(sorted, nobjects,
&cxt);"
+ echo " INSTR_TIME_SET_CURRENT(end_time);"
+ echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
+ echo " elog(NOTICE, \"[SQL inlined] size=%dMB, order=$order,
threshold=$threshold, test=%d, time=%f\", nmegs, i,
INSTR_TIME_GET_DOUBLE(end_time));"
+ echo " }"
+ echo
+
+ done;
+done;
+
+echo " free(sorted);"
+echo " free(arr_$order);"
+echo "}"
diff --git a/src/test/modules/test_sort_perf/test_sort_perf--1.0.sql
b/src/test/modules/test_sort_perf/test_sort_perf--1.0.sql
index 953717f8ba..9363eaac31 100644
--- a/src/test/modules/test_sort_perf/test_sort_perf--1.0.sql
+++ b/src/test/modules/test_sort_perf/test_sort_perf--1.0.sql
@@ -1,2 +1,4 @@
CREATE FUNCTION test_sort_object() RETURNS void AS 'MODULE_PATHNAME' LANGUAGE
C;
CREATE FUNCTION test_sort_itemptr() RETURNS void AS 'MODULE_PATHNAME' LANGUAGE
C;
+CREATE FUNCTION test_sort_datum(int4) RETURNS void AS 'MODULE_PATHNAME'
LANGUAGE C;
+CREATE FUNCTION test_sort_threshold(int4) RETURNS void AS 'MODULE_PATHNAME'
LANGUAGE C;
diff --git a/src/test/modules/test_sort_perf/test_sort_perf.c
b/src/test/modules/test_sort_perf/test_sort_perf.c
index 05a10924f3..c3c0c5be61 100644
--- a/src/test/modules/test_sort_perf/test_sort_perf.c
+++ b/src/test/modules/test_sort_perf/test_sort_perf.c
@@ -2,9 +2,13 @@
#include "funcapi.h"
#include "catalog/index.h"
+#include "catalog/pg_collation_d.h"
+#include "catalog/pg_type_d.h"
+#include "catalog/pg_opfamily_d.h"
#include "miscadmin.h"
#include "portability/instr_time.h"
#include "storage/itemptr.h"
+#include "utils/lsyscache.h"
#include <stdlib.h>
@@ -29,11 +33,104 @@ itemptr_comparator(const void *a, const void *b)
return 0;
}
+
+// standard comparators
+
+// comparator for qsort_arg()
+// XXX rewritten from the version in nbtutils.c
+static int
+btint4fastcmp(const void * x, const void * y)
+{
+ int32 *a = (int32 *) x;
+ int32 *b = (int32 *) y;
+
+ if (*a > *b)
+ return 1;
+ else if (*a == *b)
+ return 0;
+ else
+ return -1;
+}
+
+// qsort with inlined comparator
+#define ST_SORT qsort_int32
+#define ST_ELEMENT_TYPE Datum
+#define ST_COMPARE(a, b) (btint4fastcmp(a, b))
+#define ST_SCOPE static
+#define ST_DEFINE
+#define ST_DECLARE
+#include "lib/sort_template.h"
+
+// qsort with branchless comparator
+#define ST_SORT qsort_int32_branchless
+#define ST_ELEMENT_TYPE Datum
+#define ST_COMPARE(a, b) ((int64) *(a) - (int64) *(b))
+#define ST_COMPARE_RET_TYPE int64
+#define ST_SCOPE static
+#define ST_DEFINE
+#define ST_DECLARE
+#include "lib/sort_template.h"
+
+
+// SQL-callable comparators
+
+typedef struct BTSortArrayContext
+{
+ FmgrInfo flinfo;
+ Oid collation;
+ bool reverse;
+} BTSortArrayContext;
+
+// comparator for qsort arg
+static int
+_bt_compare_array_elements(const void *a, const void *b, void *arg)
+{
+ Datum da = *((const Datum *) a);
+ Datum db = *((const Datum *) b);
+ BTSortArrayContext *cxt = (BTSortArrayContext *) arg;
+ int32 compare;
+
+ compare = DatumGetInt32(FunctionCall2Coll(&cxt->flinfo,
+
cxt->collation,
+
da, db));
+ if (cxt->reverse)
+ INVERT_COMPARE_RESULT(compare);
+ return compare;
+}
+
+
+/* Define a specialized sort function for _bt_sort_array_elements. */
+#define ST_SORT qsort_bt_array_elements
+//#define ST_UNIQUE unique_bt_array_elements
+#define ST_ELEMENT_TYPE Datum
+#define ST_COMPARE(a, b, cxt) \
+ DatumGetInt32(FunctionCall2Coll(&cxt->flinfo, cxt->collation, *a, *b))
+#define ST_COMPARE_ARG_TYPE BTSortArrayContext
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+// inline the reversal
+#define ST_SORT qsort_bt_array_elements_reverse
+//#define ST_UNIQUE unique_bt_array_elements_reverse
+#define ST_ELEMENT_TYPE Datum
+#define ST_COMPARE(a, b, cxt) \
+ (0 - (DatumGetInt32(FunctionCall2Coll(&cxt->flinfo, cxt->collation, *a,
*b))))
+#define ST_COMPARE_RET_TYPE int64
+#define ST_COMPARE_ARG_TYPE BTSortArrayContext
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+
PG_MODULE_MAGIC;
/* include the generated code */
#include "test_sort_object_include.c"
#include "test_sort_itemptr_include.c"
+#include "test_sort_datum_include.c"
+#include "test_sort_threshold_include.c"
+
PG_FUNCTION_INFO_V1(test_sort_object);
PG_FUNCTION_INFO_V1(test_sort_itemptr);
@@ -53,3 +150,24 @@ test_sort_itemptr(PG_FUNCTION_ARGS)
PG_RETURN_NULL();
}
+
+
+PG_FUNCTION_INFO_V1(test_sort_datum);
+Datum
+test_sort_datum(PG_FUNCTION_ARGS)
+{
+ const int32 nmegs = PG_GETARG_INT32(0);
+
+ do_sort_datum(nmegs);
+ PG_RETURN_NULL();
+}
+
+PG_FUNCTION_INFO_V1(test_sort_threshold);
+Datum
+test_sort_threshold(PG_FUNCTION_ARGS)
+{
+ const int32 nmegs = PG_GETARG_INT32(0);
+
+ do_sort_threshold(nmegs);
+ PG_RETURN_NULL();
+}
