lambda arent inlined therefore sort is slower than expected

[bennyscetbun]

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

go version go1.8.3 darwin/amd64

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

GOARCH="amd64"
GOBIN=""
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOOS="darwin"
GORACE=""
GOROOT="/usr/local/Cellar/go/1.8.3/libexec"
GOTOOLDIR="/usr/local/Cellar/go/1.8.3/libexec/pkg/tool/darwin_amd64"
GCCGO="gccgo"
CC="clang"
GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/7d/XXXXX/T/go-buildXXXXX=/tmp/go-build -gno-record-gcc-switches -fno-common"
CXX="clang++"
CGO_ENABLED="1"
PKG_CONFIG="pkg-config"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"

What did you do?

bla.go

package pouet

import (
	"math/rand"
	"sort"
)

const (
	uuidSpace = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
)

func generateUUIDs(prefix string) []string {
	ret := make([]string, 5000)
	r := rand.New(rand.NewSource(42))
	for i := 0; i < len(ret); i++ {
		data := make([]byte, 32+len(prefix))
		for j := 0; j < len(prefix); j++ {
			data[j] = prefix[j]
		}
		r.Read(data[len(prefix):])
		for i, b := range data[len(prefix):] {
			data[i+2] = byte(uuidSpace[int(b)%len(uuidSpace)])
		}
		ret[i] = string(data)
	}
	return ret
}

func bla(s []string, i int, needle string) bool {
	return s[i] >= needle
}

func LambdaShouldBeInlined() {
	s := generateUUIDs("lol")
	sort.Strings(s)
	f := func(p []string, i int, needle string) bool {
		return p[i] >= needle
	}
	for n := 0; n < 2000; n++ {

		i, j := 0, len(s)
		for i < j {
			h := i + (j-i)/2 // avoid overflow when computing h
			// i ≤ h < j
			if !f(s, h, "dsjldsjklsd") {
				i = h + 1 // preserves f(i-1) == false
			} else {
				j = h // preserves f(j) == true
			}
		}
	}
}
func FuncIsInlined() {
	s := generateUUIDs("lol")
	sort.Strings(s)
	for n := 0; n < 2000; n++ {

		i, j := 0, len(s)
		for i < j {
			h := i + (j-i)/2 // avoid overflow when computing h
			// i ≤ h < j
			if !bla(s, h, "dsjldsjklsd") {
				i = h + 1 // preserves f(i-1) == false
			} else {
				j = h // preserves f(j) == true
			}
		}
	}
}

bla_test.go

package pouet

import (
	"sort"
	"testing"
)

//
func BenchmarkWithSort(b *testing.B) {
	b.StopTimer()
	s := generateUUIDs("lol")
	sort.Strings(s)
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		sort.SearchStrings(s, "dsjldsjklsd")
	}
}

func BenchmarkWithLambda(b *testing.B) {
	b.StopTimer()
	s := generateUUIDs("lol")
	sort.Strings(s)
	f := func(p []string, i int) bool {
		return p[i] >= "dsjldsjklsd"
	}
	b.StartTimer()
	for n := 0; n < b.N; n++ {

		i, j := 0, len(s)
		for i < j {
			h := i + (j-i)/2 // avoid overflow when computing h
			// i ≤ h < j
			if !f(s, h) {
				i = h + 1 // preserves f(i-1) == false
			} else {
				j = h // preserves f(j) == true
			}
		}
	}
}

func BenchmarkWithfunc(b *testing.B) {
	b.StopTimer()
	s := generateUUIDs("lol")
	sort.Strings(s)
	needle := "dsjldsjklsd"
	b.StartTimer()
	for n := 0; n < b.N; n++ {

		i, j := 0, len(s)
		for i < j {
			h := i + (j-i)/2 // avoid overflow when computing h
			// i ≤ h < j
			if !bla(s, h, needle) {
				i = h + 1 // preserves f(i-1) == false
			} else {
				j = h // preserves f(j) == true
			}
		}
	}
}

func BenchmarkWithNothing(b *testing.B) {
	b.StopTimer()
	s := generateUUIDs("lol")
	sort.Strings(s)
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		needle := "dsjldsjklsd"
		i, j := 0, len(s)
		for i < j {
			h := i + (j-i)/2 // avoid overflow when computing h
			// i ≤ h < j
			if !(s[h] > needle) {
				i = h + 1 // preserves f(i-1) == false
			} else {
				j = h // preserves f(j) == true
			}
		}
	}
}

func Test(t *testing.T) {
	s := generateUUIDs("lol")
	sort.Strings(s)
	needle := "lolasjldsjklsd"
	i, j := 0, len(s)
	for i < j {
		h := i + (j-i)/2 // avoid overflow when computing h
		// i ≤ h < j
		if !(s[h] > needle) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	if ret := sort.SearchStrings(s, needle); ret != i {
		t.Fatalf("Not the same result found %d %d", ret, i)
	}
}

benny@: $ ls
bla.go          bla_test.go
benny@: $ go tool compile -m bla.go
bla.go:14: inlining call to rand.New
bla.go:29: can inline bla
bla.go:36: can inline LambdaShouldBeInlined.func1
bla.go:62: inlining call to bla
bla.go:13: make([]string, 5000) escapes to heap
bla.go:16: make([]byte, 32 + len(prefix)) escapes to heap
bla.go:14: &rand.Rand literal escapes to heap
bla.go:24: string(data) escapes to heap
bla.go:12: generateUUIDs prefix does not escape
bla.go:29: bla s does not escape
bla.go:29: bla needle does not escape
bla.go:36: LambdaShouldBeInlined func literal does not escape
bla.go:36: LambdaShouldBeInlined.func1 p does not escape
bla.go:36: LambdaShouldBeInlined.func1 needle does not escape
benny@: $ go test -bench=. -test.benchmem=true
BenchmarkWithSort-8             10000000               133 ns/op               0 B/op          0 allocs/op
BenchmarkWithLambda-8           10000000               126 ns/op               0 B/op          0 allocs/op
BenchmarkWithfunc-8             20000000                82.8 ns/op             0 B/op          0 allocs/op
BenchmarkWithNothing-8          20000000                82.1 ns/op             0 B/op          0 allocs/op

What did you expect to see?

Because bla.go:36: can inline LambdaShouldBeInlined.func1 I was expecting to see
bla.go:45: inlining call to LambdaShouldBeInlined.func1
Therefore I was expecting BenchmarkWithSort and BenchmarkWithLambda to be as fast as BenchmarkWithfunc
At least we could do a quick fix in sort package by using private sort function and not lambdas

[bennyscetbun]

For info same result with go1.9rc2

benny@: $ go1.9rc2 tool compile -m bla.go
bla.go:14:15: inlining call to rand.New
bla.go:29:6: can inline bla
bla.go:36:7: can inline LambdaShouldBeInlined.func1
bla.go:62:11: inlining call to bla
bla.go:13:13: make([]string, 5000) escapes to heap
bla.go:16:15: make([]byte, 32 + len(prefix)) escapes to heap
bla.go:14:15: &rand.Rand literal escapes to heap
bla.go:24:18: string(data) escapes to heap
bla.go:12:37: generateUUIDs prefix does not escape
bla.go:29:44: bla s does not escape
bla.go:29:44: bla needle does not escape
bla.go:36:7: LambdaShouldBeInlined func literal does not escape
bla.go:36:46: LambdaShouldBeInlined.func1 p does not escape
bla.go:36:46: LambdaShouldBeInlined.func1 needle does not escape

benny@: $ go1.9rc2 test -bench=. -test.benchmem=true
goos: darwin
goarch: amd64
pkg: github.com/bennyscetbun/pouet
BenchmarkWithSort-8             10000000               124 ns/op               0 B/op          0 allocs/op
BenchmarkWithLambda-8           10000000               133 ns/op               0 B/op          0 allocs/op
BenchmarkWithfunc-8             20000000                88.2 ns/op             0 B/op          0 allocs/op
BenchmarkWithNothing-8          20000000                89.0 ns/op             0 B/op          0 allocs/op

[rasky]

Seems a duplicate of #15561

[bennyscetbun]

Agree Rasky... my bad.
should i reopen for the sort performance 'issue' ?

[rasky]

Yes please, open a different bug with the minimum amount of information required, I'm failing to understand what you mean by "sort performance issue" which is not related to inlining of closures. Thanks