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: Wed, 03 Jul 2024 22:27:33 +0200
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAEZATCUnn2JK4gSrymvmkhy_qsGybKv0-n0CTnLcfwfVNfTE7g@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>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<CAEZATCUA+GBYvzbqSr7LPDDfmr24jQE1R0iyYfjFk82xeuBCRw@mail.gmail.com>
<[email protected]>
<CAEZATCUnn2JK4gSrymvmkhy_qsGybKv0-n0CTnLcfwfVNfTE7g@mail.gmail.com>
On Wed, Jul 3, 2024, at 20:57, Dean Rasheed wrote:
> Ah yes, I think I was looking at a newer version of the code where I'd
> already fixed that bug. Unless you think there are still bugs in any
> of the boundary checks, which is entirely possible.
Ah, that explains it.
And no, I can't find any other bugs in the boundary checks.
> Ah, I can see what's going on. It's perhaps best illustrated with a
> simple example. Suppose you are multiplying a 4-digit integer x by a
> 2-digit integer y (both with dscale=0). Then the terms of the full
> product computed by mul_var() or mul_var_small() would look something
> like this:
>
> x0 x1 x2 x3
> * y0 y1
> ---------------------------------
> x0*y0 x1*y0 x2*y0 x3*y0
> x0*y1 x1*y1 x2*y1 x3*y1
>
> In the reduced-rscale case, it might perform a truncated computation,
> computing just the first 3 columns (say), and discarding the last two
> columns. Therefore it would skip the 3 rightmost digit products.
>
> However, in mul_var_int(), y0 and y1 have been combined into a single
> integer equal to y0*NBASE+y1, and the terms of full product are
> computed as follows:
>
> x0*(y0*NBASE+y1) x1*(y0*NBASE+y1) x2*(y0*NBASE+y1) x3*(y0*NBASE+y1)
>
> In the full product, that gives the same result, but if you follow the
> same rule in the reduced-rscale case, skipping the last two terms, it
> would actually discard 4 digit products, making it less accurate.
>
> That could be avoided by increasing maxdigits by 1 in mul_var_int() so
> it would always be at least as accurate as it was before, but that
> might not really be necessary. However, if we implemented
> mul_var_int64() in the same way, it would be discarding much
> higher-order digit products, and so we probably would have to increase
> maxdigits to get sufficiently accurate results. But there's an even
> bigger problem: the results would be different between platforms that
> did and didn't have 128-bit integers, which I really don't like. We
> could avoid that by not using it in reduced-rscale cases, but that
> would involve another test condition.
>
> By contrast, mul_var_small() is intended to replicate the arithmetic
> in mul_var() exactly (but in a different order) for all rscales. So if
> you've found any cases where they give different results, that's a
> bug.
>
> In light of that, it might be that mul_var_small() is the better
> option, rather than mul_var_int(), but it'd be interesting to see how
> they compare in terms of performance first.
Thanks for explaining, very helpful.
I agree on your reasoning about the pros and cons.
Not sure yet which version I prefer. Let's see how it evolves.
I've done some benchmarks.
Haven't tested Intel and AMD yet, but this is what I get on my Apple M3 Max:
--
-- varndigits=1
--
-- HEAD
SELECT SUM(numeric_mul_head(var1,var2,0)) FROM bench_mul_var_var1ndigits_1;
Time: 2976.896 ms (00:02.977)
Time: 2984.759 ms (00:02.985)
Time: 2970.364 ms (00:02.970)
-- mul_var_int() patch
SELECT SUM(numeric_mul_patch_int(var1,var2,0)) FROM bench_mul_var_var1ndigits_1;
Time: 2790.227 ms (00:02.790)
Time: 2786.338 ms (00:02.786)
Time: 2784.957 ms (00:02.785)
-- mul_var_small() patch
SELECT SUM(numeric_mul_patch_small(var1,var2,0)) FROM bench_mul_var_var1ndigits_1;
Time: 2770.211 ms (00:02.770)
Time: 2760.685 ms (00:02.761)
Time: 2773.221 ms (00:02.773)
--
-- varndigits=2
--
-- HEAD
SELECT SUM(numeric_mul_head(var1,var2,0)) FROM bench_mul_var_var1ndigits_2;
Time: 3353.258 ms (00:03.353)
Time: 3273.055 ms (00:03.273)
Time: 3266.392 ms (00:03.266)
-- mul_var_int() patch
SELECT SUM(numeric_mul_patch_int(var1,var2,0)) FROM bench_mul_var_var1ndigits_2;
Time: 2694.169 ms (00:02.694)
Time: 2687.935 ms (00:02.688)
Time: 2692.398 ms (00:02.692)
-- mul_var_small() patch
SELECT SUM(numeric_mul_patch_small(var1,var2,0)) FROM bench_mul_var_var1ndigits_2;
Time: 2997.685 ms (00:02.998)
Time: 2984.418 ms (00:02.984)
Time: 2986.976 ms (00:02.987)
--
-- varndigits=3
--
-- HEAD
SELECT SUM(numeric_mul_head(var1,var2,0)) FROM bench_mul_var_var1ndigits_3;
Time: 3471.391 ms (00:03.471)
Time: 3384.114 ms (00:03.384)
Time: 3387.031 ms (00:03.387)
-- mul_var_int() patch
SELECT SUM(numeric_mul_patch_int(var1,var2,0)) FROM bench_mul_var_var1ndigits_3;
Time: 3384.428 ms (00:03.384)
Time: 3398.044 ms (00:03.398)
Time: 3393.727 ms (00:03.394)
-- mul_var_small() patch
SELECT SUM(numeric_mul_patch_small(var1,var2,0)) FROM bench_mul_var_var1ndigits_3;
Time: 3100.567 ms (00:03.101)
Time: 3114.225 ms (00:03.114)
Time: 3116.137 ms (00:03.116)
Interesting, mul_var_small() seems to be the winner for var1ndigits=3
and mul_var_int() to be the winner for var1ndigits=2,
and about the same for var1ndigits=1.
>> What can be said about mul_var()'s contract with regards to rscale?
>> It's the number of decimal digits requested by the caller, and if not
>> requesting full precision, then the decimal digits might not be accurate,
>> but can something be said about how far off they can be?
>>
>
> I wouldn't expect it to ever be off by more than 1, given that
> MUL_GUARD_DIGITS = 2, which corresponds to 8 decimal digits, and the
> number of digits in the smaller input (and hence the number of digit
> products in each column) is limited to something like 16,000 NBASE
> digits.
OK, so then the cases I found where it was off by 2 for the mul_var_int() patch
are unexpected?
Regards,
Joel
view thread (23+ 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