Skip to content

Performance issue at WAF compilation #1644

Description

@racheedevel

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! :)

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions