gomemoryunicodereverseallocation

How to write function in Golang to reverse unicode string with only 1 alloc/op?


I need to write my own reverse.Reverse analog for unicode strings. This is my code:

func Reverse(input string) string {
    runes := []rune(input)

    var result strings.Builder
    result.Grow(len(runes))

    for i := len(runes) - 1; i >= 0; i-- {
        result.WriteRune(runes[i])
    }

    return result.String()
}

But it makes 2 allocs/op:

cpu: 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz
BenchmarkReverse
BenchmarkReverse-16       297900              7014 ns/op            1792 B/op          2 allocs/op

How to make just 1 alloc/op? I know, it's possible

And also i don't understand why result.Grow(len(runes)) makes 5 allocs/op and result.Grow(len(input)) - 1 allocs/op


Solution

  • Create a strings.Builder with the required capacity. Write runes from the source string to the builder in reverse order.

    func Reverse(str string) string {
        var result strings.Builder
        result.Grow(len(str))
        for len(str) > 0 {
            r, size := utf8.DecodeLastRuneInString(str)
            result.WriteRune(r)
            str = str[:len(str)-size]
        }
        return result.String()
    }
    

    https://go.dev/play/p/PNGmFcSTo8q


    This answer replicates the functionality in the question. I do not claim that the result is meaningful when displayed as glyphs to a human. For example, combining characters do not combine as in the original string.

    Here's a contrived example of where the reverse function is useful: An application's string keys for some set of values tend to have common prefixes and uncommon suffixes. The application can improve distribution over the space of strings by reversing the key.