strings: simplify Join using Builder

The existing implementation has a bunch of special cases and
suffers an additional allocation for longer arrays. We can replace
this code with a simple implementation using Builder, improve
performance and reduce complexity.

name      old time/op    new time/op    delta
Join/0-8    3.53ns ± 3%    3.72ns ± 2%   +5.56%  (p=0.000 n=10+10)
Join/1-8    3.94ns ± 4%    3.40ns ± 4%  -13.57%  (p=0.000 n=10+10)
Join/2-8    57.0ns ± 3%    51.0ns ± 1%  -10.48%  (p=0.000 n=10+9)
Join/3-8    74.9ns ± 2%    65.5ns ± 4%  -12.60%  (p=0.000 n=10+10)
Join/4-8     105ns ± 0%      79ns ± 4%  -24.63%  (p=0.000 n=6+10)
Join/5-8     116ns ± 2%      91ns ± 4%  -21.95%  (p=0.000 n=10+10)
Join/6-8     131ns ± 1%     104ns ± 1%  -20.66%  (p=0.000 n=10+10)
Join/7-8     141ns ± 0%     114ns ± 4%  -18.82%  (p=0.000 n=9+10)

name      old alloc/op   new alloc/op   delta
Join/0-8     0.00B          0.00B          ~     (all equal)
Join/1-8     0.00B          0.00B          ~     (all equal)
Join/2-8     16.0B ± 0%     16.0B ± 0%     ~     (all equal)
Join/3-8     32.0B ± 0%     32.0B ± 0%     ~     (all equal)
Join/4-8     96.0B ± 0%     48.0B ± 0%  -50.00%  (p=0.000 n=10+10)
Join/5-8     96.0B ± 0%     48.0B ± 0%  -50.00%  (p=0.000 n=10+10)
Join/6-8      128B ± 0%       64B ± 0%  -50.00%  (p=0.000 n=10+10)
Join/7-8      128B ± 0%       64B ± 0%  -50.00%  (p=0.000 n=10+10)

name      old allocs/op  new allocs/op  delta
Join/0-8      0.00           0.00          ~     (all equal)
Join/1-8      0.00           0.00          ~     (all equal)
Join/2-8      1.00 ± 0%      1.00 ± 0%     ~     (all equal)
Join/3-8      1.00 ± 0%      1.00 ± 0%     ~     (all equal)
Join/4-8      2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.000 n=10+10)
Join/5-8      2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.000 n=10+10)
Join/6-8      2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.000 n=10+10)
Join/7-8      2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.000 n=10+10)

Change-Id: I866a50e809c398512cb87648c955eaa4bf4d8606
Reviewed-on: https://go-review.googlesource.com/132895
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

2 files changed, 20 insertions, 13 deletions

diff --git a/src/strings/strings.go b/src/strings/strings.go
index e0bebced63..df95715ec8 100644
--- a/src/strings/strings.go
+++ b/src/strings/strings.go
@@ -423,27 +423,20 @@ func Join(a []string, sep string) string {
 		return ""
 	case 1:
 		return a[0]
-	case 2:
-		// Special case for common small values.
-		// Remove if golang.org/issue/6714 is fixed
-		return a[0] + sep + a[1]
-	case 3:
-		// Special case for common small values.
-		// Remove if golang.org/issue/6714 is fixed
-		return a[0] + sep + a[1] + sep + a[2]
 	}
 	n := len(sep) * (len(a) - 1)
 	for i := 0; i < len(a); i++ {
 		n += len(a[i])
 	}
 
-	b := make([]byte, n)
-	bp := copy(b, a[0])
+	var b Builder
+	b.Grow(n)
+	b.WriteString(a[0])
 	for _, s := range a[1:] {
-		bp += copy(b[bp:], sep)
-		bp += copy(b[bp:], s)
+		b.WriteString(sep)
+		b.WriteString(s)
 	}
-	return string(b)
+	return b.String()
 }
 
 // HasPrefix tests whether the string s begins with prefix.
diff --git a/src/strings/strings_test.go b/src/strings/strings_test.go
index d6197ed895..20bc484f39 100644
--- a/src/strings/strings_test.go
+++ b/src/strings/strings_test.go
@@ -10,6 +10,7 @@ import (
 	"io"
 	"math/rand"
 	"reflect"
+	"strconv"
 	. "strings"
 	"testing"
 	"unicode"
@@ -1711,3 +1712,16 @@ func BenchmarkIndexPeriodic(b *testing.B) {
 		})
 	}
 }
+
+func BenchmarkJoin(b *testing.B) {
+	vals := []string{"red", "yellow", "pink", "green", "purple", "orange", "blue"}
+	for l := 0; l <= len(vals); l++ {
+		b.Run(strconv.Itoa(l), func(b *testing.B) {
+			b.ReportAllocs()
+			vals := vals[:l]
+			for i := 0; i < b.N; i++ {
+				Join(vals, " and ")
+			}
+		})
+	}
+}