Optimize mul_var() for var1ndigits >= 8

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

Responses

Browse pgsql-hackers by date

  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