Built-in append vs bytes.grow

[Alexei Sholik]

A friend has shared with me this blogpost -- http://atotto.hatenadiary.jp/entry/2013/04/26/202701

Don't try to read it, just look at the code. It compares appending "a" to a string 1000 times and shows that using bytes.Buffer with WriteString is faster.

I decided to also benchmark built-in append function with byte slices and it turned out the fastest -- https://gist.github.com/alco/5481475 (disregard the VeryGood version).

Looking at the code for bytes.grow(), I see that it simply grows the slice to twice its previous size -- http://golang.org/src/pkg/bytes/buffer.go?s=3749:3806#L80. Allegedly, that's the same thing the built-in append does, as per the Effective Go document.

Can anyone shed some light as to why bytes.grow() is slower by an order of magnitude?

--
Best regards
Alexei Sholik

[Alexei Sholik]

Digging into the slice code, I see that both slices and strings use very similar code for append (both call to the same growslice1 function) http://code.google.com/p/go/source/browse/src/pkg/runtime/slice.c#134

Yet, the performance of doing str += "a" is atrocious. Can't think of a way to explain this either.

[Dave Cheney]

A string is immutable, so every loop you are adding a string to a
string ("a" is a string, 'a' is a rune, but you cannot directly append
a rune to a string), copying both into a new allocation.

> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[andrey mirtchovski]

hopefully this will give you an idea how to start answering the question yourself:

http://play.golang.org/p/xbGN7DfK8B

what i see in the profiles is that append is a much shorter and better optimized codepath.

[Alexei Sholik]

Thanks Dave, Andrey,

I was going to profile it in more detail when I have some spare time. Just thought someone might have a basic explanation for this off the top of their mind.

Conceptually, bytes.grow works similarly to growslice1 -- allocate a new slice that is twice the size and copy the data into it. But the built-in append better handles adding a few bytes by not calling memmove. This is what puzzles me -- is the overhead of memmove that big that doing *p++ = *q++ in a loop is more efficient? Why is it so? Does memcpy introduce similar overhead?