jcn-0012-addendum-20220131.txt
text/plain
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();
+}