]> Cypherpunks repositories - gostls13.git/commit
math/big: streamline divLarge initialization
authorBrian Kessler <brian.m.kessler@gmail.com>
Tue, 19 Sep 2017 05:02:55 +0000 (22:02 -0700)
committerRobert Griesemer <gri@golang.org>
Wed, 22 Aug 2018 22:54:01 +0000 (22:54 +0000)
commita3381faf81e5e9ec0b207d74f29f6c442b2abb73
treea6d0c2ce545ad500799440abe5f965f495d01d1d
parent48462bb3c04f34c93689c047d4bc5319bc79b31b
math/big: streamline divLarge initialization

The divLarge code contained "todo"s about avoiding alias
and clear calls in the initialization of variables.  By
rearranging the order of initialization and always using
an auxiliary variable for the shifted divisor, all of these
calls can be safely avoided.  On average, normalizing
the divisor (shift>0) is required 31/32 or 63/64 of the
time.  If one always performs the shift into an auxiliary
variable first, this avoids the need to check for aliasing of
vIn in the output variables u and z.  The remainder u is
initialized via a left shift of uIn and thus needs no
alias check against uIn.  Since uIn and vIn were both used,
z needs no alias checks except against u which is used for
storage of the remainder. This change has a minimal impact
on performance (see below), but cleans up the initialization
code and eliminates the "todo"s.

name                 old time/op  new time/op  delta
Div/20/10-4          86.7ns ± 6%  85.7ns ± 5%    ~     (p=0.841 n=5+5)
Div/200/100-4         523ns ± 5%   502ns ± 3%  -4.13%  (p=0.024 n=5+5)
Div/2000/1000-4      2.55µs ± 3%  2.59µs ± 5%    ~     (p=0.548 n=5+5)
Div/20000/10000-4    80.4µs ± 4%  80.0µs ± 2%    ~     (p=1.000 n=5+5)
Div/200000/100000-4  6.43ms ± 6%  6.35ms ± 4%    ~     (p=0.548 n=5+5)

Fixes #22928

Change-Id: I30d8498ef1cf8b69b0f827165c517bc25a5c32d7
Reviewed-on: https://go-review.googlesource.com/130775
Reviewed-by: Robert Griesemer <gri@golang.org>
src/math/big/int_test.go
src/math/big/nat.go