Index func benchmark

index_test.go

package main_test

import (
	"strings"
	"testing"
)

const (
	primeRK = 16777619
)

func hashStr(sep string) (uint32, uint32) {
	hash := uint32(0)
	for i := 0; i < len(sep); i++ {
		hash = hash*primeRK + uint32(sep[i])

	}
	var pow, sq uint32 = 1, primeRK
	for i := len(sep); i > 0; i >>= 1 {
		if i&1 != 0 {
			pow *= sq

		}
		sq *= sq

	}
	return hash, pow

}

func Index(s, sep string) int {
	n := len(sep)
	switch {
	case n == 0:
		return 0
	case n == 1:
		return strings.IndexByte(s, sep[0])
	case n == len(s):
		if sep == s {
			return 0
		}
		return -1
	case n > len(s):
		return -1
	}
	// Rabin-Karp search
	hashsep, pow := hashStr(sep)
	var h uint32
	for i := 0; i < n; i++ {
		h = h*primeRK + uint32(s[i])
	}
	if h == hashsep && s[:n] == sep {
		return 0
	}
	for i := n; i < len(s); {
		h *= primeRK
		h += uint32(s[i])
		h -= pow * uint32(s[i-n])
		i++
		if h == hashsep && s[i-n:i] == sep {
			return i - n
		}
	}
	return -1
}

func IndexMesb(s, sep string) int {
	n := len(sep)
	m := len(s)
	switch {
	case n == 0:
		return 0
	case n == 1:
		return strings.IndexByte(s, sep[0])
	case n == m:
		if sep == s {
			return 0
		}
		return -1
	case n > m:
		return -1
	}
	// Rabin-Karp search
	hashsep, pow := hashStr(sep)
	var h uint32
	for i := 0; i < n; i++ {
		h = h*primeRK + uint32(s[i])
	}
	if h == hashsep && s[:n] == sep {
		return 0
	}
	for i := n; i < m; {
		h *= primeRK
		h += uint32(s[i])
		h -= pow * uint32(s[i-n])
		i++
		if h == hashsep && s[i-n:i] == sep {
			return i - n
		}
	}
	return -1
}

func BenchmarkIndexStdlib(b *testing.B) {
	for n := 0; n < b.N; n++ {
		_ = Index("testing", "test")
	}
}

func BenchmarkIndexMesb(b *testing.B) {
	for n := 0; n < b.N; n++ {
		_ = IndexMesb("testing", "test")
	}
}

// produces:

// BenchmarkIndexStdlib	300000000	        35.2 ns/op
// BenchmarkIndexMesb	300000000	        35.4 ns/op
// ok  	github.com/codemodus/indextest	28.366s

// and somtimes:

// BenchmarkIndexStdlib	500000000	        35.8 ns/op
// BenchmarkIndexMesb	500000000	        35.6 ns/op
// ok  	github.com/codemodus/indextest	42.973s