Hi! I rebase, clean and some refactor my patches.
Best regards, Stepan Neretin.
From f88cbb80e478d5ac3f23945b4ba0ee881f0d9cd4 Mon Sep 17 00:00:00 2001
From: "Andrey M. Borodin" <x4mmm@night.local>
Date: Sun, 8 Sep 2024 15:43:39 +0700
Subject: [PATCH v2 01/10] Use specialized sort facilities
---
contrib/intarray/_int.h | 12 ------------
contrib/intarray/_int_gist.c | 2 +-
contrib/intarray/_int_op.c | 19 +++++++++----------
contrib/intarray/_int_tool.c | 12 ------------
src/include/port.h | 2 ++
src/port/qsort.c | 35 +++++++++++++++++++++++++++++++++++
6 files changed, 47 insertions(+), 35 deletions(-)
diff --git a/contrib/intarray/_int.h b/contrib/intarray/_int.h
index 0352cbd368..5225c9090a 100644
--- a/contrib/intarray/_int.h
+++ b/contrib/intarray/_int.h
@@ -176,16 +176,4 @@ bool execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot);
bool gin_bool_consistent(QUERYTYPE *query, bool *check);
bool query_has_required_values(QUERYTYPE *query);
-int compASC(const void *a, const void *b);
-int compDESC(const void *a, const void *b);
-
-/* sort, either ascending or descending */
-#define QSORT(a, direction) \
- do { \
- int _nelems_ = ARRNELEMS(a); \
- if (_nelems_ > 1) \
- qsort((void*) ARRPTR(a), _nelems_, sizeof(int32), \
- (direction) ? compASC : compDESC ); \
- } while(0)
-
#endif /* ___INT_H__ */
diff --git a/contrib/intarray/_int_gist.c b/contrib/intarray/_int_gist.c
index a09b7fa812..d39e40c66a 100644
--- a/contrib/intarray/_int_gist.c
+++ b/contrib/intarray/_int_gist.c
@@ -150,7 +150,7 @@ g_int_union(PG_FUNCTION_ARGS)
ptr += nel;
}
- QSORT(res, 1);
+ sort_int32_asc(ARRPTR(res), ARRNELEMS(res));
res = _int_unique(res);
*size = VARSIZE(res);
PG_RETURN_POINTER(res);
diff --git a/contrib/intarray/_int_op.c b/contrib/intarray/_int_op.c
index 5b164f6788..34d3aa183f 100644
--- a/contrib/intarray/_int_op.c
+++ b/contrib/intarray/_int_op.c
@@ -198,7 +198,6 @@ sort(PG_FUNCTION_ARGS)
text *dirstr = (fcinfo->nargs == 2) ? PG_GETARG_TEXT_PP(1) : NULL;
int32 dc = (dirstr) ? VARSIZE_ANY_EXHDR(dirstr) : 0;
char *d = (dirstr) ? VARDATA_ANY(dirstr) : NULL;
- int dir = -1;
CHECKARRVALID(a);
if (ARRNELEMS(a) < 2)
@@ -208,18 +207,18 @@ sort(PG_FUNCTION_ARGS)
&& (d[0] == 'A' || d[0] == 'a')
&& (d[1] == 'S' || d[1] == 's')
&& (d[2] == 'C' || d[2] == 'c')))
- dir = 1;
+ sort_int32_asc(ARRPTR(a), ARRNELEMS(a));
else if (dc == 4
&& (d[0] == 'D' || d[0] == 'd')
&& (d[1] == 'E' || d[1] == 'e')
&& (d[2] == 'S' || d[2] == 's')
&& (d[3] == 'C' || d[3] == 'c'))
- dir = 0;
- if (dir == -1)
+ sort_int32_desc(ARRPTR(a), ARRNELEMS(a));
+ else
ereport(ERROR,
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
errmsg("second parameter must be \"ASC\" or \"DESC\"")));
- QSORT(a, dir);
+
PG_RETURN_POINTER(a);
}
@@ -229,7 +228,7 @@ sort_asc(PG_FUNCTION_ARGS)
ArrayType *a = PG_GETARG_ARRAYTYPE_P_COPY(0);
CHECKARRVALID(a);
- QSORT(a, 1);
+ sort_int32_asc(ARRPTR(a), ARRNELEMS(a));
PG_RETURN_POINTER(a);
}
@@ -239,7 +238,7 @@ sort_desc(PG_FUNCTION_ARGS)
ArrayType *a = PG_GETARG_ARRAYTYPE_P_COPY(0);
CHECKARRVALID(a);
- QSORT(a, 0);
+ sort_int32_desc(ARRPTR(a), ARRNELEMS(a));
PG_RETURN_POINTER(a);
}
@@ -381,7 +380,7 @@ intset_union_elem(PG_FUNCTION_ARGS)
result = intarray_add_elem(a, PG_GETARG_INT32(1));
PG_FREE_IF_COPY(a, 0);
- QSORT(result, 1);
+ sort_int32_asc(ARRPTR(result), ARRNELEMS(result));
PG_RETURN_POINTER(_int_unique(result));
}
@@ -403,10 +402,10 @@ intset_subtract(PG_FUNCTION_ARGS)
CHECKARRVALID(a);
CHECKARRVALID(b);
- QSORT(a, 1);
+ sort_int32_asc(ARRPTR(a), ARRNELEMS(a));
a = _int_unique(a);
ca = ARRNELEMS(a);
- QSORT(b, 1);
+ sort_int32_asc(ARRPTR(b), ARRNELEMS(b));
b = _int_unique(b);
cb = ARRNELEMS(b);
result = new_intArrayType(ca);
diff --git a/contrib/intarray/_int_tool.c b/contrib/intarray/_int_tool.c
index c85280c842..e83c6aadc6 100644
--- a/contrib/intarray/_int_tool.c
+++ b/contrib/intarray/_int_tool.c
@@ -393,15 +393,3 @@ int_to_intset(int32 elem)
aa[0] = elem;
return result;
}
-
-int
-compASC(const void *a, const void *b)
-{
- return pg_cmp_s32(*(const int32 *) a, *(const int32 *) b);
-}
-
-int
-compDESC(const void *a, const void *b)
-{
- return pg_cmp_s32(*(const int32 *) b, *(const int32 *) a);
-}
diff --git a/src/include/port.h b/src/include/port.h
index ba9ab0d34f..b82f969fc5 100644
--- a/src/include/port.h
+++ b/src/include/port.h
@@ -443,6 +443,8 @@ extern char *strsep(char **stringp, const char *delim);
extern void pg_qsort(void *base, size_t nel, size_t elsize,
int (*cmp) (const void *, const void *));
extern int pg_qsort_strcmp(const void *a, const void *b);
+extern void sort_int32_asc(int32 *base, size_t nel);
+extern void sort_int32_desc(int32 *base, size_t nel);
#define qsort(a,b,c,d) pg_qsort(a,b,c,d)
diff --git a/src/port/qsort.c b/src/port/qsort.c
index 7879e6cd56..5175c8a6dd 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -20,3 +20,38 @@ pg_qsort_strcmp(const void *a, const void *b)
{
return strcmp(*(const char *const *) a, *(const char *const *) b);
}
+
+static inline int
+sort_int32_asc_cmp(int32* a, int32* b)
+{
+ if (*a < *b)
+ return -1;
+ if (*a > *b)
+ return 1;
+ return 0;
+}
+
+#define ST_SORT sort_int32_asc
+#define ST_ELEMENT_TYPE int32
+#define ST_COMPARE sort_int32_asc_cmp
+#define ST_SCOPE
+#define ST_DECLARE
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+static inline int
+sort_int32_desc_cmp(int32* a, int32* b)
+{
+ if (*a < *b)
+ return 1;
+ if (*a > *b)
+ return -1;
+ return 0;
+}
+#define ST_SORT sort_int32_desc
+#define ST_ELEMENT_TYPE int32
+#define ST_COMPARE sort_int32_desc_cmp
+#define ST_SCOPE
+#define ST_DECLARE
+#define ST_DEFINE
+#include "lib/sort_template.h"
--
2.43.0
From 337cb90eb37c5982e2d7f2dc6ab70fbb500c6010 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:44:00 +0700
Subject: [PATCH v2 04/10] Optimized Integer List Sorting by Using Template
Sorting Algorithm
Optimized the sorting of lists containing integers by utilizing a custom sort template.
This enhancement introduces a specialized sorting function sort_list_int defined through macros and included from sort_template.h.
The new function improves performance by directly comparing integers and sorting the list in-place.
Changes:
- Defined ST_SORT, ST_ELEMENT_TYPE, ST_COMPARE, ST_SCOPE, and ST_DEFINE macros for sort_list_int.
- Included sort_template.h to leverage the template-based sorting mechanism.
- Implemented list_int_sort function to sort lists with int type.
This optimization is expected to enhance the efficiency of sorting operations for integer lists, leading to overall performance improvements in systems that manage large lists of integers.
---
src/backend/nodes/list.c | 14 ++++++++++++++
src/include/nodes/pg_list.h | 1 +
2 files changed, 15 insertions(+)
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index b2165c6284..197ce1b8f4 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -1720,4 +1720,18 @@ list_oid_cmp(const ListCell *p1, const ListCell *p2)
*/
void list_oid_sort(List *data){
sort_list_oids(list_head(data), list_length(data));
+}
+
+#define ST_SORT sort_list_ints
+#define ST_ELEMENT_TYPE ListCell
+#define ST_COMPARE(a, b) list_int_cmp(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
+/*
+ * Sort list with int type optimization.
+ */
+void list_int_sort(List *data){
+ sort_list_ints(list_head(data), list_length(data));
}
\ No newline at end of file
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 88aa1ebea9..7757b1cdf0 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -680,6 +680,7 @@ extern pg_nodiscard List *list_copy_deep(const List *oldlist);
typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
extern void list_sort(List *list, list_sort_comparator cmp);
extern void list_oid_sort(List *list);
+extern void list_int_sort(List *list);
extern int list_int_cmp(const ListCell *p1, const ListCell *p2);
extern int list_oid_cmp(const ListCell *p1, const ListCell *p2);
--
2.43.0
From 80fbedfc64a329b506440a7374b183ad1d469748 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:44:04 +0700
Subject: [PATCH v2 05/10] Refactor Grouping Sets Sorting to Use list_int_sort
Refactored the sorting logic for grouping sets in the expand_grouping_sets function by replacing the use of list_sort with list_int_cmp to the optimized list_int_sort function for sorting individual group sets.
---
src/backend/parser/parse_agg.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c
index bee7d8346a..f949b81e84 100644
--- a/src/backend/parser/parse_agg.c
+++ b/src/backend/parser/parse_agg.c
@@ -1870,7 +1870,7 @@ expand_grouping_sets(List *groupingSets, bool groupDistinct, int limit)
/* Sort each groupset individually */
foreach(cell, result)
- list_sort(lfirst(cell), list_int_cmp);
+ list_int_sort(lfirst(cell));
/* Now sort the list of groupsets by length and contents */
list_sort(result, cmp_list_len_contents_asc);
--
2.43.0
From c068e66cb7577aaf7a668b71f17ac95ff35b7736 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:43:56 +0700
Subject: [PATCH v2 03/10] Enhanced Sorting Efficiency for Oid Lists
- Replaced `list_sort(result, list_oid_cmp)` with `list_oid_sort(result)` for optimized OID sorting.
- Updated the following files:
- `src/backend/catalog/heap.c`
- `src/backend/catalog/pg_publication.c`
- `src/backend/utils/cache/relcache.c`
---
src/backend/catalog/heap.c | 2 +-
src/backend/catalog/pg_publication.c | 2 +-
src/backend/utils/cache/relcache.c | 4 ++--
3 files changed, 4 insertions(+), 4 deletions(-)
diff --git a/src/backend/catalog/heap.c b/src/backend/catalog/heap.c
index 01b43cc6a8..368044459a 100644
--- a/src/backend/catalog/heap.c
+++ b/src/backend/catalog/heap.c
@@ -3311,7 +3311,7 @@ restart:
list_free(oids);
/* Now sort and de-duplicate the result list */
- list_sort(result, list_oid_cmp);
+ list_oid_sort(result);
list_deduplicate_oid(result);
return result;
diff --git a/src/backend/catalog/pg_publication.c b/src/backend/catalog/pg_publication.c
index 7fe5fe2b86..31e1694cfe 100644
--- a/src/backend/catalog/pg_publication.c
+++ b/src/backend/catalog/pg_publication.c
@@ -728,7 +728,7 @@ GetPublicationRelations(Oid pubid, PublicationPartOpt pub_partopt)
table_close(pubrelsrel, AccessShareLock);
/* Now sort and de-duplicate the result list */
- list_sort(result, list_oid_cmp);
+ list_oid_sort(result);
list_deduplicate_oid(result);
return result;
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 63efc55f09..1220e6ca9a 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4874,7 +4874,7 @@ RelationGetIndexList(Relation relation)
table_close(indrel, AccessShareLock);
/* Sort the result list into OID order, per API spec. */
- list_sort(result, list_oid_cmp);
+ list_oid_sort(result);
/* Now save a copy of the completed list in the relcache entry. */
oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
@@ -4966,7 +4966,7 @@ RelationGetStatExtList(Relation relation)
table_close(indrel, AccessShareLock);
/* Sort the result list into OID order, per API spec. */
- list_sort(result, list_oid_cmp);
+ list_oid_sort(result);
/* Now save a copy of the completed list in the relcache entry. */
oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
--
2.43.0
From 0189f0997747c7ed9e0a834e436cec72b14fdb0f Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:43:52 +0700
Subject: [PATCH v2 02/10] Optimized Oid List Sorting by using template sorting
algorithm
Optimized the sorting of lists containing Oids by utilizing a custom sort template.
This enhancement introduces a specialized sorting function sort_list_oids defined through macros and included from sort_template.h.
The new function improves performance by directly comparing Oids and sorting the list in-place.
Changes:
- Defined ST_SORT, ST_ELEMENT_TYPE, ST_COMPARE, ST_SCOPE, and ST_DEFINE macros for sort_list_oids.
- Included sort_template.h to leverage the template-based sorting mechanism.
- Implemented list_oid_sort function to sort lists with Oid type.
This optimization is expected to provide better sorting efficiency for lists containing Oids, contributing to overall system performance improvements.
---
src/backend/nodes/list.c | 14 ++++++++++++++
src/include/nodes/pg_list.h | 1 +
2 files changed, 15 insertions(+)
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index e2615ab105..b2165c6284 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -1707,3 +1707,17 @@ list_oid_cmp(const ListCell *p1, const ListCell *p2)
return pg_cmp_u32(v1, v2);
}
+
+#define ST_SORT sort_list_oids
+#define ST_ELEMENT_TYPE ListCell
+#define ST_COMPARE(a, b) list_oid_cmp(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
+/*
+ * Sort list with Oid type optimization.
+ */
+void list_oid_sort(List *data){
+ sort_list_oids(list_head(data), list_length(data));
+}
\ No newline at end of file
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 52df93759f..88aa1ebea9 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -679,6 +679,7 @@ extern pg_nodiscard List *list_copy_deep(const List *oldlist);
typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
extern void list_sort(List *list, list_sort_comparator cmp);
+extern void list_oid_sort(List *list);
extern int list_int_cmp(const ListCell *p1, const ListCell *p2);
extern int list_oid_cmp(const ListCell *p1, const ListCell *p2);
--
2.43.0
From f248a7f9ca8c85426f89de29caac0135b374c107 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:44:07 +0700
Subject: [PATCH v2 06/10] Optimize int16 Array Sorting in CreateStatistics
Optimized the sorting of int16 arrays in the CreateStatistics function by replacing qsort with the custom sort_int_16_arr function generated via the template-based sorting mechanism.
Changes:
- Introduced a new sort_int_16_arr function using the sorting template.
- Defined macros ST_SORT, ST_ELEMENT_TYPE, ST_COMPARE, ST_SCOPE, and ST_DEFINE for sort_int_16_arr.
- Replaced qsort(attnums, nattnums, sizeof(int16), compare_int16) with sort_int_16_arr(attnums, nattnums).
---
src/backend/commands/statscmds.c | 9 ++++++++-
1 file changed, 8 insertions(+), 1 deletion(-)
diff --git a/src/backend/commands/statscmds.c b/src/backend/commands/statscmds.c
index 1db3ef69d2..23952e83fd 100644
--- a/src/backend/commands/statscmds.c
+++ b/src/backend/commands/statscmds.c
@@ -55,6 +55,13 @@ compare_int16(const void *a, const void *b)
return (av - bv);
}
+#define ST_SORT sort_int_16_arr
+#define ST_ELEMENT_TYPE int16
+#define ST_COMPARE(a, b) compare_int16(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
/*
* CREATE STATISTICS
*/
@@ -404,7 +411,7 @@ CreateStatistics(CreateStatsStmt *stmt)
* it does not hurt (it does not matter for the contents, unlike for
* indexes, for example).
*/
- qsort(attnums, nattnums, sizeof(int16), compare_int16);
+ sort_int_16_arr(attnums, nattnums);
/*
* Check for duplicates in the list of columns. The attnums are sorted so
--
2.43.0
From 8e46856468d631e65efe8b06c8fb09bd1eeb0cfa Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:44:10 +0700
Subject: [PATCH v2 07/10] Introduce a sorting template for float8 arrays in
geo_spgist.c to boost performance.
---
src/backend/utils/adt/geo_spgist.c | 11 +++++++++++
1 file changed, 11 insertions(+)
diff --git a/src/backend/utils/adt/geo_spgist.c b/src/backend/utils/adt/geo_spgist.c
index 51378dca5b..fa0a753fa4 100644
--- a/src/backend/utils/adt/geo_spgist.c
+++ b/src/backend/utils/adt/geo_spgist.c
@@ -100,6 +100,17 @@ compareDoubles(const void *a, const void *b)
return (x > y) ? 1 : -1;
}
+ /*
++ * Instantiating a Sorting Template for float8 Arrays
++ * enhancing speed performance.
++ */
+#define ST_SORT sort_float8_arr
+#define ST_ELEMENT_TYPE float8
+#define ST_COMPARE(a, b) compareDoubles(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
typedef struct
{
float8 low;
--
2.43.0
From 1676025cf6c95996ed4f0d44520ef9d06d0d7b6c Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:44:19 +0700
Subject: [PATCH v2 09/10] Add extenstion to bench perfomance improvements.
---
contrib/bench_sort_improvements/Makefile | 20 ++
contrib/bench_sort_improvements/bench.c | 230 ++++++++++++++++++
.../bench_sort_improvements--1.0.sql | 7 +
.../bench_sort_improvements.control | 5 +
4 files changed, 262 insertions(+)
create mode 100644 contrib/bench_sort_improvements/Makefile
create mode 100644 contrib/bench_sort_improvements/bench.c
create mode 100644 contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
create mode 100644 contrib/bench_sort_improvements/bench_sort_improvements.control
diff --git a/contrib/bench_sort_improvements/Makefile b/contrib/bench_sort_improvements/Makefile
new file mode 100644
index 0000000000..46458ee76c
--- /dev/null
+++ b/contrib/bench_sort_improvements/Makefile
@@ -0,0 +1,20 @@
+MODULE_big = bench_sort_improvements
+
+OBJS = \
+ $(WIN32RES) \
+ bench.o
+
+EXTENSION = bench_sort_improvements
+
+DATA = bench_sort_improvements--1.0.sql
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/bench_sort_improvements
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/bench_sort_improvements/bench.c b/contrib/bench_sort_improvements/bench.c
new file mode 100644
index 0000000000..a4088783c6
--- /dev/null
+++ b/contrib/bench_sort_improvements/bench.c
@@ -0,0 +1,230 @@
+#include "postgres.h"
+#include "fmgr.h"
+#include "utils/builtins.h"
+#include "nodes/pg_list.h"
+#include <limits.h>
+#include <time.h>
+
+
+PG_MODULE_MAGIC;
+
+Datum bench_int_sort(PG_FUNCTION_ARGS);
+Datum bench_int16_sort(PG_FUNCTION_ARGS);
+Datum bench_float8_sort(PG_FUNCTION_ARGS);
+Datum bench_oid_sort(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(bench_oid_sort);
+PG_FUNCTION_INFO_V1(bench_int_sort);
+PG_FUNCTION_INFO_V1(bench_int16_sort);
+PG_FUNCTION_INFO_V1(bench_float8_sort);
+
+Datum
+bench_oid_sort(PG_FUNCTION_ARGS)
+{
+ int32 list_size = PG_GETARG_INT32(0);
+ List *list_first = NIL;
+ List *list_second = NIL;
+ Oid random_oid;
+ struct timespec start, end;
+ long time_spent_first;
+ long time_spent_second;
+ double percentage_difference = 0.0;
+ char *result_message;
+
+ for (int i = 0; i < list_size; i++)
+ {
+ random_oid = (Oid) (random() % (UINT_MAX - 1) + 1);
+ list_first = lappend_oid(list_first, random_oid);
+ list_second = lappend_oid(list_second, random_oid);
+ }
+
+ // Timing the first sort function
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ list_sort(list_first, list_oid_cmp);
+ clock_gettime(CLOCK_MONOTONIC, &end);
+ time_spent_first = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+ // Timing the second sort function
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ list_oid_sort(list_second);
+ clock_gettime(CLOCK_MONOTONIC, &end);
+ time_spent_second = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+ percentage_difference = ((double)(time_spent_first - time_spent_second) / time_spent_first) * 100.0;
+
+ list_free(list_first);
+ list_free(list_second);
+
+ result_message = psprintf("Time taken by list_sort: %ld ns, Time taken by list_oid_sort: %ld ns, Percentage difference: %.2f%%",
+ time_spent_first, time_spent_second, percentage_difference);
+ PG_RETURN_TEXT_P(cstring_to_text(result_message));
+}
+
+Datum
+bench_int_sort(PG_FUNCTION_ARGS)
+{
+ int32 list_size = PG_GETARG_INT32(0);
+ List *list_first = NIL;
+ List *list_second = NIL;
+ int random_int;
+ struct timespec start, end;
+ long time_spent_first;
+ long time_spent_second;
+ double percentage_difference = 0.0;
+ char *result_message;
+
+ for (int i = 0; i < list_size; i++)
+ {
+ random_int = rand();
+ list_first = lappend_int(list_first, random_int);
+ list_second = lappend_int(list_second, random_int);
+ }
+
+ // Timing the first sort function
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ list_sort(list_first, list_oid_cmp);
+ clock_gettime(CLOCK_MONOTONIC, &end);
+ time_spent_first = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+ // Timing the second sort function
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ list_int_sort(list_second);
+ clock_gettime(CLOCK_MONOTONIC, &end);
+ time_spent_second = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+ percentage_difference = ((double)(time_spent_first - time_spent_second) / time_spent_first) * 100.0;
+
+ list_free(list_first);
+ list_free(list_second);
+
+ result_message = psprintf("Time taken by list_sort: %ld ns, Time taken by list_int_sort: %ld ns, Percentage difference: %.2f%%",
+ time_spent_first, time_spent_second, percentage_difference);
+ PG_RETURN_TEXT_P(cstring_to_text(result_message));
+}
+
+/*
+stupid copy for tests
+*/
+static int
+compare_int16(const void *a, const void *b)
+{
+ int av = *(const int16 *) a;
+ int bv = *(const int16 *) b;
+
+ /* this can't overflow if int is wider than int16 */
+ return (av - bv);
+}
+
+Datum
+bench_int16_sort(PG_FUNCTION_ARGS)
+{
+ int32 arr_size = PG_GETARG_INT32(0);
+ int16 *arr_first = (int16 *)palloc(arr_size * sizeof(int16));
+ int16 *arr_second = (int16 *)palloc(arr_size * sizeof(int16));
+ struct timespec start, end;
+ long time_spent_first;
+ long time_spent_second;
+ double percentage_difference = 0.0;
+ char *result_message;
+
+ for (int i = 0; i < arr_size; i++)
+ {
+ arr_first[i] = (int16)rand();
+ arr_second[i] = (int16)rand();
+ }
+
+ // Timing the first sort function
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ qsort(arr_first, arr_size, sizeof(int16), compare_int16);
+ clock_gettime(CLOCK_MONOTONIC, &end);
+ time_spent_first = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+ // Timing the second sort function
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ sort_int_16_arr(arr_second, arr_size);
+ clock_gettime(CLOCK_MONOTONIC, &end);
+ time_spent_second = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+ percentage_difference = ((double)(time_spent_first - time_spent_second) / time_spent_first) * 100.0;
+
+ pfree(arr_first);
+ pfree(arr_second);
+
+ result_message = psprintf("Time taken by usual sort: %ld ns, Time taken by optimized sort: %ld ns, Percentage difference: %.2f%%",
+ time_spent_first, time_spent_second, percentage_difference);
+ PG_RETURN_TEXT_P(cstring_to_text(result_message));
+}
+
+double inline rand_double() {
+ return (double)rand() / RAND_MAX;
+}
+
+/*
+stupid copy for tests
+*/
+static int
+compareDoubles(const void *a, const void *b)
+{
+ float8 x = *(float8 *) a;
+ float8 y = *(float8 *) b;
+
+ if (x == y)
+ return 0;
+ return (x > y) ? 1 : -1;
+}
+
+/*
+stupid copy for tests
+*/
+#define ST_SORT sort_float8_arr
+#define ST_ELEMENT_TYPE float8
+#define ST_COMPARE(a, b) compareDoubles(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
+Datum
+bench_float8_sort(PG_FUNCTION_ARGS)
+{
+ int32 arr_size = PG_GETARG_INT32(0);
+ float8 *arr_first = (float8 *)palloc(arr_size * sizeof(float8));
+ float8 *arr_second = (float8 *)palloc(arr_size * sizeof(float8));
+ struct timespec start, end;
+ long time_spent_first;
+ long time_spent_second;
+ double percentage_difference = 0.0;
+ char *result_message;
+
+ for (int i = 0; i < arr_size; i++)
+ {
+ arr_first[i] = rand_double();
+ arr_second[i] = rand_double();
+ }
+
+ // Timing the first sort function
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ qsort(arr_first, arr_size, sizeof(float8), compareDoubles);
+ clock_gettime(CLOCK_MONOTONIC, &end);
+ time_spent_first = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+ // Timing the second sort function
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ sort_float8_arr(arr_second, arr_size);
+ clock_gettime(CLOCK_MONOTONIC, &end);
+ time_spent_second = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+ percentage_difference = ((double)(time_spent_first - time_spent_second) / time_spent_first) * 100.0;
+
+ pfree(arr_first);
+ pfree(arr_second);
+
+ result_message = psprintf("Time taken by usual sort: %ld ns, Time taken by optimized sort: %ld ns, Percentage difference: %.2f%%",
+ time_spent_first, time_spent_second, percentage_difference);
+ PG_RETURN_TEXT_P(cstring_to_text(result_message));
+}
+
+void
+_PG_init()
+{
+ srand(time(NULL));
+}
\ No newline at end of file
diff --git a/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql b/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
new file mode 100644
index 0000000000..5c51a5ef81
--- /dev/null
+++ b/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
@@ -0,0 +1,7 @@
+create function bench_oid_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_oid_sort' LANGUAGE C;
+
+create function bench_int_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_int_sort' LANGUAGE C;
+
+create function bench_int16_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_int16_sort' LANGUAGE C;
+
+create function bench_float8_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_float8_sort' LANGUAGE C;
diff --git a/contrib/bench_sort_improvements/bench_sort_improvements.control b/contrib/bench_sort_improvements/bench_sort_improvements.control
new file mode 100644
index 0000000000..7dc05056ac
--- /dev/null
+++ b/contrib/bench_sort_improvements/bench_sort_improvements.control
@@ -0,0 +1,5 @@
+# fuzzystrmatch extension
+comment = 'test extension'
+default_version = '1.0'
+module_pathname = '$libdir/bench_sort_improvements'
+relocatable = true
--
2.43.0
From b55e9c3ea08140928589d25275e00cc68f0edbe9 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:44:13 +0700
Subject: [PATCH v2 08/10] Replace qsort calls with the new sorting template
`sort_float8_arr` for better performance in spg_box_quad_picksplit function.
---
src/backend/utils/adt/geo_spgist.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/src/backend/utils/adt/geo_spgist.c b/src/backend/utils/adt/geo_spgist.c
index fa0a753fa4..e9ce26d816 100644
--- a/src/backend/utils/adt/geo_spgist.c
+++ b/src/backend/utils/adt/geo_spgist.c
@@ -472,10 +472,10 @@ spg_box_quad_picksplit(PG_FUNCTION_ARGS)
highYs[i] = box->high.y;
}
- qsort(lowXs, in->nTuples, sizeof(float8), compareDoubles);
- qsort(highXs, in->nTuples, sizeof(float8), compareDoubles);
- qsort(lowYs, in->nTuples, sizeof(float8), compareDoubles);
- qsort(highYs, in->nTuples, sizeof(float8), compareDoubles);
+ sort_float8_arr(lowXs, in->nTuples);
+ sort_float8_arr(highXs, in->nTuples);
+ sort_float8_arr(lowYs, in->nTuples);
+ sort_float8_arr(highYs, in->nTuples);
median = in->nTuples / 2;
--
2.43.0
From fafe3079d4a1316f88e3b5107a7131fe0b028c58 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <sndc...@gmail.com>
Date: Sun, 8 Sep 2024 15:44:22 +0700
Subject: [PATCH v2 10/10] Refactor LSN Sorting to Use Template-Based
sort_cmp_lsn
Refactored the sorting logic for Write, Flush, and Apply LSN arrays in SyncRepGetNthLatestSyncRecPtr to replace qsort with the optimized sort_cmp_lsn function, which leverages a template-based sorting mechanism.
---
src/backend/replication/syncrep.c | 29 +++++++++++++----------------
1 file changed, 13 insertions(+), 16 deletions(-)
diff --git a/src/backend/replication/syncrep.c b/src/backend/replication/syncrep.c
index fa5988c824..bea4b7275b 100644
--- a/src/backend/replication/syncrep.c
+++ b/src/backend/replication/syncrep.c
@@ -118,7 +118,6 @@ static void SyncRepGetNthLatestSyncRecPtr(XLogRecPtr *writePtr,
uint8 nth);
static int SyncRepGetStandbyPriority(void);
static int standby_priority_comparator(const void *a, const void *b);
-static int cmp_lsn(const void *a, const void *b);
#ifdef USE_ASSERT_CHECKING
static bool SyncRepQueueIsOrderedByLSN(int mode);
@@ -642,6 +641,16 @@ SyncRepGetOldestSyncRecPtr(XLogRecPtr *writePtr,
}
}
+/*
+- * Compare lsn in order to sort array in descending order.
+-*/
+#define ST_SORT sort_cmp_lsn
+#define ST_ELEMENT_TYPE XLogRecPtr
+#define ST_COMPARE(a, b) pg_cmp_u64(*(b), *(a)) /* Dereference pointers for comparison */
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
/*
* Calculate the Nth latest Write, Flush and Apply positions among sync
* standbys.
@@ -674,9 +683,9 @@ SyncRepGetNthLatestSyncRecPtr(XLogRecPtr *writePtr,
}
/* Sort each array in descending order */
- qsort(write_array, num_standbys, sizeof(XLogRecPtr), cmp_lsn);
- qsort(flush_array, num_standbys, sizeof(XLogRecPtr), cmp_lsn);
- qsort(apply_array, num_standbys, sizeof(XLogRecPtr), cmp_lsn);
+ sort_cmp_lsn(write_array, num_standbys);
+ sort_cmp_lsn(flush_array, num_standbys);
+ sort_cmp_lsn(apply_array, num_standbys);
/* Get Nth latest Write, Flush, Apply positions */
*writePtr = write_array[nth - 1];
@@ -688,18 +697,6 @@ SyncRepGetNthLatestSyncRecPtr(XLogRecPtr *writePtr,
pfree(apply_array);
}
-/*
- * Compare lsn in order to sort array in descending order.
- */
-static int
-cmp_lsn(const void *a, const void *b)
-{
- XLogRecPtr lsn1 = *((const XLogRecPtr *) a);
- XLogRecPtr lsn2 = *((const XLogRecPtr *) b);
-
- return pg_cmp_u64(lsn2, lsn1);
-}
-
/*
* Return data about walsenders that are candidates to be sync standbys.
*
--
2.43.0
