From 76cc881ef09e0358dd72106860d5da5e4c517f2a Mon Sep 17 00:00:00 2001 From: =?utf8?q?Martin=20Mo=CC=88hrmann?= Date: Tue, 23 Dec 2014 20:44:10 +0100 Subject: [PATCH] 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 Reviewed-by: Ian Lance Taylor --- src/sort/sort.go | 24 ++++++++---------------- 1 file 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) } /* -- 2.50.0