Re: A qsort template

I wrote:

> One of the points of the talk I linked to is "if doing the sensible thing
makes things worse, try something silly instead".

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:

# SELECT test_sort_itemptr();
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=0,
time=4.964657
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=1,
time=5.185384
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=2,
time=5.058179
NOTICE:  order=random, threshold=7, cmp=std, test=0, time=2.810627
NOTICE:  order=random, threshold=7, cmp=std, test=1, time=2.804940
NOTICE:  order=random, threshold=7, cmp=std, test=2, time=2.800677
NOTICE:  order=random, threshold=7, cmp=ids, test=0, time=1.692711
NOTICE:  order=random, threshold=7, cmp=ids, test=1, time=1.694546
NOTICE:  order=random, threshold=7, cmp=ids, test=2, time=1.692839
NOTICE:  order=random, threshold=12, cmp=std, test=0, time=2.687033
NOTICE:  order=random, threshold=12, cmp=std, test=1, time=2.681974
NOTICE:  order=random, threshold=12, cmp=std, test=2, time=2.687833
NOTICE:  order=random, threshold=12, cmp=ids, test=0, time=1.666418
NOTICE:  order=random, threshold=12, cmp=ids, test=1, time=1.666188
NOTICE:  order=random, threshold=12, cmp=ids, test=2, time=1.664176
NOTICE:  order=random, threshold=16, cmp=std, test=0, time=2.574147
NOTICE:  order=random, threshold=16, cmp=std, test=1, time=2.579981
NOTICE:  order=random, threshold=16, cmp=std, test=2, time=2.572861
NOTICE:  order=random, threshold=16, cmp=ids, test=0, time=1.699432
NOTICE:  order=random, threshold=16, cmp=ids, test=1, time=1.703075
NOTICE:  order=random, threshold=16, cmp=ids, test=2, time=1.697173
NOTICE:  order=random, threshold=32, cmp=std, test=0, time=2.750040
NOTICE:  order=random, threshold=32, cmp=std, test=1, time=2.744138
NOTICE:  order=random, threshold=32, cmp=std, test=2, time=2.748026
NOTICE:  order=random, threshold=32, cmp=ids, test=0, time=1.677414
NOTICE:  order=random, threshold=32, cmp=ids, test=1, time=1.683792
NOTICE:  order=random, threshold=32, cmp=ids, test=2, time=1.701309
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=0,
time=2.543837
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=1,
time=2.290497
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=2,
time=2.262956
NOTICE:  order=increasing, threshold=7, cmp=std, test=0, time=1.033052
NOTICE:  order=increasing, threshold=7, cmp=std, test=1, time=1.032079
NOTICE:  order=increasing, threshold=7, cmp=std, test=2, time=1.041836
NOTICE:  order=increasing, threshold=7, cmp=ids, test=0, time=0.367355
NOTICE:  order=increasing, threshold=7, cmp=ids, test=1, time=0.367428
NOTICE:  order=increasing, threshold=7, cmp=ids, test=2, time=0.367384
NOTICE:  order=increasing, threshold=12, cmp=std, test=0, time=1.004991
NOTICE:  order=increasing, threshold=12, cmp=std, test=1, time=1.008045
NOTICE:  order=increasing, threshold=12, cmp=std, test=2, time=1.010778
NOTICE:  order=increasing, threshold=12, cmp=ids, test=0, time=0.370944
NOTICE:  order=increasing, threshold=12, cmp=ids, test=1, time=0.368669
NOTICE:  order=increasing, threshold=12, cmp=ids, test=2, time=0.370100
NOTICE:  order=increasing, threshold=16, cmp=std, test=0, time=1.023682
NOTICE:  order=increasing, threshold=16, cmp=std, test=1, time=1.025805
NOTICE:  order=increasing, threshold=16, cmp=std, test=2, time=1.022005
NOTICE:  order=increasing, threshold=16, cmp=ids, test=0, time=0.365398
NOTICE:  order=increasing, threshold=16, cmp=ids, test=1, time=0.365586
NOTICE:  order=increasing, threshold=16, cmp=ids, test=2, time=0.364807
NOTICE:  order=increasing, threshold=32, cmp=std, test=0, time=0.950780
NOTICE:  order=increasing, threshold=32, cmp=std, test=1, time=0.949920
NOTICE:  order=increasing, threshold=32, cmp=std, test=2, time=0.953239
NOTICE:  order=increasing, threshold=32, cmp=ids, test=0, time=0.367866
NOTICE:  order=increasing, threshold=32, cmp=ids, test=1, time=0.372179
NOTICE:  order=increasing, threshold=32, cmp=ids, test=2, time=0.371115
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=0,
time=2.317475
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=1,
time=2.323446
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=2,
time=2.326714
NOTICE:  order=decreasing, threshold=7, cmp=std, test=0, time=1.022270
NOTICE:  order=decreasing, threshold=7, cmp=std, test=1, time=1.015133
NOTICE:  order=decreasing, threshold=7, cmp=std, test=2, time=1.016367
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=0, time=0.386884
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=1, time=0.388397
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=2, time=0.386328
NOTICE:  order=decreasing, threshold=12, cmp=std, test=0, time=0.993594
NOTICE:  order=decreasing, threshold=12, cmp=std, test=1, time=0.995031
NOTICE:  order=decreasing, threshold=12, cmp=std, test=2, time=0.995320
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=0, time=0.391243
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=1, time=0.391938
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=2, time=0.392478
NOTICE:  order=decreasing, threshold=16, cmp=std, test=0, time=1.006240
NOTICE:  order=decreasing, threshold=16, cmp=std, test=1, time=1.009817
NOTICE:  order=decreasing, threshold=16, cmp=std, test=2, time=1.010281
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=0, time=0.386388
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=1, time=0.385801
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=2, time=0.384484
NOTICE:  order=decreasing, threshold=32, cmp=std, test=0, time=0.959647
NOTICE:  order=decreasing, threshold=32, cmp=std, test=1, time=0.958833
NOTICE:  order=decreasing, threshold=32, cmp=std, test=2, time=0.960234
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=0, time=0.403014
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=1, time=0.393329
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=2, time=0.395659

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