jcn-addendum-test-branchless-techniques.txt
text/plain
Filename: jcn-addendum-test-branchless-techniques.txt
Type: text/plain
Part: 1
Message:
Re: A qsort template
diff --git a/src/test/modules/test_sort_perf/Makefile b/src/test/modules/test_sort_perf/Makefile
index ab7f8e24b0..e70187f3a6 100644
--- a/src/test/modules/test_sort_perf/Makefile
+++ b/src/test/modules/test_sort_perf/Makefile
@@ -6,12 +6,15 @@ 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_int64_include.c
+test_sort_perf.o: test_sort_int64_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_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_int64_include.c: make-int32-tests.sh
+ ./make-int32-tests.sh > test_sort_int32_include.c
ifdef USE_PGXS
PG_CONFIG = pg_config
diff --git a/src/test/modules/test_sort_perf/make-int32-tests.sh b/src/test/modules/test_sort_perf/make-int32-tests.sh
new file mode 100755
index 0000000000..a861ef608a
--- /dev/null
+++ b/src/test/modules/test_sort_perf/make-int32-tests.sh
@@ -0,0 +1,151 @@
+#!/bin/sh
+
+cat <<EOF
+#include "utils/builtins.h"
+
+EOF
+
+# generate the function that runs all the tests
+echo "static void"
+echo "do_sort_int32(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/test_sort_perf--1.0.sql b/src/test/modules/test_sort_perf/test_sort_perf--1.0.sql
index 953717f8ba..15203d9382 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,3 @@
-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_object() RETURNS void AS 'MODULE_PATHNAME' LANGUAGE C;
+--CREATE FUNCTION test_sort_itemptr() RETURNS void AS 'MODULE_PATHNAME' LANGUAGE C;
+CREATE FUNCTION test_sort_int32(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..177d2b1c35 100644
--- a/src/test/modules/test_sort_perf/test_sort_perf.c
+++ b/src/test/modules/test_sort_perf/test_sort_perf.c
@@ -2,12 +2,18 @@
#include "funcapi.h"
#include "catalog/index.h"
+#include "catalog/pg_collation.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>
+
+/*
static int
itemptr_comparator(const void *a, const void *b)
{
@@ -27,14 +33,106 @@ itemptr_comparator(const void *a, const void *b)
if (oa > ob)
return 1;
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_object_include.c"
+// #include "test_sort_itemptr_include.c"
+#include "test_sort_int32_include.c"
+/*
PG_FUNCTION_INFO_V1(test_sort_object);
PG_FUNCTION_INFO_V1(test_sort_itemptr);
@@ -53,3 +151,15 @@ test_sort_itemptr(PG_FUNCTION_ARGS)
PG_RETURN_NULL();
}
+*/
+
+
+PG_FUNCTION_INFO_V1(test_sort_int32);
+Datum
+test_sort_int32(PG_FUNCTION_ARGS)
+{
+ const int32 nmegs = PG_GETARG_INT32(0);
+
+ do_sort_int32(nmegs);
+ PG_RETURN_NULL();
+}