SORTING STRINGS IN GO, FAST & SLOW

In Go 1.21, the slices package got added to the Go standard library. It provides generic functions for working with slices of any type. For example, one may sort a []string using sort.Strings before Go 1.21. Now, we can use slices.Sort which is generic and according to the documentation also faster:

// Strings sorts a slice of strings in increasing order.
//
// Note: consider using the newer slices.Sort function,
// which runs faster.
func Strings(x []string) { Sort(StringSlice(x)) }

So, by replacing sort.Strings with slices.Sort performance decreases by 38%.^[1] Wait, what?!

goos: darwin
goarch: arm64
pkg: aead.dev/sort
            │ /tmp/before.txt │           /tmp/after.txt           │
            │     sec/op      │   sec/op     vs base               │
Sort_1000-8       7.195µ ± 3%   9.991µ ± 4%  +38.87% (p=0.002 n=6)

Similarly, slices.SortFunc is also slower than the sort package. Combined with strings.Compare, the performance drops by about 33%, and with cmp.Compare, sorting is more than twice as slow (156%). What is going on?

One might think that sort.Strings is specially optimized for sorting strings, while the generic counterparts are, well, generic implementations. However, this is not the case. The difference between the sort and the slices package is that sort uses a Less(i, j int) bool function for comparison, while slices uses a Cmp func(a,b T) int. But sorting an []int with the slices package is about 70% faster than the sort package. So, how is it possible that sorting numbers is faster, but sorting strings is slower?

Well, let's take a look at the implementation of strings.Compare:

1
func Compare(a, b string) int {
2
    // NOTE(rsc): This function does NOT call the runtime cmpstring
7
    // If performance is important, the compiler should be changed
8
    // to recognize the pattern so that all code doing three-way
9
    // comparisons, not just code using strings.Compare, can benefit.
10
    if a == b {
11
       return 0
12
    }
13
    if a < b {
14
       return -1
15
    }
16
    return +1
17
}

func (x StringSlice) Less(i, j int) bool { return x[i] < x[j] }

This is it^[2]. The three-way string comparison may compare two strings twice while the sort package compares two strings only once and the compiler is not smart enough (yet) to replace this pattern with a single function call.^[3]

This also explains cmp.Compare being even slower because it compares two strings at least three times and up to four times in the worst case.

However, if all of this is true, then sorting a slice containing only identical strings with sort.Strings should be about as fast as sorting with slices.SortFunc using strings.Compare.

goos: darwin
goarch: arm64
pkg: aead.dev/sort
            │ /tmp/before_equal.txt │       /tmp/after_equal.txt        │
            │        sec/op         │   sec/op     vs base              │
Sort_1000-8             5.673µ ± 0%   5.910µ ± 3%  +4.18% (p=0.002 n=6)

Similarly, checking if two slices are sorted should not depend on the sorting implementation. You just compare whether the current element is smaller, or greater depending on the sort order, than the previous element. Now, verifying whether a []string is sorted is slower using the slices package^[4].

goos: darwin
goarch: arm64
pkg: aead.dev/sort
            │ /tmp/sort.txt │          /tmp/slices.txt           │
            │    sec/op     │   sec/op     vs base               │
Sort_1000-8     6.909µ ± 8%   9.573µ ± 2%  +38.56% (p=0.002 n=6)

But now, what? Do we stop using the slices package for sorting? No. First of all, the slices package is faster than the sort package, for example, when sorting numbers. It is just slower when sorting strings until go/issues/61725 is fixed. Also, most of the time, sorting is not part of performance-critical paths. Don't optimize prematurely. However, if sorting strings is in a hot path, then switching to the slices package, e.g., because documentation advised to do so, could cause a performance regression.

1. The micro benchmark for comparing sort.Strings and slices.Sort.

   1
   func BenchmarkSort_1000(b *testing.B) {
   2
        const N = 1000
   3
        items := make([]string, N)
   4
        for i := range items {
   5
            items[i] = strings.Repeat("a", 100) + strconv.Itoa(i)
   6
        }
   7
   
   8
        b.ResetTimer()
   9
        for i := 0; i < b.N; i++ {
   10
            // slices.Sort(items)
   11
            // slices.SortFunc(items, strings.Compare)
   12
            // slices.SortFunc(items, cmp.Compare)
   13
            sort.Strings(items)
   14
        }
   15
   }
   

2. In fact, slices.Sort does not call strings.Compare but it performs the same three-way comparsion.

3. In contrast to strings.Compare, the bytes.Compare function compares all elements at most once. So, comparing two strings, represented as []byte, is faster than using strings.Compare. However, this is offset by the fact that converting a string to a []byte slice performs a memory allocation. Hence, dynamically converting strings to []bytes for comparison is slower overall.

4. The micro benchmark for comparing sort.StringsAreSorted and slices.IsSorted.

   1
   func BenchmarkIsSorted_1000(b *testing.B) {
   2
       const N = 1000
   3
       items := make([]string, N)
   4
       for i := range items {
   5
           items[i] = strings.Repeat("a", 100) + strconv.Itoa(i)
   6
       }
   7
       slices.Sort(items)
   8
   
   9
       b.ResetTimer()
   10
       for i := 0; i < b.N; i++ {
   11
           // slices.IsSorted(items)
   12
           sort.StringsAreSorted(items)
   13
       }
   14
   }