sort: simplify rotate and reduce calls to it

Move the checks for empty rotate changes
from the beginning of rotate to the callers.

Remove additional variable p used instead of existing m with same value.

Remove special casing of equal ranges (i==j) to exit early as no
work is saved vs checking (i!=j) and  making a single
swapRange call if this is false.

benchmark                   old ns/op      new ns/op      delta
BenchmarkStableString1K     417195         425218         +1.92%
BenchmarkStableInt1K        126661         124498         -1.71%
BenchmarkStableInt64K       10365014       10417438       +0.51%
BenchmarkStable1e2          132151         130648         -1.14%
BenchmarkStable1e4          42027428       40812649       -2.89%
BenchmarkStable1e6          8524772364     8430192391     -1.11%

Change-Id: Ia7642e9d31408496970c700f5843d53cc3ebe817
Reviewed-on: https://go-review.googlesource.com/2100
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

1 files changed, 8 insertions, 16 deletions

diff --git a/src/sort/sort.go b/src/sort/sort.go
index 55134956c0..600a486a0e 100644
--- a/src/sort/sort.go
+++ b/src/sort/sort.go
@@ -381,7 +381,9 @@ func symMerge(data Interface, a, m, b int) {
 	}
 
 	end := n - start
-	rotate(data, start, m, end)
+	if start < m && m < end {
+		rotate(data, start, m, end)
+	}
 	if a < start && start < mid {
 		symMerge(data, a, start, mid)
 	}
@@ -393,32 +395,22 @@ func symMerge(data Interface, a, m, b int) {
 // Rotate two consecutives blocks u = data[a:m] and v = data[m:b] in data:
 // Data of the form 'x u v y' is changed to 'x v u y'.
 // Rotate performs at most b-a many calls to data.Swap.
+// Rotate assumes non-degenerate arguments: a < m && m < b.
 func rotate(data Interface, a, m, b int) {
 	i := m - a
-	if i == 0 {
-		return
-	}
 	j := b - m
-	if j == 0 {
-		return
-	}
-
-	if i == j {
-		swapRange(data, a, m, i)
-		return
-	}
 
-	p := a + i
 	for i != j {
 		if i > j {
-			swapRange(data, p-i, p, j)
+			swapRange(data, m-i, m, j)
 			i -= j
 		} else {
-			swapRange(data, p-i, p+j-i, i)
+			swapRange(data, m-i, m+j-i, i)
 			j -= i
 		}
 	}
-	swapRange(data, p-i, p, i)
+	// i == j
+	swapRange(data, m-i, m, i)
 }
 
 /*