main body (of a book)
Recently, I had the opportunity to use generics in a real Golang scenario while looking for functions equivalent to Stream filter(Predicate<? super T> predicate) and Python list comprehension equivalents. Instead of relying on existing packages, I chose to write my own filter function for learning purposes.
func filterStrings(collection []string, test func(string) bool) (f []string) {
for _, s := range collection {
if test(s) {
f = append(f, s)
}
}
return
}
However, this only works for strings. If I need to filter a collection of integers, then I need another extremely similar function.
This seems like a perfect choice for a paradigm function.
func filter[T any](collection []T, test func(T) bool) (f []T) {
for _, e := range collection {
if test(e) {
f = append(f, e)
}
}
return
}
Analyzing the (few) differences between typed and paradigm versions
- The name of the function is followed by the definition of a paradigm T .
- T is defined as any type.
- The type of the element in the input slice changes from a string to T
- The input and output clice types have also changed from strings to T
Without further ado, let's write some unit tests. First, I need a generator for a random collection (in my case, strings).
func generateStringCollection(size, strLen int) []string {
var collection []string
for i := 0; i < size; i++ {
collection = append(collection, (("%c", rune('A'+(i%10))), strLen))
}
return collection
}
Now I can write a test case that determines that thefilterStrings The output of the function is the same as the output of my filter paradigm maker.
func TestFilter(t *) {
c := generateStringCollection(1000, 3)
("the output of the typed and generic functions is the same", func(t *) {
predicate := func(s string) bool { return s == "AAA" }
filteredStrings := filterStrings(c, predicate)
filteredElements := filter(c, predicate)
if !(filteredStrings, filteredElements) {
("the output of the two functions is not the same")
}
})
}
=== RUN TestFilter
=== RUN TestFilter/the_output_of_the_typed_and_generic_functions_is_the_same
--- PASS: TestFilter (0.00s)
--- PASS: TestFilter/the_output_of_the_typed_and_generic_functions_is_the_same (0.00s)
PASS
Consider the performance of the new function when dealing with large slice. How can I make sure it performs well even in this case?
The answer: benchmarking. Writing benchmark tests in Go is very similar to unit testing.
const (
CollectionSize = 1000
ElementSize = 3
)
func BenchmarkFilter_Typed_Copying(b *) {
c := generateStringCollection(CollectionSize, ElementSize)
("Equals to AAA", func(b *) {
for i := 0; i < ; i++ {
filterStrings(c, func(s string) bool { return s == "AAA" })
}
})
}
func BenchmarkFilter_Generics_Copying(b *) {
c := generateStringCollection(CollectionSize, ElementSize)
("Equals to AAA", func(b *) {
for i := 0; i < ; i++ {
filter(c, func(s string) bool { return s == "AAA" })
}
})
}
go test -bench=. -count=10 -benchmem goos: darwin goarch: arm64 pkg: /timliudream/go-test/generic_test BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 718408 1641 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 718148 1640 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 732939 1655 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 723036 1639 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 699075 1639 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 707232 1643 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 616422 1652 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 730702 1649 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 691488 1700 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 717043 1646 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 428851 2754 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 428437 2762 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 430444 2800 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 429314 2757 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 430938 2754 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 429795 2754 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 426714 2755 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 418152 2755 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 431739 2761 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 412221 2755 ns/op 4080 B/op 8 allocs/op PASS ok /timliudream/go-test/generic_test 25.005s
I'm not happy with the result. It looks like I traded readability for performance.
Also, I'm a little concerned about the number of allocations. Did you notice the _Copying suffix in my test name? That's because both of my filter functions are copying filtered items from the input collection to the output collection. Why do I have to take up memory for such a simple task?
At the end of the day, all I needed to do was filter the original collection. I decided to tackle that first.
func filterInPlace[T any](collection []T, test func(T) bool) []T {
var position, size = 0, len(collection)
for i := 0; i < size; i++ {
if test(collection[i]) {
collection[position] = collection[i]
position++
}
}
return collection[:position]
}
Instead of writing the filtered result to a new collection and returning it, I write the result back to the original collection and keep an extra index to "slice" through the filtered number of items.
My unit test still passes, after changing the line below.
filteredStrings := filterStrings(c, predicate) //filteredElements := filter(c, predicate) filteredElements := filterInPlace(c, predicate) // new memory-savvy function
Add another bench method
func BenchmarkFilter_Generics_InPlace(b *) {
c := generateStringCollection(CollectionSize, 3)
("Equals to AAA", func(b *) {
for i := 0; i < ; i++ {
filterInPlace(c, func(s string) bool { return s == "AAA" })
}
})
}
The results are outstanding.
go test -bench=. -benchmem goos: darwin goarch: arm64 pkg: /timliudream/go-test/generic_test BenchmarkFilter_Typed_Copying/Equals_to_AAA-8 713928 1642 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Copying/Equals_to_AAA-8 426055 2787 ns/op 4080 B/op 8 allocs/op BenchmarkFilter_Generics_Inplace/Equals_to_AAA-8 483994 2467 ns/op 0 B/op 0 allocs/op PASS ok /timliudream/go-test/generic_test 4.925s
Not only does the memory allocation go to zero, but the performance is significantly improved.
Above is the detailed content of the filtering paradigm collection performance examples in Go, more information about Go filtering paradigm collection of information please pay attention to my other related articles!