What is the correct way of using bytes.Buffer to implement Fibonacci-like string concatenation in Go?

Question

I tested simple string concatenation in Go with “+” and bytes.Buffer (both “WriteString” and “Write(bytes)”. The result shows that “+” is much slower than the other two, which makes sense.

However, when I use the three ways to implement Fibonacci-like string concatenation (i.e. a, b, ab, bab, abbab, bababbab, abbabbababbab), “+” performs the best. The sample codes and the benchmarking results are shown as follows.

String “+”

func Fibonacci(n int) string {  
    FiboResult := ""
    prev_result := "a"
    next_result := "b"
    if n == 1{  
        FiboResult = "a"
    }else if n == 2 {  
        FiboResult = "b"
    }else{
        for i := 3; i <= n; i++ {
            FiboResult = prev_result + next_result
            prev_result = next_result
            next_result = FiboResult
        }
    }   
    return FiboResult
}

bytes.Buffer (WriteString)

func Fibonacci(n int) bytes.Buffer {  
    var FiboResult bytes.Buffer
    var prev_result bytes.Buffer
    prev_result.WriteString("a")
    var next_result bytes.Buffer
    next_result.WriteString("b")
    if n == 1{  
        FiboResult.WriteString("a")
    }else if n == 2 {  
        FiboResult.WriteString("b")
    }else{
        for i := 3; i <= n; i++ {
            FiboResult.Reset()
            FiboResult.WriteString(prev_result.String())
            FiboResult.WriteString(next_result.String())
            prev_result.Reset()
            prev_result.WriteString(next_result.String())
            next_result.Reset()
            next_result.WriteString(FiboResult.String())
        }
    }   
    return FiboResult
}

the benchmarking results

I believe it is the overhead of bytes.Buffer.String() that make this happen. But I could not figure out how to use bytes.Buffer correctly in this case. Or how could I modify my code to avoid the problem? Hints, sample codes, or explanations are all appreciated. Many thanks in advance!

Answer 1

bytes.Buffer (or the newer and faster strings.Builder) wins over simple + string concatenation if you want to append "many" values, and obtain the result once in the end, because intermediate allocations are not needed compared to using + multiple times.

And you are not using bytes.Buffer this way: you just write one string into it, and you obtain its content and you reset it. That's just a roundtrip which turns out to be an overhead.

The problem here is that generating the Fibonacci string you are seeking, that requires prepending text to the buffer, not appending to it. And bytes.Buffer only supports appending to it, so using it like this is not a good fit at all.

Generating reverse with bytes.Buffer

Note that a prepend operation is basically an append operation if you generate the reverse of a string. Which means if we first would generate the reverse of the result, we could use bytes.Buffer to perform an append when otherwise a prepend would be needed. Of course the appended string would have to also be the reverse of what otherwise would be prepended.

And of course when we're done, we have to reverse the result to get what we originally wanted.

Also note that when building result in an iterative way, the successive intermediate result is the concatenation of the previous and the one before that. So to obtain the nth result, we can simply append the substring of what we already have! This is a nice optimization.

Here's how it would look like:

func FibonacciReverseBuf(n int) string {
    switch n {
    case 0:
        return ""
    case 1:
        return "a"
    case 2:
        return "b"
    }

    prev, prev2 := 1, 1

    buf := bytes.NewBufferString("ba")

    for i := 3; i < n; i++ {
        buf.Write(buf.Bytes()[:buf.Len()-prev2])
        prev2, prev = prev, prev+prev2
    }

    // Reverse
    b := buf.Bytes()
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }

    return string(b)
}

Generating reverse with []byte and append()

Also note that since we're only appending, we can just as easily use a []byte and use the builtin append() function:

func FibonacciReverse(n int) string {
    switch n {
    case 0:
        return ""
    case 1:
        return "a"
    case 2:
        return "b"
    }

    prev, prev2 := 1, 1

    b := []byte("ba")

    for i := 3; i < n; i++ {
        b = append(b, b[:len(b)-prev2]...)
        prev2, prev = prev, prev+prev2
    }

    // Reverse
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }

    return string(b)
}

Preallocating and using copy() in a single []byte

Still, using append() may cause reallocations, because we don't know how big the buffer (the result) will be. So we start with a small buffer, and append() will increase it as needed. Also append() requires slice value (slice header) assignments. And we also have to reverse the result.

A much faster solution would be to get rid of those cons.

First let's calculate how big the result will be (this is essentially calculating the Fibonacci numbers), and allocate the required byte slice in one step.

If we do so, we can do the "prepend" operations by copying parts of our buffer (which is a []byte) to specific positions. So no append(), no reallocations, no reversing.

This is how it will look like:

func Fibonacci(n int) string {
    switch n {
    case 0:
        return ""
    case 1:
        return "a"
    case 2:
        return "b"
    }

    fibs := make([]int, n)
    fibs[0], fibs[1] = 1, 1
    for i := 2; i < n; i++ {
        fibs[i] = fibs[i-1] + fibs[i-2]
    }

    l := fibs[n-1]
    b := make([]byte, l)
    b[l-2], b[l-1] = 'a', 'b'
    for i := 3; i < n; i++ {
        copy(b[l-fibs[i]:], b[l-fibs[i-2]:])
    }

    return string(b)
}

Testing the output

To test if the above functions give the result we expect them to give, we may use the following testing function:

func TestFibonacci(t *testing.T) {
    cases := []struct {
        n   int
        exp string
    }{
        {0, ""},
        {1, "a"},
        {2, "b"},
        {3, "ab"},
        {4, "bab"},
        {5, "abbab"},
        {6, "bababbab"},
        {7, "abbabbababbab"},
    }

    funcs := []struct {
        name string
        f    func(int) string
    }{
        {"FibonacciReverseBuf", FibonacciReverseBuf},
        {"FibonacciReverse", FibonacciReverse},
        {"Fibonacci", Fibonacci},
    }

    for _, c := range cases {
        for _, f := range funcs {
            if got := f.f(c.n); got != c.exp {
                t.Errorf("%s: Expected: %s, got: %s, n: %d",
                    f.name, c.exp, got, c.n)
            }
        }
    }
}

Benchmark results

Benchmarking with n = 20:

BenchmarkFibonacciReverseBuf-4   200000   10739 ns/op    18024 B/op   10 allocs/op
BenchmarkFibonacciReverse-4      100000   13208 ns/op    28864 B/op   10 allocs/op
BenchmarkFibonacci-4             500000    3383 ns/op    13728 B/op    3 allocs/op
BenchmarkPeterSO-4               300000    4417 ns/op    13568 B/op    2 allocs/op
BenchmarkPlus-4                  200000    6072 ns/op    18832 B/op   18 allocs/op
BenchmarkBuffer-4                 50000   29608 ns/op    90256 B/op   60 allocs/op

We can see that this use of bytes.Buffer was much better than yours. Still, using concatenation was faster, because there aren't many concatenations here, they are small ones, and that doesn't require reversing in the end.

On the other hand my Fibonacci() solution outperformed all other presented solutions.