diff options
author | David R. Jenni <david.r.jenni@gmail.com> | 2017-02-08 11:32:58 +0100 |
---|---|---|
committer | Russ Cox <rsc@golang.org> | 2017-02-10 16:53:24 +0000 |
commit | 78e6abd244eb4f75180fdb3bc72d69a2f471feca (patch) | |
tree | 7bcb7c647653cb7642233e0eea8ef38ae333c11b /src/sort | |
parent | 6ac8ccf4b3b7ffe946b99e5031b88edc611e32ec (diff) | |
download | go-78e6abd244eb4f75180fdb3bc72d69a2f471feca.tar.gz go-78e6abd244eb4f75180fdb3bc72d69a2f471feca.zip |
sort: optimize average calculation in symMerge and doPivot.
Change code of the form `i + (j-i)/2` to `int(uint(i+j) >> 1)`.
The optimized average calculation uses fewer instructions to calculate
the average without overflowing at the addition.
Analogous to https://golang.org/cl/36332.
name old time/op new time/op delta
StableString1K-4 49.6µs ± 3% 49.1µs ± 8% ~ (p=0.659 n=16+19)
StableInt1K-4 160µs ±10% 148µs ± 5% -7.29% (p=0.000 n=20+16)
StableInt1K_Slice-4 139µs ± 4% 136µs ± 3% -2.52% (p=0.000 n=20+16)
StableInt64K-4 8.84ms ± 6% 8.57ms ± 5% -3.07% (p=0.001 n=20+19)
Stable1e2-4 162µs ±19% 147µs ±16% -8.79% (p=0.002 n=20+20)
Stable1e4-4 31.0ms ± 5% 30.6ms ± 5% ~ (p=0.221 n=20+20)
Stable1e6-4 6.37s ± 3% 6.27s ± 2% -1.67% (p=0.000 n=19+20)
Change-Id: I1cea0bcb9ace8ef7e48b8fab772e41b4b2170da9
Reviewed-on: https://go-review.googlesource.com/36570
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
Diffstat (limited to 'src/sort')
-rw-r--r-- | src/sort/genzfunc.go | 4 | ||||
-rw-r--r-- | src/sort/sort.go | 10 | ||||
-rw-r--r-- | src/sort/zfuncversion.go | 10 |
3 files changed, 14 insertions, 10 deletions
diff --git a/src/sort/genzfunc.go b/src/sort/genzfunc.go index 6d2b471b62..3bb7691f6a 100644 --- a/src/sort/genzfunc.go +++ b/src/sort/genzfunc.go @@ -115,6 +115,10 @@ func rewriteCall(ce *ast.CallExpr) { // e.g. skip SelectorExpr (data.Less(..) calls) return } + // skip casts + if ident.Name == "int" || ident.Name == "uint" { + return + } if len(ce.Args) < 1 { return } diff --git a/src/sort/sort.go b/src/sort/sort.go index 72d24efcea..54f92a4217 100644 --- a/src/sort/sort.go +++ b/src/sort/sort.go @@ -96,7 +96,7 @@ func swapRange(data Interface, a, b, n int) { } func doPivot(data Interface, lo, hi int) (midlo, midhi int) { - m := lo + (hi-lo)/2 // Written like this to avoid integer overflow. + m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow. if hi-lo > 40 { // Tukey's ``Ninther,'' median of three medians of three. s := (hi - lo) / 8 @@ -447,7 +447,7 @@ func symMerge(data Interface, a, m, b int) { i := m j := b for i < j { - h := i + (j-i)/2 + h := int(uint(i+j) >> 1) if data.Less(h, a) { i = h + 1 } else { @@ -471,7 +471,7 @@ func symMerge(data Interface, a, m, b int) { i := a j := m for i < j { - h := i + (j-i)/2 + h := int(uint(i+j) >> 1) if !data.Less(m, h) { i = h + 1 } else { @@ -485,7 +485,7 @@ func symMerge(data Interface, a, m, b int) { return } - mid := a + (b-a)/2 + mid := int(uint(a+b) >> 1) n := mid + m var start, r int if m > mid { @@ -498,7 +498,7 @@ func symMerge(data Interface, a, m, b int) { p := n - 1 for start < r { - c := start + (r-start)/2 + c := int(uint(start+r) >> 1) if !data.Less(p-c, c) { start = c + 1 } else { diff --git a/src/sort/zfuncversion.go b/src/sort/zfuncversion.go index 7abb18a24d..99c95a22c1 100644 --- a/src/sort/zfuncversion.go +++ b/src/sort/zfuncversion.go @@ -70,7 +70,7 @@ func swapRange_func(data lessSwap, a, b, n int) { // Auto-generated variant of sort.go:doPivot func doPivot_func(data lessSwap, lo, hi int) (midlo, midhi int) { - m := lo + (hi-lo)/2 + m := int(uint(lo+hi) >> 1) if hi-lo > 40 { s := (hi - lo) / 8 medianOfThree_func(data, lo, lo+s, lo+2*s) @@ -189,7 +189,7 @@ func symMerge_func(data lessSwap, a, m, b int) { i := m j := b for i < j { - h := i + (j-i)/2 + h := int(uint(i+j) >> 1) if data.Less(h, a) { i = h + 1 } else { @@ -205,7 +205,7 @@ func symMerge_func(data lessSwap, a, m, b int) { i := a j := m for i < j { - h := i + (j-i)/2 + h := int(uint(i+j) >> 1) if !data.Less(m, h) { i = h + 1 } else { @@ -217,7 +217,7 @@ func symMerge_func(data lessSwap, a, m, b int) { } return } - mid := a + (b-a)/2 + mid := int(uint(a+b) >> 1) n := mid + m var start, r int if m > mid { @@ -229,7 +229,7 @@ func symMerge_func(data lessSwap, a, m, b int) { } p := n - 1 for start < r { - c := start + (r-start)/2 + c := int(uint(start+r) >> 1) if !data.Less(p-c, c) { start = c + 1 } else { |