Golang Release 1.21: slices - Part 2
- 11 minutes read - 2295 wordsHow to use the new package in Go standard library to sort slices efficiently.
With the release of Go 1.21, the Go standard library introduced several new features. While we’ve already discussed some of them in previous articles, in this episode, we’ll dive into more advanced enhancements. Naturally, we’ll focus on the new functions designed for sorting slices, which are part of the new slices package. This article will provide a deeper look into the implementation of these three new functions and touch on benchmarking as well.
Sort
The Sort function is the first one we’d like to explore. This implementation is built upon the enhanced
Pattern-defeating Quicksort, positioning
it as one of the best-known unstable sorting algorithms. Don’t worry; we will discuss this “instability” aspect in this
article. But first, let’s take a look at the function’s signature:
Sort function
func Sort[S ~[]E, E cmp.Ordered](x S)
As we’ve seen in some other articles, nearly all improvements in the Go standard library
are built upon generics, a feature introduced in Go version 1.18, almost
three years ago. Similar to other functions, the Sort function also expects a slice of a generic type as an argument,
where each item must adhere to the Ordered
constraint. The function doesn’t return a new value but sorts the original slice in place. Below, you’ll find some basic
examples:
Sort function examples
ints := []int{1, 2, 3, 5, 5, 7, 9}
slices.Sort(ints)
fmt.Println(ints)
// Output:
// 1 2 3 5 5 7 9
ints2 := []int{9, 7, 5, 5, 3, 2, 1}
slices.Sort(ints2)
fmt.Println(ints2)
// Output:
// 1 2 3 5 5 7 9
floats := []float64{9, 3, 5, 7, 1, 2, 5}
slices.Sort(floats)
fmt.Println(floats)
// Output:
// 1 2 3 5 5 7 9
strings := []string{"3", "9", "2", "5", "1", "7", "5"}
slices.Sort(strings)
fmt.Println(strings)
// Output:
// 1 2 3 5 5 7 9
In the example above, we can observe the result of the Sort method. All the outputs consist of sorted slices, arranged
in ascending order. However, what makes this function particularly intriguing is its ability to handle various data types
using a single function, distinguishing it from the implementations we already possess in the sort
package. Now that we’ve examined the results, let’s proceed to compare the performance benchmarks with the existing package.
Benchmark
In this section, we aim to evaluate the performance of the new function by comparing it to the already existing sort
package. Below, you’ll find the benchmark test results:
Benchmark test cases
const cases = 1000
const size = 100000
var randomInts = (func() [][]int {
var result [][]int
for i := 1; i <= cases; i++ {
result = append(result, makeRandomInts(size))
}
return result
})()
var sortedInts = (func() [][]int {
var result [][]int
for i := 1; i <= cases; i++ {
result = append(result, makeSortedInts(size))
}
return result
})()
var reversedInts = (func() [][]int {
var result [][]int
for i := 1; i <= cases; i++ {
result = append(result, makeReversedInts(size))
}
return result
})()
func makeRandomInts(n int) []int {
rand.Seed(42)
ints := make([]int, n)
for i := 0; i < n; i++ {
ints[i] = rand.Intn(n)
}
return ints
}
func makeSortedInts(n int) []int {
rand.Seed(42)
start := rand.Intn(n)
ints := make([]int, n)
for i := 0; i < n; i++ {
ints[i] = start + i
}
return ints
}
func makeReversedInts(n int) []int {
rand.Seed(42)
start := rand.Intn(n)
ints := make([]int, n)
for i := 0; i < n; i++ {
ints[i] = start - i
}
return ints
}
First and foremost, we need to create our test cases, as shown in the example above. Here, we provide three functions for
generating test cases: one with randomly distributed integers in slices, another with already sorted slices, and a third
with reversely sorted slices. It’s crucial to note that before the tests begin, we generate all the test cases. That’s
why we execute anonymous functions and store their results in global variables: randomInts, sortedInts, and reversedInts
right at the start. By creating these test cases in the beginning, we ensure that our tests use the same predefined cases.
You can find the actual test results below:
Benchmark test functions
func Benchmark_sort_RandomInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(randomInts[i%cases])
b.StartTimer()
sort.Ints(testCase)
}
}
func Benchmark_slices_RandomInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(randomInts[i%cases])
b.StartTimer()
slices.Sort(testCase)
}
}
func Benchmark_sort_SortedInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(sortedInts[i%cases])
b.StartTimer()
sort.Ints(testCase)
}
}
func Benchmark_slices_SortedInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(sortedInts[i%cases])
b.StartTimer()
slices.Sort(testCase)
}
}
func Benchmark_sort_ReversedInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(reversedInts[i%cases])
b.StartTimer()
sort.Ints(testCase)
}
}
func Benchmark_slices_ReversedInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(reversedInts[i%cases])
b.StartTimer()
slices.Sort(testCase)
}
}
// Output:
// goos: darwin
// goarch: amd64
// pkg: test
// cpu: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz
// Benchmark_sort_RandomInts
// Benchmark_sort_RandomInts-8 67 15759326 ns/op
// Benchmark_slices_RandomInts
// Benchmark_slices_RandomInts-8 141 8161744 ns/op
// Benchmark_sort_SortedInts
// Benchmark_sort_SortedInts-8 4279 349835 ns/op
// Benchmark_slices_SortedInts
// Benchmark_slices_SortedInts-8 9817 115025 ns/op
// Benchmark_sort_ReversedInts
// Benchmark_sort_ReversedInts-8 2364 454587 ns/op
// Benchmark_slices_ReversedInts
// Benchmark_slices_ReversedInts-8 6807 161754 ns/op
// PASS
You can observe the benchmarking results in the code above. In each iteration of the benchmarks, we used the test cases
generated at the beginning of the test. However, we ensured to create clones of these test cases to prevent modifying the
original ones, as all Sort functions work with slices by reference and modify the originals.
The outcome shows that, across all three groups of cases, the sorting solution from the new slices package is remarkably
2.5 times faster than the existing solution from the sort package. Personally, while I was hopeful for improved
benchmarking in the new package, I didn’t anticipate such significantly better performance compared to the sort package.
SortFunc and SortStableFunc
In this section, we will explore the SortFunc function and delve into the concept of instability introduced by this
package. Before we proceed with the explanation, let’s take a look at the function’s signature:
SortFunc function
func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int)
Similar to previous examples, the purpose of SortFunc here is to sort slices that may contain items of any type, not
necessarily belonging to the Ordered constraint. However, it’s precisely in these scenarios, where we introduce sorting
for more complex types, that we may encounter some instability, as demonstrated below:
SortFunc function example
type TestStruct struct {
Value int
Name string
}
testData := []TestStruct{
{
Value: 1,
Name: "first",
},
{
Value: 1,
Name: "second",
},
{
Value: 1,
Name: "third",
},
{
Value: 1,
Name: "four",
},
{
Value: 1,
Name: "fifth",
},
{
Value: 0,
Name: "sixth",
},
{
Value: 0,
Name: "seventh",
},
{
Value: 0,
Name: "eight",
},
{
Value: 0,
Name: "ninth",
},
{
Value: 0,
Name: "tenth",
},
{
Value: 2,
Name: "eleventh",
},
{
Value: 2,
Name: "twelfth",
},
{
Value: 2,
Name: "thirteenth",
},
{
Value: 2,
Name: "fourteenth",
},
{
Value: 2,
Name: "fifteenth",
},
}
for i := 0; i < 5; i++ {
testCase := slices.Clone(testData)
slices.SortFunc(testCase, func(a, b TestStruct) int {
return cmp.Compare(a.Value, b.Value)
})
fmt.Println(testCase)
}
// Output:
// [{0 tenth} {0 sixth} {0 seventh} {0 ninth} {0 eight} {1 fifth} {1 second} {1 four} {1 third} {1 first} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
// [{0 tenth} {0 sixth} {0 seventh} {0 ninth} {0 eight} {1 fifth} {1 second} {1 four} {1 third} {1 first} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
// [{0 tenth} {0 sixth} {0 seventh} {0 ninth} {0 eight} {1 fifth} {1 second} {1 four} {1 third} {1 first} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
// [{0 tenth} {0 sixth} {0 seventh} {0 ninth} {0 eight} {1 fifth} {1 second} {1 four} {1 third} {1 first} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
// [{0 tenth} {0 sixth} {0 seventh} {0 ninth} {0 eight} {1 fifth} {1 second} {1 four} {1 third} {1 first} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
In the example above, we introduce a custom struct named TestStruct (quite unexpected, right?). It has two attributes:
Value, which we’ll use in the comparison function to determine the item’s position in the sorted slice, and Name,
which serves as a description for tracking items’ positions in the slice after sorting, without influencing the sorting
logic itself.
For our test data, we’ve created a slice comprising fifteen items (to reveal instability, a slice should have at least
13 items). In this slice, we have three groups of values (1, 2, and 3) with item names uniquely derived from
ordered numbers (first to fifteenth). What were the results of execution? The sorting process consistently produced
the correctly sorted slice, maintaining the same order of items. However, items that were supposed to change their positions
during sorting didn’t preserve their initial order when their values were identical.
For instance, the item named sixth now appears as the second item, right after the tenth item. However, originally,
sixth was added to the original slice before tenth. This exemplifies a critical aspect of instability introduced by
SortFunc: it doesn’t randomly rearrange identical items with each execution. Instead, one slice will consistently have
the same order after sorting, but SortFunc doesn’t guarantee that identical items will retain their original ordering.
To explore how we can address this issue, let’s take a look at the signature of another function:
SortStableFunc function
func SortStableFunc[S ~[]E, E any](x S, cmp func(a, b E) int)
The signature of SortStableFunc is identical to that of SortFunc, so there’s nothing new in this regard. Let’s examine
its behavior using the exact same test case we discussed earlier:
SortStableFunc function example
// ....
for i := 0; i < 5; i++ {
testCase := slices.Clone(testData)
slices.SortStableFunc(testCase, func(a, b TestStruct) int {
return cmp.Compare(a.Value, b.Value)
})
fmt.Println(testCase)
}
// Output:
// [{0 sixth} {0 seventh} {0 eight} {0 ninth} {0 tenth} {1 first} {1 second} {1 third} {1 four} {1 fifth} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
// [{0 sixth} {0 seventh} {0 eight} {0 ninth} {0 tenth} {1 first} {1 second} {1 third} {1 four} {1 fifth} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
// [{0 sixth} {0 seventh} {0 eight} {0 ninth} {0 tenth} {1 first} {1 second} {1 third} {1 four} {1 fifth} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
// [{0 sixth} {0 seventh} {0 eight} {0 ninth} {0 tenth} {1 first} {1 second} {1 third} {1 four} {1 fifth} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
// [{0 sixth} {0 seventh} {0 eight} {0 ninth} {0 tenth} {1 first} {1 second} {1 third} {1 four} {1 fifth} {2 eleventh} {2 twelfth} {2 thirteenth} {2 fourteenth} {2 fifteenth}]
In this instance, the concept of stability becomes quite evident. Concerning values, the SortStableFunc function also
arranges items with the value 0 five times, followed by five occurrences of the value 1, and finally, five instances
of the value 2. However, what distinguishes this function is that elements with the same value maintain the same order
established during the initialization of the slice. With this function, we can anticipate the order of identical elements.
But, are there any consequences to consider? Let’s revisit the benchmark to find out.
Benchmark
To compare the performance of both functions, we’ll use the same setup as in the previous benchmark:
Benchmark test functions
func Benchmark_stable_RandomInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(randomInts[i%cases])
b.StartTimer()
slices.SortStableFunc(testCase, cmp.Compare[int])
}
}
func Benchmark_unstable_RandomInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(randomInts[i%cases])
b.StartTimer()
slices.SortFunc(testCase, cmp.Compare[int])
}
}
func Benchmark_stable_SortedInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(sortedInts[i%cases])
b.StartTimer()
slices.SortStableFunc(testCase, cmp.Compare[int])
}
}
func Benchmark_unstable_SortedInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(sortedInts[i%cases])
b.StartTimer()
slices.SortFunc(testCase, cmp.Compare[int])
}
}
func Benchmark_stable_ReversedInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(reversedInts[i%cases])
b.StartTimer()
slices.SortStableFunc(testCase, cmp.Compare[int])
}
}
func Benchmark_unstable_ReversedInts(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
testCase := slices.Clone(reversedInts[i%cases])
b.StartTimer()
slices.SortFunc(testCase, cmp.Compare[int])
}
}
// Output:
// goos: darwin
// goarch: amd64
// pkg: test
// cpu: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz
// Benchmark_stable_RandomInts
// Benchmark_stable_RandomInts-8 33 30398118 ns/op
// Benchmark_unstable_RandomInts
// Benchmark_unstable_RandomInts-8 84 13595359 ns/op
// Benchmark_stable_SortedInts
// Benchmark_stable_SortedInts-8 2229 509601 ns/op
// Benchmark_unstable_SortedInts
// Benchmark_unstable_SortedInts-8 3250 308542 ns/op
// Benchmark_stable_ReversedInts
// Benchmark_stable_ReversedInts-8 285 4087567 ns/op
// Benchmark_unstable_ReversedInts
// Benchmark_unstable_ReversedInts-8 3195 370620 ns/op
// PASS
The outcome we observed shouldn’t come as a big surprise, right? After all, why would we need unstable sorting in the first place? As seen in the benchmark results, the efficiency of unstable sorting varies depending on the case, ranging from 50% faster than the stable variant to over 10 times faster! This vividly highlights the significance of having both stable and unstable versions of the function. It also provides us with guidance on how to proceed with these functions: always opt for the unstable one if you aren’t particularly concerned about the order of identical elements.
Conclusion
New version of Golang, 1.21, delivered many new updates, affecting standard library as well. In this article we checked
how some functions from slices packages work. Those new functions give us now possibility to more efficiently sort
slices than ever before, by using the modern algorithms.
Useful Resources