How to prepend a string in GoLang without plus operation?

Question

This may be a duplicate but I haven't been able to find the correct answer anywhere. How do you prepend to a string in GoLang without using + operator (which is considered slow)?

I know I can append to a string using bytes.Buffer but WriteString only appends. If I want to prepend, I'll have to write to the prefix with the string of suffix like so:

package main

import (
    "bytes"
    "fmt"
)

func main() {
    var b bytes.Buffer 
      
    b.WriteString("W") 
    b.WriteString("o") 
    b.WriteString("r") 
    b.WriteString("l") 
    b.WriteString("d") 
   
    var a bytes.Buffer
    a.WriteString("Hello ")
    a.WriteString(b.String())
  
    fmt.Println(a.String()) 
}

Is there a better way?

Did you measure? + outperforms alternatives for many cases in terms of performance and clarity. — Burak Serdar
– Burak Serdar, Commented Aug 24, 2020 at 16:13
Never base your decisions on rumored micro-optimizations. Write code to be correct, readable, and maintainable. Then benchmark it. If performance is unacceptable, profile it, and optimize what the profiler indicates has the biggest performance impact. Remember: premature optimization is the root of all evil. — Adrian
– Adrian, Commented Aug 24, 2020 at 16:40
BurakSerdar: no, I didn't. I just checked answers (including correct-marked ones). My lack of experience with Go plus my own curiosity lead to this question. Adiran: thank you for your reminder. — Viet
– Viet, Commented Aug 24, 2020 at 20:32

wasmup · Accepted Answer · 2021-09-16 01:23:25Z

9

Using the strings.Builder is the way to go, if it is on a performance critical path, otherwise a simple + is more than good; should you know the length beforehand you may use the array or slice and copy too (Thanks to @mh-cbon, and see slice-allocation-performance):

go test -benchtime=4731808x -benchmem -bench .
BenchmarkBufferArraySimplified-8  4731808   11.36 ns/op   0 B/op  0 allocs/op
BenchmarkBufferArray-8            4731808   62.19 ns/op   0 B/op  0 allocs/op
BenchmarkBuilder-8                4731808  140.7 ns/op   32 B/op  3 allocs/op
BenchmarkBuffer-8                 4731808  200.7 ns/op  128 B/op  2 allocs/op
BenchmarkByteAppend-8             4731808  223.2 ns/op   16 B/op  4 allocs/op
BenchmarkPlus-8                   4731808  226.2 ns/op   16 B/op  4 allocs/op
BenchmarkByteCopy-8               4731808  254.1 ns/op   32 B/op  5 allocs/op
BenchmarkPrepend-8                4731808  273.7 ns/op   24 B/op  5 allocs/op

Benchmark:

package main

import (
    "bytes"
    "strings"
    "testing"
)

func BenchmarkBufferArraySimplified(b *testing.B) {
    for i := 0; i < b.N; i++ {
        var y [11]byte // should you know the length beforehand
        y[6] = 'W'
        y[7] = 'o'
        y[8] = 'r'
        y[9] = 'l'
        y[10] = 'd'

        copy(y[0:], "Hello ")
        _ = string(y[:])
    }
}
func BenchmarkBufferArray(b *testing.B) {
    for i := 0; i < b.N; i++ {
        var y [11]byte
        hello := "Hello "
        n := len(hello) // should you know the length beforehand
        b := bytes.NewBuffer(y[:n])
        b.WriteString("W")
        b.WriteString("o")
        b.WriteString("r")
        b.WriteString("l")
        b.WriteString("d")

        a := bytes.NewBuffer(y[:0])
        a.WriteString(hello) // prepend
        _ = b.String()
    }
}
func BenchmarkBuilder(b *testing.B) {
    for i := 0; i < b.N; i++ {
        var b strings.Builder
        b.WriteString("W")
        b.WriteString("o")
        b.WriteString("r")
        b.WriteString("l")
        b.WriteString("d")

        var a strings.Builder
        a.WriteString("Hello ") // prepend
        a.WriteString(b.String())
        _ = a.String()
    }
}
func BenchmarkBuffer(b *testing.B) {
    for i := 0; i < b.N; i++ {
        var b bytes.Buffer
        b.WriteString("W")
        b.WriteString("o")
        b.WriteString("r")
        b.WriteString("l")
        b.WriteString("d")

        var a bytes.Buffer
        a.WriteString("Hello ") // prepend
        a.WriteString(b.String())
        _ = a.String()
    }
}
func BenchmarkByteAppend(b *testing.B) {
    for i := 0; i < b.N; i++ {
        b := "W"
        b += "o"
        b += "r"
        b += "l"
        b += "d"

        _ = ByteAppend("Hello ", b) // prepend
    }
}
func ByteAppend(a, b string) string {
    return string(append([]byte(a), []byte(b)...)) // a+b
}
func BenchmarkPlus(b *testing.B) {
    for i := 0; i < b.N; i++ {
        b := "W"
        b += "o"
        b += "r"
        b += "l"
        b += "d"

        _ = "Hello " + b // prepend
    }
}
func BenchmarkByteCopy(b *testing.B) {
    for i := 0; i < b.N; i++ {
        b := "W"
        b += "o"
        b += "r"
        b += "l"
        b += "d"

        _ = byteCopy("Hello ", b) // prepend
    }
}
func byteCopy(a, b string) string {
    c := make([]byte, len(a)+len(b))
    copy(c, a)
    copy(c[len(a):], b) // a+b
    return string(c)
}
func BenchmarkPrepend(b *testing.B) {
    for i := 0; i < b.N; i++ {
        b := " "
        b += "W"
        b += "o"
        b += "r"
        b += "l"
        b += "d"

        _ = string(prepend([]byte(b), []byte("Hello"))) // prepend
    }
}

// prepend: insert b into a at index 0:  len(a) >= len(b)
func prepend(a, b []byte) []byte {
    // if len(a) >= len(b) {
    a = append(a[:len(b)], a...) // grow
    copy(a, b)
    return a
    // }
    // return append(b, a...)
}

edited Sep 16, 2021 at 1:23

answered Aug 24, 2020 at 16:22

wasmup

16.5k6 gold badges50 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Константин Ван Over a year ago

Good to know the twice-faster alternative, but this does not answer the question. The OP’s asking for a way to prepend strings to an existing one.

user4466350 Over a year ago

if you dnt mind about thread safety, you can also do play.golang.org/p/hvM_A9VIOHj

wasmup Over a year ago

@КонстантинВан: See the new edit for prepend.

wasmup Over a year ago

@mh-cbon Thank you for the comment, See the new edit and benchmark: b := bytes.NewBuffer(y[:n]), note: You may use here y[:n] instead of y[:0] in your example

user4466350 Over a year ago

yes, i encountered some allocations using :n, so I harshly switch them all to :0. Though, i wanted to shed some light to the fact you can allocate a big chunk of memory, like var y [1024 * 1024 * 5000]byte and it also works. If the code also uses the bytes.Buffer then it can automatically grow on-demand. It is als possible to achieve automatc growth using the builtin keywords. play.golang.org/p/58CHh2mnn0_w

Patrick Riordan · Accepted Answer · 2021-11-11 16:26:14Z

I ran into a case where I needed to prepend 10,000 strings. This is a bit different then the fastest way to prepend 10 strings but hasn't been answered here yet.

TL;DR Store the 10,000 strings in []string and then use strings.StringBuilder to assemble it in reverse order.

        var strs []string
        for i := 0; i < 10000; i++ {
            strs = append(strs, "Put your string here")
        }
        var b strings.Builder
        for i := len(strs) - 1; i >= 0; i -= 1 {
            b.WriteString(strs[j])
        }

A naive approach with + used 10 gigabytes of memory + 1 second. Putting a decent amount of time into custom prepend code that fills up a buffer from the back reduced that same test case to 10mb + 2 milliseconds. But it turns out just storing every string and then using string builder achieves almost the same result with less code. (14mb 2.4 ms). Here's the benchmark results:

go test -benchtime=50x -benchmem -bench .
BenchmarkPrepend10kAddition-20                                50         971398162 ns/op        9666950277 B/op    20325 allocs/op
BenchmarkPrepend10kPrepender-20                               50           1924394 ns/op        10165544 B/op      29913 allocs/op
BenchmarkPrepend10kReorderThenStringBuilder-20                50           2436740 ns/op        14518100 B/op      19952 allocs/op

Here's the code (without the prepender class because that needs a bit more work to be public ready):

package main

import (
    "strconv"
    "strings"
    "testing"

    "github.com/stretchr/testify/assert"
)

var teststrings []string = []string{
    "Test test tses test test sets etsetsetsetsettesestsetet\n",
    "TEST TEST TEST TEST TEST EST SET ET SET EST EST SET E TSE TES T STE ET SETT\n",
    "ashkajshfksjhdfksjdhfklhjasdfkljhasdfljashdfkljahsdfkjshafdkjashdflkjhsdgkljhsdfklgjhsklfjghksdfjgkldsjfghldksjhfgkdsfjghkdsjhfgkldjsghkldsjfghdklsfgasdjhaksdhjaksdjhasdkjhfksdjhfkjashfdjldhjasfkljashdfkljsahdflkjashdfldhjasfkjsdhf\n",    "asdhakjsdhaksjdhdskajhsdajkshdkajshdkjasdkjdhasfhjadshfashdasgfkjashdgfjhsadgfjashgdfkjhasgdfkjhgasdfkjghasdfkjhgasdkjfhgasdkjghfasdkjghfasdhjfgasjkghfsadhjgfaashkajshfksjhdfksjdhfklhjasdfkljhasdfljashdfkljahsdfkjshafdkjashdflkjhsdgkljhsdfklgjhsklfjghksdfjgkldsjfghldksjhfgkdsfjghkdsjhfgkldjsghkldsjfghdklsfgasdjhaksdhjaksdjhasdkjhfksdjhfkjashfdjldhjasfkljashdfkljsahdflkjashdfldhjasfkjsdhf\n",
    "asdhakjsdhaksjdhdskajhsdajkshdkajshdkjasdkjdhasfhjadshfashdasgfkjashdgfjhsadgfjashgdfkjhasgdfkjhgasdfkjghasdfkjhgasdkjfhgasdkjghfasdkjghfasdhjfgasjkghfsadhjgfaashkajshfksjhdfksjdhfklhjasdfkljhasdfljashdfkljahsdfkjshafdkjashdflkjhsdgkljhsdfklgjhsklfjghksdfjgkldsjfghldksjhfgkdsfjghkdsjhfgkldjsghkldsjfghdklsfgasdjhaksdhjaksdjhasdkjhfksdjhfkjashfdjldhjasfkljashdfkljsahdflkjashdfldhjasfkjsdhf\n",
    "asdhakjsdhaksjdhdskajhsdajkshdkajshdkjasdkjdhasfhjadshfashdasgfkjashdgfjhsadgfjashgdfkjhasgdfkjhgasdfkjghasdfkjhgasdkjfhgasdkjghfasdkjghfasdhjfgasjkghfsadhjgfaashkajshfksjhdfksjdhfklhjasdfkljhasdfljashdfkljahsdfkjshafdkjashdflkjhsdgkljhsdfklgjhsklfjghksdfjgkldsjfghldksjhfgkdsfjghkdsjhfgkldjsghkldsjfghdklsfgasdjhaksdhjaksdjhasdkjhfksdjhfkjashfdjldhjasfkljashdfkljsahdflkjashdfldhjasfkjsdhf\n",
    "asdhakjsdhaksjdhdskajhsdajkshdkajshdkjasdkjdhasfhjadshfashdasgfkjashdgfjhsadgfjashgdfkjhasgdfkjhgasdfkjghasdfkjhgasdkjfhgasdkjghfasdkjghfasdhjfgasjkghfsadhjgfaashkajshfksjhdfksjdhfklhjasdfkljhasdfljashdfkljahsdfkjshafdkjashdflkjhsdgkljhsdfklgjhsklfjghksdfjgkldsjfghldksjhfgkdsfjghkdsjhfgkldjsghkldsjfghdklsfgasdjhaksdhjaksdjhasdkjhfksdjhfkjashfdjldhjasfkljashdfkljsahdflkjashdfldhjasfkjsdhf\n",
    "asdhakjsdhaksjdhdskajhsdajkshdkajshdkjasdkjdhasfhjadshfashdasgfkjashdgfjhsadgfjashgdfkjhasgdfkjhgasdfkjghasdfkjhgasdkjfhgasdkjghfasdkjghfasdhjfgasjkghfsadhjgfaashkajshfksjhdfksjdhfklhjasdfkljhasdfljashdfkljahsdfkjshafdkjashdflkjhsdgkljhsdfklgjhsklfjghksdfjgkldsjfghldksjhfgkdsfjghkdsjhfgkldjsghkldsjfghdklsfgasdjhaksdhjaksdjhasdkjhfksdjhfkjashfdjldhjasfkljashdfkljsahdflkjashdfldhjasfkjsdhf\n",
    "asdhakjsdhaksjdhdskajhsdajkshdkajshdkjasdkjdhasfhjadshfashdasgfkjashdgfjhsadgfjashgdfkjhasgdfkjhgasdfkjghasdfkjhgasdkjfhgasdkjghfasdkjghfasdhjfgasjkghfsadhjgfaashkajshfksjhdfksjdhfklhjasdfkljhasdfljashdfkljahsdfkjshafdkjashdflkjhsdgkljhsdfklgjhsklfjghksdfjgkldsjfghldksjhfgkdsfjghkdsjhfgkldjsghkldsjfghdklsfgasdjhaksdhjaksdjhasdkjhfksdjhfkjashfdjldhjasfkljashdfkljsahdflkjashdfldhjasfkjsdhf\n",
}

func BenchmarkPrepend10kAddition(b *testing.B) {
    for i := 0; i < b.N; i++ {
        str := ""
        for j := 0; j < 10000; j++ {
            str = (strconv.Itoa(j) + teststrings[j%4]) + str
        }
        _ = string(str)
    }
}

func BenchmarkPrepend10kPrepender(b *testing.B) {
    for i := 0; i < b.N; i++ {
        // Example using custom prepender code not included in this post
        prepender := NewStringPrepender()
        for j := 0; j < 10000; j++ {
            prepender.Prepend(strconv.Itoa(j) + teststrings[j%4])
        }
        _ = string(prepender.String())
    }
}

func BenchmarkPrepend10kReorderThenStringBuilder(b *testing.B) {
    for i := 0; i < b.N; i++ {
        // What if we have 10,000 strings and assemble them at the end?
        var strs []string
        for j := 0; j < 10000; j++ {
            strs = append(strs, strconv.Itoa(j)+teststrings[j%4])
        }
        var b strings.Builder
        for j := len(strs) - 1; j >= 0; j -= 1 {
            b.WriteString(strs[j])
        }
        _ = string(b.String())
    }
}

To generate the strings in the benchmark tests I'm using Itoa + a list of test strings. This might be unnecessary but I added them to make sure values in []string do not point to the same memory location. The randomish test strings vary the length of the strings concatenated.

Collectives™ on Stack Overflow

How to prepend a string in GoLang without plus operation?

2 Answers 2

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related