public inbox for [email protected]
help / color / mirror / Atom feedFrom: Joel Jacobson <[email protected]>
To: Dean Rasheed <[email protected]>
Cc: Dagfinn Ilmari Mannsåker <[email protected]>
Cc: pgsql-hackers <[email protected]>
Subject: Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands.
Date: Tue, 02 Jul 2024 22:10:27 +0200
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<CAEZATCV2qPTGo2Fd8xDs06Q7iU5aorgSa9+Fw9zkuQv1y15rcw@mail.gmail.com>
<[email protected]>
<CAEZATCWEou=NjpvS-r1WxymbAYihsdKQoQBj1HfBeocoNcv5Ww@mail.gmail.com>
<[email protected]>
<[email protected]>
<CAEZATCW+N9qaE=5_1xcB0isMrirojN=Bd0yY4Pw67iji4swYiQ@mail.gmail.com>
<[email protected]>
<[email protected]>
<[email protected]>
On Tue, Jul 2, 2024, at 21:55, Joel Jacobson wrote:
> On Tue, Jul 2, 2024, at 20:53, Joel Jacobson wrote:
>> Trying to wrap my head around what could cause this.
I found the bug in the case 3 code,
and it turns out the same type of bug also exists in the case 2 code:
case 2:
newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
The problem here is that res_ndigits could become less than 4,
if rscale is low enough,
and then we would try to access a negative array index in var2digits.
Fix:
case 2:
if (res_ndigits - 4 >= 0 && res_ndigits - 4 < var2ndigits)
newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
else
newdig = 0;
Another problem in the case 2 code:
if (res_ndigits - 3 < var2ndigits)
newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
Fix:
if (res_ndigits - 3 >= 0 && res_ndigits - 3 < var2ndigits)
newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
New version attached that fixes both the case 2 and case 3 code.
Regards,
Joel
Attachments:
[application/octet-stream] v4-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch (4.3K, ../[email protected]/2-v4-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch)
download | inline diff:
From a7d421d5fcd4f6b367f266c3b005c82abff03d7c Mon Sep 17 00:00:00 2001
From: Joel Jakobsson <[email protected]>
Date: Tue, 2 Jul 2024 17:54:25 +0200
Subject: [PATCH] numeric: Simplified fast-path computation for mul_var()
---
src/backend/utils/adt/numeric.c | 106 ++++++++++++++++++++++++++++++++
1 file changed, 106 insertions(+)
diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c
index 5510a203b0..e3bc29b626 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -8747,6 +8747,112 @@ mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result,
return;
}
+ /*
+ * Simplified fast-path computation, if var1 has just one or two digits.
+ * This is significantly faster, since it avoids allocating a separate
+ * digit array, making multiple passes over var2, and having separate
+ * carry-propagation passes.
+ */
+ if (var1ndigits <= 3)
+ {
+ NumericDigit *res_buf;
+
+ /* Allocate result digit array */
+ res_buf = digitbuf_alloc(res_ndigits);
+ res_buf[0] = 0; /* spare digit for later rounding */
+ res_digits = res_buf + 1;
+
+ /*
+ * Compute the result digits directly, in one pass, propagating the
+ * carry up as we go.
+ */
+ switch (var1ndigits)
+ {
+ case 1:
+ carry = 0;
+ for (i = res_ndigits - 3; i >= 0; i--)
+ {
+ newdig = (int) var1digits[0] * var2digits[i] + carry;
+ res_digits[i + 1] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ }
+ res_digits[0] = (NumericDigit) carry;
+ break;
+
+ case 2:
+ if (res_ndigits - 4 >= 0 && res_ndigits - 4 < var2ndigits)
+ newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
+ else
+ newdig = 0;
+ if (res_ndigits - 3 >= 0 && res_ndigits - 3 < var2ndigits)
+ newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
+ res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ for (i = res_ndigits - 4; i >= 1; i--)
+ {
+ newdig = (int) var1digits[0] * var2digits[i] +
+ (int) var1digits[1] * var2digits[i - 1] + carry;
+ res_digits[i + 1] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ }
+ newdig = (int) var1digits[0] * var2digits[0] + carry;
+ res_digits[1] = (NumericDigit) (newdig % NBASE);
+ res_digits[0] = (NumericDigit) (newdig / NBASE);
+ break;
+
+ case 3:
+ if (res_ndigits - 5 >= 0 && res_ndigits - 5 < var2ndigits)
+ newdig = (int) var1digits[2] * var2digits[res_ndigits - 5];
+ else
+ newdig = 0;
+ if (res_ndigits - 4 >= 0 && res_ndigits - 4 < var2ndigits)
+ newdig += (int) var1digits[1] * var2digits[res_ndigits - 4];
+ if (res_ndigits - 3 >= 0 && res_ndigits - 3 < var2ndigits)
+ newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
+ res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ for (i = res_ndigits - 4; i >= 2; i--)
+ {
+ newdig = carry;
+ if (i < var2ndigits)
+ newdig += (int) var1digits[0] * var2digits[i];
+ if (i - 1 >= 0 && i - 1 < var2ndigits)
+ newdig += (int) var1digits[1] * var2digits[i - 1];
+ if (i - 2 >= 0 && i - 2 < var2ndigits)
+ newdig += (int) var1digits[2] * var2digits[i - 2];
+ res_digits[i + 1] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ }
+ newdig = carry;
+ if (var2ndigits > 1)
+ newdig += (int) var1digits[0] * var2digits[1];
+ if (var2ndigits > 0)
+ newdig += (int) var1digits[1] * var2digits[0];
+ res_digits[2] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ newdig = (int) var1digits[0] * var2digits[0] + carry;
+ res_digits[1] = (NumericDigit) (newdig % NBASE);
+ res_digits[0] = (NumericDigit) (newdig / NBASE);
+ break;
+ }
+
+ /* Store the product in result (minus extra rounding digit) */
+ digitbuf_free(result->buf);
+ result->ndigits = res_ndigits - 1;
+ result->buf = res_buf;
+ result->digits = res_digits;
+ result->weight = res_weight - 1;
+ result->sign = res_sign;
+
+ /* Round to target rscale (and set result->dscale) */
+ round_var(result, rscale);
+
+ /* Strip leading and trailing zeroes */
+ strip_var(result);
+
+ return;
+ }
+
/*
* We do the arithmetic in an array "dig[]" of signed int's. Since
* INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom
--
2.45.1
view thread (3+ messages) latest in thread
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], [email protected], [email protected]
Subject: Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands.
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