> +/* Needed for sort template to work with pointers to PagetableEntry */
> +typedef PagetableEntry *PagetableEntryPtr;
>
> This is a workaround; let's fix it properly, like this:
>
> ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data;
> ST_POINTER_TYPE *pa;
> ST_POINTER_TYPE *pb;
> ...
>
> I see that Thomas already encountered that problem in the 0001 patch
> of that series:
>
> https://www.postgresql.org/message-id/attachment/120554/0001-Add-bsearch-and-unique-templates-to-sort_template.h.patch
Makes sense. I should have done that right away. Done in patch v2-0001.
> +#define ST_COMPARE(a, b) pg_cmp_u32((*(a))->blockno, (*(b))->blockno)
> ...
> +#define ST_COMPARE(a, b, base) pg_cmp_u32(base[*(a)].blockno,
> base[*(b)].blockno)
>
> There's a comment in common/int.h that says:
>
> * NB: If the comparator function is inlined, some compilers may produce
> * worse code with these helper functions than with code with the
> * following form:
> *
> * if (a < b)
> * return -1;
> * if (a > b)
> * return 1;
> * return 0;
>
> ...and that's been true every time it's tried. It should be fine to
> instead make the current comparators static inline and make both match
> the above pattern. You might get a further speed-up.
Oh, right. The qsort partitioning code does:
return DO_COMPARE(a, b) < 0 ?
(DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
: (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
With the if-cascade the compiler can better optimize the expression in
DO_COMPARE().
I revived the original comparators with some minor modifications.
Runtimes of just the sorting now are:
master: 189 ms
patched v1: 136 ms
patched v2: 106 ms
Nice additional speedup!
--
David GeierFrom 029ec00036db1d218df83117ad576299287e888d Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Tue, 13 Oct 2026 13:36:22 +0200
Subject: [PATCH v2 2/2] TIDBitmap uses sort_template.h for pagetable sorting
Generate specialized sort functions for the pagetable instead of
going through generic qsort()/qsort_arg() comparator calls. The
inlined comparator avoids function call overhead per comparison.
The shared-iteration index arrays need the pagetable base address
to resolve indexes to entries, so that variant uses
ST_COMPARE_ARG_TYPE to pass it through.
---
src/backend/nodes/tidbitmap.c | 58 ++++++++++++++++++++++-------------
1 file changed, 37 insertions(+), 21 deletions(-)
diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index f1f925cb13b..5108ba1eef1 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -225,9 +225,10 @@ static PagetableEntry *tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno);
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno);
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno);
static void tbm_lossify(TIDBitmap *tbm);
-static int tbm_comparator(const void *left, const void *right);
-static int tbm_shared_comparator(const void *left, const void *right,
- void *arg);
+static inline int tbm_comparator(PagetableEntry **lpage,
+ PagetableEntry **rpage);
+static inline int tbm_shared_comparator(const int *lindex, const int *rindex,
+ const PagetableEntry *base);
/* define hashtable mapping block numbers to PagetableEntry's */
#define SH_USE_NONDEFAULT_ALLOCATOR
@@ -242,6 +243,25 @@ static int tbm_shared_comparator(const void *left, const void *right,
#define SH_DECLARE
#include "lib/simplehash.h"
+#define ST_SORT qsort_pagetable
+#define ST_ELEMENT_TYPE PagetableEntry *
+#define ST_COMPARE(a, b) tbm_comparator(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+/*
+ * The shared-iteration arrays contain indexes into the pagetable entry
+ * array rather than pointers, so their comparator needs the base address
+ * of the entry array passed through as an argument.
+ */
+#define ST_SORT qsort_pagetable_index
+#define ST_ELEMENT_TYPE int
+#define ST_COMPARE(a, b, arg) tbm_shared_comparator(a, b, arg)
+#define ST_COMPARE_ARG_TYPE PagetableEntry
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
/*
* tbm_create - create an initially-empty bitmap
@@ -727,11 +747,9 @@ tbm_begin_private_iterate(TIDBitmap *tbm)
Assert(npages == tbm->npages);
Assert(nchunks == tbm->nchunks);
if (npages > 1)
- qsort(tbm->spages, npages, sizeof(PagetableEntry *),
- tbm_comparator);
+ qsort_pagetable(tbm->spages, npages);
if (nchunks > 1)
- qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
- tbm_comparator);
+ qsort_pagetable(tbm->schunks, nchunks);
}
tbm->iterating = TBM_ITERATING_PRIVATE;
@@ -840,11 +858,9 @@ tbm_prepare_shared_iterate(TIDBitmap *tbm)
if (ptbase != NULL)
pg_atomic_init_u32(&ptbase->refcount, 0);
if (npages > 1)
- qsort_arg(ptpages->index, npages, sizeof(int),
- tbm_shared_comparator, ptbase->ptentry);
+ qsort_pagetable_index(ptpages->index, npages, ptbase->ptentry);
if (nchunks > 1)
- qsort_arg(ptchunks->index, nchunks, sizeof(int),
- tbm_shared_comparator, ptbase->ptentry);
+ qsort_pagetable_index(ptchunks->index, nchunks, ptbase->ptentry);
}
/*
@@ -1421,13 +1437,14 @@ tbm_lossify(TIDBitmap *tbm)
/*
* qsort comparator to handle PagetableEntry pointers.
*/
-static int
-tbm_comparator(const void *left, const void *right)
+static inline int
+tbm_comparator( PagetableEntry **lpage, PagetableEntry **rpage)
{
- BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
- BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
-
- return pg_cmp_u32(l, r);
+ if ((*lpage)->blockno < (*rpage)->blockno)
+ return -1;
+ else if ((*lpage)->blockno > (*rpage)->blockno)
+ return 1;
+ return 0;
}
/*
@@ -1436,11 +1453,10 @@ tbm_comparator(const void *left, const void *right)
* blockno.
*/
static int
-tbm_shared_comparator(const void *left, const void *right, void *arg)
+tbm_shared_comparator(const int *lindex, const int *rindex, const PagetableEntry *base)
{
- PagetableEntry *base = (PagetableEntry *) arg;
- PagetableEntry *lpage = &base[*(const int *) left];
- PagetableEntry *rpage = &base[*(const int *) right];
+ const PagetableEntry *lpage = &base[*lindex];
+ const PagetableEntry *rpage = &base[*rindex];
if (lpage->blockno < rpage->blockno)
return -1;
--
2.53.0
From 763cffbad4f90cb75b703b7483772f2e475d2842 Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Wed, 14 Oct 2026 14:17:42 +0200
Subject: [PATCH v2 1/2] sort_template.h supports pointer element types
Changed the ST_POINTER_TYPE variable declarations in ST_SORT()
to work with ST_ELEMENT_TYPEs which are pointers.
---
src/include/lib/sort_template.h | 16 ++++++++--------
1 file changed, 8 insertions(+), 8 deletions(-)
diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h
index 22b2092d03b..eae2d80270f 100644
--- a/src/include/lib/sort_template.h
+++ b/src/include/lib/sort_template.h
@@ -294,14 +294,14 @@ ST_SORT(ST_ELEMENT_TYPE * data, size_t n
ST_SORT_PROTO_COMPARE
ST_SORT_PROTO_ARG)
{
- ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data,
- *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data;
+ ST_POINTER_TYPE *pa;
+ ST_POINTER_TYPE *pb;
+ ST_POINTER_TYPE *pc;
+ ST_POINTER_TYPE *pd;
+ ST_POINTER_TYPE *pl;
+ ST_POINTER_TYPE *pm;
+ ST_POINTER_TYPE *pn;
size_t d1,
d2;
int r,
--
2.53.0
