The standard library’s slices package includes a number of operations that take function arguments to control their behavior: SortFunc, EqualFunc, etc. These operations are flexible, but they control their behavior using function parameters, which can inhibit compiler optimizations, and they can do a lot of copying, internally and to pass slice elements to those functions by value. As a result, they can leave a lot of performance on the table.
To solve this, I wrote monoslices: a tool that generates specialized (“monomorphic”) versions of the slices.*Func operations.
monoslices is not a library. It generates code that gets checked into your project and adds no module dependencies. The generator itself is intended to be installed as a tool dependency in your project, which helps with versioning and toolchain consistency:
go get -tool github.com/zolstein/monoslices
Then, it’s invoked with:
go tool monoslices
from the CLI, or via go generate.
Instead of writing:
slices.SortFunc(records, compareRecords)
you declare compareRecords as the comparator for a generated set of operations:
func compareRecords(a, b Record) int { … }
//monoslices:generate name=Records cmp=compareRecords
and monoslices generates functions like:
func RecordsSort(s []Record)
func RecordsBinarySearch(s []Record, target Record) (int, bool)
func RecordsMin(s []Record) Record
These generated functions are based on the standard library implementations, but call compareRecords directly. As a result, the compiler has much more room to optimize.
It also supports specialization functions that receive pointers to elements instead of copies, using the byref option:
func compareRecords(a, b *Record) int { … }
//monoslices:generate name=Records cmp=compareRecords byref=true
How much this matters depends heavily on the operation and element type. Some cases already get optimized well and there’s basically no difference. But for many operations, the difference is substantial, and byref benefits even moderately sized values:
| Operation | 16 B value | 64 B by-ref | 256 B by-ref |
|---|---|---|---|
Equal |
1.6-2.0× speedup | 3.3-5.9× speedup | 3.4-10× speedup |
BinarySearch |
1.7-1.9× speedup | 1.8-2.3× speedup | 2.9-3.8× speedup |
Sort |
1.7-2.1× speedup | 3.3-4.0× speedup | 4.2-5.3× speedup |
Part of the reason I wrote this was to explore the performance impact of specialization in Go. Specialization is an important part of how languages like Rust and C++ generate efficient generic code. Generic Go code can’t specialize in all the same ways, and I wanted to see how much difference explicit specialization would make for some common Go operations.
It turns out that, at least for some of them, the difference is pretty large. I hope to see better support for this kind of optimization in Go over time, whether that’s through language changes, compiler improvements, or better codegen tooling and a culture that encourages writing code generators like this.