From f91fe2d895bc19acccac06a098fe947df7d3ac41 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Thu, 15 Feb 2024 15:52:10 -0600
Subject: [PATCH v8 2/3] Introduce efficient, overflow-aware integer comparison
 functions.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This commit adds integer comparison functions that are designed to
be as efficient as possible while avoiding overflow.  A follow-up
commit will make use of these functions in many of the in-tree
qsort() comparators.  The new functions are not a clear win in all
cases (e.g., when the comparator function is inlined), so it is
important to consider the context before using them.

Author: Mats Kindahl
Reviewed-by: Tom Lane, Heikki Linnakangas, Andres Freund, Thomas Munro, Andrey Borodin, Fabrízio de Royes Mello
Discussion: https://postgr.es/m/CA%2B14426g2Wa9QuUpmakwPxXFWG_1FaY0AsApkvcTBy-YfS6uaw%40mail.gmail.com
---
 src/include/common/int.h        | 75 ++++++++++++++++++++++++++++++++-
 src/include/lib/sort_template.h | 13 ++++++
 2 files changed, 86 insertions(+), 2 deletions(-)

diff --git a/src/include/common/int.h b/src/include/common/int.h
index fedf7b3999..fa2d6329f1 100644
--- a/src/include/common/int.h
+++ b/src/include/common/int.h
@@ -1,7 +1,7 @@
 /*-------------------------------------------------------------------------
  *
  * int.h
- *	  Routines to perform integer math, while checking for overflows.
+ *	  Overflow-aware integer math and integer comparison routines.
  *
  * The routines in this file are intended to be well defined C, without
  * relying on compiler flags like -fwrapv.
@@ -22,7 +22,7 @@
 
 
 /*---------
- * The following guidelines apply to all the routines:
+ * The following guidelines apply to all the overflow routines:
  * - If a + b overflows, return true, otherwise store the result of a + b
  * into *result. The content of *result is implementation defined in case of
  * overflow.
@@ -438,4 +438,75 @@ pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result)
 #endif
 }
 
+/*------------------------------------------------------------------------
+ *
+ * Comparison routines for integer types.
+ *
+ * These routines are primarily intended for use in qsort() comparator
+ * functions and therefore return a positive integer, 0, or a negative
+ * integer depending on whether "a" is greater than, equal to, or less
+ * than "b", respectively.  These functions are written to be as efficient
+ * as possible without introducing overflow risks, thereby helping ensure
+ * the comparators that use them are transitive.
+ *
+ * Types with fewer than 32 bits are cast to signed integers and
+ * subtracted.  Other types are compared using > and <, and the results of
+ * those comparisons (which are either (int) 0 or (int) 1 per the C
+ * standard) are subtracted.
+ *
+ * NB: If the comparator functions are 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;
+ *
+ *------------------------------------------------------------------------
+ */
+
+static inline int
+pg_cmp_s16(int16 a, int16 b)
+{
+	return (int32) a - (int32) b;
+}
+
+static inline int
+pg_cmp_u16(uint16 a, uint16 b)
+{
+	return (int32) a - (int32) b;
+}
+
+static inline int
+pg_cmp_s32(int32 a, int32 b)
+{
+	return (a > b) - (a < b);
+}
+
+static inline int
+pg_cmp_u32(uint32 a, uint32 b)
+{
+	return (a > b) - (a < b);
+}
+
+static inline int
+pg_cmp_s64(int64 a, int64 b)
+{
+	return (a > b) - (a < b);
+}
+
+static inline int
+pg_cmp_u64(uint64 a, uint64 b)
+{
+	return (a > b) - (a < b);
+}
+
+static inline int
+pg_cmp_size(size_t a, size_t b)
+{
+	return (a > b) - (a < b);
+}
+
 #endif							/* COMMON_INT_H */
diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h
index a470fa1103..6772bf5ee3 100644
--- a/src/include/lib/sort_template.h
+++ b/src/include/lib/sort_template.h
@@ -34,6 +34,16 @@
  *	  - ST_COMPARE(a, b, arg) - variant that takes an extra argument
  *	  - ST_COMPARE_RUNTIME_POINTER - sort function takes a function pointer
  *
+ *    NB: If the comparator function is inlined, some compilers may produce
+ *    worse code with the optimized comparison routines in common/int.h than
+ *    with code with the following form:
+ *
+ *        if (a < b)
+ *            return -1;
+ *        if (a > b)
+ *            return 1;
+ *        return 0;
+ *
  *	  To say that the comparator and therefore also sort function should
  *	  receive an extra pass-through argument, specify the type of the
  *	  argument.
@@ -243,6 +253,9 @@ ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n
  * Find the median of three values.  Currently, performance seems to be best
  * if the comparator is inlined here, but the med3 function is not inlined
  * in the qsort function.
+ *
+ * Refer to the comment at the top of this file for known caveats to consider
+ * when writing inlined comparator functions.
  */
 static pg_noinline ST_ELEMENT_TYPE *
 ST_MED3(ST_ELEMENT_TYPE * a,
-- 
2.25.1