[go] reflect, sort: add reflect.Value.Swapper, sort.Slice

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,
Robert Griesemer, Austin Clements

Brad Fitzpatrick uploaded a change:
https://go-review.googlesource.com/27321

reflect, sort: add reflect.Value.Swapper, sort.Slice

DO NOT SUBMIT

Prototype.

Currently less than 10% slower, but optimizations remain:

BenchmarkSortString1K-2 10000 260030 ns/op
BenchmarkSortString1K_Reflect-2 10000 281133 ns/op

Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go
M src/reflect/value.go
M src/runtime/mbarrier.go
M src/sort/export_test.go
M src/sort/sort.go
M src/sort/sort_test.go
6 files changed, 188 insertions(+), 15 deletions(-)



diff --git a/src/reflect/all_test.go b/src/reflect/all_test.go
index bbb098f..1c93721 100644
--- a/src/reflect/all_test.go
+++ b/src/reflect/all_test.go
@@ -5750,3 +5750,48 @@
New(v)
}
}
+
+func TestValueSwapper(t *testing.T) {
+ tests := []struct {
+ in interface{}
+ i, j int
+ want interface{}
+ }{
+ {
+ in: []int{1, 20, 300},
+ i: 0,
+ j: 2,
+ want: []int{300, 20, 1},
+ },
+ {
+ in: []string{"eric", "sergey", "larry"},
+ i: 0,
+ j: 2,
+ want: []string{"larry", "sergey", "eric"},
+ },
+ }
+ for i, tt := range tests {
+ inStr := fmt.Sprint(tt.in)
+ ValueOf(tt.in).Swapper()(tt.i, tt.j)
+ if !DeepEqual(tt.in, tt.want) {
+ t.Errorf("%d. swapping %v and %v of %v = %v; want %v", i, tt.i, tt.j,
inStr, tt.in, tt.want)
+ }
+ }
+}
+
+func BenchmarkSwap(b *testing.B) {
+ const N = 1024
+ strs := make([]string, N)
+ for i := range strs {
+ strs[i] = strconv.Itoa(i)
+ }
+ swap := ValueOf(strs).Swapper()
+
+ b.ResetTimer()
+ i, j := 0, 1
+ for n := 0; n < b.N; n++ {
+ i = (i + 1) % N
+ j = (j + 2) % N
+ swap(i, j)
+ }
+}
diff --git a/src/reflect/value.go b/src/reflect/value.go
index e6b846e..088b5fc 100644
--- a/src/reflect/value.go
+++ b/src/reflect/value.go
@@ -824,6 +824,49 @@

var uint8Type = TypeOf(uint8(0)).(*rtype)

+// Swapper returns a function which swaps the slice elements in v.
+func (v Value) Swapper() func(i, j int) {
+ if v.kind() != Slice {
+ panic(&ValueError{"reflect.Value.Swap", v.kind()})
+ }
+ s := (*sliceHeader)(v.ptr)
+ maxLen := uint(s.Len)
+
+ tt := (*sliceType)(unsafe.Pointer(v.typ))
+ typ := tt.elem
+
+ tmpVal := New(typ)
+ if tmpVal.flag&flagIndir != 0 {
+ panic("unsupported scratch value")
+ }
+ tmp := tmpVal.ptr
+ size := typ.size
+
+ if typ.kind&kindNoPointers != 0 {
+ return func(i, j int) {
+ if uint(i) >= maxLen || uint(j) >= maxLen {
+ panic("reflect: slice index out of range")
+ }
+ val1 := arrayAt(s.Data, i, size)
+ val2 := arrayAt(s.Data, j, size)
+ memmove(tmp, val1, size)
+ memmove(val1, val2, size)
+ memmove(val2, tmp, size)
+ }
+ }
+
+ return func(i, j int) {
+ if uint(i) >= maxLen || uint(j) >= maxLen {
+ panic("reflect: slice index out of range")
+ }
+ val1 := arrayAt(s.Data, i, size)
+ val2 := arrayAt(s.Data, j, size)
+ typedmemmove_pointers(tmp, val1, size)
+ typedmemmove_pointers(val1, val2, size)
+ typedmemmove_pointers(val2, tmp, size)
+ }
+}
+
// Index returns v's i'th element.
// It panics if v's Kind is not Array, Slice, or String or i is out of
range.
func (v Value) Index(i int) Value {
@@ -2493,10 +2536,27 @@

func ifaceE2I(t *rtype, src interface{}, dst unsafe.Pointer)

+// memmove copies size bytes from src to dst.
+// The memory must not contain any pointers.
+//go:noescape
+func memmove(dst, src unsafe.Pointer, size uintptr)
+
// typedmemmove copies a value of type t to dst from src.
//go:noescape
func typedmemmove(t *rtype, dst, src unsafe.Pointer)

+// typedmemmove_pointers is like typedmemmove, but optimized for the
+// needs of Value.Swapper. In particular, dst and src must still contain
+// the same types, but in addition, the type MUST contain pointers
+// (that is, typ.kind&kindNoPointers == 0).
+// Further, the size is passed directly to avoid deferencing typ again,
+// which matters for performance. As a result, the cgo memory copying
+// checks are also disabled. The assumption is this is only used
+// by Value.Swapper, and only ever swapping memory within a particular
+// object, not crossing cgo boundaries.
+//go:noescape
+func typedmemmove_pointers(dst, src unsafe.Pointer, size uintptr)
+
// typedmemmovepartial is like typedmemmove but assumes that
// dst and src point off bytes into the value and only copies size bytes.
//go:noescape
diff --git a/src/runtime/mbarrier.go b/src/runtime/mbarrier.go
index 4a8f501..a00270b 100644
--- a/src/runtime/mbarrier.go
+++ b/src/runtime/mbarrier.go
@@ -188,6 +188,22 @@
typedmemmove(typ, dst, src)
}

+// typedmemmove_pointers is like typedmemmove, but optimized for the
+// needs of reflect.Value.Swapper. In particular, dst and src must
+// still contain the same types, but in addition, the type MUST
+// contain pointers (that is, typ.kind&kindNoPointers == 0). Further,
+// the size is passed directly to avoid deferencing typ again, which
+// matters for performance. Due to lack of of *_type, and for
+// performance, the cgo memory copying checks are also disabled. The
+// assumption is this is only used by Value.Swapper, and only ever
+// swapping memory within a particular object, not crossing cgo
+// boundaries.
+//go:linkname reflect_typedmemmove_pointers reflect.typedmemmove_pointers
+func reflect_typedmemmove_pointers(dst, src unsafe.Pointer, size uintptr) {
+ memmove(dst, src, size)
+ heapBitsBulkBarrier(uintptr(dst), size)
+}
+
// typedmemmovepartial is like typedmemmove but assumes that
// dst and src point off bytes into the value and only copies size bytes.
//go:linkname reflect_typedmemmovepartial reflect.typedmemmovepartial
diff --git a/src/sort/export_test.go b/src/sort/export_test.go
index b6e30ce..a978f39 100644
--- a/src/sort/export_test.go
+++ b/src/sort/export_test.go
@@ -5,5 +5,5 @@
package sort

func Heapsort(data Interface) {
- heapSort(data, 0, data.Len())
+ heapSort(lessSwap{data.Less, data.Swap}, 0, data.Len())
}
diff --git a/src/sort/sort.go b/src/sort/sort.go
index d07a0c2..1d52693 100644
--- a/src/sort/sort.go
+++ b/src/sort/sort.go
@@ -6,6 +6,8 @@
// collections.
package sort

+import "reflect"
+
// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
@@ -19,8 +21,18 @@
Swap(i, j int)
}

+// lessSwap is an internal subset of Interface, with just the Less and
+// Swap function.
+// This struct is as big (as small) as an interface value, and is used
+// instead of an interface so callers can provide direct Less
+// functions (via Slice) without interface indirection overhead.
+type lessSwap struct {
+ Less func(i, j int) bool
+ Swap func(i, j int)
+}
+
// Insertion sort
-func insertionSort(data Interface, a, b int) {
+func insertionSort(data lessSwap, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && data.Less(j, j-1); j-- {
data.Swap(j, j-1)
@@ -30,7 +42,7 @@

// siftDown implements the heap property on data[lo, hi).
// first is an offset into the array where the root of the heap lies.
-func siftDown(data Interface, lo, hi, first int) {
+func siftDown(data lessSwap, lo, hi, first int) {
root := lo
for {
child := 2*root + 1
@@ -48,7 +60,7 @@
}
}

-func heapSort(data Interface, a, b int) {
+func heapSort(data lessSwap, a, b int) {
first := a
lo := 0
hi := b - a
@@ -69,7 +81,7 @@
// ``Engineering a Sort Function,'' SP&E November 1993.

// medianOfThree moves the median of the three values data[m0], data[m1],
data[m2] into data[m1].
-func medianOfThree(data Interface, m1, m0, m2 int) {
+func medianOfThree(data lessSwap, m1, m0, m2 int) {
// sort 3 elements
if data.Less(m1, m0) {
data.Swap(m1, m0)
@@ -85,13 +97,13 @@
// now data[m0] <= data[m1] <= data[m2]
}

-func swapRange(data Interface, a, b, n int) {
+func swapRange(data lessSwap, a, b, n int) {
for i := 0; i < n; i++ {
data.Swap(a+i, b+i)
}
}

-func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
+func doPivot(data lessSwap, lo, hi int) (midlo, midhi int) {
m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
if hi-lo > 40 {
// Tukey's ``Ninther,'' median of three medians of three.
@@ -178,7 +190,7 @@
return b - 1, c
}

-func quickSort(data Interface, a, b, maxDepth int) {
+func quickSort(data lessSwap, a, b, maxDepth int) {
for b-a > 12 { // Use ShellSort for slices <= 12 elements
if maxDepth == 0 {
heapSort(data, a, b)
@@ -212,8 +224,20 @@
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
+ sort(data.Len(), lessSwap{data.Less, data.Swap})
+}
+
+// Slice sorts the provided slice using the function less.
+// The sort calls Sort. It is not stable.
+// If the provided slice argument is not a slice, Slice panics.
+func Slice(slice interface{}, less func(i, j int) bool) {
+ rv := reflect.ValueOf(slice)
+ sort(rv.Len(), lessSwap{less, rv.Swapper()})
+}
+
+func sort(dataLen int, data lessSwap) {
// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
- n := data.Len()
+ n := dataLen
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
@@ -338,24 +362,26 @@
// data.Less and O(n*log(n)*log(n)) calls to data.Swap.
func Stable(data Interface) {
n := data.Len()
+ ls := lessSwap{data.Less, data.Swap}
+
blockSize := 20 // must be > 0
a, b := 0, blockSize
for b <= n {
- insertionSort(data, a, b)
+ insertionSort(ls, a, b)
a = b
b += blockSize
}
- insertionSort(data, a, n)
+ insertionSort(ls, a, n)

for blockSize < n {
a, b = 0, 2*blockSize
for b <= n {
- symMerge(data, a, a+blockSize, b)
+ symMerge(ls, a, a+blockSize, b)
a = b
b += 2 * blockSize
}
if m := a + blockSize; m < n {
- symMerge(data, a, m, n)
+ symMerge(ls, a, m, n)
}
blockSize *= 2
}
@@ -380,7 +406,7 @@
// symMerge assumes non-degenerate arguments: a < m && m < b.
// Having the caller check this condition eliminates many leaf recursion
calls,
// which improves performance.
-func symMerge(data Interface, a, m, b int) {
+func symMerge(data lessSwap, a, m, b int) {
// Avoid unnecessary recursions of symMerge
// by direct insertion of data[a] into data[m:b]
// if data[a:m] only contains one element.
@@ -466,7 +492,7 @@
// 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) {
+func rotate(data lessSwap, a, m, b int) {
i := m - a
j := b - m

diff --git a/src/sort/sort_test.go b/src/sort/sort_test.go
index 60fac2d..e968f4b 100644
--- a/src/sort/sort_test.go
+++ b/src/sort/sort_test.go
@@ -74,6 +74,17 @@
}
}

+func TestSliceStrings(t *testing.T) {
+ data := strings
+ Slice(data[0:], func(i, j int) bool {
+ return data[i] < data[j]
+ })
+ if !StringsAreSorted(data[0:]) {
+ t.Errorf("sorted %v", strings)
+ t.Errorf(" got %v", data)
+ }
+}
+
func TestSortLarge_Random(t *testing.T) {
n := 1000000
if testing.Short() {
@@ -159,6 +170,21 @@
}
}

+func BenchmarkSortString1K_Reflect(b *testing.B) {
+ b.StopTimer()
+ for i := 0; i < b.N; i++ {
+ data := make([]string, 1<<10)
+ for i := 0; i < len(data); i++ {
+ data[i] = strconv.Itoa(i ^ 0x2cc)
+ }
+ b.StartTimer()
+ Slice(data, func(i, j int) bool {
+ return data[i] < data[j]
+ })
+ b.StopTimer()
+ }
+}
+
func BenchmarkStableString1K(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,
Robert Griesemer, Austin Clements

Brad Fitzpatrick uploaded a new patch set:

https://go-review.googlesource.com/27321

reflect, sort: add reflect.Value.Swapper, sort.Slice

DO NOT SUBMIT

Prototype.

Currently less than 10% slower, but optimizations remain:

BenchmarkSortString1K-2 10000 260030 ns/op
BenchmarkSortString1K_Reflect-2 10000 281133 ns/op

Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---

M src/go/build/deps_test.go

M src/reflect/all_test.go
M src/reflect/value.go
M src/runtime/mbarrier.go
M src/sort/export_test.go
M src/sort/sort.go
M src/sort/sort_test.go

7 files changed, 189 insertions(+), 16 deletions(-)

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

reflect, sort: add reflect.Value.Swapper, sort.Slice

Patch Set 2:

(1 comment)

https://go-review.googlesource.com/#/c/27321/2/src/sort/sort.go
File src/sort/sort.go:

Line 28: // functions (via Slice) without interface indirection overhead.
this part of the CL (like the whole CL, actually) was an experiment. It
definitely made the reflect case faster and was driven by pprof, but I
didn't compare the numbers for the interface case. Off hand I remember them
looking about the same before & after, but I haven't done proper
benchmarking of the impact of this on sort.Sort yet. If it makes it slower,
this would be removed.

And if this stayed, there should be a way to make it publicly accessible to
keep people happy about the sort package retaining no private tricks.
Something like an http.HandlerFunc for sort, for instance:

sort.Sort(sort.Funcs{len(s), lessFunc, swapFrunc})

.. which would be an interface, but get turned into a lessSwap at runtime
with a type assertion on Funcs which removed the interface indirection.

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-HasComments: Yes

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,
Robert Griesemer, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

reflect, sort: add reflect.Swapper, sort.With

DO NOT SUBMIT

Prototype.

This version is way slower than patchset 1. Instead of 7% slower it's 83%
slower.

Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go
M src/reflect/value.go
M src/runtime/mbarrier.go

M src/sort/sort.go
M src/sort/sort_test.go
5 files changed, 166 insertions(+), 0 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,
Robert Griesemer, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

reflect, sort: add reflect.Swapper, sort.With

DO NOT SUBMIT

Prototype.

This version is way slower than patchset 1. Instead of 7% slower it's

50 slower. But that's also because the traditional way was penalized
in patchset 1 by making its less/swap calls bounce through the .fm
method->func thunks.

Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go
M src/reflect/value.go
M src/runtime/mbarrier.go

M src/sort/sort.go
M src/sort/sort_test.go
5 files changed, 166 insertions(+), 0 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,
Robert Griesemer, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

reflect, sort: add reflect.Swapper, sort.With

DO NOT SUBMIT

Prototype. Still 33% slower:

BenchmarkSortString1K-2 50000 30999 ns/op
BenchmarkSortString1K_WithSwapper-2 30000 40887 ns/op
BenchmarkStableString1K-2 30000 46438 ns/op

Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go
M src/reflect/value.go
M src/runtime/mbarrier.go

M src/sort/sort.go
M src/sort/sort_test.go
5 files changed, 183 insertions(+), 8 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,
Robert Griesemer, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

reflect, sort: add reflect.Swapper, sort.With

This CL adds two features that can be used separately or together.

The first feature is sort.With, which returns a sort.Interface given a
length, swapper function, and less function.

The second feature is reflect.Swapper which returns a specialized and
GC-compatible swapper function given a slice interface{}. The main
motivation of Swapper is so people can write:

sort.Stable(sort.With(len(s), reflect.Swapper(s), func(i, j int) bool {
if s[i].Foo != s[j].Foo {
return s[i].Foo < s[j].Foo
}
return s[i].Bar < s[j].Bar
})

Because the calling conventions for interface calls differs from
function calls, sort.With cannot be implemented competitively if it's
used as an interface. This CL also recognizes the interface type
returned by sort.With and instead calls an auto-generated mirror of
the sort routines with the func calling convention.

As a result, this CL actually make sort.With-based sorting faster than
regular sorting:

name time/op
SortString1K-2 240µs ± 4%
SortString1K_With-2 229µs ± 6%
SortString1K_WithSwapper-2 224µs ± 5%

StableInt1K-2 177µs ± 0%
StableInt1K_With-2 134µs ± 0%
StableInt1K_WithSwapper-2 140µs ± 0%

In the table above, the first of the three numbers is the traditional
sort. The second is a func-based sort (sort.With) with no
reflection. The last number is sort.With+reflect.Swapper. The second
and third numbers are effectively identical and in the noise. I only
ran with 10 iterations of each, though. I can do longer runs later.

DO NOT SUBMIT - Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go

A src/reflect/swapper.go

M src/runtime/mbarrier.go
M src/sort/sort.go
M src/sort/sort_test.go

5 files changed, 350 insertions(+), 14 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,
Robert Griesemer, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

DO NOT SUBMIT - Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go

A src/reflect/swapper.go
M src/runtime/mbarrier.go
M src/sort/sort.go
M src/sort/sort_test.go

A src/sort/zfuncversion.go
6 files changed, 626 insertions(+), 14 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

reflect, sort: add reflect.Swapper, sort.With

Patch Set 7:

Ready for review. I'm pretty happy with it now.

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-HasComments: No

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,
Robert Griesemer, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

DO NOT SUBMIT - Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go

A src/reflect/swapper.go

M src/sort/sort.go
M src/sort/sort_test.go
A src/sort/zfuncversion.go

5 files changed, 608 insertions(+), 14 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Andrew Ekstedt (Gerrit)]

Andrew Ekstedt has posted comments on this change.

reflect, sort: add reflect.Swapper, sort.With

Patch Set 8:

(1 comment)

https://go-review.googlesource.com/#/c/27321/8/src/sort/zfuncversion.go
File src/sort/zfuncversion.go:

Line 1: // DO NOT EDIT; AUTO-GENERATED from sort.go using genzfunc.go
Add genzfunc.go? I don't see it in the CL.


--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>
Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-HasComments: Yes

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,

Robert Griesemer, Andrew Ekstedt, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

DO NOT SUBMIT - Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go

A src/reflect/swapper.go
M src/sort/sort.go
M src/sort/sort_test.go
A src/sort/zfuncversion.go

5 files changed, 603 insertions(+), 14 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,

Robert Griesemer, Andrew Ekstedt, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

DO NOT SUBMIT - Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go

A src/reflect/swapper.go
A src/sort/genzfunc.go

M src/sort/sort.go
M src/sort/sort_test.go
A src/sort/zfuncversion.go

6 files changed, 725 insertions(+), 14 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

reflect, sort: add reflect.Swapper, sort.With

Patch Set 8:

(1 comment)

https://go-review.googlesource.com/#/c/27321/8/src/sort/zfuncversion.go
File src/sort/zfuncversion.go:

Line 1: // DO NOT EDIT; AUTO-GENERATED from sort.go using genzfunc.go
> Add genzfunc.go? I don't see it in the CL.

Done

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-HasComments: Yes

[Brad Fitzpatrick (Gerrit)]

Reviewers: Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher Snyder,

Robert Griesemer, Andrew Ekstedt, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

reflect, sort: add reflect.Swapper, sort.MakeInterface, sort.With

This CL adds two features that can be used separately or together.

The first feature is sort.MakeInterface, which returns a

sort.Interface given a length, swapper function, and less function.

Also included is a wrapper (sort.With) for brevity, equivalent to
calling sort.Sort(sort.MakeInterface(n, swapper, less)).

The second feature is reflect.Swapper which returns a specialized and
GC-compatible swapper function given a slice interface{}. The main
motivation of Swapper is so people can write:

sort.With(len(s), reflect.Swapper(s), func(i, j int) bool {
if s[i].Foo != s[j].Foo {
return s[i].Foo < s[j].Foo
}
return s[i].Bar < s[j].Bar
})

Because the calling conventions for interface calls differs from
function calls, sort.With cannot be implemented competitively if it's
used as an interface. This CL also recognizes the interface type
returned by sort.With and instead calls an auto-generated mirror of
the sort routines with the func calling convention.

As a result, even though it was not a goal, this CL actually makes
func-based sorting using sort.MakeInterface faster than
interface-based sorting:

name time/op
SortString1K-2 240µs ± 4%
SortString1K_With-2 229µs ± 6%
SortString1K_WithSwapper-2 224µs ± 5%

StableInt1K-2 177µs ± 0%
StableInt1K_With-2 134µs ± 0%
StableInt1K_WithSwapper-2 140µs ± 0%

In the table above, the first of the three numbers is the traditional
sort. The second is a func-based sort (sort.With) with no
reflection. The last number is sort.With+reflect.Swapper. The second
and third numbers are effectively identical and in the noise. I only
ran with 10 iterations of each, though. I can do longer runs later.

DO NOT SUBMIT - Demo for #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/reflect/all_test.go

A src/reflect/swapper.go
A src/sort/genzfunc.go
M src/sort/sort.go
M src/sort/sort_test.go
A src/sort/zfuncversion.go

6 files changed, 741 insertions(+), 19 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Ian Lance Taylor (Gerrit)]

Ian Lance Taylor has posted comments on this change.

reflect, sort: add reflect.Swapper, sort.MakeInterface, sort.With

Patch Set 11:

(3 comments)

https://go-review.googlesource.com/#/c/27321/11/src/reflect/swapper.go
File src/reflect/swapper.go:

Line 9: // Swapper returns a function which swaps the elements in slice.
s/which/that/


Line 10: // Swapper panics if the provided interface is not a slice.
Probably the comment should mention sort.Sort, as otherwise this function
makes no sense.

I wonder if the comment should say anything about not modifying the slice
or about holding a reference to the original slice. What I'm thinking is
that writing
fn := reflect.Swapper(s)
s = append(s, 0)
fn(0, 1)
is going to have somewhat unpredictable results, depending on whether the
append reallocates the slice's backing array or not.


Line 57: if tmpVal.flag&flagIndir != 0 {
Instead of checking flagIndir and referring directly to the ptr field, just
call tmpVal.pointer().

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-HasComments: Yes

[Brad Fitzpatrick (Gerrit)]

Reviewers: Russ Cox, Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher

Snyder, Robert Griesemer, Andrew Ekstedt, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

sort: add Slice, SliceStable, and SliceIsSorted

Add helpers for sorting slices.

Slice sorts slices:

sort.Slice(s, func(i, j int) bool {

if s[i].Foo != s[j].Foo {
return s[i].Foo < s[j].Foo
}
return s[i].Bar < s[j].Bar
})

SliceStable is the same, but does a stable sort.

SliceIsSorted reports whether a slice is already sorted.

Fixes #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/go/build/deps_test.go

A src/sort/genzfunc.go
M src/sort/sort.go
M src/sort/sort_test.go
A src/sort/zfuncversion.go

5 files changed, 512 insertions(+), 19 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-Reviewer: Russ Cox <r...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

sort: add Slice, SliceStable, and SliceIsSorted

Patch Set 12: Run-TryBot+1

(2 comments)

Russ, PTAL.

Notably: are you cool with sort now depending on reflect? Presumably you
are if if you approved this route. But it means sort goes from zero
dependencies to many. In practice I don't imagine it matters, since nobody
sorts in isolation.

https://go-review.googlesource.com/#/c/27321/12/src/sort/sort.go
File src/sort/sort.go:

Line 241: // Slice sorts the provided slice given the provided less
function.
I don't like this wording much.


Line 264: // SliceIsSorted tests whether a slice is sorted.
say more here?

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-HasComments: Yes

[Gobot Gobot (Gerrit)]

Gobot Gobot has posted comments on this change.

sort: add Slice, SliceStable, and SliceIsSorted

Patch Set 12:

TryBots beginning. Status page: http://farmer.golang.org/try?commit=616cddd8

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-HasComments: No

[Gobot Gobot (Gerrit)]

Gobot Gobot has posted comments on this change.

sort: add Slice, SliceStable, and SliceIsSorted

Patch Set 12:

Build is still in progress...
This change failed on linux-amd64-race:
See
https://storage.googleapis.com/go-build-log/616cddd8/linux-amd64-race_c56d5138.log

Consult https://build.golang.org/ to see whether it's a new failure. Other
builds still in progress; subsequent failure notices suppressed until final
report.

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Reviewers: Russ Cox, Rick Hudson, Ian Lance Taylor, Rob Pike, Josh Bleecher
Snyder, Robert Griesemer, Andrew Ekstedt, Austin Clements

Brad Fitzpatrick uploaded a new patch set:
https://go-review.googlesource.com/27321

sort: add Slice, SliceStable, and SliceIsSorted

Add helpers for sorting slices.

Slice sorts slices:

sort.Slice(s, func(i, j int) bool {
if s[i].Foo != s[j].Foo {
return s[i].Foo < s[j].Foo
}
return s[i].Bar < s[j].Bar
})

SliceStable is the same, but does a stable sort.

SliceIsSorted reports whether a slice is already sorted.

Fixes #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
---
M src/cmd/dist/deps.go

M src/go/build/deps_test.go
A src/sort/genzfunc.go
M src/sort/sort.go
M src/sort/sort_test.go
A src/sort/zfuncversion.go

6 files changed, 518 insertions(+), 25 deletions(-)

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-Reviewer: Russ Cox <r...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

sort: add Slice, SliceStable, and SliceIsSorted

Patch Set 13: Run-TryBot+1

PTAL

mkdeps.bash re-ran.

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

[Gobot Gobot (Gerrit)]

Gobot Gobot has posted comments on this change.

sort: add Slice, SliceStable, and SliceIsSorted

Patch Set 13:

TryBots beginning. Status page: http://farmer.golang.org/try?commit=df70e703

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

[Gobot Gobot (Gerrit)]

Gobot Gobot has posted comments on this change.

sort: add Slice, SliceStable, and SliceIsSorted

Patch Set 13: TryBot-Result+1

TryBots are happy.

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Gobot Gobot <go...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

sort: add Slice, SliceStable, and SliceIsSorted

Patch Set 13: Code-Review+2

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Gobot Gobot <go...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has submitted this change and it was merged.

sort: add Slice, SliceStable, and SliceIsSorted

Add helpers for sorting slices.

Slice sorts slices:

sort.Slice(s, func(i, j int) bool {
if s[i].Foo != s[j].Foo {
return s[i].Foo < s[j].Foo
}
return s[i].Bar < s[j].Bar
})

SliceStable is the same, but does a stable sort.

SliceIsSorted reports whether a slice is already sorted.

Fixes #16721

Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7

Reviewed-on: https://go-review.googlesource.com/27321
Run-TryBot: Brad Fitzpatrick <brad...@golang.org>
TryBot-Result: Gobot Gobot <go...@golang.org>
Reviewed-by: Russ Cox <r...@golang.org>

---
M src/cmd/dist/deps.go
M src/go/build/deps_test.go
A src/sort/genzfunc.go
M src/sort/sort.go
M src/sort/sort_test.go
A src/sort/zfuncversion.go
6 files changed, 518 insertions(+), 25 deletions(-)

Approvals:
Russ Cox: Looks good to me, approved
Brad Fitzpatrick: Run TryBots
Gobot Gobot: TryBots succeeded

--
https://go-review.googlesource.com/27321
Gerrit-Reviewer: Andrew Ekstedt <andrew....@gmail.com>

Gerrit-Reviewer: Austin Clements <aus...@google.com>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Gobot Gobot <go...@golang.org>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Josh Bleecher Snyder <josh...@gmail.com>
Gerrit-Reviewer: Rick Hudson <r...@golang.org>
Gerrit-Reviewer: Rob Pike <r...@golang.org>
Gerrit-Reviewer: Robert Griesemer <g...@golang.org>

Gerrit-Reviewer: Russ Cox <r...@golang.org>