Description
Quadratic complexity when compiling a new WAF, since each rule goes through RuleGroup.Add, which calls RuleGroup.FindById, which does a full pass through the existing rules, which at 100 000 rules takes ~30s to compile.
Steps to reproduce
Not a user-facing issue, but this performance benchmark helps see the complexity is quadratic:
// internal/corazawaf/rulegroup_bench_test.go
package corazawaf
import (
"strconv"
"testing"
)
func BenchmarkRuleGroupAdd(b *testing.B) {
for _, n := range []int{1_000, 10_000, 100_000} {
b.Run(strconv.Itoa(n), func(b *testing.B) {
for i := 0; i < b.N; i++ {
rg := NewRuleGroup()
for id := 1; id <= n; id++ {
if err := rg.Add(newTestRule(id)); err != nil {
b.Fatal(err)
}
}
}
})
}
}
Expected result
Expectation would be that linear or more-or-less linear compilation times are visible, something like
| Rules |
Compile |
| 1,000 |
8 ms |
| 10,000 |
80 ms - 160 ms |
| 100,000 |
800 ms - 1600ms |
Actual result
| Rules |
Compile |
| 1,000 |
8 ms |
| 10,000 |
241 ms |
| 100,000 |
30,616 ms |
The 100k ruleset takes 127x as much time as the 10k ruleset.
Will throw in my PR as well to address it! :)
Description
Quadratic complexity when compiling a new WAF, since each rule goes through
RuleGroup.Add, which callsRuleGroup.FindById, which does a full pass through the existing rules, which at 100 000 rules takes ~30s to compile.Steps to reproduce
Not a user-facing issue, but this performance benchmark helps see the complexity is quadratic:
Expected result
Expectation would be that linear or more-or-less linear compilation times are visible, something like
Actual result
The 100k ruleset takes 127x as much time as the 10k ruleset.
Will throw in my PR as well to address it! :)