agora inbox for pgsql-hackers@postgresql.org
help / color / mirror / Atom feedFrom: Nathan Bossart <nathan@postgresql.org>
Subject: [PATCH v8 2/3] Introduce efficient, overflow-aware integer comparison functions.
Date: Thu, 15 Feb 2024 15:52:10 -0600
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
--AhhlLboLdkugWU4S
Content-Type: text/x-diff; charset=iso-8859-1
Content-Disposition: attachment;
filename="v8-0003-Use-new-overflow-aware-integer-comparison-functio.patch"
Content-Transfer-Encoding: 8bit
view thread (104+ messages)
Message-ID: <no-message-id-1141023@localhost>
Permalink: ../../no-message-id-1141023@localhost/
Also on: postgresql.org/message-id/no-message-id-1141023@localhost
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: nathan@postgresql.org
Subject: Re: [PATCH v8 2/3] Introduce efficient, overflow-aware integer comparison functions.
In-Reply-To: <no-message-id-1141023@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox