2
\$\begingroup\$

I am creating a two-dimensional array, which I am going to process later in ways similar to image MinFilter, procedural labyrinth generation, etc. -- implying using coordinates and neighbors.

Here are two ways I came up with now:

array := make([][]byte, 0, HEIGHT)
for i := 0; i < HEIGHT; i++ {
    array = append(array, bytes.Repeat([]byte{5}, WIDTH))
}


array := make([][]byte, HEIGHT)
for i := range array {
    array[i] = bytes.Repeat([]byte{5}, WIDTH)
}

They are both less straight-forward than the original Ruby code:

array = Array.new(HEIGHT){ Array.new(WIDTH){ 5 } }

But it is the first time I tried Go, so I ask you:

Which of these solutions is better?
And which is faster?
And why?

Improve this question
\$\endgroup\$

2 Answers 2

Reset to default
6
\$\begingroup\$

First, let's rewrite your code in idiomatic Go.

// For loop using a for clause
func NewRectangleF(height, width int, value byte) [][]byte {
    r := make([][]byte, 0, height)
    for i := 0; i < height; i++ {
        r = append(r, bytes.Repeat([]byte{value}, width))
    }
    return r
}

// For loop using a range clause
func NewRectangleR(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    for i := range r {
        r[i] = bytes.Repeat([]byte{value}, width)
    }
    return r
}

Then write and run some tests and benchmarks using Go 1.3.

$ go version
go version go1.3rc2 linux/amd64
$ go test -v -bench=.
=== RUN TestNewRectangle
--- PASS: TestNewRectangle (0.00 seconds)
PASS
BenchmarkNewRectangleFL5          50      38272524 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleRL5          50      38195877 ns/op     6340608 B/op       2049 allocs/op

The benchmarks are for a large rectangle ((2 * 1024) by (3 * 1024)) with an initial value of 5.

Not surprisingly, the results are the same because we are doing the same thing. The range form is clearly better because it's easier to read and easier to verify that it's correct.

Are the results fast? Here's a simple alternative basic implementation.

// Benchmark basic
func NewRectangleB(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    for i := range r {
        w := make([]byte, width)
        if value != 0 {
            for j := range w {
                w[j] = value
            }
        }
        r[i] = w
    }
    return r
}

The benchmark results:

$ go test -v -bench=. -run=!
PASS
BenchmarkNewRectangleFL5          50      38272524 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleRL5          50      38195877 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleBL5         500       5428041 ns/op     6340608 B/op       2049 allocs/op

The basic implementation looks faster; it uses about 86% less CPU time (5428041 ns/op vs. average 38234200.5 ns/op). It doesn't use the bytes.Repeat function. In Go 1.2 and Go 1.3 the bytesRepeat function looks slow.

// bytes.Repeat returns a new byte slice consisting of count copies of b.
func Repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    bp := 0
    for i := 0; i < count; i++ {
        bp += copy(nb[bp:], b)
    }
    return nb
}

Let's see if we can write an optimal version by improving the repeat function and reducing the large number of heap allocations (2049 allocs/op). Plus, since make sets the underlying array to the zero value for the type, we can make a zero initial value a special case.

func repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    if len(b) == 1 && b[0] == 0 {
        return nb
    }
    bp := copy(nb, b)
    for bp < len(nb) {
        copy(nb[bp:], nb[:bp])
        bp *= 2
    }
    return nb
}

// Benchmark optimization
func NewRectangleO(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    a := repeat([]byte{value}, height*width)
    start, end := 0, width
    for i := range r {
        r[i] = a[start:end:end]
        start, end = end, end+width
    }
    return r
}

The benchmark results:

$ go test -v -bench=. -run=!
PASS
BenchmarkNewRectangleFL5          50      38272524 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleRL5          50      38195877 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleBL5         500       5428041 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleOL5        2000       1468944 ns/op     6340608 B/op          2 allocs/op
BenchmarkNewRectangleOL0       50000         34646 ns/op       55296 B/op          2 allocs/op

The optimal implementation looks faster; it uses about 96% less CPU time (1468944 ns/op vs. average 38234200.5 ns/op) and about 99.9% less heap allocations (2 allocs/op vs. 2049 allocs/op). It's even faster for a zero initial value (34646 ns/op vs. average 38234200.5 ns/op).

We should also check that small rectangles (2 by 3 with an initial value of 5) are also reasonable.

$ go test -v -bench=.
PASS
BenchmarkNewRectangleOS5    10000000           233 ns/op          57 B/op          1 allocs/op
BenchmarkNewRectangleOS0    10000000           206 ns/op          57 B/op          1 allocs/op

Go performance is continually being improved. The version at tip, which will be released as Go 1.4, incorporates some of the optimizations in bytes.Repeat. Currently, it doesn't include the special-case optimization for a zero initial value.

// bytes.Repeat returns a new byte slice consisting of count copies of b.
func Repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    bp := copy(nb, b)
    for bp < len(nb) {
        copy(nb[bp:], nb[:bp])
        bp *= 2
    }
    return nb
}

For Go 1.4 and later versions, we can at least write:

func NewRectangle14(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    var a []byte
    if value == 0 {
        a = make([]byte, height*width)
    } else {
        a = bytes.Repeat([]byte{value}, height*width)
    }
    start, end := 0, width
    for i := range r {
        r[i] = a[start:end:end]
        start, end = end, end+width
    }
    return r
}

The results at tip for Go 1.4 are:

$ go version
go version devel +7d2e78c502ab Sat Jun 14 16:47:40 2014 +1000 linux/amd64
$ go test -v -bench=. -run=!
PASS
BenchmarkNewRectangleFL5        1000       2061854 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleRL5        1000       2054323 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleBL5         500       5276701 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleOL5        1000       1496754 ns/op     6340608 B/op          2 allocs/op
BenchmarkNewRectangleOL0       50000         32721 ns/op       55296 B/op          2 allocs/op
BenchmarkNewRectangleOS5    10000000           221 ns/op          57 B/op          1 allocs/op
BenchmarkNewRectangleOS0    10000000           194 ns/op          57 B/op          1 allocs/op
BenchmarkNewRectangle14L5       1000       1497511 ns/op     6340608 B/op          2 allocs/op
BenchmarkNewRectangle14L0       2000        803754 ns/op     6340608 B/op          2 allocs/op

The optimal implementation is still faster; it uses about 29% less CPU time (1496754 ns/op vs. average 2058088.5 ns/op) and about 99.9% less heap allocations (2 allocs/op vs. 2049 allocs/op). It's even faster for a zero initial value (32721 ns/op vs. average 2058088.5 ns/op).

In addition to the benchmarks, we could have used profiling.

File rectangle.go:

package rectangle

import (
    "bytes"
)

// For loop using a for clause
func NewRectangleF(height, width int, value byte) [][]byte {
    r := make([][]byte, 0, height)
    for i := 0; i < height; i++ {
        r = append(r, bytes.Repeat([]byte{value}, width))
    }
    return r
}

// For loop using a range clause
func NewRectangleR(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    for i := range r {
        r[i] = bytes.Repeat([]byte{value}, width)
    }
    return r
}

// Benchmark basic
func NewRectangleB(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    for i := range r {
        w := make([]byte, width)
        if value != 0 {
            for j := range w {
                w[j] = value
            }
        }
        r[i] = w
    }
    return r
}

func repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    if len(b) == 1 && b[0] == 0 {
        return nb
    }
    bp := copy(nb, b)
    for bp < len(nb) {
        copy(nb[bp:], nb[:bp])
        bp *= 2
    }
    return nb
}

// Benchmark optimization
func NewRectangleO(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    a := repeat([]byte{value}, height*width)
    start, end := 0, width
    for i := range r {
        r[i] = a[start:end:end]
        start, end = end, end+width
    }
    return r
}

// Go version tip (go1.4)
func NewRectangle14(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    var a []byte
    if value == 0 {
        a = make([]byte, height*width)
    } else {
        a = bytes.Repeat([]byte{value}, height*width)
    }
    start, end := 0, width
    for i := range r {
        r[i] = a[start:end:end]
        start, end = end, end+width
    }
    return r
}

File rectangle_test.go:

package rectangle

import (
    "fmt"
    "testing"
)

type nrFunc func(height, width int, value byte) [][]byte

func testNewRectangle(t *testing.T, nr nrFunc) {
    /*
        #!/usr/bin/env ruby
        HEIGHT = 2
        WIDTH = 3
        array = Array.new(HEIGHT){ Array.new(WIDTH){ 5 } }
        # [[5, 5, 5], [5, 5, 5]]
        print array
        print "\n"
    */
    height, width, value := 2, 3, byte(5)
    r := nr(height, width, value)
    if len(r) != height || cap(r) != height ||
        len(r[0]) != width || cap(r[0]) != width ||
        fmt.Sprintln(r) != "[[5 5 5] [5 5 5]]\n" {
        t.Error("Invalid rectangle:", r, fmt.Sprint(r))
    }
}

func TestNewRectangle(t *testing.T) {
    var tests = []nrFunc{
        NewRectangleF, NewRectangleR,
        NewRectangleB, NewRectangleO, NewRectangle14,
    }
    for _, test := range tests {
        testNewRectangle(t, test)
    }
}

var (
    smallHeight = 2
    smallWidth  = 3
    largeHeight = smallHeight * 1024
    largeWidth  = smallWidth * 1024
    zeroValue   = byte(0)
    fiveValue   = byte(5)
)

func BenchmarkNewRectangleFL5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleF(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleRL5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleR(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleBL5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleB(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleOL5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleO(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleOL0(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleO(largeHeight, smallWidth, zeroValue)
    }
    _ = r
}

func BenchmarkNewRectangleOS5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleO(smallHeight, smallWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleOS0(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleO(smallHeight, smallWidth, zeroValue)
    }
    _ = r
}

func BenchmarkNewRectangle14L5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangle14(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangle14L0(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangle14(largeHeight, largeWidth, zeroValue)
    }
    _ = r
}
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ comprehensive!! '___')b \$\endgroup\$
    – Kokizzu
    Jun 17, 2014 at 3:45
  • \$\begingroup\$ Nice work. I've got the point. In Ruby if you can use stdlib function, you use it, because it is already compiled, and the less functions you call, the faster code will be. Now I know, that it doesn't work for Go, because all that functions that you already have are written in the same Go and rewriting them for your special case makes profit unlike in Ruby. \$\endgroup\$
    – Nakilon
    Jun 18, 2014 at 11:22
2
\$\begingroup\$

In terms of speed, there will be almost no difference. Both allocate enough space up front in the slice, hence any calls to append will not perform a reallocation. That being said, I imagine that using append could potentially incur a very slight penalty as, on each call, it will likely have to perform a capacity check to see if the slice needs to be reallocated with extra space. If this was in a particularly tight loop, then perhaps this would be worth worrying about, however, given modern branch prediction, the difference is likely to be immeasurable.

Anyway, range is considered more idiomatic for Go code; it all but eliminates off-by-one errors that can be so common when using a loop index.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.