The previous two days showed the CPU profile and benchmark result for linear event search. Now, we have an improved version of search but with the use of indexes, basically a map. Instead of iterating the list of allowed names, CountAllowedEventsIndexed uses a map to search for an event, replacing the O(N) complexity of CountAllowedEventsLinear to O(1).
func CountAllowedEventsLinear(eventNames, allowedNames []string) int {
count := 0
for _, name := range eventNames {
if slices.Contains(allowedNames, name) {
count++
}
}
return count
}
func CountAllowedEventsIndexed(eventNames []string, allowed map[string]struct{}) int {
count := 0
for _, name := range eventNames {
if _, ok := allowed[name]; ok {
count++
}
}
return count
}
func NewAllowedEventSet(allowedNames []string) map[string]struct{} {
allowed := make(map[string]struct{}, len(allowedNames))
for _, name := range allowedNames {
allowed[name] = struct{}{}
}
return allowed
}
func BenchmarkCountAllowedEvents(b *testing.B) {
allowedNames := make([]string, 1_000)
for i := range allowedNames {
allowedNames[i] = fmt.Sprintf("event.%04d", i)
}
eventNames := make([]string, 2_000)
for i := range eventNames {
eventNames[i] = allowedNames[len(allowedNames)-1]
}
b.Run("implementation=linear", func(b *testing.B) {
var count int
b.ReportAllocs()
for b.Loop() {
count = CountAllowedEventsLinear(eventNames, allowedNames)
}
sinkAllowedCount = count
})
allowed := NewAllowedEventSet(allowedNames)
b.Run("implementation=indexed", func(b *testing.B) {
var count int
b.ReportAllocs()
for b.Loop() {
count = CountAllowedEventsIndexed(eventNames, allowed)
}
sinkAllowedCount = count
})
}We can see in the result that the indexed version uses 99.68% less time per operation:
go test -run '^$' \
-bench '^BenchmarkCountAllowedEvents$' \
-count=10 \
> /tmp/codec01-allowlist.txt
benchstat \
-col /implementation \
-row .name \
/tmp/codec01-allowlist.txt
goos: linux
goarch: arm64
pkg: codec01
│ linear │ indexed │
│ sec/op │ sec/op vs base │
CountAllowedEvents 4021.60µ ± 4% 12.67µ ± 1% -99.68% (p=0.000 n=10)
│ linear │ indexed │
│ B/op │ B/op vs base │
CountAllowedEvents 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
¹ all samples are equal
│ linear │ indexed │
│ allocs/op │ allocs/op vs base │
CountAllowedEvents 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
¹ all samples are equal