Faster sorting with Go generics - Eli Bendersky's website

Generic sorting in Go: where the speed comes from

Go 1.18's generics added a new family of sorting functions to golang.org/x/exp/slices. Beyond the more ergonomic API—no more implementing sort.Interface—these functions also run faster than their counterparts in the sort package, even though the underlying algorithms are identical. The performance gap comes from how generics are implemented in the Go compiler, not from any algorithmic trickery.

To isolate the difference, we can strip away the standard library specifics and compare two implementations of the same simple sort. Bubble sort is a clean test case: it does O(N²) comparisons, and the inner loop's behavior dominates everything else.

Interface-based bubble sort

The classic generics-free approach relies on sort.Interface, which requires three methods: Len, Less, and Swap. The standard library provides adapters like sort.StringSlice so you can sort a []string with:

sort.Sort(sort.StringSlice(ss))

The sort loop itself never touches the elements directly; every comparison and swap goes through interface method calls. That abstraction is the key cost.

Generic bubble sort

The generic version looks nearly identical, but the type parameter is constrained to constraints.Ordered, so the function can use < directly on elements and swap them with Go's multiple-assignment syntax. No interface methods are involved.

Benchmarking the two on a randomly generated slice of 1000 strings shows the generic version is over 20% faster. Why?

Where the time goes in the interface version

CPU profiling of the interface-based sort shows the inner loop spends nearly all its time in comparisons—specifically in the dispatch to Less. Calling an interface method requires loading the type's itab and method offset, then jumping to the implementation. For a slice of strings, that implementation is sort.StringSlice.Less, which contains bounds-check instructions at the entry and ultimately calls runtime.cmpstring for the actual work.

The bounds checks matter. The compiler cannot eliminate them because Less is a standalone method that receives arbitrary indices; nothing at the call site tells the compiler the indices are safe. And because the call is through an interface, there's no inlining across the boundary.

How Go 1.18 generics compile

The design decision for Go generics sits between two extremes: C++-style monomorphization (fast code, slow compile, large binaries) and Java-style boxing (simple compiler, slow execution). Go 1.18 takes a middle path called GC shape stenciling.

The compiler groups types by their "GC shape"—a coarse classification based on underlying type. Distinct underlying types like int and string each get their own generated function with the type hard-coded. Pointer types all share a single shape, so those instantiations resort to dictionaries and dynamic dispatch. This is a Go 1.18 implementation detail and likely to evolve.

Why the generic string sort is faster

With the generic bubble sort on strings, the compiler emits a stenciled function for the string GC shape. Profiling shows the inner loop calls runtime.cmpstring directly—no itab lookup, no method indirection.

More importantly, the bounds checks disappear. The loop is:

for i := 1; i < len(x); i++ {
    if x[i] < x[i-1] {
        x[i-1], x[i] = x[i], x[i-1]
    }
}

The compiler's bounds-check elimination pass can prove x[i] and x[i-1] are always in range: i is constrained to [1, len(x)) by the loop structure and is never modified in the body. In the interface version, Less is a separate function receiving arbitrary indices, so the same proof is impossible. Devirtualization could theoretically help, but it does not kick in here.

Sorting with a custom comparison function

The slices package also offers a SortFunc variant that takes an explicit comparison function instead of relying on constraints.Ordered. A bubble sort built this way:

func bubbleSortFunc[T any](x []T, less func(a, b T) bool) { ... }

lands between the other two versions in benchmarks—about 14% slower than the fully generic <-based sort but 10% faster than the interface-based one.

The assembly explains the middle ground. The element access happens in the function's own body, so bounds-check elimination applies. But each comparison still goes through an indirect call to the passed-in less function — that call overhead is not eliminated.

This matters in practice: SortFunc is the more general API in slices since it works for any type, not just Ordered ones. It still beats the old sort.Sort on speed.

For pointer types, the picture differs. Go 1.18 groups all pointers into one GC shape, so generics on pointer types fall back to dictionary-based dispatch. The pointer versions run somewhat slower than fully stenciled types, though bounds-check elimination still provides a partial win. Sorting a large slice of integers with the generic function shows a far larger speedup than strings; the Less method for integers does nontrivial work that benefits proportionally more from removal of the dispatch and bounds overhead.

Generics Are Still Warming Up

A few weeks before this post was finalized, the Planetscale team published an analysis of cases where converting monomorphized code to generics produced significant slowdowns. It’s a solid piece of work, and the inline disassembly views are especially nice. The short version: Go’s generics are not a zero-cost abstraction in every path.

That shouldn’t surprise anyone who has watched the feature land. Go 1.18’s generics shipped two weeks prior to that write-up. The first implementation was built for correctness, with a lot of effort going into tricky corner cases. Performance optimization was explicitly deferred to later iterations.

That work is already underway. A change slated for Go 1.19 addresses some of the specific slowdowns the Planetscale article identified. Still, it’s unlikely generics will ever be completely free in all scenarios. Fast compilation and small binaries are core Go values, and those priorities force tradeoffs in any generics design. The compiler has to pick its battles.

The practical takeaway: benchmark your own code, not someone else’s benchmarks. Generics are brand new, and the implementation is changing quickly. Try them in your hot paths, inspect the generated assembly when something feels off, and file issues for both correctness bugs and performance regressions. The rough edges you find now are exactly the ones the team needs to smooth out next.