strings: implement a faster byte->string Replacer

This implements a replacer for when all old strings are single
bytes, but new values are not.

BenchmarkHTMLEscapeNew   1000000   1090 ns/op
BenchmarkHTMLEscapeOld   1000000   2049 ns/op

R=rsc
CC=golang-dev
https://golang.org/cl/5176043

1 files changed, 31 insertions, 1 deletions

diff --git a/src/pkg/strings/replace_test.go b/src/pkg/strings/replace_test.go
index 20e734f6cd..e337856c64 100644
--- a/src/pkg/strings/replace_test.go
+++ b/src/pkg/strings/replace_test.go
@@ -41,14 +41,21 @@ var capitalLetters = NewReplacer("a", "A", "b", "B")
 var blankToXReplacer = NewReplacer("", "X", "o", "O")
 
 var ReplacerTests = []ReplacerTest{
+	// byte->string
 	{htmlEscaper, "No changes", "No changes"},
 	{htmlEscaper, "I <3 escaping & stuff", "I &lt;3 escaping &amp; stuff"},
 	{htmlEscaper, "&&&", "&amp;&amp;&amp;"},
+
+	// generic
 	{replacer, "fooaaabar", "foo3[aaa]b1[a]r"},
 	{replacer, "long, longerst, longer", "short, most long, medium"},
 	{replacer, "XiX", "YiY"},
+
+	// byte->byte
 	{capitalLetters, "brad", "BrAd"},
 	{capitalLetters, Repeat("a", (32<<10)+123), Repeat("A", (32<<10)+123)},
+
+	// hitting "" special case
 	{blankToXReplacer, "oo", "XOXOX"},
 }
 
@@ -84,7 +91,9 @@ type pickAlgorithmTest struct {
 
 var pickAlgorithmTests = []pickAlgorithmTest{
 	{capitalLetters, "*strings.byteReplacer"},
-	{NewReplacer("a", "A", "b", "Bb"), "*strings.genericReplacer"},
+	{NewReplacer("12", "123"), "*strings.genericReplacer"},
+	{NewReplacer("1", "12"), "*strings.byteStringReplacer"},
+	{htmlEscaper, "*strings.byteStringReplacer"},
 }
 
 func TestPickAlgorithm(t *testing.T) {
@@ -118,6 +127,27 @@ func BenchmarkByteByteMatch(b *testing.B) {
 	}
 }
 
+func BenchmarkByteStringMatch(b *testing.B) {
+	str := "<" + Repeat("a", 99) + Repeat("b", 99) + ">"
+	for i := 0; i < b.N; i++ {
+		htmlEscaper.Replace(str)
+	}
+}
+
+func BenchmarkHTMLEscapeNew(b *testing.B) {
+	str := "I <3 to escape HTML & other text too."
+	for i := 0; i < b.N; i++ {
+		htmlEscaper.Replace(str)
+	}
+}
+
+func BenchmarkHTMLEscapeOld(b *testing.B) {
+	str := "I <3 to escape HTML & other text too."
+	for i := 0; i < b.N; i++ {
+		oldhtmlEscape(str)
+	}
+}
+
 // BenchmarkByteByteReplaces compares byteByteImpl against multiple Replaces.
 func BenchmarkByteByteReplaces(b *testing.B) {
 	str := Repeat("a", 100) + Repeat("b", 100)