Does this Go method "allocate new memory"?

user_26702 0
Viewed 383

(I'm learning Go using Donovan and Kernighan's The Go Programming Language. The answer to this will probably be painfully obvious to others, but I'm stumped and not sure where to begin.)

As an exercise in GOPL, the authors ask the reader to modify their reverse program (which reverses a slice of ints in place) "to reverse the characters of a []byte slice that represents a UTF-8 encoded string, in place" (93). They add: "Can you do it without allocating new memory?"

In a nutshell, I want to ask whether the following allocates new memory. I think that it doesn't, based on the outcome of the print statements, but I'm not sure. Another way to put my confusion is this: if the reverse method reverses in place, I would expect it not to allocate new memory. So, I'm assuming that I must be missing something because they ask for the method to work in place and then add the challenge of not allocating new memory. Are they nudging me to avoid something I've done? Is there some extra trick here worth knowing about memory allocation (in Go or in general)?

package main

import (
    "fmt"
    "unicode/utf8"
)

func main() {
    phrase := "Hello, 世界!"
    fmt.Printf("Before reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
    phrase = string(reverseByRune([]byte(phrase)))
    fmt.Printf("After reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
}

func reverseByRune(b []byte) []byte {
    for i := 0; i < len(b); {
        _, size := utf8.DecodeRune(b[i:])
        reverse(b[i : i+size])
        i += size
    }
    reverse(b)
    return b
}

func reverse(b []byte) []byte {
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }
    return b
}

Here it is on the Go Playground: https://play.golang.org/p/Qn7nYXLGoQn.

PS I can only upvote and accept once, but if anyone wants extra thanks, I'd love any links about memory allocation (especially in Go).

go memory-management
1 Answers

EDIT: Probably the implementation in the question also does not allocate memory on the heap, but the suggested modification still should be a tiny little bit more efficient. I originally thought the code in the question is from the book and has memory allocations that I can't check due to lack of local compiler.

Here is an implementation that I believe should be without memory allocation.

https://play.golang.org/p/N4mkYoiIHvn

package main

import (
    "fmt"
    "unicode/utf8"
)

func main() {
    phrase := "Hello, 世界!"
    fmt.Printf("Before reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
    phrase = string(reverseByRune([]byte(phrase)))
    fmt.Printf("After reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
}

func reverseByRune(b []byte) []byte {
    reverse := func (i, j int) {
        for ; i < j; i, j = i+1, j-1 {
            b[i], b[j] = b[j], b[i]
        }
    }
    for i := 0; i < len(b); {
        _, size := utf8.DecodeRune(b[i:])
        reverse(i, i+size-1)
        i += size
    }
    reverse(0, len(b)-1)
    return b
}

The original implementation of reverse() needs memory to create the b []byte slice and also unnecessarily returns a value. Though theoretically that could be optimized by removing return from reverse. Then a compiler can "guess" nobody can keep a pointer to the slice and can make sure the slice is created on stack instead of the heap. But this is just theoretical speculation-I'm not sure if Go's compiler is that smart.

The suggested implementation does same as the original but within the original slice.

When we talk about "no memory allocation," we usually mean what happens within a function, in this case the reverseByRune(). Local variables allocated on stack like i & j does not count as they are cheap.

And here is what probably would be the most efficient implementation for given approach:

https://play.golang.org/p/YOOSZjIWKZ_r

package main

import (
    "fmt"
    "unicode/utf8"
)

func main() {
    phrase := []byte("Hello, 世界!")
    fmt.Printf("Before reverse:\tmemory address %p => phrase: %s\n", &phrase, string(phrase))
    reverseByRune(phrase)
    fmt.Printf("After reverse:\tmemory address %p => phrase: %s\n", &phrase, string(phrase))
}

func reverseByRune(b []byte) {
    for i := 0; i < len(b); {
        _, size := utf8.DecodeRune(b[i:])
        for k, p := i, i+size-1; k < p; k, p = k+1, p-1 {
            b[k], b[p] = b[p], b[k]
        }
        i += size
    }
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }
}

But that is overkill!

user_19750860
Related