[go] regexp: avoid copying the input when ReplaceAllString finds no match
0 views
Skip to first unread message
Gerrit Bot (Gerrit)
8:29 PM (2 hours ago) 8:29 PM
to goph...@pubsubhelper.golang.org, David Teather, golang-co...@googlegroups.com
Gerrit Bot has uploaded the change for review![]( "Open in Gerrit")
Commit message
regexp: avoid copying the input when ReplaceAllString finds no match
replaceAll already knows whether it matched, so report that rather than
searching again. The string methods can then return src directly instead
of building an equal copy. The []byte methods still copy, since callers
may mutate the result and it must not alias src.
Allocations drop on every no-match path. The time saving depends on how
expensive the search itself is: for a pattern with a literal prefix the
search is nearly free and the avoided copy dominates, while for a
character class the NFA search dominates instead. The match path
allocates the same as before.
goos: darwin
goarch: arm64
pkg: regexp
cpu: Apple M2 Pro
│ old │ new │
│ sec/op │ sec/op vs base │
ReplaceAll-10 510.6n ± 0% 517.5n ± 0% +1.35% (p=0.000 n=25)
ReplaceAllNoMatch-10 310.9n ± 0% 288.1n ± 0% -7.33% (p=0.000 n=25)
ReplaceAllLongNoMatch-10 24.16µ ± 0% 23.80µ ± 1% -1.49% (p=0.000 n=25)
ReplaceAllPrefixNoMatch-10 61.31n ± 1% 38.67n ± 0% -36.93% (p=0.000 n=25)
ReplaceAllLongPrefixNoMatch-10 721.60n ± 1% 95.65n ± 0% -86.74% (p=0.000 n=25)
geomean 701.3n 420.4n -40.06%
│ old │ new │
│ B/op │ B/op vs base │
ReplaceAll-10 96.00 ± 0% 96.00 ± 0% ~ (p=1.000 n=25)
ReplaceAllNoMatch-10 80.00 ± 0% 16.00 ± 0% -80.00% (p=0.000 n=25)
ReplaceAllLongNoMatch-10 5397.00 ± 0% 16.00 ± 0% -99.70% (p=0.000 n=25)
ReplaceAllPrefixNoMatch-10 80.00 ± 0% 16.00 ± 0% -80.00% (p=0.000 n=25)
ReplaceAllLongPrefixNoMatch-10 5449.00 ± 0% 16.00 ± 0% -99.71% (p=0.000 n=25)
geomean 448.1 22.90 -94.89%
│ old │ new │
│ allocs/op │ allocs/op vs base │
ReplaceAll-10 5.000 ± 0% 5.000 ± 0% ~ (p=1.000 n=25)
ReplaceAllNoMatch-10 3.000 ± 0% 1.000 ± 0% -66.67% (p=0.000 n=25)
ReplaceAllLongNoMatch-10 3.000 ± 0% 1.000 ± 0% -66.67% (p=0.000 n=25)
ReplaceAllPrefixNoMatch-10 3.000 ± 0% 1.000 ± 0% -66.67% (p=0.000 n=25)
ReplaceAllLongPrefixNoMatch-10 3.000 ± 0% 1.000 ± 0% -66.67% (p=0.000 n=25)
geomean 3.323 1.380 -58.48%
Fixes #80280
Change-Id: I3a3d9a432348d2e92c28487b914b9f7048e84f0d
GitHub-Last-Rev: d13afd390736b7a6a697cbf81f34ea2d61871823
GitHub-Pull-Request: golang/go#80502
Change diff
diff --git a/src/regexp/all_test.go b/src/regexp/all_test.go
index dd5fb8f..03498ec 100644
--- a/src/regexp/all_test.go
+++ b/src/regexp/all_test.go
@@ -741,6 +741,38 @@
}
}
+func BenchmarkReplaceAllNoMatch(b *testing.B) {
+ x := "abcdefghijklmnopqrstuvwxyz"
+ re := MustCompile("[123]")
+ for b.Loop() {
+ re.ReplaceAllString(x, "")
+ }
+}
+
+func BenchmarkReplaceAllLongNoMatch(b *testing.B) {
+ x := strings.Repeat("abcdefghijklmnopqrstuvwxyz", 100)
+ re := MustCompile("[123]")
+ for b.Loop() {
+ re.ReplaceAllString(x, "")
+ }
+}
+
+func BenchmarkReplaceAllPrefixNoMatch(b *testing.B) {
+ x := "abcdefghijklmnopqrstuvwxyz"
+ re := MustCompile("123")
+ for b.Loop() {
+ re.ReplaceAllString(x, "")
+ }
+}
+
+func BenchmarkReplaceAllLongPrefixNoMatch(b *testing.B) {
+ x := strings.Repeat("abcdefghijklmnopqrstuvwxyz", 100)
+ re := MustCompile("123")
+ for b.Loop() {
+ re.ReplaceAllString(x, "")
+ }
+}
+
func BenchmarkAnchoredLiteralShortNonMatch(b *testing.B) {
b.StopTimer()
x := []byte("abcdefghijklmnopqrstuvwxyz")
diff --git a/src/regexp/regexp.go b/src/regexp/regexp.go
index 29f50bb..1a4bc4d 100644
--- a/src/regexp/regexp.go
+++ b/src/regexp/regexp.go
@@ -546,43 +546,55 @@
}
// ReplaceAllString returns a copy of src, replacing matches of the [Regexp]
-// with the replacement string repl.
+// with the replacement string repl, or src itself if there is no match.
// Inside repl, $ signs are interpreted as in [Regexp.Expand].
func (re *Regexp) ReplaceAllString(src, repl string) string {
n := 2
if strings.Contains(repl, "$") {
n = 2 * (re.numSubexp + 1)
}
- b := re.replaceAll(nil, src, n, func(dst []byte, match []int) []byte {
+ b, matched := re.replaceAll(nil, src, n, func(dst []byte, match []int) []byte {
return re.expand(dst, repl, nil, src, match)
})
+ if !matched {
+ return src
+ }
return string(b)
}
// ReplaceAllLiteralString returns a copy of src, replacing matches of the [Regexp]
-// with the replacement string repl. The replacement repl is substituted directly,
-// without using [Regexp.Expand].
+// with the replacement string repl, or src itself if there is no match.
+// The replacement repl is substituted directly, without using [Regexp.Expand].
func (re *Regexp) ReplaceAllLiteralString(src, repl string) string {
- return string(re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
+ b, matched := re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
return append(dst, repl...)
- }))
+ })
+ if !matched {
+ return src
+ }
+ return string(b)
}
// ReplaceAllStringFunc returns a copy of src in which all matches of the
// [Regexp] have been replaced by the return value of function repl applied
-// to the matched substring. The replacement returned by repl is substituted
-// directly, without using [Regexp.Expand].
+// to the matched substring, or src itself if there is no match.
+// The replacement returned by repl is substituted directly, without using
+// [Regexp.Expand]. If there is no match, repl is not called.
func (re *Regexp) ReplaceAllStringFunc(src string, repl func(string) string) string {
- b := re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
+ b, matched := re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
return append(dst, repl(src[match[0]:match[1]])...)
})
+ if !matched {
+ return src
+ }
return string(b)
}
-func (re *Regexp) replaceAll(bsrc []byte, src string, nmatch int, repl func(dst []byte, m []int) []byte) []byte {
+// replaceAll returns the result of replacing all matches in bsrc or src, and
+// reports whether any match was found.
+func (re *Regexp) replaceAll(bsrc []byte, src string, nmatch int, repl func(dst []byte, m []int) []byte) (buf []byte, matched bool) {
lastMatchEnd := 0 // end position of the most recent match
searchPos := 0 // position where we next look for a match
- var buf []byte
var endPos int
if bsrc != nil {
endPos = len(bsrc)
@@ -599,6 +611,7 @@
if len(a) == 0 {
break // no more matches
}
+ matched = true
// Copy the unmatched characters before this match.
if bsrc != nil {
@@ -634,6 +647,12 @@
}
}
+ if !matched {
+ // Nothing was replaced, so the result equals the input.
+ // Skip copying it, the caller decides what to return.
+ return nil, false
+ }
+
// Copy the unmatched characters after the last match.
if bsrc != nil {
buf = append(buf, bsrc[lastMatchEnd:]...)
@@ -641,7 +660,7 @@
buf = append(buf, src[lastMatchEnd:]...)
}
- return buf
+ return buf, true
}
// ReplaceAll returns a copy of src, replacing matches of the [Regexp]
@@ -653,12 +672,15 @@
n = 2 * (re.numSubexp + 1)
}
srepl := ""
- b := re.replaceAll(src, "", n, func(dst []byte, match []int) []byte {
+ b, matched := re.replaceAll(src, "", n, func(dst []byte, match []int) []byte {
if len(srepl) != len(repl) {
srepl = string(repl)
}
return re.expand(dst, srepl, src, "", match)
})
+ if !matched {
+ return append([]byte(nil), src...)
+ }
return b
}
@@ -666,9 +688,13 @@
// with the replacement bytes repl. The replacement repl is substituted directly,
// without using [Regexp.Expand].
func (re *Regexp) ReplaceAllLiteral(src, repl []byte) []byte {
- return re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
+ b, matched := re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
return append(dst, repl...)
})
+ if !matched {
+ return append([]byte(nil), src...)
+ }
+ return b
}
// ReplaceAllFunc returns a copy of src in which all matches of the
@@ -676,9 +702,13 @@
// to the matched byte slice. The replacement returned by repl is substituted
// directly, without using [Regexp.Expand].
func (re *Regexp) ReplaceAllFunc(src []byte, repl func([]byte) []byte) []byte {
- return re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
+ b, matched := re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
return append(dst, repl(src[match[0]:match[1]])...)
})
+ if !matched {
+ return append([]byte(nil), src...)
+ }
+ return b
}
// Bitmap used by func special to check whether a character needs to be escaped.
Change information
Files:
- M src/regexp/all_test.go
- M src/regexp/regexp.go
Change size: M
Delta: 2 files changed, 77 insertions(+), 15 deletions(-)
Related details
Attention set is empty
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Reply all
Reply to author
Forward
0 new messages