strings: implement a faster single-string Replacer

The string searching is implemented separately so other functions
may make use of it in the future.

benchmark                        old ns/op    new ns/op    delta
BenchmarkSingleMaxSkipping          125889         2474  -98.03%
BenchmarkSingleLongSuffixFail        16252         1996  -87.72%
BenchmarkSingleMatch                260793       136266  -47.75%

benchmark                         old MB/s     new MB/s  speedup
BenchmarkSingleMaxSkipping           79.43      4041.57   50.88x
BenchmarkSingleLongSuffixFail        61.65       501.81    8.14x
BenchmarkSingleMatch                 57.52       110.08    1.91x

R=nigeltao
CC=golang-dev
https://golang.org/cl/6545049

1 files changed, 73 insertions, 7 deletions

diff --git a/src/pkg/strings/replace.go b/src/pkg/strings/replace.go
index d863eeb5c6..f63b1792c5 100644
--- a/src/pkg/strings/replace.go
+++ b/src/pkg/strings/replace.go
@@ -33,6 +33,10 @@ func NewReplacer(oldnew ...string) *Replacer {
 		panic("strings.NewReplacer: odd argument count")
 	}
 
+	if len(oldnew) == 2 && len(oldnew[0]) > 1 {
+		return &Replacer{r: makeSingleStringReplacer(oldnew[0], oldnew[1])}
+	}
+
 	allNewBytes := true
 	for i := 0; i < len(oldnew); i += 2 {
 		if len(oldnew[i]) != 1 {
@@ -288,6 +292,10 @@ func (w *appendSliceWriter) WriteString(s string) (int, error) {
 	return len(s), nil
 }
 
+type stringWriterIface interface {
+	WriteString(string) (int, error)
+}
+
 type stringWriter struct {
 	w io.Writer
 }
@@ -296,6 +304,14 @@ func (w stringWriter) WriteString(s string) (int, error) {
 	return w.w.Write([]byte(s))
 }
 
+func getStringWriter(w io.Writer) stringWriterIface {
+	sw, ok := w.(stringWriterIface)
+	if !ok {
+		sw = stringWriter{w}
+	}
+	return sw
+}
+
 func (r *genericReplacer) Replace(s string) string {
 	buf := make(appendSliceWriter, 0, len(s))
 	r.WriteString(&buf, s)
@@ -303,13 +319,7 @@ func (r *genericReplacer) Replace(s string) string {
 }
 
 func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error) {
-	sw, ok := w.(interface {
-		WriteString(string) (int, error)
-	})
-	if !ok {
-		sw = stringWriter{w}
-	}
-
+	sw := getStringWriter(w)
 	var last, wn int
 	var prevMatchEmpty bool
 	for i := 0; i <= len(s); {
@@ -340,6 +350,62 @@ func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error)
 	return
 }
 
+// singleStringReplacer is the implementation that's used when there is only
+// one string to replace (and that string has more than one byte).
+type singleStringReplacer struct {
+	finder *stringFinder
+	// value is the new string that replaces that pattern when it's found.
+	value string
+}
+
+func makeSingleStringReplacer(pattern string, value string) *singleStringReplacer {
+	return &singleStringReplacer{finder: makeStringFinder(pattern), value: value}
+}
+
+func (r *singleStringReplacer) Replace(s string) string {
+	var buf []byte
+	i := 0
+	for {
+		match := r.finder.next(s[i:])
+		if match == -1 {
+			break
+		}
+		buf = append(buf, s[i:i+match]...)
+		buf = append(buf, r.value...)
+		i += match + len(r.finder.pattern)
+	}
+	if buf == nil {
+		return s
+	}
+	buf = append(buf, s[i:]...)
+	return string(buf)
+}
+
+func (r *singleStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
+	sw := getStringWriter(w)
+	var i, wn int
+	for {
+		match := r.finder.next(s[i:])
+		if match == -1 {
+			break
+		}
+		wn, err = sw.WriteString(s[i : i+match])
+		n += wn
+		if err != nil {
+			return
+		}
+		wn, err = sw.WriteString(r.value)
+		n += wn
+		if err != nil {
+			return
+		}
+		i += match + len(r.finder.pattern)
+	}
+	wn, err = sw.WriteString(s[i:])
+	n += wn
+	return
+}
+
 // byteReplacer is the implementation that's used when all the "old"
 // and "new" values are single ASCII bytes.
 type byteReplacer struct {