Optimize mul_var() for var1ndigits >= 8
Joel Jacobson <joel@compiler.org>
From: "Joel Jacobson" <joel@compiler.org>
To: pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2024-07-07T19:46:20Z
Lists: pgsql-hackers
Attachments
- mul_var_large.patch (application/octet-stream) patch
- bench_mul.sql (application/octet-stream)
- bench_mul-init.sql (application/octet-stream)
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
Commits
-
Optimise numeric multiplication using base-NBASE^2 arithmetic.
- 8dc28d7eb868 18.0 landed
-
Extend mul_var_short() to 5 and 6-digit inputs.
- c4e44224cf61 18.0 landed