sort: slices.Sort is slightly slower than sort.Strings on some sorted inputs

[qiulaidongfeng]

What version of Go are you using (go version)?

$ go version devel go1.21-39effbc105 Fri Jun 9 04:07:29 2023 +0000 windows/amd64

Does this issue reproduce with the latest release?

yes

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
set GOOS=windows
set GOARCH=amd64
set GOAMD64=v2

What did you do?

Use the following benchmark code

code

package main
import (

//"slices"

"sort"

"strconv"

"testing"

)
var s []string
func init() {

const n = 10000000

s = make([]string, n)

for i := 0; i < n; i++ {

s[i] = strconv.Itoa(i)

}

}
func BenchmarkStringSort(b *testing.B) {

for i := 0; i < b.N; i++ {

sort.Strings(s)

}

}
// func BenchmarkStringSort(b *testing.B) {

// 	for i := 0; i < b.N; i++ {

// 		slices.Sort(s)

// 	}

// }

What did you expect to see?

Expected document to be successfully validated

Note: consider using the new slices.Sort function, which runs faster

What did you see instead?

│ sort.txt │ slices.txt │ │ sec/op │ sec/op vs base │ StringSort-4 123.7m ± 2% 134.0m ± 1% +8.36% (p=0.002 n=10)

The test results do not match the document, which says slices is faster, but the test found that sort is faster.

[randall77]

The test results do not match the document, which says slices is faster, but the test found that sort is faster.

Which document are you referring to?

[ianlancetaylor]

CC @eliben

[ianlancetaylor]

That's not a great benchmark, because it just calls the sorting function over and over again on the same slice. After the first call, the slice will be fully sorted. So you aren't really testing how long it takes to sort, you are testing how long it takes to determine that the slice is already sorted.

There are some existing benchmarks in slices/sort_benchmark_test.go and sort/sort_test.go that don't have that problem.

[qiulaidongfeng]

Document in https://pkg.go.dev/sort@master#Strings
I use the following benchmarks to sort different slices in each loop：

code

package main

import (
//"slices"
"sort"
"strconv"
"testing"
)

const n = 100000

func BenchmarkStringSort(b *testing.B) {
for i := 0; i < b.N; i++ {
s := make([]string, n)
for i := 0; i < n; i++ {
s[i] = strconv.Itoa(i)
}
sort.Strings(s)
}
}

// func BenchmarkStringSort(b *testing.B) {
// for i := 0; i < b.N; i++ {
// s := make([]string, n)
// for i := 0; i < n; i++ {
// s[i] = strconv.Itoa(i)
// }
// slices.Sort(s)
// }
// }

│ sort.txt │ slices.txt │ │ sec/op │ sec/op vs base │ StringSort-4 38.63m ± 1% 36.23m ± 2% -6.23% (p=0.000 n=10)

Note: consider using the new slides. Sort function, which runs faster

This document is easily understood as calling slices.Sort on the same slice (using [] string as an example) is faster than calling sort.Strings.

I think this part of the document should be changed to: "Note: Consider using the newer slices.Sort function to run faster on Not sorted slices", It's much less likely to be misunderstood.

[mitar]

Which document are you referring to?

I think author means "documentation".

[eliben]

In my measurements, slices.Sort is 15-20% faster on a shuffled slice of strings (this is what I get by running the in-tree benchmarks @iant mentioned). For a presorted slice, I see measurement noise - either function is ~1% faster depending on the run.

Both functions end up in the same code-generated implementation, and the difference between them is the cost of dispatch (StringSlice interface for sort.Strings and generic dispatch for cmp.Ordered for slices.Sort) so I don't really see why sorting a sorted slice would be consistently faster for sort.Strings.

@zhangyunhao116

[zhangyunhao116]

For this benchmark, the sort.Strings is slightly faster.

func sortedStrings() []string {
	const N = 10000
	x := make([]string, N)
	for i := 0; i < N; i++ {
		x[i] = strconv.Itoa(i)
	}
	slices.Sort(x)
	return x
}

func BenchmarkSlices(b *testing.B) {
	x := sortedStrings()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		slices.Sort(x)
	}
}

func BenchmarkSort(b *testing.B) {
	x := sortedStrings()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		sort.Strings(x)
	}
}

We can see the diff from its flame graph. I think the reason is that the slices use cmp.Less, which consumes too much CPU on the isNaN. IMO, we can optimize this pattern in the compiler, there are many types like the string that don't require the isNaN.

[bronze1man]

"IMOP, we can optimize this pattern in the compiler, there are many types like the string that don't require the isNaN."
Can golang just add compile time type check (rust called "Zero Cost Abstractions") to only check isNan with float32 or float64? Or the compiler can transform runtime type check to compile time type check?

[randall77]

That just looks like a missing optimization. x==x should always return true for strings, and it doesn't.

func f(x string) bool {
	return x == x
}

That should compile to the equivalent of return true, but it doesn't. It ends up calling memequal (which does shortcut immediately to return true, but the call itself is still there).

[eliben]

For this benchmark, the sort.Strings is slightly faster.

func sortedStrings() []string {
	const N = 10000
	x := make([]string, N)
	for i := 0; i < N; i++ {
		x[i] = strconv.Itoa(i)
	}
	slices.Sort(x)
	return x
}

func BenchmarkSlices(b *testing.B) {
	x := sortedStrings()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		slices.Sort(x)
	}
}

func BenchmarkSort(b *testing.B) {
	x := sortedStrings()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		sort.Strings(x)
	}
}

Yes, this data is different so I see slightly different results. sort.Strings is faster by 1-2%

@randall77 makes a good point about how this can be fixed.

In the meantime, I'm not sure whether the doc comment should be modified. The new slices.Sort is certainly much faster on "real" inputs; it seems like for some subset of pre-sorted inputs it can be slightly slower. We could qualify the comment from "runs faster" to "runs faster in most cases", but I'm not sure it's worth it.

[gopherbot]

Change https://go.dev/cl/503795 mentions this issue: cmd/compile: optimize s==s for strings

[gopherbot]

Change https://go.dev/cl/503815 mentions this issue: slices: add sort benchmark for sorted strings

[eliben]

I've updated the issue title to better reflect the current understanding. @randall77 's https://go.dev/cl/503795 fixes this, but we're not sure whether this fix is worth it for inclusion in 1.21 or will have to wait for 1.22

In the meantime, my inclination is not to do anything about the documentation, given the special circumstances where it's inaccurate (only for sorted inputs, and even then, only for some sorted inputs). Happy to hear other opinions