public inbox for [email protected]
help / color / mirror / Atom feedFrom: John Naylor <[email protected]>
To: Thomas Munro <[email protected]>
Cc: pgsql-hackers <[email protected]>
Subject: Re: A qsort template
Date: Thu, 1 Jul 2021 12:39:32 -0400
Message-ID: <CAFBsxsG_c24CHKA3cWrOP1HynWGLOkLb8hyZfsD9db5g-ZPagA@mail.gmail.com> (raw)
In-Reply-To: <CAFBsxsFVG8-Q-98C__N=brinC6pAFs7kGjAZj5LO77M8VmTn-Q@mail.gmail.com>
References: <CA+hUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse+HG0Yig@mail.gmail.com>
<[email protected]>
<CA+hUKGJhOtjQH+wjCodtJzHAFCAPYyt6Qm9E1mUoJph42qo1hg@mail.gmail.com>
<[email protected]>
<CA+hUKGLqmksGRKQRF6qkih6jV_d9qVrrk4wh5F_EgTXyRGeCyw@mail.gmail.com>
<CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com>
<CALNJ-vRSvudAbdY-DChFv8C0-dJYD3FamX4FpW9A2xivKuB83A@mail.gmail.com>
<CA+hUKGKWR3_-sqTE8BSrSy0kp0WJeKQ1ffyYxEKuykA7vmG9uQ@mail.gmail.com>
<CA+hUKGLAfouP-rUpik45Z_KPM5+oxrX_564bLfiZPX4f25MYbA@mail.gmail.com>
<CAFBsxsFSTSrrhAyFQo6Kz4vP40iXyvUdvzU0LvHa4LVyK-eDfA@mail.gmail.com>
<CA+hUKG+-Nx4CfutUsgG-x7qfzmV-VHtcdD_kyRksE4t7CWYN3w@mail.gmail.com>
<CA+hUKGLSaWnz4gznDp6aMhi4dzzUBJZEUACo6QAOC28JjvhxBg@mail.gmail.com>
<CA+hUKGLPommgNw-SVwUGkw1YmTDwmJ5vSKO0kFnZfbRHtNFW5w@mail.gmail.com>
<CAFBsxsFVG8-Q-98C__N=brinC6pAFs7kGjAZj5LO77M8VmTn-Q@mail.gmail.com>
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
Attachments:
[application/octet-stream] itemptr-cmp-blockids.patch (4.5K, ../CAFBsxsG_c24CHKA3cWrOP1HynWGLOkLb8hyZfsD9db5g-ZPagA@mail.gmail.com/3-itemptr-cmp-blockids.patch)
download | inline diff:
diff --git a/src/test/modules/test_sort_perf/make-itemptr-tests.sh b/src/test/modules/test_sort_perf/make-itemptr-tests.sh
index 9151ea703f..fd0048eba3 100755
--- a/src/test/modules/test_sort_perf/make-itemptr-tests.sh
+++ b/src/test/modules/test_sort_perf/make-itemptr-tests.sh
@@ -1,7 +1,7 @@
#!/bin/sh
# different values to test for insertion sorts
-THRESHOLDS="7 8 9 10 11 12 13"
+THRESHOLDS="7 12 16 32"
# amount of data to sort, in megabytes
MEMORY=128
@@ -18,10 +18,9 @@ for threshold in $THRESHOLDS ; do
echo "#define ST_DEFINE"
echo "#include \"lib/sort_template.h\""
echo
- echo "#define ST_SORT sort64_${threshold}_itemptr"
+ echo "#define ST_SORT sort_ids_${threshold}_itemptr"
echo "#define ST_ELEMENT_TYPE ItemPointerData"
- echo "#define ST_COMPARE(a, b) (itemptr_encode(a) - itemptr_encode(b))"
- echo "#define ST_COMPARE_RET_TYPE int64"
+ echo "#define ST_COMPARE(a, b) itemptr_comparator_blockids(a, b)"
echo "#define ST_SCOPE static"
echo "#define ST_SORT_SMALL_THRESHOLD $threshold"
echo "#define ST_CHECK_FOR_INTERRUPTS"
@@ -76,7 +75,7 @@ for order in random increasing decreasing ; do
echo " sort_${threshold}_itemptr(sorted, nobjects);"
echo " INSTR_TIME_SET_CURRENT(end_time);"
echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
- echo " elog(NOTICE, \"order=$order, threshold=$threshold, cmp=32, test=%d, time=%f\", i, INSTR_TIME_GET_DOUBLE(end_time));"
+ echo " elog(NOTICE, \"order=$order, threshold=$threshold, cmp=std, test=%d, time=%f\", i, INSTR_TIME_GET_DOUBLE(end_time));"
echo " }"
echo " for (int i = 0; i < 3; ++i)"
echo " {"
@@ -84,10 +83,10 @@ for order in random increasing decreasing ; do
echo " memcpy(sorted, unsorted, sizeof(sorted[0]) * nobjects);"
echo " INSTR_TIME_SET_CURRENT(start_time);"
echo " memcpy(sorted, unsorted, sizeof(sorted[0]) * nobjects);"
- echo " sort64_${threshold}_itemptr(sorted, nobjects);"
+ echo " sort_ids_${threshold}_itemptr(sorted, nobjects);"
echo " INSTR_TIME_SET_CURRENT(end_time);"
echo " INSTR_TIME_SUBTRACT(end_time, start_time);"
- echo " elog(NOTICE, \"order=$order, threshold=$threshold, cmp=64, test=%d, time=%f\", i, INSTR_TIME_GET_DOUBLE(end_time));"
+ echo " elog(NOTICE, \"order=$order, threshold=$threshold, cmp=ids, test=%d, time=%f\", i, INSTR_TIME_GET_DOUBLE(end_time));"
echo " }"
done
done
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..1ebaf41329 100644
--- a/src/test/modules/test_sort_perf/test_sort_perf.c
+++ b/src/test/modules/test_sort_perf/test_sort_perf.c
@@ -8,6 +8,44 @@
#include <stdlib.h>
+/*
+ * ItemPointerGetBlockIdHiNoCheck
+ * Returns the high short of a disk item pointer blockid.
+ */
+#define ItemPointerGetBlockIdHiNoCheck(pointer) \
+( \
+ (pointer)->ip_blkid.bi_hi \
+)
+
+/*
+ * ItemPointerGetBlockIdHi
+ * As above, but verifies that the item pointer looks valid.
+ */
+#define ItemPointerGetBlockIdHi(pointer) \
+( \
+ AssertMacro(ItemPointerIsValid(pointer)), \
+ ItemPointerGetBlockIdHiNoCheck(pointer) \
+)
+
+/*
+ * ItemPointerGetBlockIdLoNoCheck
+ * Returns the low short of a disk item pointer blockid.
+ */
+#define ItemPointerGetBlockIdLoNoCheck(pointer) \
+( \
+ (pointer)->ip_blkid.bi_lo \
+)
+
+/*
+ * ItemPointerGetBlockIdLo
+ * As above, but verifies that the item pointer looks valid.
+ */
+#define ItemPointerGetBlockIdLo(pointer) \
+( \
+ AssertMacro(ItemPointerIsValid(pointer)), \
+ ItemPointerGetBlockIdHiNoCheck(pointer) \
+)
+
static int
itemptr_comparator(const void *a, const void *b)
{
@@ -29,6 +67,38 @@ itemptr_comparator(const void *a, const void *b)
return 0;
}
+static int
+itemptr_comparator_blockids(const void *a, const void *b)
+{
+ const ItemPointerData *ipa = (const ItemPointerData *) a;
+ const ItemPointerData *ipb = (const ItemPointerData *) b;
+
+ uint16 ba_hi = ItemPointerGetBlockIdHi(ipa);
+ uint16 bb_hi = ItemPointerGetBlockIdHi(ipb);
+
+ if (ba_hi < bb_hi)
+ return -1;
+ if (ba_hi > bb_hi)
+ return 1;
+
+ uint16 ba_lo = ItemPointerGetBlockIdLo(ipa);
+ uint16 bb_lo = ItemPointerGetBlockIdLo(ipb);
+
+ if (ba_lo < bb_lo)
+ return -1;
+ if (ba_lo > bb_lo)
+ return 1;
+
+ OffsetNumber oa = ItemPointerGetOffsetNumber(ipa);
+ OffsetNumber ob = ItemPointerGetOffsetNumber(ipb);
+
+ if (oa < ob)
+ return -1;
+ if (oa > ob)
+ return 1;
+ return 0;
+}
+
PG_MODULE_MAGIC;
/* include the generated code */
view thread (52+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected]
Subject: Re: A qsort template
In-Reply-To: <CAFBsxsG_c24CHKA3cWrOP1HynWGLOkLb8hyZfsD9db5g-ZPagA@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox