v30-0003-Bucket-sort-for-compactify_tuples.patch

From 64c03b2040eefa8164447534bf1c3dd5d5cbb320 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Tue, 14 Jan 2020 15:27:54 -0800
Subject: [PATCH v30 3/5] Bucket sort for compactify_tuples.

Original commit message from Sokolov Yura:

This patch implements bucket sort for compactify_tuples:
- one pass of stable prefix sort on high 8 bits of offset
- and insertion sort for buckets larger than 1 element

This approach allows to save 3% of cpu in degenerate case
(highly intensive HOT random updates on unlogged table with
 synchronized_commit=off), and speeds up WAL replaying (as were
found by Heikki Linnakangas).

Same approach were implemented by Heikki Linnakangas some time ago with
several distinctions.

This patch was retrieved from:
https://postgr.es/m/CAL-rCA2n7UfVu1Ui0f%2B7cVN4vAKVM0%2B-cZKb_ka6-mGQBAF92w%40mail.gmail.com

CF Entry for patch: https://commitfest.postgresql.org/14/1138/

Related thread: https://postgr.es/m/546B89DE.7030906%40vmware.com
---
 src/backend/storage/page/bufpage.c | 80 +++++++++++++++++++++++++++++-
 1 file changed, 78 insertions(+), 2 deletions(-)

diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c
index 32ff03b3e4..0081dd921b 100644
--- a/src/backend/storage/page/bufpage.c
+++ b/src/backend/storage/page/bufpage.c
@@ -436,6 +436,79 @@ itemoffcompare(const void *itemidp1, const void *itemidp2)
 		((itemIdSort) itemidp1)->itemoff;
 }
 
+#define QS_SUFFIX itemIds
+#define QS_TYPE itemIdSortData
+#define QS_SCOPE static
+#define QS_CMP itemoffcompare
+#define QS_DEFINE
+#define QS_SKIP_MED3
+#include "lib/qsort_template.h"
+
+/*
+ * Sort an array of itemIdSort's on itemoff, descending.
+ *
+ * It uses bucket sort:
+ * - single pass of stable prefix sort on high 8 bits
+ * - and insertion sort on buckets larger than 1 element
+ */
+static void
+bucketsort_itemIds(itemIdSort itemidbase, int nitems)
+{
+	itemIdSortData copy[Max(MaxIndexTuplesPerPage, MaxHeapTuplesPerPage)];
+#define NSPLIT 256
+#define PREFDIV (BLCKSZ / NSPLIT)
+	/* two extra elements to emulate offset on previous step */
+	uint16		count[NSPLIT + 2] = {0};
+	int			i,
+				max,
+				total,
+				pos,
+				highbits;
+
+	Assert(nitems <= MaxIndexTuplesPerPage);
+	for (i = 0; i < nitems; i++)
+	{
+		highbits = itemidbase[i].itemoff / PREFDIV;
+		count[highbits]++;
+	}
+	/* sort in decreasing order */
+	max = total = count[NSPLIT - 1];
+	for (i = NSPLIT - 2; i >= 0; i--)
+	{
+		max |= count[i];
+		total += count[i];
+		count[i] = total;
+	}
+
+	/*
+	 * count[k+1] is start of bucket k, count[k] is end of bucket k, and
+	 * count[k] - count[k+1] is length of bucket k.
+	 */
+	Assert(count[0] == nitems);
+	for (i = 0; i < nitems; i++)
+	{
+		highbits = itemidbase[i].itemoff / PREFDIV;
+		pos = count[highbits + 1];
+		count[highbits + 1]++;
+		copy[pos] = itemidbase[i];
+	}
+	Assert(count[1] == nitems);
+
+	if (max > 1)
+	{
+		/*
+		 * count[k+2] is start of bucket k, count[k+1] is end of bucket k, and
+		 * count[k+1]-count[k+2] is length of bucket k.
+		 */
+		for (i = NSPLIT; i > 0; i--)
+		{
+			insertion_sort_itemIds(copy + count[i + 1], count[i] - count[i + 1]);
+		}
+	}
+
+	memcpy(itemidbase, copy, sizeof(itemIdSortData) * nitems);
+}
+
 /*
  * After removing or marking some line pointers unused, move the tuples to
  * remove the gaps caused by the removed items.
@@ -448,8 +521,11 @@ compactify_tuples(itemIdSort itemidbase, int nitems, Page page)
 	int			i;
 
 	/* sort itemIdSortData array into decreasing itemoff order */
-	qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),
-		  itemoffcompare);
+	if (nitems > 48)
+		bucketsort_itemIds(itemidbase, nitems);
+	else
+		qsort_itemIds(itemidbase, nitems);
+
 
 	upper = phdr->pd_special;
 	for (i = 0; i < nitems; i++)
-- 
2.17.1