Feedback-ID: ic6394509:Fastmail
User-Agent: Cyrus-JMAP/3.11.0-alpha0-566-g3812ddbbc-fm-20240627.001-g3812ddbb
MIME-Version: 1.0
Message-Id: <f2a08b83-35f7-4a9b-a3a1-37ffdfb1e2e3@app.fastmail.com>
In-Reply-To: 
 <CAEZATCUmrq4pgJdQNQendiPkmyM=qdnZv1g-vtoMyrOyCi6xdA@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>
 <bbc62c2d-1173-4454-9e17-be99437c0e7e@app.fastmail.com>
 <0459ded5-6daf-4bf0-9ab0-e1f11ab15ec6@app.fastmail.com>
 <CAEZATCW+N9qaE=5_1xcB0isMrirojN=Bd0yY4Pw67iji4swYiQ@mail.gmail.com>
 <4e54bf4f-59fe-4c9a-b446-a2b64cbfd584@app.fastmail.com>
 <fb6e4aa6-54e1-4be4-a7f6-3edc99aa7e6e@app.fastmail.com>
 <27d42b25-f328-4231-9db0-3811dc77c8cf@app.fastmail.com>
 <33c51978-8ee8-438c-9804-e46c0ca8f3f9@app.fastmail.com>
 <CAEZATCUA+GBYvzbqSr7LPDDfmr24jQE1R0iyYfjFk82xeuBCRw@mail.gmail.com>
 <018dd6e8-8f21-4b3b-8d80-2d128f6d00b4@app.fastmail.com>
 <CAEZATCUnn2JK4gSrymvmkhy_qsGybKv0-n0CTnLcfwfVNfTE7g@mail.gmail.com>
 <32510d71-8c00-4896-9c11-5ea4b3c01ffc@app.fastmail.com>
 <31b8386d-4bcb-4909-b7da-bbeb9a8ece55@app.fastmail.com>
 <CAEZATCXVB15_RfzROFiO_7Fh3voOuOe7FotbvON-6a+ManuGJg@mail.gmail.com>
 <42d93ebe-fbed-448f-b550-096be9e577db@app.fastmail.com>
 <CAEZATCWY_h7jTzsQnZY3bChNF85W4KLYV-rRgy=cc4QAUXEUdg@mail.gmail.com>
 <58e5e7d2-7ad8-40b4-9b76-a5c3049346e5@app.fastmail.com>
 <ce08a807-b3ca-4316-8fcf-98be5dec10a2@app.fastmail.com>
 <CAEZATCUmrq4pgJdQNQendiPkmyM=qdnZv1g-vtoMyrOyCi6xdA@mail.gmail.com>
Date: Sat, 06 Jul 2024 13:16:58 +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/f2a08b83-35f7-4a9b-a3a1-37ffdfb1e2e3%40app.fastmail.com>
Precedence: bulk

On Sat, Jul 6, 2024, at 11:34, Dean Rasheed wrote:
> On Fri, 5 Jul 2024 at 18:37, Joel Jacobson <joel@compiler.org> wrote:
>>
>> On Fri, Jul 5, 2024, at 18:42, Joel Jacobson wrote:
>> > Very nice, v7-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
>> > is now the winner on all my CPUs:
>>
>> I thought it would be interesting to also measure the isolated effect
>> on just numeric_mul() without the query overhead.
>>
>> Impressive speed-up, between 25% - 81%.
>>
>
> Cool. I think we should go with the mul_var_small() patch then, since
> it's more generally applicable.

I agree.

> I also did some testing with much larger var2 values, and saw similar
> speed-ups. One high-level function that benefits from that is
> factorial(), which accepts inputs up to 32177, and so uses both the
> 1-digit and 2-digit code with very large var2 values. I doubt anyone
> actually uses it with such large inputs, but it's interesting
> nonetheless:
>
> SELECT factorial(32177);
> Time: 923.117 ms  -- HEAD
> Time: 534.375 ms  -- mul_var_small() patch

Nice!

> I did one more round of (mostly cosmetic) copy-editing. Aside from
> improving some of the comments, it occurred to me that there's no need
> to pass rscale to mul_var_small(), or for it to call round_var(),
> since it's always computing the exact result. That shaves off a few
> more cycles.

Nice, also cleaner.

> Additionally, I didn't like how res_weight and res_ndigits were being
> set 1 higher than they needed to be. That makes sense in mul_var()
> because it may round the result, causing a non-zero carry to propagate
> into the next digit up, but it's just confusing in mul_var_small(). So
> I've reduced those by 1, which makes the look much more logical. To be
> clear, this doesn't change how many digits we're calculating. But now
> res_ndigits is actually the number of digits being calculated, whereas
> before, res_ndigits was 1 larger and we were calculating res_ndigits -
> 1 digits, which was confusing.

Nice, much cleaner.

> I think this is good to go, so unless there are any further comments,
> I plan to commit it soon.

LGTM.

Benchmark, only on Apple M3 Max:

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_1; -- HEAD
Time: 3042.157 ms (00:03.042)
Time: 3027.711 ms (00:03.028)
Time: 3078.215 ms (00:03.078)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_1; -- v8
Time: 2700.676 ms (00:02.701)
Time: 2713.594 ms (00:02.714)
Time: 2704.139 ms (00:02.704)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_2; -- HEAD
Time: 4506.064 ms (00:04.506)
Time: 3316.204 ms (00:03.316)
Time: 3321.086 ms (00:03.321)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_2; -- v8
Time: 2904.786 ms (00:02.905)
Time: 2921.996 ms (00:02.922)
Time: 2919.269 ms (00:02.919)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- HEAD
Time: 4636.051 ms (00:04.636)
Time: 3439.951 ms (00:03.440)
Time: 3471.245 ms (00:03.471)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- v8
Time: 3034.364 ms (00:03.034)
Time: 3025.351 ms (00:03.025)
Time: 3075.024 ms (00:03.075)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_4; -- HEAD
Time: 4978.086 ms (00:04.978)
Time: 3580.283 ms (00:03.580)
Time: 3582.719 ms (00:03.583)

SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_4; -- v8
Time: 3147.352 ms (00:03.147)
Time: 3135.903 ms (00:03.136)
Time: 3172.491 ms (00:03.172)

Regards,
Joel