0007-Experiment-Remove-shellsort-just-use-qsort.patch

From 84fcd24909eeb10294c2ba7bb6f46a15d04a49a4 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Mon, 11 Jan 2021 14:51:16 -0800
Subject: [PATCH 7/7] Experiment: Remove shellsort, just use qsort

---
 src/backend/access/heap/heapam.c | 41 ++++++--------------------------
 1 file changed, 7 insertions(+), 34 deletions(-)

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 7eb4962946..e4dac65ade 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -7304,11 +7304,13 @@ heap_index_delete_tuples(Relation rel, TM_IndexDeleteOp *delstate)
 }
 
 /*
- * Specialized inlineable comparison function for index_delete_sort()
+ * qsort comparison function for index_delete_sort()
  */
-static inline int
-index_delete_sort_cmp(TM_IndexDelete *deltid1, TM_IndexDelete *deltid2)
+static int
+index_delete_sort_cmp(const void *arg1, const void *arg2)
 {
+	TM_IndexDelete *deltid1 = (TM_IndexDelete *) arg1;
+	TM_IndexDelete *deltid2 = (TM_IndexDelete *) arg2;
 	ItemPointer tid1 = &deltid1->tid;
 	ItemPointer tid2 = &deltid2->tid;
 
@@ -7335,43 +7337,14 @@ index_delete_sort_cmp(TM_IndexDelete *deltid1, TM_IndexDelete *deltid2)
 /*
  * Sort deltids array from delstate by TID.  This prepares it for further
  * processing by heap_index_delete_tuples().
- *
- * This operation becomes a noticeable consumer of CPU cycles with some
- * workloads, so we go to the trouble of specialization/micro optimization.
- * We use shellsort for this because it's easy to specialize, compiles to
- * relatively few instructions, and is adaptive to presorted inputs/subsets
- * (which are typical here).
  */
 static void
 index_delete_sort(TM_IndexDeleteOp *delstate)
 {
 	TM_IndexDelete *deltids = delstate->deltids;
-	int			ndeltids = delstate->ndeltids;
-	int			low = 0;
+	int				ndeltids = delstate->ndeltids;
 
-	/*
-	 * Shellsort gap sequence (taken from Sedgewick-Incerpi paper).
-	 *
-	 * This implementation is fast with array sizes up to ~4500.  This covers
-	 * all supported BLCKSZ values.
-	 */
-	const int	gaps[9] = {1968, 861, 336, 112, 48, 21, 7, 3, 1};
-
-	for (int g = 0; g < lengthof(gaps); g++)
-	{
-		for (int hi = gaps[g], i = low + hi; i < ndeltids; i++)
-		{
-			TM_IndexDelete d = deltids[i];
-			int			j = i;
-
-			while (j >= hi && index_delete_sort_cmp(&deltids[j - hi], &d) >= 0)
-			{
-				deltids[j] = deltids[j - hi];
-				j -= hi;
-			}
-			deltids[j] = d;
-		}
-	}
+	qsort(deltids, ndeltids, sizeof(TM_IndexDelete), index_delete_sort_cmp);
 }
 
 /*
-- 
2.27.0