prealloc

prealloc

prealloc is a Go static analysis tool to find slice declarations that could potentially be preallocated.

Installation

go install github.com/alexkohler/prealloc@latest

Usage

Similar to other Go static analysis tools (such as golint, go vet), prealloc can be invoked with one or more filenames, directories, or packages named by its import path. Prealloc also supports the ... wildcard.

prealloc [flags] files/directories/packages

Flags

• -simple (default true) - Report preallocation suggestions only on simple loops that have no returns/breaks/continues/gotos in them. Setting this to false may increase false positives.
• -rangeloops (default true) - Report preallocation suggestions on range loops.
• -forloops (default false) - Report preallocation suggestions on for loops. This is false by default due to there generally being weirder things happening inside for loops (at least from what I've observed in the Standard Library).

Purpose

While Go does attempt to avoid reallocation by growing the capacity in advance, this sometimes isn't enough for longer slices. If the size of a slice is known at the time of its creation, it should be specified.

Consider the following benchmark: (this can be found in prealloc_test.go in this repo)

import "testing"

func BenchmarkNoPreallocate(b *testing.B) {
	existing := make([]int64, 10, 10)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		// Don't preallocate our initial slice
		var init []int64
		for _, element := range existing {
			init = append(init, element)
		}
	}
}

func BenchmarkPreallocate(b *testing.B) {
	existing := make([]int64, 10, 10)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		// Preallocate our initial slice
		init := make([]int64, 0, len(existing))
		for _, element := range existing {
			init = append(init, element)
		}
	}
}

$ go test -bench=. -benchmem
goos: linux
goarch: amd64
BenchmarkNoPreallocate-4   	 3000000	       510 ns/op	     248 B/op	       5 allocs/op
BenchmarkPreallocate-4     	20000000	       111 ns/op	      80 B/op	       1 allocs/op

As you can see, not preallocating can cause a performance hit, primarily due to Go having to reallocate the underlying array. The pattern benchmarked above is common in Go: declare a slice, then write some sort of range or for loop that appends or indexes into it. The purpose of this tool is to flag slice/loop declarations like the one in BenchmarkNoPreallocate.

Example

Some examples from the Go 1.9.2 source:

…

// cmd/api/goapi.go:301
var missing []string
for feature := range optionalSet {
	missing = append(missing, feature)
}

// cmd/fix/typecheck.go:219
var b []ast.Expr
for _, x := range a {
	b = append(b, x)
}

// net/internal/socktest/switch.go:34
var st []Stat
sw.smu.RLock()
for _, s := range sw.stats {
	ns := *s
	st = append(st, ns)
}
sw.smu.RUnlock()

// cmd/api/goapi.go:301
var missing []string
for feature := range optionalSet {
	missing = append(missing, feature)
}

Even if the size the slice is being preallocated to is small, there's still a performance gain to be had in explicitly specifying the capacity rather than leaving it up to append to discover that it needs to preallocate. Of course, preallocation doesn't need to be done everywhere. This tool's job is just to help suggest places where one should consider preallocating.

How do I fix prealloc's suggestions?

During the declaration of your slice, rather than using the zero value of the slice with var, initialize it with Go's built-in make function, passing the appropriate type and length. This length will generally be whatever you are ranging over. Fixing the examples from above would look like so:

// cmd/api/goapi.go:301
missing := make([]string, 0, len(optionalSet))
for feature := range optionalSet {
	missing = append(missing, feature)
}

// cmd/fix/typecheck.go:219
b := make([]ast.Expr, 0, len(a))
for _, x := range a {
	b = append(b, x)
}

// net/internal/socktest/switch.go:34
st := make([]Stat, 0, len(sw.stats))
sw.smu.RLock()
for _, s := range sw.stats {
	ns := *s
	st = append(st, ns)
}
sw.smu.RUnlock()

// cmd/api/goapi.go:301
missing := make ([]string, 0, len(optionalSet))
for feature := range optionalSet {
	missing = append(missing, feature)
}

Note: If performance is absolutely critical, it may be more efficient to use copy instead of append for larger slices. For reference, see the following benchmark:

func BenchmarkSize200PreallocateCopy(b *testing.B) {
	existing := make([]int64, 200, 200)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		// Preallocate our initial slice
		init := make([]int64, len(existing))
		copy(init, existing)
	}
}

$ go test -bench=. -benchmem
goos: linux
goarch: amd64
BenchmarkSize200NoPreallocate-4     	  500000	      3080 ns/op	    4088 B/op	       9 allocs/op
BenchmarkSize200Preallocate-4       	 1000000	      1163 ns/op	    1792 B/op	       1 allocs/op
BenchmarkSize200PreallocateCopy-4   	 2000000	       807 ns/op	    1792 B/op	       1 allocs/op

TODO

• Configuration on whether or not to run on test files.
• Globbing support (e.g. prealloc *.go).

Contributing

Pull requests welcome!

Other static analysis tools

If you've enjoyed prealloc, take a look at my other static analysis tools!

• nakedret - Finds naked returns.
• unimport - Finds unnecessary import aliases.