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 18:20:35 +0200
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAEZATCW+N9qaE=5_1xcB0isMrirojN=Bd0yY4Pw67iji4swYiQ@mail.gmail.com>
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>
On Tue, Jul 2, 2024, at 13:44, Dean Rasheed wrote:
>> Can you think of an example that should trigger the bug?
>
> 9999.0001 * 5000.9999_9999 with rscale = 0 triggers it (returned
> 50004999 instead of 50005000).
Thanks, helpful.
Attached patch adds the var1ndigits=3 case.
Benchmark:
/*
* Apple M3 Max
*/
SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- HEAD
Time: 3809.005 ms (00:03.809)
Time: 3438.260 ms (00:03.438)
Time: 3453.920 ms (00:03.454)
SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
Time: 3230.017 ms (00:03.230)
Time: 3244.094 ms (00:03.244)
Time: 3246.370 ms (00:03.246)
/*
* Intel Core i9-14900K
*/
SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- HEAD
Time: 4082.759 ms (00:04.083)
Time: 4077.372 ms (00:04.077)
Time: 4080.830 ms (00:04.081)
SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
Time: 3989.021 ms (00:03.989)
Time: 3978.263 ms (00:03.978)
Time: 3955.331 ms (00:03.955)
/*
* AMD Ryzen 9 7950X3D
*/
SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- HEAD
Time: 3791.271 ms (00:03.791)
Time: 3760.138 ms (00:03.760)
Time: 3758.773 ms (00:03.759)
SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
Time: 3400.824 ms (00:03.401)
Time: 3373.714 ms (00:03.374)
Time: 3345.505 ms (00:03.346)
Regards,
Joel
Attachments:
[application/octet-stream] v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch (4.1K, ../[email protected]/2-v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch)
download | inline diff:
From ece9611d080f0c048cef6e413f4a5e51683ec177 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 | 100 ++++++++++++++++++++++++++++++++
1 file changed, 100 insertions(+)
diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c
index 5510a203b0..0fb217f6e9 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -8747,6 +8747,106 @@ 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:
+ newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
+ if (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:
+ newdig = (int) var1digits[2] * var2digits[res_ndigits - 5];
+ if (res_ndigits - 4 < var2ndigits)
+ newdig += (int) var1digits[1] * var2digits[res_ndigits - 4];
+ if (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 (13+ 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