String reverse with []rune and strings.Builder slower than same with byte array

Issue

I tried/benched three ways to reverse a string,
With Runes and in place swap. suggested multiple places like here

func ReverseWithRune(str string) string {
    runes := []rune(str)
    for i, j := len(runes)-1, 0; j < i; i, j = i-1, j+1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

With strings.Builder

func ReverseWithBuilder(str string) string {
    var ret strings.Builder
    strLen := len(str)
    ret.Grow(strLen)
    for i := strLen - 1; i >= 0; i-- {
        ret.WriteByte(str[i])
    }
    return ret.String()
}

With a byte array fill up from end of input string

func ReverseWithByteArray(str string) string {
    strLen := len(str)
    ret := make([]byte, strLen)
    for i := strLen - 1; i >= 0; i-- {
        ret[strLen-i-1] = str[i]
    }
    return string(ret)
}

I thought ReverseWithRune and ReverseWithBuilder should be faster than ReverseWithByteArray. No-copy, lesser allocations etc. But the benchmarks are other way around for small 9 or large 99999 length strings ReverseWithByteArray with byte array is always faster.

RuneArr_9-4           9545110       111.3 ns/op       16 B/op        1 allocs/op
StringBuil_9-4       24685213       40.79 ns/op       16 B/op        1 allocs/op
ByteArr_9-4          23045233       52.35 ns/op       32 B/op        2 allocs/op

Rune_99999-4             1110     1002334 ns/op   507904 B/op        2 allocs/op
StringBuil_99999-4       6679      179333 ns/op   106496 B/op        1 allocs/op
ByteArr_99999-4         12200       97876 ns/op   212992 B/op        2 allocs/op

My question is

  1. Why is rune and builder approach not faster despite lesser iterations(lenght/2) and in place etc.
  2. Obvious another, can rune/builder appraoches be improved? May be I am using them wrong here.

Details

goos: linux goarch: amd64 
cpu: Intel(R) Core(TM) i5-7200U CPU @2.50GHz 
go version: go1.19.2 linux/amd64

I tried to look into profile and it shows slicerunetostring and strings.Builder.WriteBytes the main heavy operations.
enter image description here
Bytes reverse is also large but also because it has more ops.

Solution

It is not so relevant which one is faster, since two out of three are incorrect. Only ReverseWithRune is correct.

The others manipulate the individual bytes in the string. In Go, strings are UTF-8 encoded, and this is a multibyte encoding. Characters with a codepoint outside the ASCII range are encoded using more than 1 bytes, and if you reverse them byte-by-byte, you break that character as the multibyte encoding in reverse doesn’t mean the same as in forward direction.

You can check it easily on the Go playground, use the string "Hello, 世界" that is provided in their standard example:

https://go.dev/play/p/oYfPsO-C_OR

Output:

ReverseWithByteArray ��疸� ,olleH
ReverseWithBuilder ��疸� ,olleH
ReverseWithRune 界世 ,olleH

As to why ReverseWithRune is slower: it involves creating a slice of rune (a 32-bit integer), then copying the string into it, while decoding the character boundaries from the UTF-8 encoding. Then you reverse it, and after that, allocate a new byte array, then encoding a slice of rune as UTF-8.

Answered By – Erwin Bolwidt

Answer Checked By – Robin (GoLangFix Admin)

Leave a Reply

Your email address will not be published.