Feedback-ID: ic6394509:Fastmail
User-Agent: Cyrus-JMAP/3.11.0-alpha0-566-g3812ddbbc-fm-20240627.001-g3812ddbb
MIME-Version: 1.0
Message-Id: <bbc62c2d-1173-4454-9e17-be99437c0e7e@app.fastmail.com>
In-Reply-To: 
 <CAEZATCWEou=NjpvS-r1WxymbAYihsdKQoQBj1HfBeocoNcv5Ww@mail.gmail.com>
References: <44d2ffca-d560-4919-b85a-4d07060946aa@app.fastmail.com>
 <87zfr1e1uj.fsf@wibble.ilmari.org>
 <9ff90ff9-5ac1-4529-b2f4-f93b37734b9c@app.fastmail.com>
 <81348268-b9fd-4308-bf52-056070aa7c2a@app.fastmail.com>
 <f25ddfc8-4f02-4e8f-8e74-0532f48d0817@app.fastmail.com>
 <CAEZATCV2qPTGo2Fd8xDs06Q7iU5aorgSa9+Fw9zkuQv1y15rcw@mail.gmail.com>
 <8e909218-1965-4515-99e3-4bb5b625e004@app.fastmail.com>
 <CAEZATCWEou=NjpvS-r1WxymbAYihsdKQoQBj1HfBeocoNcv5Ww@mail.gmail.com>
Date: Tue, 02 Jul 2024 11:05:03 +0200
From: "Joel Jacobson" <joel@compiler.org>
To: "Dean Rasheed" <dean.a.rasheed@gmail.com>
Cc: =?UTF-8?Q?Dagfinn_Ilmari_Manns=C3=A5ker?= <ilmari@ilmari.org>,
 pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: Optimize numeric multiplication for one and two base-NBASE digit
 multiplicands.
Content-Type: text/plain
Archived-At: <https://www.postgresql.org/message-id/bbc62c2d-1173-4454-9e17-be99437c0e7e%40app.fastmail.com>
Precedence: bulk

On Tue, Jul 2, 2024, at 10:22, Dean Rasheed wrote:
> Shortly after posting that, I realised that there was a small bug. This bit:
>
>             case 2:
>                 newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
>
> isn't quite right in the case where rscale is less than the full
> result. In that case, the least significant result digit has a
> contribution from one more var2 digit, so it needs to be:
>
>                 newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
>                 if (res_ndigits - 3 < var2ndigits)
>                     newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
>
> That doesn't noticeably affect the performance though. Update attached.

Nice catch. Could we add a test somehow that would test mul_var()
with rscale less than the full result, that would catch bugs like this one
and others?

I created a new benchmark, that specifically tests different var1ndigits.
I've only run it on Apple M3 Max yet. More to come.

\timing
SELECT setseed(0.12345);
CREATE TABLE bench_mul_var_var1ndigits_1 (var1 numeric, var2 numeric);
INSERT INTO bench_mul_var_var1ndigits_1 (var1, var2)
SELECT random(0::numeric,9999::numeric), random(10000000::numeric,1e32::numeric) FROM generate_series(1,1e8);
CREATE TABLE bench_mul_var_var1ndigits_2 (var1 numeric, var2 numeric);
INSERT INTO bench_mul_var_var1ndigits_2 (var1, var2)
SELECT random(10000000::numeric,99999999::numeric), random(100000000000::numeric,1e32::numeric) FROM generate_series(1,1e8);
CREATE TABLE bench_mul_var_var1ndigits_3 (var1 numeric, var2 numeric);
INSERT INTO bench_mul_var_var1ndigits_3 (var1, var2)
SELECT random(100000000000::numeric,999999999999::numeric), random(1000000000000000::numeric,1e32::numeric) FROM generate_series(1,1e8);
CREATE TABLE bench_mul_var_var1ndigits_4 (var1 numeric, var2 numeric);
INSERT INTO bench_mul_var_var1ndigits_4 (var1, var2)
SELECT random(1000000000000000::numeric,9999999999999999::numeric), random(10000000000000000000::numeric,1e32::numeric) FROM generate_series(1,1e8);

/*
 * Apple M3 Max
 */

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_1; -- HEAD
Time: 2986.952 ms (00:02.987)
Time: 2991.765 ms (00:02.992)
Time: 2987.253 ms (00:02.987)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_1; -- v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
Time: 2874.841 ms (00:02.875)
Time: 2883.070 ms (00:02.883)
Time: 2899.973 ms (00:02.900)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_2; -- HEAD
Time: 3459.556 ms (00:03.460)
Time: 3304.983 ms (00:03.305)
Time: 3299.728 ms (00:03.300)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_2; -- v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
Time: 3053.140 ms (00:03.053)
Time: 3065.227 ms (00:03.065)
Time: 3069.995 ms (00:03.070)

/*
 * Just for completeness, also testing var1ndigits 3 and 4,
 * although no change is expected since not yet implemented.
 */

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; -- v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
Time: 3437.592 ms (00:03.438)
Time: 3457.586 ms (00:03.458)
Time: 3474.344 ms (00:03.474)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_4; -- HEAD
Time: 4133.193 ms (00:04.133)
Time: 3554.477 ms (00:03.554)
Time: 3560.855 ms (00:03.561)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_4; -- v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
Time: 3508.540 ms (00:03.509)
Time: 3566.721 ms (00:03.567)
Time: 3524.083 ms (00:03.524)

> I think it'd probably be worth trying to extend this to 3 or maybe 4
> var1 digits, since that would cover a lot of "everyday" sized numeric
> values that a lot of people might be using. I don't think we should go
> beyond that though.

I think so too. I'm working on var1ndigits=3 now.

/Joel