This is an automated email from the ASF dual-hosted git repository.
hsluoyz pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/casbin.git
The following commit(s) were added to refs/heads/master by this push:
new 0936f2c perf: cache compiled patterns by key2 in KeyMatch/KeyGet
0936f2c is described below
commit 0936f2c3ff4962f2910118348220068367541557
Author: Yang Luo <[email protected]>
AuthorDate: Fri Aug 7 00:38:52 2026 +0800
perf: cache compiled patterns by key2 in KeyMatch/KeyGet
---
util/builtin_operators.go | 144 ++++++++++++++++++++++++++++++---------
util/builtin_operators_b_test.go | 65 ++++++++++++++++++
2 files changed, 177 insertions(+), 32 deletions(-)
diff --git a/util/builtin_operators.go b/util/builtin_operators.go
index 404aaa8..cb0361e 100644
--- a/util/builtin_operators.go
+++ b/util/builtin_operators.go
@@ -84,6 +84,49 @@ func keyMatchShortcut(key1 string, key2 string, extraChars
string) (matched bool
return false, false
}
+// compiledPattern is the fully prepared form of a matcher's key2: the regexp
that
+// key1 is tested against, plus the names of the pattern variables in the order
+// their capture groups appear (only KeyGet2/KeyGet3/KeyMatch4 use tokens).
+//
+// Everything in it is a pure function of key2, so it is built once per
distinct
+// key2 and reused afterwards.
+type compiledPattern struct {
+ re *regexp.Regexp
+ tokens []string
+}
+
+// patternCache memoizes compiledPattern by raw key2, one cache per matcher
since
+// each of them reads key2 in its own dialect. Only compiling the regexp used
to be
+// cached (see mustCompileOrGet), which still left every call rebuilding the
regexp
+// source with a chain of ReplaceAll passes just to look it up. Keying on key2
+// instead makes the steady state a single map read.
+//
+// A policy holds a bounded set of patterns, so the cache converges to that set
+// after the first pass; sync.Map suits that read-mostly shape.
+type patternCache struct {
+ m sync.Map // string -> *compiledPattern
+}
+
+func (c *patternCache) get(key2 string, build func(key2 string)
*compiledPattern) *compiledPattern {
+ if v, ok := c.m.Load(key2); ok {
+ return v.(*compiledPattern)
+ }
+
+ p := build(key2)
+ c.m.Store(key2, p)
+
+ return p
+}
+
+var (
+ keyMatch2Cache patternCache
+ keyMatch3Cache patternCache
+ keyMatch4Cache patternCache
+ keyMatch5Cache patternCache
+ keyGet2Cache patternCache
+ keyGet3Cache patternCache
+)
+
func mustCompileOrGet(key string) *regexp.Regexp {
reCacheMu.RLock()
re, ok := reCache[key]
@@ -184,11 +227,15 @@ func KeyMatch2(key1 string, key2 string) bool {
return matched
}
+ return keyMatch2Cache.get(key2, buildKeyMatch2).re.MatchString(key1)
+}
+
+func buildKeyMatch2(key2 string) *compiledPattern {
key2 = strings.ReplaceAll(key2, "/*", "/.*")
key2 = keyMatch2Re.ReplaceAllString(key2, "$1[^/]+$2")
- return RegexMatch(key1, "^"+key2+"$")
+ return &compiledPattern{re: mustCompileOrGet("^" + key2 + "$")}
}
// KeyMatch2Func is the wrapper for KeyMatch2.
@@ -207,24 +254,34 @@ func KeyMatch2Func(args ...interface{}) (interface{},
error) {
// For example, "/resource1" matches "/:resource"
// if the pathVar == "resource", then "resource1" will be returned.
func KeyGet2(key1, key2 string, pathVar string) string {
- key2 = strings.ReplaceAll(key2, "/*", "/.*")
- keys := keyGet2Re1.FindAllString(key2, -1)
- key2 = keyGet2Re1.ReplaceAllString(key2, "$1([^/]+)$2")
- key2 = "^" + key2 + "$"
+ p := keyGet2Cache.get(key2, buildKeyGet2)
- re := mustCompileOrGet(key2)
- values := re.FindAllStringSubmatch(key1, -1)
+ values := p.re.FindAllStringSubmatch(key1, -1)
if len(values) == 0 {
return ""
}
- for i, key := range keys {
- if pathVar == key[1:] {
+ for i, key := range p.tokens {
+ if pathVar == key {
return values[0][i+1]
}
}
return ""
}
+func buildKeyGet2(key2 string) *compiledPattern {
+ key2 = strings.ReplaceAll(key2, "/*", "/.*")
+
+ // The ":" is dropped here so that the lookup in KeyGet2 is a plain
comparison.
+ tokens := keyGet2Re1.FindAllString(key2, -1)
+ for i, token := range tokens {
+ tokens[i] = token[1:]
+ }
+
+ key2 = keyGet2Re1.ReplaceAllString(key2, "$1([^/]+)$2")
+
+ return &compiledPattern{re: mustCompileOrGet("^" + key2 + "$"), tokens:
tokens}
+}
+
// KeyGet2Func is the wrapper for KeyGet2.
func KeyGet2Func(args ...interface{}) (interface{}, error) {
if err := validateVariadicArgs(3, args...); err != nil {
@@ -245,10 +302,14 @@ func KeyMatch3(key1 string, key2 string) bool {
return matched
}
+ return keyMatch3Cache.get(key2, buildKeyMatch3).re.MatchString(key1)
+}
+
+func buildKeyMatch3(key2 string) *compiledPattern {
key2 = strings.ReplaceAll(key2, "/*", "/.*")
key2 = keyMatch3Re.ReplaceAllString(key2, "$1[^/]+$2")
- return RegexMatch(key1, "^"+key2+"$")
+ return &compiledPattern{re: mustCompileOrGet("^" + key2 + "$")}
}
// KeyMatch3Func is the wrapper for KeyMatch3.
@@ -267,24 +328,35 @@ func KeyMatch3Func(args ...interface{}) (interface{},
error) {
// For example, "project/proj_project1_admin/" matches
"project/proj_{project}_admin/"
// if the pathVar == "project", then "project1" will be returned.
func KeyGet3(key1, key2 string, pathVar string) string {
- key2 = strings.ReplaceAll(key2, "/*", "/.*")
+ p := keyGet3Cache.get(key2, buildKeyGet3)
- keys := keyGet3Re1.FindAllString(key2, -1)
- key2 = keyGet3Re1.ReplaceAllString(key2, "$1([^/]+?)$2")
- key2 = "^" + key2 + "$"
- re := mustCompileOrGet(key2)
- values := re.FindAllStringSubmatch(key1, -1)
+ values := p.re.FindAllStringSubmatch(key1, -1)
if len(values) == 0 {
return ""
}
- for i, key := range keys {
- if pathVar == key[1:len(key)-1] {
+ for i, key := range p.tokens {
+ if pathVar == key {
return values[0][i+1]
}
}
return ""
}
+func buildKeyGet3(key2 string) *compiledPattern {
+ key2 = strings.ReplaceAll(key2, "/*", "/.*")
+
+ // The surrounding "{}" is dropped here so that the lookup in KeyGet3
is a plain
+ // comparison.
+ tokens := keyGet3Re1.FindAllString(key2, -1)
+ for i, token := range tokens {
+ tokens[i] = token[1 : len(token)-1]
+ }
+
+ key2 = keyGet3Re1.ReplaceAllString(key2, "$1([^/]+?)$2")
+
+ return &compiledPattern{re: mustCompileOrGet("^" + key2 + "$"), tokens:
tokens}
+}
+
// KeyGet3Func is the wrapper for KeyGet3.
func KeyGet3Func(args ...interface{}) (interface{}, error) {
if err := validateVariadicArgs(3, args...); err != nil {
@@ -308,30 +380,21 @@ func KeyMatch4(key1 string, key2 string) bool {
return matched
}
- key2 = strings.ReplaceAll(key2, "/*", "/.*")
-
- tokens := []string{}
-
- re := keyMatch4Re
- key2 = re.ReplaceAllStringFunc(key2, func(s string) string {
- tokens = append(tokens, s[1:len(s)-1])
- return "([^/]+)"
- })
+ p := keyMatch4Cache.get(key2, buildKeyMatch4)
- re = mustCompileOrGet("^" + key2 + "$")
- matches := re.FindStringSubmatch(key1)
+ matches := p.re.FindStringSubmatch(key1)
if matches == nil {
return false
}
matches = matches[1:]
- if len(tokens) != len(matches) {
+ if len(p.tokens) != len(matches) {
panic(errors.New("KeyMatch4: number of tokens is not equal to
number of values"))
}
values := map[string]string{}
- for key, token := range tokens {
+ for key, token := range p.tokens {
if _, ok := values[token]; !ok {
values[token] = matches[key]
}
@@ -343,6 +406,19 @@ func KeyMatch4(key1 string, key2 string) bool {
return true
}
+func buildKeyMatch4(key2 string) *compiledPattern {
+ key2 = strings.ReplaceAll(key2, "/*", "/.*")
+
+ tokens := []string{}
+
+ key2 = keyMatch4Re.ReplaceAllStringFunc(key2, func(s string) string {
+ tokens = append(tokens, s[1:len(s)-1])
+ return "([^/]+)"
+ })
+
+ return &compiledPattern{re: mustCompileOrGet("^" + key2 + "$"), tokens:
tokens}
+}
+
// KeyMatch4Func is the wrapper for KeyMatch4.
func KeyMatch4Func(args ...interface{}) (interface{}, error) {
if err := validateVariadicArgs(2, args...); err != nil {
@@ -373,10 +449,14 @@ func KeyMatch5(key1 string, key2 string) bool {
return matched
}
+ return keyMatch5Cache.get(key2, buildKeyMatch5).re.MatchString(key1)
+}
+
+func buildKeyMatch5(key2 string) *compiledPattern {
key2 = strings.ReplaceAll(key2, "/*", "/.*")
key2 = keyMatch5Re.ReplaceAllString(key2, "$1[^/]+$2")
- return RegexMatch(key1, "^"+key2+"$")
+ return &compiledPattern{re: mustCompileOrGet("^" + key2 + "$")}
}
// KeyMatch5Func is the wrapper for KeyMatch5.
diff --git a/util/builtin_operators_b_test.go b/util/builtin_operators_b_test.go
new file mode 100644
index 0000000..f254e3c
--- /dev/null
+++ b/util/builtin_operators_b_test.go
@@ -0,0 +1,65 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package util
+
+import "testing"
+
+// The key2 of each benchmark holds a pattern character, so the
keyMatchShortcut
+// fast path does not apply and the regexp pipeline is what is being measured.
+
+func BenchmarkKeyMatch2(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ KeyMatch2("/alice_data/resource1", "/:name/resource1")
+ }
+}
+
+func BenchmarkKeyMatch3(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ KeyMatch3("/proxy/myid/res/1", "/proxy/{id}/res/{rid}")
+ }
+}
+
+func BenchmarkKeyMatch4(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ KeyMatch4("/parent/123/child/123", "/parent/{id}/child/{id}")
+ }
+}
+
+func BenchmarkKeyMatch5(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ KeyMatch5("/parent/child1?status=1", "/parent/{id}")
+ }
+}
+
+func BenchmarkKeyGet2(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ KeyGet2("/alice_data/resource1", "/:name/resource1", "name")
+ }
+}
+
+func BenchmarkKeyGet3(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ KeyGet3("project/proj_project1_admin/",
"project/proj_{project}_admin/", "project")
+ }
+}
+
+func BenchmarkRegexMatch(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ RegexMatch("/topic/1", "^/topic/[0-9]+$")
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
