# Some improvements to numeric sqrt() and ln()

10 messages
Open this post in threaded view
|

## Some improvements to numeric sqrt() and ln()

Open this post in threaded view
|

## Re: Some improvements to numeric sqrt() and ln()

 On Fri, 28 Feb 2020 at 08:15, Dean Rasheed <[hidden email]> wrote: > > It's possible that there are further gains to be had in the sqrt() > algorithm on platforms that support 128-bit integers, but I haven't > had a chance to investigate that yet. > Rebased patch attached, now using 128-bit integers for part of sqrt_var() on platforms that support them. This turned out to be well worth it (1.5 to 2 times faster than the previous version if the result has less than 30 or 40 digits). Regards, Dean numeric-sqrt-v2.patch (29K) Download Attachment
Open this post in threaded view
|

## Re: Some improvements to numeric sqrt() and ln()

 Dear Dean, On 2020-03-01 20:47, Dean Rasheed wrote: > On Fri, 28 Feb 2020 at 08:15, Dean Rasheed <[hidden email]> > wrote: >> >> It's possible that there are further gains to be had in the sqrt() >> algorithm on platforms that support 128-bit integers, but I haven't >> had a chance to investigate that yet. >> > > Rebased patch attached, now using 128-bit integers for part of > sqrt_var() on platforms that support them. This turned out to be well > worth it (1.5 to 2 times faster than the previous version if the > result has less than 30 or 40 digits). Thank you for these patches, these sound like really nice improvements. One thing can to my mind while reading the patch: + * If r < 0 Then + * Let r = r + 2*s - 1 + * Let s = s - 1 + /* s is too large by 1; let r = r + 2*s - 1 and s = s - 1 */ + r_int64 += 2 * s_int64 - 1; + s_int64--; This can be reformulated as: + * If r < 0 Then + * Let r = r + s + * Let s = s - 1 + * Let r = r + s + /* s is too large by 1; let r = r + 2*s - 1 and s = s - 1 */ + r_int64 += s_int64; + s_int64--; + r_int64 += s_int64; which would remove one mul/shift and the temp. variable. Mind you, I have not benchmarked this, so it might make little difference, but maybe it is worth trying it. Best regards, Tels numeric-sqrt-v2.patch (29K) Download Attachment
Open this post in threaded view
|

## Re: Some improvements to numeric sqrt() and ln()

 On Tue, 3 Mar 2020 at 00:17, Tels <[hidden email]> wrote: > > Thank you for these patches, these sound like really nice improvements. Thanks for looking! > One thing can to my mind while reading the patch: > > +        *              If r < 0 Then > +        *                      Let r = r + 2*s - 1 > +        *                      Let s = s - 1 > > This can be reformulated as: > > +        *              If r < 0 Then > +        *                      Let r = r + s > +        *                      Let s = s - 1 > +        *                      Let r = r + s > > which would remove one mul/shift and the temp. variable. Good point, that's a neat little optimisation. I wasn't able to detect any difference in performance, because those corrections are only triggered about 1 time in every 50 or so, but it looks neater to me, especially in the numeric iterations, where it saves a sub_var() by const_one as well as not using the temporary variable. Regards, Dean
Open this post in threaded view
|

## Re: Some improvements to numeric sqrt() and ln()

 In reply to this post by Dean Rasheed-3 Hi Dean, On 2/28/20 3:15 AM, Dean Rasheed wrote: > Attached is a WIP patch to improve the performance of numeric sqrt() > and ln(), which also makes a couple of related improvements to > div_var_fast(), all of which have knock-on benefits for other numeric > functions. The actual impact varies greatly depending on the inputs, > but the overall effect is to reduce the run time of the numeric_big > regression test by about 20%. Are these improvements targeted at PG13 or PG14?  This seems a pretty big change for the last CF of PG13. Regards, -- -David [hidden email]
Open this post in threaded view
|

## Re: Some improvements to numeric sqrt() and ln()

 On Wed, 4 Mar 2020 at 14:41, David Steele <[hidden email]> wrote: > > Are these improvements targeted at PG13 or PG14?  This seems a pretty > big change for the last CF of PG13. > Well of course that's not entirely up to me, but I was hoping to commit it for PG13. It's very well covered by a large number of regression tests in both numeric.sql and numeric_big.sql, since nearly anything that calls ln(), log() or pow() ends up going through sqrt_var(). Also, the changes are local to functions in numeric.c, which makes them easy to revert if something proves to be wrong. Regards, Dean
Open this post in threaded view
|

## Re: Some improvements to numeric sqrt() and ln()

 Dean Rasheed <[hidden email]> writes: > On Wed, 4 Mar 2020 at 14:41, David Steele <[hidden email]> wrote: >> Are these improvements targeted at PG13 or PG14?  This seems a pretty >> big change for the last CF of PG13. > Well of course that's not entirely up to me, but I was hoping to > commit it for PG13. > It's very well covered by a large number of regression tests in both > numeric.sql and numeric_big.sql, since nearly anything that calls > ln(), log() or pow() ends up going through sqrt_var(). Also, the > changes are local to functions in numeric.c, which makes them easy to > revert if something proves to be wrong. FWIW, I agree that this is a reasonable thing to consider committing for v13.  It's not adding any new user-visible behavior, so there's no definitional issues to quibble over, which is usually what I worry about regretting after an overly-hasty commit.  And it's only touching a few functions in one file, so even if the patch is a bit long, the complexity seems pretty well controlled. I've not read the patch in detail so this isn't meant as a review, but from a process standpoint I see no reason not to go forward.                         regards, tom lane
Open this post in threaded view
|