public inbox for [email protected]
help / color / mirror / Atom feedFrom: David Fetter <[email protected]>
To: PostgreSQL Development <[email protected]>
Subject: Shave a few cycles off our ilog10 implementation
Date: Wed, 30 Oct 2024 20:27:40 +0100
Message-ID: <[email protected]> (raw)
Please find attached a patch to $Subject
I've done some preliminary testing, and it appears to shave somewhere
between 25-50% off the operations themselves, and these cascade into
things like formatting result sets and COPY OUT.
Best,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778
Attachments:
[text/x-diff] v1-0001-Shave-a-few-instructions-off-ilog10.patch (4.8K, ../[email protected]/2-v1-0001-Shave-a-few-instructions-off-ilog10.patch)
download | inline diff:
From 612c848d8025d318e5b6e0da5bb04d0f7ed22126 Mon Sep 17 00:00:00 2001
From: David Fetter <[email protected]>
Date: Mon, 28 Oct 2024 04:38:16 -0700
Subject: [PATCH v1] Shave a few instructions off ilog10
by using SWAR and a lookup table.
---
src/backend/utils/adt/numutils.c | 73 ++++++++++++++++++++++++++------
1 file changed, 60 insertions(+), 13 deletions(-)
diff --git a/src/backend/utils/adt/numutils.c b/src/backend/utils/adt/numutils.c
index 63c2beb6a29..a53b647c054 100644
--- a/src/backend/utils/adt/numutils.c
+++ b/src/backend/utils/adt/numutils.c
@@ -39,30 +39,76 @@ static const char DIGIT_TABLE[200] =
"90" "91" "92" "93" "94" "95" "96" "97" "98" "99";
/*
- * Adapted from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
+ * Adapted from https://lemire.me/blog/2021/06/03/computing-the-number-of-digits-of-an-integer-even-faster/
*/
static inline int
decimalLength32(const uint32 v)
{
- int t;
- static const uint32 PowersOfTen[] = {
- 1, 10, 100,
- 1000, 10000, 100000,
- 1000000, 10000000, 100000000,
- 1000000000
+ /* Each entry in the table is a 64-bit unsigned integer.
+ * - The upper 32 bits of this integer is floor(ilog10(v)), a thing we can know from lg(v).
+ * - The lower 32 bits of the integer is a number n such that v + n = 2^32 when v is a power of 10.
+ *
+ * These two parts taken together create a way to put the number of decimal
+ * digits as the upper 32 bits.
+ *
+ */
+ static const uint64_t BaseTwoToBaseTenPivot[] = {
+ 4294967296, 8589934582, 8589934582, 8589934582, 12884901788,
+ 12884901788, 12884901788, 17179868184, 17179868184, 17179868184,
+ 21474826480, 21474826480, 21474826480, 21474826480, 25769703776,
+ 25769703776, 25769703776, 30063771072, 30063771072, 30063771072,
+ 34349738368, 34349738368, 34349738368, 34349738368, 38554705664,
+ 38554705664, 38554705664, 41949672960, 41949672960, 41949672960,
+ 42949672960, 42949672960
};
- /*
- * Compute base-10 logarithm by dividing the base-2 logarithm by a
- * good-enough approximation of the base-2 logarithm of 10
- */
- t = (pg_leftmost_one_pos32(v) + 1) * 1233 / 4096;
- return t + (v >= PowersOfTen[t]);
+ return (v + BaseTwoToBaseTenPivot[pg_leftmost_one_pos32(v)]) >> 32;
}
+/*
+ * Adapted from https://lemire.me/blog/2021/06/03/computing-the-number-of-digits-of-an-integer-even-faster/
+ */
static inline int
decimalLength64(const uint64 v)
{
+#ifdef HAS_INT128
+ /* Each entry in the table is a 128-bit unsigned integer.
+ * - The upper 64 bits of this integer is floor(ilog10(v)), a thing we can know from lg(v).
+ * - The lower 64 bits of the integer is a number n such that v + n = 2^64 when v is a power of 10.
+ *
+ * These two parts taken together create a way to put the number of decimal
+ * digits as the upper 64 bits.
+ *
+ */
+ static const uint128 BaseTwoToBaseTenPivot[] = {
+ 18446744073709551616,
+ 18446744073709551606, 18446744073709551606, 18446744073709551606,
+ 36893488147419103132, 36893488147419103132, 36893488147419103132,
+ 55340232221128653848, 55340232221128653848, 55340232221128653848,
+ 73786976294838196464, 73786976294838196464, 73786976294838196464,
+ 92233720368547658080, 92233720368547658080, 92233720368547658080,
+ 110680464442256309696, 110680464442256309696, 110680464442256309696,
+ 129127208515956861312, 129127208515956861312, 129127208515956861312,
+ 147573952589576412928, 147573952589576412928, 147573952589576412928,
+ 166020696662385964544, 166020696662385964544, 166020696662385964544,
+ 184467440727095516160, 184467440727095516160, 184467440727095516160,
+ 202914184710805067776, 202914184710805067776, 202914184710805067776,
+ 221360927884514619392, 221360927884514619392, 221360927884514619392,
+ 239807662958224171008, 239807662958224171008, 239807662958224171008,
+ 258254317031933722624, 258254317031933722624, 258254317031933722624,
+ 276700161105643274240, 276700161105643274240, 276700161105643274240,
+ 295137905179352825856, 295137905179352825856, 295137905179352825856,
+ 313494649253062377472, 313494649253062377472, 313494649253062377472,
+ 331041393326771929088, 331041393326771929088, 331041393326771929088,
+ 340488137400481480704, 340488137400481480704, 340488137400481480704,
+ 268934881474191032320, 268934881474191032320, 268934881474191032320
+ };
+
+ return (v + BaseTwoToBaseTenPivot[pg_leftmost_one_pos64(v)]) >> 64;
+#else /* !HAVE_INT128 */
+ /*
+ * * Adapted from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
+ */
int t;
static const uint64 PowersOfTen[] = {
UINT64CONST(1), UINT64CONST(10),
@@ -83,6 +129,7 @@ decimalLength64(const uint64 v)
*/
t = (pg_leftmost_one_pos64(v) + 1) * 1233 / 4096;
return t + (v >= PowersOfTen[t]);
+#endif /* HAVE_INT128 */
}
static const int8 hexlookup[128] = {
--
2.47.0
view thread (2+ messages)
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: [email protected]
Cc: [email protected]
Subject: Re: Shave a few cycles off our ilog10 implementation
In-Reply-To: <[email protected]>
* 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