diff options
| author | David R. Jenni <david.r.jenni@gmail.com> | 2017-02-05 11:02:03 +0100 |
|---|---|---|
| committer | Robert Griesemer <gri@golang.org> | 2017-02-06 17:08:13 +0000 |
| commit | fd37b8ccf2262bb3f0a608f7545f78a72e8d661f (patch) | |
| tree | 3a72bdc5931c3c12283d3f79ed323433711f3363 /src/sort | |
| parent | 91ad2a219445d6df3ddb796d0f44190da24f429d (diff) | |
| download | go-fd37b8ccf2262bb3f0a608f7545f78a72e8d661f.tar.gz go-fd37b8ccf2262bb3f0a608f7545f78a72e8d661f.zip | |
sort: optimize average calculation in binary search
Use fewer instructions to calculate the average of i and j without
overflowing at the addition.
Even if both i and j are math.MaxInt{32,64}, the sum fits into a
uint{32,64}. Because the sum of i and j is always ≥ 0, the right
shift by one does the same as a division by two. The result of the
shift operation is at most math.MaxInt{32,64} and fits again into
an int{32,64}.
name old time/op new time/op delta
SearchWrappers-4 153ns ± 3% 143ns ± 6% -6.33% (p=0.000 n=90+100)
This calculation is documented in:
https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
Change-Id: I2be7922afc03b3617fce32e59364606c37a83678
Reviewed-on: https://go-review.googlesource.com/36332
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Diffstat (limited to 'src/sort')
| -rw-r--r-- | src/sort/search.go | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/src/sort/search.go b/src/sort/search.go index b9640a40af..24cc90248c 100644 --- a/src/sort/search.go +++ b/src/sort/search.go @@ -61,7 +61,7 @@ func Search(n int, f func(int) bool) int { // Invariant: f(i-1) == false, f(j) == true. i, j := 0, n for i < j { - h := i + (j-i)/2 // avoid overflow when computing h + h := int(uint(i+j) >> 1) // avoid overflow when computing h // i ≤ h < j if !f(h) { i = h + 1 // preserves f(i-1) == false |