anagram benches

anagram.go

package a

import (
	"cmp"
	_ "runtime"
	"slices"
	_ "unsafe"
)

func anagramMap(a, b string) bool {
	if len(a) == 0 {
		return len(b) == 0
	}

	var m = make(map[rune]int)
	for _, r := range a {
		m[r]++
	}
	for _, r := range b {
		m[r]--
	}

	for _, v := range m {
		if v != 0 {
			return false
		}
	}
	return true
}

func anagramSlice(a, b string) bool {
	ab := []rune(a)
	bb := []rune(b)
	slices.Sort(ab)
	slices.Sort(bb)
	return slices.Equal(ab, bb)
}

type frame struct {
	low, high int
	state     uint8
	p         int
}

type coro struct{}

//go:linkname newcoro runtime.newcoro
func newcoro(func(*coro)) *coro

//go:linkname coroswitch runtime.coroswitch
func coroswitch(*coro)

type xdd[T any] struct {
	isStart bool
	arr     []T
	stack   []frame
	c       *coro
	v       T
	ok      bool
}

func (x *xdd[T]) Start(s []T) {
	x.arr = s
	x.isStart = true
}

func (x *xdd[T]) Next() (v1 T, ok1 bool) {
	coroswitch(x.c)
	return x.v, x.ok
}

func Pull[T cmp.Ordered]() *xdd[T] {
	x := &xdd[T]{}
	x.stack = make([]frame, 0, 20)
	x.c = newcoro(func(c *coro) {
		for {
		START:
			x.isStart = false
			x.stack = x.stack[:0]
			low, high := 0, len(x.arr)-1
			x.stack = append(x.stack, frame{low, high, 0, 0})
			for len(x.stack) > 0 {
				if x.isStart {
					goto START
				}

				f := x.stack[len(x.stack)-1]
				low, high := f.low, f.high
				if low > high {
					x.stack = x.stack[:len(x.stack)-1]
					continue
				}
				if low == high {
					x.v, x.ok = x.arr[low], true
					coroswitch(c)
					x.stack = x.stack[:len(x.stack)-1]
					continue
				}

				switch f.state {
				case 0:
					p := low
					{ // partition
						pivot := x.arr[high]
						for i := low; i < high; i++ {
							if x.arr[i] < pivot {
								x.arr[p], x.arr[i] = x.arr[i], x.arr[p]
								p++
							}
						}
						x.arr[p], x.arr[high] = x.arr[high], x.arr[p]
					}
					x.stack[len(x.stack)-1].state = 1
					x.stack[len(x.stack)-1].p = p
					x.stack = append(x.stack, frame{low, p - 1, 0, 0})
				case 1:
					x.v, x.ok = x.arr[f.p], true
					coroswitch(c)
					x.stack[len(x.stack)-1].state = 2
					x.stack = append(x.stack, frame{f.p + 1, high, 0, 0})
				case 2:
					x.stack = x.stack[:len(x.stack)-1]
				}
			}
			var v0 T
			x.v, x.ok = v0, false
			coroswitch(c)
		}
		panic("unreachable")
	})
	return x
}

func anagramQuick(
	a, b string,
	ai, bi *xdd[rune],
) bool {
	ai.Start([]rune(a))
	bi.Start([]rune(b))
	for {
		ac, aok := ai.Next()
		bc, bok := bi.Next()
		if !aok && !bok {
			return true
		}
		if !aok || !bok || ac != bc {
			return false
		}
	}
}

anagram_test.go

// go test  -ldflags='-checklinkname=0' -bench=. -benchmem .
package a

import "testing"

var tests = map[string]struct {
	a, b string
	want bool
}{
	"empty": {
		want: true,
	},
	"one_char": {
		a:    "a",
		b:    "a",
		want: true,
	},
	"anagram_1": {
		a:    "foo",
		b:    "ofo",
		want: true,
	},
	"anagram_2": {
		a:    "foobaranagram",
		b:    "anarobramfoag",
		want: true,
	},
	"anagram_cyr": {
		a:    "инфографика_ABC",
		b:    "ииоAгBнраCфф_ка",
		want: true,
	},
	"not_anagram_wrong_len": {
		a:    "bar",
		b:    "baar",
		want: false,
	},
	"not_anagram_correct_len": {
		a:    "bar",
		b:    "baa",
		want: false,
	},
}

func BenchmarkAnagramQuick(b *testing.B) {
	for name, test := range tests {
		ai := Pull[rune]()
		bi := Pull[rune]()
		if got := anagramQuick(test.a, test.b, ai, bi); got != test.want {
			b.Fatalf("test %s: got %v, want %v", name, got, test.want)
		}
		b.Run(name, func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				anagramQuick(test.a, test.b, ai, bi)
			}
		})
	}
}

func BenchmarkAnagramMap(b *testing.B) {
	for name, test := range tests {
		if got := anagramMap(test.a, test.b); got != test.want {
			b.Fatalf("test %s: got %v, want %v", name, got, test.want)
		}
		b.Run(name, func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				anagramMap(test.a, test.b)
			}
		})
	}
}

func BenchmarkAnagramSlice(b *testing.B) {
	for name, test := range tests {
		if got := anagramSlice(test.a, test.b); got != test.want {
			b.Fatalf("test %s: got %v, want %v", name, got, test.want)
		}
		b.Run(name, func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				anagramSlice(test.a, test.b)
			}
		})
	}
}

func TestQuickSort(t *testing.T) {
	for name, test := range map[string]struct {
		s, expected string
	}{
		"empty":   {"", ""},
		"anagram": {"anarobramfoag", "aaaabfgmnoorr"},
	} {
		t.Run(name, func(t *testing.T) {
			ai := Pull[rune]()
			bi := Pull[rune]()
			if !anagramQuick(test.s, test.expected, ai, bi) {
				t.Fatalf("got %s, want %s", test.s, test.expected)
			}
		})
	}
}

func TestPull(t *testing.T) {
	ai := Pull[rune]()
	ai.Start([]rune("abc"))
	f := func(wantC rune) {
		c, ok := ai.Next()
		if !ok {
			t.Logf("eof: want=%c", wantC)
			t.Fail()
		}
		if wantC != c {
			t.Logf("c=%d want=%c", c, wantC)
			t.Fail()
		}
	}
	f('a')
	f('b')
	f('c')
	if _, ok := ai.Next(); ok {
		t.Logf("not eof")
		t.Fail()
	}
}

func TestPull2(t *testing.T) {
	ai := Pull[rune]()
	f := func(wantC rune) {
		c, ok := ai.Next()
		if !ok {
			t.Logf("eof: want=%c", wantC)
			t.Fail()
		}
		if wantC != c {
			t.Logf("c=%d want=%c", c, wantC)
			t.Fail()
		}
	}
	ai.Start([]rune("abc"))
	f('a')
	f('b')
	ai.Start([]rune("def"))
	f('d')
	f('e')
	f('f')
	if _, ok := ai.Next(); ok {
		t.Logf("not eof")
		t.Fail()
	}
}