From: Dean Rasheed <dean.a.rasheed@gmail.com>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Speed up numeric division by always using the "fast" algorithm.
Date: Fri, 04 Oct 2024 08:52:16 +0000
Message-ID: <E1swe2p-0026iO-GQ@gemulon.postgresql.org> (raw)
Speed up numeric division by always using the "fast" algorithm.
Formerly there were two internal functions in numeric.c to perform
numeric division, div_var() and div_var_fast(). div_var() performed
division exactly to a specified rscale using Knuth's long division
algorithm, while div_var_fast() used the algorithm from the "FM"
library, which approximates each quotient digit using floating-point
arithmetic, and computes a truncated quotient with DIV_GUARD_DIGITS
extra digits. div_var_fast() could be many times faster than
div_var(), but did not guarantee correct results in all cases, and was
therefore only suitable for use in transcendental functions, where
small errors are acceptable.
This commit merges div_var() and div_var_fast() together into a single
function with an extra "exact" boolean parameter, which can be set to
false if the caller is OK with an approximate result. The new function
uses the faster algorithm from the "FM" library, except that when
"exact" is true, it does not truncate the computation with
DIV_GUARD_DIGITS extra digits, but instead performs the full-precision
computation, subtracting off complete multiples of the divisor for
each quotient digit. However, it is able to retain most of the
performance benefits of div_var_fast(), by delaying the propagation of
carries, allowing the inner loop to be auto-vectorized.
Since this may still lead to an inaccurate result, when "exact" is
true, it then inspects the remainder and uses that to adjust the
quotient, if necessary, to make it correct. In practice, the quotient
rarely needs to be adjusted, and never by more than one in the final
digit, though it's difficult to prove that, so the code allows for
larger adjustments, just in case.
In addition, use base-NBASE^2 arithmetic and a 64-bit dividend array,
similar to mul_var(), so that the number of iterations of the outer
loop is roughly halved. Together with the faster algorithm, this makes
div_var() up to around 20 times as fast as the old Knuth algorithm
when "exact" is true, and up to 2 or 3 times as fast as the old
div_var_fast() function when "exact" is false.
Dean Rasheed, reviewed by Joel Jacobson.
Discussion: https://postgr.es/m/CAEZATCVHR10BPDJSANh0u2+Sg6atO3mD0G+CjKDNRMD-C8hKzQ@mail.gmail.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/9428c001f67540e6206b7a76adfc5377d9207777
Modified Files
--------------
src/backend/utils/adt/numeric.c | 824 +++++++++++++++-------------------
src/test/regress/expected/numeric.out | 18 +
src/test/regress/sql/numeric.sql | 3 +
3 files changed, 371 insertions(+), 474 deletions(-)
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: pgsql-committers@postgresql.org
Cc: dean.a.rasheed@gmail.com, pgsql-committers@lists.postgresql.org
Subject: Re: pgsql: Speed up numeric division by always using the "fast" algorithm.
In-Reply-To: <E1swe2p-0026iO-GQ@gemulon.postgresql.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox