Joining strings is so common that many of us take it for granted. While working through the exercises in ‘The Go Programming Language’ book as part of the London Study Group, I wanted to understand the differences between the various approaches for joining strings.
If you are looking to concatenate strings in Go, here is what I’d do:
- Outside a loop: use the
+operator: e.g. `“a” + “b” - Inside a loop: use
strings.Join([]string, string)
If you want to know why read on. The notes that follow are primarily for my own understanding. They chart my attempt to explain the results of exercise 1.3 and explore different options for string concatenation.
Benchmarks
The exercise looked at comparing the use of three common string concatenation approaches; +, fmt.Sprintf() and strings.Join(). Because I like to explore a little, I wrote my own version which I’m calling Custom(). This is a terrible name for a function.
$ go test -bench=. -benchmem -run=^
goos: darwin
goarch: amd64
pkg: ../ex1.3
BenchmarkFormat-8 200000 8959 ns/op 1952 B/op 102 allocs/op
BenchmarkConcat-8 200000 6053 ns/op 14912 B/op 99 allocs/op
BenchmarkJoin-8 2000000 875 ns/op 640 B/op 2 allocs/op
BenchmarkCustom-8 1000000 1500 ns/op 752 B/op 3 allocs/op
I expected that there would be some variation between these different approaches for string concatenation. I was also pleasantly surprised that I’d got so close to standard library performance with my custom function. However, I couldn’t see any obvious ways to improve.
Concatenation with +
The benchmarking set-up is shown below.
Function under test:
// Concat takes a slice of strings and returns a string containing the space
// separated values. It uses the + operator to join the strings.
func concat(args []string) string {
var s, sep string
for _, arg := range args {
s += sep + arg
sep = " "
}
return s
}
Benchmarking:
var args = generate(100)
func generate(n int) []string {
s := make([]string, n)
for i := range s {
s[i] = strconv.Itoa(i)
}
return s
}
func BenchmarkConcat(b *testing.B) {
for n := 0; n < b.N; n++ {
concat(args)
}
}
Benchmarking shows that there are 99 memory allocations when joining 100 strings. My working theory is that this is one memory allocation per concatenation operation. We can validate this by looking at the code.
go doc -all -u -src runtime.concatstrings
// concatstrings implements a Go string concatenation x+y+z+...
// The operands are passed in the slice a.
// If buf != nil, the compiler has determined that the result does not
// escape the calling function, so the string data can be stored in buf
// if small enough.
func concatstrings(buf *tmpBuf, a []string) string {
idx := 0
l := 0
count := 0
for i, x := range a {
n := len(x)
if n == 0 {
continue
}
if l+n < l {
throw("string concatenation too long")
}
l += n
count++
idx = i
}
if count == 0 {
return ""
}
// If there is just one string and either it is not on the stack
// or our result does not escape the calling frame (buf != nil),
// then we can return that string directly.
if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
return a[idx]
}
s, b := rawstringtmp(buf, l)
for _, x := range a {
copy(b, x)
b = b[len(x):]
}
return s
}
There are two loops at play here. The first computes the length of the combined string. It includes a small optimisation and returns quickly if the resulting string is empty. It also checks that we don’t overflow the length variable, l.
Note: I’m going to gloss over the check to see whether the data is on the stack as I don’t fully understand this. If you can explain this, I’d love to hear from you.
In the second loop, rawstringtmp(buf, l) returns a []byte slice and a string. This results in memory allocation and why we see one allocation per iteration of our concatenation function. Interestingly, the []byte and string point to the same underlying memory. This allows the concatstrings function can operate directly on the underlying []byte slice but return the string to the caller.
What stands out is that these loops are run once per call to concatstrings. When joining multiple strings the length and resulting memory allocation would be computed for each string join. We should be able to do this once for all strings.
Conclusion: Simple syntax, most efficient approach for joining two strings, inefficient inside a loop.
Concatenation with strings.Join
Function under test:
// Join takes a slice of strings and returns a string containing the space
// separated values. It uses strings.Join to join the strings.
func join(args []string) string {
s := strings.Join(args, " ")
return s
}
The same benchmark test was used and so it is not repeated here.
Using strings.Join to concatenate 100 strings is clearly faster than using the + operator. But why? Let’s take a look at the source.
go doc -all -u -src strings.Join
// Join concatenates the elements of a to create a single string. The separator string
// sep is placed between elements in the resulting string.
func Join(a []string, sep string) string {
switch len(a) {
case 0:
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])
for _, s := range a[1:] {
bp += copy(b[bp:], sep)
bp += copy(b[bp:], s)
}
return string(b)
}
This performs two memory allocations, once when creating the []byte slice and again when casting to string in the return statement. This explains the 2 allocs/op that we see in the benchmark results.
$ go test -bench=. -benchmem -run=^
goos: darwin
goarch: amd64
pkg: ../ex1.3
BenchmarkConcat-8 200000 6053 ns/op 14912 B/op 99 allocs/op
BenchmarkJoin-8 2000000 875 ns/op 640 B/op 2 allocs/op
This function takes advantage of the fact that it is possible to pre-compute and allocate the required memory for the concatenation of all strings. This reduces the work that needs to be done within the loop. Interestingly, when joining a []string slice with fewer than 4 elements, the function resorts to using the + operator to concatenate the strings.
Conclusion: Simple syntax but not quite as nice as + operator, most efficient approach for joining two strings, inefficient inside a loop.
Custom Concatenation Function
strings.Join is pretty fast but I wanted to see how efficiently I could write a concatenation function myself. I did this before looking at the approach used in the standard library.
My working assumption was that memory writes are cheap and memory allocation is expensive. I wanted to avoid the pitfalls of the + operator by allocating memory once and then iterating through my slice of strings, adding each to my target string.
There is one gotcha. “In Go, a string is in effect a read-only slice of bytes (src).” Strings are immutable. To get around this, I used []byte slice during concatenation and then cast to a string on return.
Here is my initial approach:
- Compute the length of the final string
- Create a
bytes.Bufferlong enough to hold the final string - Loop through the arguments and:
- write the argument into the
bytes.Buffer - write the separator into the
bytes.Buffer
- write the argument into the
- Read the contents of
bytes.Bufferby using theString()method - Return the resulting string
// Custom takes a slice of strings and returns a string containing the space
// separated values. It uses custom code to join the strings.
func custom(args []string, s string) string {
var l int
for i := range args {
l += len(args[i])
}
l += len(s) * (len(args) - 1)
b := bytes.Buffer{}
b.Grow(l)
for i := range args {
b.WriteString(args[i])
if i == len(args)-1 {
break
}
b.WriteString(s)
}
return b.String()
}
My expectation was that this approach required a single memory allocation. Performance should be comparable to the functions in the standard library.
$ go test -bench=. -benchmem -run=^
goos: darwin
goarch: amd64
pkg: ../ex1.3
BenchmarkConcat-8 200000 6053 ns/op 14912 B/op 99 allocs/op
BenchmarkJoin-8 2000000 875 ns/op 640 B/op 2 allocs/op
BenchmarkCustom-8 1000000 1500 ns/op 752 B/op 3 allocs/op
This wasn’t bad for a first attempt, but why was I seeing three allocations when I was expecting only one?
It turns out that what is happening behind the scenes is that Buffer.String() makes a copy of the underlying data and in the process performs another memory allocation.
These issues explain additional allocation and the introduction of the strings.Builder type to avoid this. Change List 74931 was included in Go 1.10. For a more concise summary see The State of Go by Francec Campoy.
The strings.Builder is intended to be a drop-in replacement for bytes.Buffer. A quick comparison between the String() method on both the Buffer and the Builder shows one of the key changes.
// String returns the contents of the unread portion of the buffer
// as a string. If the Buffer is a nil pointer, it returns "<nil>".
//
// To build strings more efficiently, see the strings.Builder type.
func (b *Buffer) String() string {
if b == nil {
// Special case, useful in debugging.
return "<nil>"
}
return string(b.buf[b.off:])
}
Compare this with the somewhat less readable, but more efficient approach taken for the Builder.
func (b *Builder) String() string {
return *(*string)(unsafe.Pointer(&b.buf))
}
This avoids the cast to string by utilising the fact that both string and []byte have the same headers.
I modified my function to use this new strings.Builder type.
// Custom takes a slice of strings and returns a string containing the space
// separated values. It uses custom code to join the strings.
func custom(args []string, s string) string {
var l int
for i := range args {
l += len(args[i])
}
l += len(s) * (len(args) - 1)
b := strings.Builder{}
b.Grow(l)
for i := range args {
b.WriteString(args[i])
if i == len(args)-1 {
break
}
b.WriteString(s)
}
return b.String()
}
These new benchmarks show that we are now able to better the strings.Join function by 2% or so.
$ go test -bench=. -benchmem -run=^x
goos: darwin
goarch: amd64
pkg: github.com/go-london-user-group/study-group/workspaces/billglover/exercises/01_tutorial/ex1.3
BenchmarkFormat-8 200000 10866 ns/o 1952 B/op 102 allocs/op
BenchmarkConcat-8 200000 7421 ns/op 14912 B/op 99 allocs/op
BenchmarkJoin-8 2000000 985 ns/op 640 B/op 2 allocs/op
BenchmarkCustom-8 2000000 964 ns/op 320 B/op 1 allocs/op
My Custom function now outperformed the standard library.
A Twist
Whilst writing this blog post, I realised that Go 1.12 included changes to the strings package. One of the included changes:
- Change List 132895 - simplify Join using Builder
The implementation is remarkably similar to my custom method. A couple of notable differences include the omission of error handling and the avoidance of a conditional within the loop.
Benchmarks with Go 1.12
$ go test -bench=. -benchmem -run=^x
goos: darwin
goarch: amd64
pkg: github.com/go-london-user-group/study-group/workspaces/billglover/exercises/01_tutorial/ex1.3
BenchmarkFormat-8 200000 9458 ns/op 1952 B/op 102 allocs/op
BenchmarkConcat-8 200000 7085 ns/op 14912 B/op 99 allocs/op
BenchmarkJoin-8 2000000 923 ns/op 320 B/op 1 allocs/op
BenchmarkCustom-8 2000000 960 ns/op 320 B/op 1 allocs/op
The standard library is back in front again… just.
Conclusion
String concatenation with the + operator is simple and easy to understand. The familiar syntax means this is often the default approach when joining strings. If you are only joining a couple of strings, it is still the most efficient approach.
When joining strings within a loop or when joining a large slice of strings, use strings.Join. Recent changes in the standard library mean this more efficient than ever.