diff options
| author | Rui Ueyama <ruiu@google.com> | 2014-06-17 22:08:46 -0700 |
|---|---|---|
| committer | Russ Cox <rsc@golang.org> | 2014-06-17 22:08:46 -0700 |
| commit | 14950d89e583e8fe7c4f1ba0ea01495f8e6afac3 (patch) | |
| tree | 8e6052cddd18cf517eec412e5a9f4cd71e565ef7 /src/pkg/strings/replace.go | |
| parent | 14c8143c31fc38fc661188247aa6d3b9d25ae394 (diff) | |
| download | go-14950d89e583e8fe7c4f1ba0ea01495f8e6afac3.tar.xz | |
strings: add fast path to Replace
genericReplacer.lookup is called for each byte of an input
string. In many (most?) cases, lookup will fail for the first
byte, and it will return immediately. Adding a fast path for
that case seems worth it.
Benchmark on my Xeon 3.5GHz Linux box:
benchmark old ns/op new ns/op delta
BenchmarkGenericNoMatch 2691 774 -71.24%
BenchmarkGenericMatch1 7920 8151 +2.92%
BenchmarkGenericMatch2 52336 39927 -23.71%
BenchmarkSingleMaxSkipping 1575 1575 +0.00%
BenchmarkSingleLongSuffixFail 1429 1429 +0.00%
BenchmarkSingleMatch 56228 55444 -1.39%
BenchmarkByteByteNoMatch 568 568 +0.00%
BenchmarkByteByteMatch 977 972 -0.51%
BenchmarkByteStringMatch 1669 1687 +1.08%
BenchmarkHTMLEscapeNew 422 422 +0.00%
BenchmarkHTMLEscapeOld 692 670 -3.18%
BenchmarkByteByteReplaces 8492 8474 -0.21%
BenchmarkByteByteMap 2817 2808 -0.32%
LGTM=rsc
R=golang-codereviews, bradfitz, dave, rsc
CC=golang-codereviews
https://golang.org/cl/79200044
Diffstat (limited to 'src/pkg/strings/replace.go')
| -rw-r--r-- | src/pkg/strings/replace.go | 9 |
1 files changed, 9 insertions, 0 deletions
diff --git a/src/pkg/strings/replace.go b/src/pkg/strings/replace.go index 3e05d2057b..16889bac99 100644 --- a/src/pkg/strings/replace.go +++ b/src/pkg/strings/replace.go @@ -323,6 +323,15 @@ func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error) var last, wn int var prevMatchEmpty bool for i := 0; i <= len(s); { + // Fast path: s[i] is not a prefix of any pattern. + if i != len(s) && r.root.priority == 0 { + index := int(r.mapping[s[i]]) + if index == r.tableSize || r.root.table[index] == nil { + i++ + continue + } + } + // Ignore the empty match iff the previous loop found the empty match. val, keylen, match := r.lookup(s[i:], prevMatchEmpty) prevMatchEmpty = match && keylen == 0 |