cmd/compile: slices.BinarySearchFunc is not inlined, making it slower than sort.Search #81887

package binsearch

import (
	"fmt"
	"slices"
	"sort"
	"strings"
	"testing"
)

type entry struct {
	id  string
	val *int
}

var list = func() []entry {
	var list []entry
	for _, id := range []string{
		"A", "B", "C", "D", "Grow", "Len", "Read", "Reset",
		"String", "Write", "WriteString", "p.a", "p.b", "p.c", "p.d", "q.grow",
	} {
		list = append(list, entry{id, new(int)})
	}
	if !slices.IsSortedFunc(list, func(x, y entry) int { return strings.Compare(x.id, y.id) }) {
		panic("unsorted")
	}
	return list
}()

//go:noinline
func lookupSort(list []entry, key string) *int {
	i := sort.Search(len(list), func(i int) bool {
		return strings.Compare(list[i].id, key) >= 0
	})
	if i < len(list) && list[i].id == key {
		return list[i].val
	}
	return nil
}

//go:noinline
func lookupSlices(list []entry, key string) *int {
	i, found := slices.BinarySearchFunc(list, key, func(e entry, key string) int {
		return strings.Compare(e.id, key)
	})
	if found {
		return list[i].val
	}
	return nil
}

var keys = []string{"C", "WriteString", "p.c", "q.grow", "missing"}

func TestAgree(t *testing.T) {
	for _, e := range list {
		if lookupSort(list, e.id) != e.val || lookupSlices(list, e.id) != e.val {
			t.Errorf("lookup(%q) failed", e.id)
		}
	}
	if lookupSort(list, "missing") != nil || lookupSlices(list, "missing") != nil {
		t.Errorf("lookup(missing) succeeded")
	}
}

var sink *int

func BenchmarkSortSearch(b *testing.B) {
	for _, key := range keys {
		b.Run(fmt.Sprint(key), func(b *testing.B) {
			for b.Loop() {
				sink = lookupSort(list, key)
			}
		})
	}
}

func BenchmarkSlicesBinarySearchFunc(b *testing.B) {
	for _, key := range keys {
		b.Run(fmt.Sprint(key), func(b *testing.B) {
			for b.Loop() {
				sink = lookupSlices(list, key)
			}
		})
	}
}