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
}