From: | "Joel Jacobson" <joel(at)compiler(dot)org> |
---|---|
To: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Optimize mul_var() for var1ndigits >= 8 |
Date: | 2024-07-07 19:46:20 |
Message-ID: | 9d8a4a42-c354-41f3-bbf3-199e1957db97@app.fastmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
Hello hackers,
This patch adds a mul_var_large() that is dispatched to from mul_var()
for var1ndigits >= 8, regardless of rscale.
The main idea with mul_var_large() is to reduce the "n" in O(n^2) by a factor
of two.
This is achieved by first converting the (ndigits) number of int16 NBASE digits,
to (ndigits/2) number of int32 NBASE^2 digits, as well as upgrading the
int32 variables to int64-variables so that the products and carry values fit.
The existing mul_var() algorithm is then executed without structural change.
Finally, the int32 NBASE^2 result digits are converted back to twice the number
of int16 NBASE digits.
This adds overhead of approximately 4 * O(n), due to the conversion.
Benchmarks indicates mul_var_large() starts to be beneficial when
var1 is at least 8 ndigits, or perhaps a little more.
Definitively an interesting speed-up for 100 ndigits and above.
Benchmarked on Apple M3 Max so far:
-- var1ndigits == var2ndigits == 10
SELECT COUNT(*) FROM n_10 WHERE product = var1 * var2;
Time: 3957.740 ms (00:03.958) -- HEAD
Time: 3943.795 ms (00:03.944) -- mul_var_large
-- var1ndigits == var2ndigits == 100
SELECT COUNT(*) FROM n_100 WHERE product = var1 * var2;
Time: 1532.594 ms (00:01.533) -- HEAD
Time: 1065.974 ms (00:01.066) -- mul_var_large
-- var1ndigits == var2ndigits == 1000
SELECT COUNT(*) FROM n_1000 WHERE product = var1 * var2;
Time: 3055.372 ms (00:03.055) -- HEAD
Time: 2295.888 ms (00:02.296) -- mul_var_large
-- var1ndigits and var2ndigits completely random,
-- with random number of decimal digits
SELECT COUNT(*) FROM n_mixed WHERE product = var1 * var2;
Time: 46796.240 ms (00:46.796) -- HEAD
Time: 27970.006 ms (00:27.970) -- mul_var_large
-- var1ndigits == var2ndigits == 16384
SELECT COUNT(*) FROM n_max WHERE product = var1 * var2;
Time: 3191.145 ms (00:03.191) -- HEAD
Time: 1836.404 ms (00:01.836) -- mul_var_large
Regards,
Joel
Attachment | Content-Type | Size |
---|---|---|
mul_var_large.patch | application/octet-stream | 9.6 KB |
bench_mul.sql | application/octet-stream | 862 bytes |
bench_mul-init.sql | application/octet-stream | 1.8 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Joel Jacobson | 2024-07-07 20:39:46 | Thoughts on NBASE=100000000 |
Previous Message | Tom Lane | 2024-07-07 19:20:56 | Re: XML test error on Arch Linux |