perf: reduce allocations handling terms #8116
Conversation
anderseknert
force-pushed
the
term-allocs
branch
from
6c6792d to
9a869d8
Compare
✅ Deploy Preview for openpolicyagent ready!
To edit notification comments on pull requests, go to your Netlify project configuration. |
✅ Deploy Preview for openpolicyagent ready!
To edit notification comments on pull requests, go to your Netlify project configuration. |
|
Great suggestion! However, the method
What I mean by point 2: str := "hello world" // len = 11
// After PathEscape: "hello%20world" // len = 13
// Buffer will be undersized and need to grow!We could implement this method with a single loop iteration and correct buffer length calculation: func (ref Ref) Ptr() (string, error) {
tail := ref[1:]
if len(tail) == 0 {
return "", nil
}
// Estimate buffer size: original length + separators + ~30% for escaping
estSize := 0
for i := range tail {
if str, ok := tail[i].Value.(String); ok {
estSize += len(str)
} else {
return "", errors.New("invalid path value type")
}
}
estSize += len(tail) - 1 // separators ('/')
estSize += estSize / 3 // ~30% overhead for potential escaping
var buf strings.Builder
buf.Grow(estSize)
for i := range tail {
if i > 0 {
buf.WriteByte('/')
}
str := string(tail[i].Value.(String)) // safe: already validated above
buf.WriteString(url.PathEscape(str))
}
return buf.String(), nil
}Or even integrate the escaping to avoid intermediate allocations from url.PathEscape: const upperhex = "0123456789ABCDEF"
// shouldEscapePath checks if byte needs escaping in URL path component
// RFC 3986: unreserved = ALPHA / DIGIT / "-" / "." / "_" / "~"
func shouldEscapePath(c byte) bool {
if 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9' {
return false
}
switch c {
case '-', '_', '.', '~':
return false
}
return true
}
func (ref Ref) Ptr() (string, error) {
tail := ref[1:]
if len(tail) == 0 {
return "", nil
}
// Validate all terms and calculate size
estSize := len(tail) - 1 // separators
for i := range tail {
str, ok := tail[i].Value.(String)
if !ok {
return "", errors.New("invalid path value type")
}
estSize += len(str) + len(str)/3 // string + ~30% escape overhead
}
var buf strings.Builder
buf.Grow(estSize)
for i := range tail {
if i > 0 {
buf.WriteByte('/')
}
s := string(tail[i].Value.(String))
// Inline path escaping - avoids url.PathEscape allocations
for j := 0; j < len(s); j++ {
c := s[j]
if shouldEscapePath(c) {
buf.WriteByte('%')
buf.WriteByte(upperhex[c>>4])
buf.WriteByte(upperhex[c&15])
} else {
buf.WriteByte(c)
}
}
}
return buf.String(), nil
}What do you think? |
|
@alex60217101990 Hey! And thanks for your suggestion. I'm sorry though, but I'm not sure I understand your comment vs. your code. The code you posted also iterates twice over the parts, and I'm frankly not sure how any solution could correctly calculate the length to pre-allocate without it doing that. As for the I think an appender for URL path components in some util lib of ours (which relied on the logic from your example) would likely be a good option. |
|
@anderseknert Okay, I agree with you. One small question, wouldn't it perhaps be better if the object were allocated on the stack rather than the heap ? buf := &strings.Builder{} // forces heap allocationBetter: var buf strings.Builder // stack allocation (if it doesn't escape)Also, we could start the loop in the method func (ref Ref) GroundPrefix() Ref {
if ref.IsGround() {
return ref
}
// Head is always ground by definition, start checking from index 1
for i := 1; i < len(ref); i++ {
if !ref[i].IsGround() {
return ref[:i]
}
}
return ref
} |
|
In addition to your comment. I looked at the code via the link you attached, thank you. Looking at Go's stdlib As suggested, creating a reusable package util
import "strings"
const upperhex = "0123456789ABCDEF"
// shouldEscapePathSegment checks if byte needs escaping in URL path segment
// Based on RFC 3986 and Go's url.shouldEscape(c, encodePathSegment)
func shouldEscapePathSegment(c byte) bool {
// Unreserved characters (RFC 3986 §2.3)
if 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9' {
return false
}
switch c {
case '-', '_', '.', '~':
return false
// Additional allowed in path segment
case '!', '$', '&', '\'', '(', ')', '*', '+', '=', ':', '@':
return false
}
return true
}
// AppendPathEscape appends the path-escaped form of s to buf.
// This avoids intermediate allocations compared to url.PathEscape.
func AppendPathEscape(buf *strings.Builder, s string) {
for i := 0; i < len(s); i++ {
c := s[i]
if shouldEscapePathSegment(c) {
buf.WriteByte('%')
buf.WriteByte(upperhex[c>>4])
buf.WriteByte(upperhex[c&15])
} else {
buf.WriteByte(c)
}
}
}
// CountPathEscapeLen returns the length of s after path escaping.
// Useful for pre-allocating buffers.
func CountPathEscapeLen(s string) int {
n := 0
for i := 0; i < len(s); i++ {
if shouldEscapePathSegment(s[i]) {
n += 3 // %XX
} else {
n++
}
}
return n
}And then the func (ref Ref) Ptr() (string, error) {
tail := ref[1:]
if len(tail) == 0 {
return "", nil
}
// Calculate exact buffer size
l := len(tail) - 1 // separators
for i := range tail {
str, ok := tail[i].Value.(String)
if !ok {
return "", errors.New("invalid path value type")
}
l += util.CountPathEscapeLen(string(str))
}
var buf strings.Builder
buf.Grow(l)
for i := range tail {
if i > 0 {
buf.WriteByte('/')
}
util.AppendPathEscape(&buf, string(tail[i].Value.(String)))
}
return buf.String(), nil
} |
johanfylling
left a comment
johanfylling
left a comment
There was a problem hiding this comment.
I'm not super concerned with dropping the copying if we don't rely on that internally. To be safe, maybe we should update the comment for public functions to let users know they're not getting a copy. Would this be something we want to mention as a possible breaking change for SDK users in the release notes? 🤔
| parts = append(parts, url.PathEscape(string(str))) | ||
| } else { | ||
| buf := &strings.Builder{} | ||
| tail := ref[1:] |
There was a problem hiding this comment.
Interesting that we're dropping the first term. I suppose this is always the data/input root doc?
| return true | ||
| case Var, Ref, *ArrayComprehension, *ObjectComprehension, *SetComprehension, Call: | ||
| return false | ||
| } |
Reduce allocations in various methods working on ast.Term's: - 1 alloc less needed in `Set.Copy`(!) - 1 alloc less needed for `Ref.Ptr` - 2 allocs less needed in `*object.MergeWith` - Remove `.Copy` call in all the various ref prefix functions The latter is likely the only "controversial" change, but reading the docstrings for these functions made no mention of returing deep copies, and importantly, we had **no** code that depended on them doing so. Meaning we paid a cost without reaping benefits from that. If future callers want copies, they can copy. Also added relevant micro-benchmarks. Signed-off-by: Anders Eknert <[email protected]>
anderseknert
force-pushed
the
term-allocs
branch
from
9a869d8 to
a03fd05
Compare
Signed-off-by: Johan Fylling <[email protected]>
3 participants
Reduce allocations in various methods working on ast.Term's:
Set.Copy(!)Ref.Ptr*object.MergeWith.Copycall in all the various ref prefix functionsThe latter is likely the only "controversial" change, but reading the docstrings for these functions made no mention of returing deep copies, and importantly, we had no code that depended on them doing so. Meaning we paid a cost without reaping benefits from that. If future callers want copies, they can copy.
Also added relevant micro-benchmarks.