Inhibition rules evaluation performance on many target alerts

Context

Requesting /alerts from my organizations alertmanager returns a reply in 4-6 seconds.
The alertmanager has consistently

• between 10k-13k alerts and
• 86 inhibition rules.

Given this scale, I was a bit surprised that fetching the alerts takes multiple seconds.
Taking a trace via pprof revealed that at least 4 seconds are spent calculating inhibited alerts.
Furthermore, a few hundred milliseconds are spent serializing the json response, which is expected due to the size of ~20 MiB in our case.
The structure of my organizations inhibition rules can lead to ~10k alerts matching a target matcher and ~1k alerts matching the source matcher.
Currently the benchmarks only consider cases with a single alert satisfying a target matcher.

Calling /alerts results basically in the following algorithm being executed at the moment:

• For each T in all alerts (calls into Mutes here):
  • For each R in all inhibition rules:
    • Continue if T is not valid target
    • For each S in source alerts cached by R:
      • Check for label equality
      • Prevent two-sided match

Memoize source cache target match evaluations

The Prevent two-sided match step evaluates r.TargetMatchers.Matches(a.Labels), where a is from the cached source alerts.
It's invoked over and over again for each alert that is a valid target (potentially evaluating regular expressions), but it is not dependent on a specific target alert.
Assuming I did not miss a side effect, the result of r.TargetMatchers.Matches(a.Labels) is only dependent on a specific inhibition rule and that rule's source alert cache.
By memoizing that expression, a performance gain can be achieved when many alerts are valid targets.

Constructing indices

Checking for label equality between the set of valid source alerts and valid target alerts runs in quadratic time.
By maintaining an index per label, which maps that label's values to an "index into a slice of all alerts", alerts that have a label with a specific value can found by a map lookup.
For multiple labels that need to be checked for equality, multiple slices of indices can be intersected in linear time.
This would be a larger change though.

Start with inhibit/inhibit.go and the existing cases in inhibit/inhibit_bench_test.go, then trace the /alerts path through api/v2/api.go and cmd/alertmanager/main.go. Evaluate the memoized target-match approach first; done means benchmarks cover many target alerts and demonstrate improved inhibition evaluation without changing behavior.