From 7a0286b3e1f403c622f8cf7dd65dc86103745ebb Mon Sep 17 00:00:00 2001 From: John Naylor Date: Mon, 30 May 2022 09:55:46 +0700 Subject: [PATCH v2 1/3] Add sort test module XXX not for commit --- src/include/lib/sort_template.h | 2 +- src/test/modules/test_sort_perf/Makefile | 20 ++ .../run-microbenchmark-thresholds.sh | 37 +++ .../test_sort_cmp_weight_include.c | 237 ++++++++++++++++++ .../test_sort_perf/test_sort_perf--1.0.sql | 1 + .../modules/test_sort_perf/test_sort_perf.c | 90 +++++++ .../test_sort_perf/test_sort_perf.control | 4 + 7 files changed, 390 insertions(+), 1 deletion(-) create mode 100644 src/test/modules/test_sort_perf/Makefile create mode 100755 src/test/modules/test_sort_perf/run-microbenchmark-thresholds.sh create mode 100644 src/test/modules/test_sort_perf/test_sort_cmp_weight_include.c create mode 100644 src/test/modules/test_sort_perf/test_sort_perf--1.0.sql create mode 100644 src/test/modules/test_sort_perf/test_sort_perf.c create mode 100644 src/test/modules/test_sort_perf/test_sort_perf.control diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h index 3122a93009..5a2f1d3fbb 100644 --- a/src/include/lib/sort_template.h +++ b/src/include/lib/sort_template.h @@ -296,7 +296,7 @@ ST_SORT(ST_ELEMENT_TYPE * data, size_t n loop: DO_CHECK_FOR_INTERRUPTS(); - if (n < 7) + if (n < ST_INSERTION_SORT_THRESHOLD) { for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP; pm += ST_POINTER_STEP) diff --git a/src/test/modules/test_sort_perf/Makefile b/src/test/modules/test_sort_perf/Makefile new file mode 100644 index 0000000000..1e49fb43c0 --- /dev/null +++ b/src/test/modules/test_sort_perf/Makefile @@ -0,0 +1,20 @@ +MODULE_big = test_sort_perf +OBJS = test_sort_perf.o +PGFILEDESC = "test" +EXTENSION = test_sort_perf +DATA = test_sort_perf--1.0.sql + +first: all + +test_sort_perf.o: test_sort_cmp_weight_include.c + +ifdef USE_PGXS +PG_CONFIG = pg_config +PGXS := $(shell $(PG_CONFIG) --pgxs) +include $(PGXS) +else +subdir = src/test/modules/test_sort_perf +top_builddir = ../../../.. +include $(top_builddir)/src/Makefile.global +include $(top_srcdir)/contrib/contrib-global.mk +endif diff --git a/src/test/modules/test_sort_perf/run-microbenchmark-thresholds.sh b/src/test/modules/test_sort_perf/run-microbenchmark-thresholds.sh new file mode 100755 index 0000000000..90df741f1e --- /dev/null +++ b/src/test/modules/test_sort_perf/run-microbenchmark-thresholds.sh @@ -0,0 +1,37 @@ +# ../papers-sorting/sort-bench-pdqsort-sql-20220529.sh 1000 setup + +set -e + +#ROWS=10000000 +#../papers-sorting/sort-bench-pdqsort-sql-20220529.sh $ROWS setup + + +# test actual funcs +for threshold in 7 10 12 14 16 18 20 22 24 32; do +#for threshold in 7 10; do + +# version 10 +echo "Threshold: $threshold" + +# TODO: run queries +#../rebuild.sh +#../papers-sorting/sort-bench-pdqsort-sql-20220529.sh $ROWS +#mv results.csv queryresult-$(date +'%Y%m%d')-$threshold.csv + +# run microbenchmark + +# build perf module +pushd src/test/modules/test_sort_perf/ >/dev/null +touch test_sort_perf.c +make -s CPPFLAGS=-DST_INSERTION_SORT_THRESHOLD=$threshold && make install -s +popd >/dev/null + +padthreshold=$(printf "%02d" $threshold) +./inst/bin/psql -c 'drop extension if exists test_sort_perf; create extension test_sort_perf;' +./inst/bin/psql -c 'select test_sort_cmp_weight(1 * 1024*1024)' 2> microresult-$padthreshold.txt +#./inst/bin/psql -c 'select test_sort_cmp_weight(1 * 1024)' 2> microresult-$padthreshold.txt + +perl -n -e 'print "$1\t$2\t$3\t$4\t$5\n" if /NOTICE: \[(.+)\] num=(\d+), threshold=(\d+), order=(\w+), time=(\d+\.\d+)/;' microresult-$padthreshold.txt > microresult-$(date +'%Y%m%d')-$padthreshold.csv + +done + diff --git a/src/test/modules/test_sort_perf/test_sort_cmp_weight_include.c b/src/test/modules/test_sort_perf/test_sort_cmp_weight_include.c new file mode 100644 index 0000000000..eaf1191d09 --- /dev/null +++ b/src/test/modules/test_sort_perf/test_sort_cmp_weight_include.c @@ -0,0 +1,237 @@ +#include + +static void run_tests(char* type, Datum *unsorted, Datum *sorted, BTSortArrayContext *cxt, int nobjects) +{ + const int numtests = 10; + double time, + min; + + if (nobjects <= 100) + { + elog(NOTICE, "order: %s", type); + for (int j = 0; j < nobjects; ++j) + elog(NOTICE, "%d", DatumGetInt32(unsorted[j])); + return; + } + + min = 1000000; + for (int i = 1; i <= numtests; ++i) + { + instr_time start_time, end_time; + memcpy(sorted, unsorted, sizeof(Datum) * nobjects); + INSTR_TIME_SET_CURRENT(start_time); + qsort_arg((void *) sorted, nobjects, sizeof(Datum), _bt_compare_array_elements, (void *) cxt); + INSTR_TIME_SET_CURRENT(end_time); + INSTR_TIME_SUBTRACT(end_time, start_time); + time = INSTR_TIME_GET_DOUBLE(end_time); + if (time < min) + min = time; + } + elog(NOTICE, "[fmgr runtime] num=%d, threshold=%d, order=%s, time=%f", nobjects, ST_INSERTION_SORT_THRESHOLD, type, min); + + min = 1000000; + for (int i = 1; i <= numtests; ++i) + { + instr_time start_time, end_time; + memcpy(sorted, unsorted, sizeof(Datum) * nobjects); + INSTR_TIME_SET_CURRENT(start_time); + qsort_bt_array_elements(sorted, nobjects, cxt); + INSTR_TIME_SET_CURRENT(end_time); + INSTR_TIME_SUBTRACT(end_time, start_time); + time = INSTR_TIME_GET_DOUBLE(end_time); + if (time < min) + min = time; + } + elog(NOTICE, "[fmgr specialized] num=%d, threshold=%d, order=%s, time=%f", nobjects, ST_INSERTION_SORT_THRESHOLD, type, min); + + min = 1000000; + for (int i = 1; i <= numtests; ++i) + { + instr_time start_time, end_time; + memcpy(sorted, unsorted, sizeof(Datum) * nobjects); + INSTR_TIME_SET_CURRENT(start_time); + qsort(sorted, nobjects, sizeof(Datum), btint4fastcmp); + INSTR_TIME_SET_CURRENT(end_time); + INSTR_TIME_SUBTRACT(end_time, start_time); + time = INSTR_TIME_GET_DOUBLE(end_time); + if (time < min) + min = time; + } + elog(NOTICE, "[C runtime] num=%d, threshold=%d, order=%s, time=%f", nobjects, ST_INSERTION_SORT_THRESHOLD, type, min); + + min = 1000000; + for (int i = 0; i < numtests; ++i) + { + instr_time start_time, end_time; + memcpy(sorted, unsorted, sizeof(Datum) * nobjects); + INSTR_TIME_SET_CURRENT(start_time); + qsort_int32(sorted, nobjects); + INSTR_TIME_SET_CURRENT(end_time); + INSTR_TIME_SUBTRACT(end_time, start_time); + time = INSTR_TIME_GET_DOUBLE(end_time); + if (time < min) + min = time; + } + elog(NOTICE, "[C specialized] num=%d, threshold=%d, order=%s, time=%f", nobjects, ST_INSERTION_SORT_THRESHOLD, type, min); +} + +typedef struct source_value +{ + int32 value; + float rand; +} source_value; + +static int +source_rand_cmp(const void * x, const void * y) +{ + source_value *a = (source_value *) x; + source_value *b = (source_value *) y; + + if (a->rand > b->rand) + return 1; + else if (a->rand < b->rand) + return -1; + else + return 0; +} + +static int +source_dither_cmp(const void * x, const void * y, void * nobjects) +{ + source_value *a = (source_value *) x; + source_value *b = (source_value *) y; + float dither; + + if (*(int *) nobjects <= 100) + dither = 5; + else + dither = 100; + + if ((a->value + dither * a->rand) > (b->value + dither * b->rand)) + return 1; + else if ((a->value + dither * a->rand) < (b->value + dither * b->rand)) + return -1; + else + return 0; +} + +static void +do_sort_cmp_weight(int nobjects) +{ + source_value *source = malloc(sizeof(source_value) * nobjects); + source_value *tmp = malloc(sizeof(source_value) * nobjects); + Datum *unsorted = malloc(sizeof(Datum) * nobjects); + Datum *sorted = malloc(sizeof(Datum) * nobjects); + + // for fmgr comparator tests + + 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; + + // needed for some distributions: first populate source array with ascending value and random tag + for (int i = 0; i < nobjects; ++i) + { + source[i].value = i; + source[i].rand = (float) random() / (float) RAND_MAX; // between 0 and 1 + } +// if (nobjects <= 100) +// for (int j = 0; j < nobjects; ++j) +// elog(NOTICE, "%f", (source[j].rand)); + qsort(source, nobjects, sizeof(source_value), source_rand_cmp); + + // random + for (int i = 0; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(source[i].value); + run_tests("random", unsorted, sorted, &cxt, nobjects); + + // for these, sort the first X % of the array + + // sort50 + for (int i = 0; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(source[i].value); + // sort first part of unsorted[] + qsort(unsorted, nobjects/2, sizeof(Datum), btint4fastcmp); + run_tests("sort50", unsorted, sorted, &cxt, nobjects); + + // sort90 + qsort(unsorted, nobjects/10 * 9, sizeof(Datum), btint4fastcmp); + run_tests("sort90", unsorted, sorted, &cxt, nobjects); + + // sort99 + qsort(unsorted, nobjects/100 * 99, sizeof(Datum), btint4fastcmp); + run_tests("sort99", unsorted, sorted, &cxt, nobjects); + + // dither -- copy source to tmp array because it sorts differently + memcpy(tmp, source, sizeof(source_value) * nobjects); + qsort_arg(tmp, nobjects, sizeof(source_value), source_dither_cmp, (void *) &nobjects); + for (int i = 0; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(tmp[i].value); + run_tests("dither", unsorted, sorted, &cxt, nobjects); + + // descending + for (int i = 0; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(nobjects - i); + run_tests("descending", unsorted, sorted, &cxt, nobjects); + + // organ + for (int i = 0; i < nobjects/2; ++i) + unsorted[i] = Int32GetDatum(i); + for (int i = nobjects/2; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(nobjects - i); + run_tests("organ", unsorted, sorted, &cxt, nobjects); + + // merge + for (int i = 0; i < nobjects/2; ++i) + unsorted[i] = Int32GetDatum(i); + for (int i = nobjects/2; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(i - nobjects/2); + run_tests("merge", unsorted, sorted, &cxt, nobjects); + + // dup8 + for (int i = 0; i < nobjects; ++i) + { + uint32 tmp = 1; // XXX this will only show duplicates for large nobjects + for (int j=0; j<8; ++j) + tmp *= (uint32) source[i].value; + tmp = (tmp + nobjects/2) % nobjects; + unsorted[i] = Int32GetDatum((int) tmp); + } + run_tests("dup8", unsorted, sorted, &cxt, nobjects); + + // dupsq + for (int i = 0; i < nobjects; ++i) + unsorted[i] = Int32GetDatum((int) sqrt(source[i].value)); + run_tests("dupsq", unsorted, sorted, &cxt, nobjects); + + // mod100 + for (int i = 0; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(source[i].value % 100); + run_tests("mod100", unsorted, sorted, &cxt, nobjects); + + // mod8 + for (int i = 0; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(source[i].value % 8); + run_tests("mod8", unsorted, sorted, &cxt, nobjects); + + // ascending + for (int i = 0; i < nobjects; ++i) + unsorted[i] = Int32GetDatum(i); + run_tests("ascending", unsorted, sorted, &cxt, nobjects); + + free(tmp); + free(source); + free(sorted); + free(unsorted); +} 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 new file mode 100644 index 0000000000..22e0726a57 --- /dev/null +++ b/src/test/modules/test_sort_perf/test_sort_perf--1.0.sql @@ -0,0 +1 @@ +CREATE FUNCTION test_sort_cmp_weight(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 new file mode 100644 index 0000000000..d162e42049 --- /dev/null +++ b/src/test/modules/test_sort_perf/test_sort_perf.c @@ -0,0 +1,90 @@ +#include "postgres.h" + +#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 + +// standard comparators + +// comparator for qsort_arg() copied from 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; +} + +// specialized 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" + +// 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_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" + +PG_MODULE_MAGIC; + +/* include the test suites */ +#include "test_sort_cmp_weight_include.c" + +PG_FUNCTION_INFO_V1(test_sort_cmp_weight); +Datum +test_sort_cmp_weight(PG_FUNCTION_ARGS) +{ + const int32 nobjects = PG_GETARG_INT32(0); + + do_sort_cmp_weight(nobjects); + PG_RETURN_NULL(); +} diff --git a/src/test/modules/test_sort_perf/test_sort_perf.control b/src/test/modules/test_sort_perf/test_sort_perf.control new file mode 100644 index 0000000000..336cb0c5ba --- /dev/null +++ b/src/test/modules/test_sort_perf/test_sort_perf.control @@ -0,0 +1,4 @@ +comment = 'test' +default_version = '1.0' +module_pathname = '$libdir/test_sort_perf' +relocatable = true -- 2.36.1