Performance

[MikeYast]

Hi, I've run simple benchmark for cloudflare and your implementations:

var (
	patterns = []string{"field1", "field2", "field3", "field4", "field5", "field6", "field7", "field8", "field9", "fieldN"}
	logLine  = `
XXXXXfield1adfasdffield2ASDFQWEFQWEFfield3ASDFASDFfield4ASDFASDFASDFfield5ASDFASDFASDFASDFASDFASDFfield6nuqfweiuh2893hfiuqgwefqweuifhg2q394fhiqushffield9mxpqwoeifmxpqowiefmxfield7qlwbzei	uqwbefzp9qxwehmfpiuwehfpiuqshfield8z	podhuw	poquwhd	ipquewfiuw	beffieldN
`
)

func BenchmarkCloudflareStringsLogFindAll(b *testing.B) {
	m := ahocorasick.NewStringMatcher(patterns)
	bLine := []byte(logLine)

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		matches := m.Match(bLine)
		require.Equal(b, NumOfPatterns, len(matches))
	}
}

// ahocorasick "github.com/petar-dambovaliev/aho-corasick"
func BenchmarkPDambovalievLogFindAll(b *testing.B) {
	builder := ahoc.NewAhoCorasickBuilder(ahoc.Opts{
		AsciiCaseInsensitive: false,
		MatchOnlyWholeWords:  false,
		MatchKind:            ahoc.LeftMostLongestMatch,
		DFA:                  true,
	})
	ac := builder.Build(patterns)

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		matches := ac.FindAll(logLine)
		require.Equal(b, NumOfPatterns, len(matches))
	}
}

And on Mac M1 Pro I've got the following results:

BenchmarkCloudflareLogFindAll-10      	 1350039	       894.4 ns/op	     248 B/op	       5 allocs/op

BenchmarkPDambovalievLogFindAll-10    	  528724	      2155 ns/op	    1472 B/op	      29 allocs/op

It looks like the performance is twice as bad compared to the Cloudflare implementation,
with 29 allocations vs 5. Could you check please?

[petar-dambovaliev]

2 things here are causing the extra allocations.

This slice should preallocate some reasonable amount.

 func (ac AhoCorasick) FindAll(haystack string) []Match {
 .......
       matches := make([]Match, 0)

And the fact that every search is returning a *Match, which is allocating.
The cloudflare one returns only an int for an ID to the thing it matched.
Do you wanna make these improvements?
Maybe we can have 2 different APIS for matching and replacing?
Maybe we can keep the Match structure but return by value, instead of by reference?
Try a few things and see how it performs.

[MikeYast]

2 things here are causing the extra allocations.

This slice should preallocate some reasonable amount.
The slice is not a big deal. It's only single allocation

 func (ac AhoCorasick) FindAll(haystack string) []Match {
 .......
       matches := make([]Match, 0)

And the fact that every search is returning a *Match, which is allocating. The cloudflare one returns only an int for an ID to the thing it matched. Do you wanna make these improvements? Maybe we can have 2 different APIS for matching and replacing? Maybe we can keep the Match structure but return by value, instead of by reference? Try a few things and see how it performs.

I tried replacing references to Match with Match by value throughout the code, which reduced heap allocations by 10. (This is related to heap escapes.)

However, the CPU performance is still about twice as bad compared to the Cloudflare implementation.

[petar-dambovaliev]

matches := make([]Match, 0)

Did you also give the slice allocation a good cap?

Maybe?

matches := make([]Match, 0, 32)

Try it and if it doesn't work, i'll take a look this weekend.

[MikeYast]

No it will not work as planned:
➜ ahocorasick git:(d7354e5) ✗ go test -benchmem -test.bench '^(BenchmarkPDambovalievLogFindAll|BenchmarkCloudflareLogFindAll)$'
goos: darwin
goarch: arm64
pkg: github.com/rrethy/biblio
BenchmarkCloudflareLogFindAll-10 1454005 803.5 ns/op 248 B/op 5 allocs/op
BenchmarkPDambovalievLogFindAll-10 557647 2115 ns/op 1472 B/op 29 allocs/op
PASS