Performance comparison of Go functional stream libraries
source link: https://macias.info/entry/202212020000_go_streams.md
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
With the arrival of Generics to Go 1.18, a new programming model has arrived to Go: functional stream processing. This post evaluates some current libraries providing such functionality, and compares the achieved performance in single-thread streams.
Contenders
The first contender is the mariomac/gostream library, which was created by myself. Since there aren't popular or widely used stream libraries in Go, we had to Google for a while to find the other alternatives to compare:
We found any other interesting libraries, but they are not compared here for diverse reasons:
- jucardi/go-streams
requires that all the elements in the stream implement the
comparable
constraint. The test scenario described in the next section uses maps, which do not fulfill that constraint, so it was impossible to implement it with this library. - reugn/go-streams looks as a very powerful library, but it seems to be more oriented to be connected to external services (Kafka, filesystems...) rather than general-purpose in-memory operations.
Test scenario: anagram finder
To test the performance libraries, whe choose a simple example using a few subset of operations that is common to all the libraries:
- Convert a slice to a stream
- Filter elements that match a given premise
- Map elements, transforming or converting them to another type
- Reduce the stream into a single object by aggregating all the objects
The scenario receives a slice of words and returns a map with a set of anagrams. The pseudo-code would be something like:
function Anagrams(input: []string)
Returns :Map<key: set of letters, value: list of anagrams to the key>
{
return input.ConvertToStream()
.Filter(MoreThanOneChar)
.Map(ToLowerCase)
.Map(SingleWordToMap)
.Reduce(Accumulate)
}
The implementations rely on some provided functions:
MoreThanOneChar(string) bool
returns true if the input string length is >1. This will allow us discarding empty words or words with 1 letter whose anagrams are not interesting to us.ToLowerCase(string) string
converts the input string to lower case so we avoid words with uppercase to be treated differently as their lowercase equivalent.SingleWordToMap
converts a string to a single-map entry where the key is an ordered set of the characters of the input word and the value is a 1-lengt set with the actual word.Accumulate
merges two anagrams' map into a single map: it adds the keys of the source map that are missing in the destination map, and merges the sets of the coinciding keys.
Implementations
The different implementations for the anagrams finder can be completely seen in the following repository:
https://github.com/mariomac/go-stream-benchmarks
Baseline implementation
Functional processing might come at a cost, so we also provide an iterative implementation that would act as "theoretically fastest" implementation and would give us a better perspective of the performance of the functional approaches.
func Baseline(words []string) map[string]map[string]struct{} {
var swa []Anagrams
for _, w := range words {
if !MoreThanOneChar(w) {
continue
}
swa = append(swa, SingleWordToMap(strings.ToLower(w)))
}
if len(swa) == 0 {
return nil
}
seed := swa[0]
for i := range swa[1:] {
seed = Accumulate(seed, swa[i])
}
return seed
}
mariomac/gostream
The mariomac/gostream library implements the above pseudo-code as following:
func Mariomac(words []string) map[string]map[string]struct{} {
wordStream := stream.OfSlice(words).
Filter(MoreThanOneChar).
Map(strings.ToLower)
groupedWords, _ := stream.Map(wordStream, SingleWordToMap).
Reduce(Accumulate)
return groupedWords
}
Observe that the above pseudo-code defines the whole stream pipeline in a fluent
style (the result of a method invocation is immediately invoked without storing
it into a variable). However, here we require an intermediate groupedWords
variable. The reason is a limitation in the Go generics' implementation
that prevents that a Map
method returns an element with different type of the
argument. So here we need to invoke it as a function.
primetalk/goio
primetalk/goio would implement anagram finder would be implemented as follows:
func Goio(words []string) map[string]map[string]struct{} {
wordStr := stream.FromSlice(words)
fWords := stream.Filter(wordStr, MoreThanOneChar)
lfWords := stream.Map(fWords, strings.ToLower)
swAgrs := stream.Map(lfWords, SingleWordToMap)
swAgrsSl := stream.ToSlice(swAgrs)
swArgsRs, err := io.ObtainResult(io.Continuation[[]Anagrams](swAgrsSl))
if err != nil {
panic(err)
}
return slice.Reduce(swArgsRs, Accumulate)
}
You will notice some subtle changes in the different API design decisions.
vladimirvivien/automi
vladimirvivien/automi does not
provide yet Generics' support so you will notice that at some point we need to
do a type cast. The API is clean but at the cost of potential runtime errors, since
methods accept unchecked interface{}
as argument.
func Automi(words []string) map[string]map[string]struct{} {
var res Anagrams
str := stream.New(words).
Filter(MoreThanOneChar).
Map(strings.ToLower).
Map(SingleWordToMap).
Reduce(Anagrams{}, Accumulate).
Into(collectors.Func(func(i interface{}) error {
res = i.(Anagrams)
return nil
}))
if err := <-str.Open(); err != nil {
panic(err)
}
return res
}
koss-null/lambda
And last, but not least, koss-null/lambda is providing an API that is very similar to mariomac/gostream.
func Lambda(words []string) map[string]map[string]struct{} {
wordStream := pipe.Slice(words).Parallel(1).
Filter(MoreThanOneChar).
Map(strings.ToLower)
groupedWords := pipe.Map(wordStream, SingleWordToMap).
Reduce(Accumulate)
return *groupedWords
}
Please notice that we limited the parallelization to 1 single worker, as not all the contenders implement parallelization, and this blog post compares the most common single-thread scenario (e.g. willing to keep the order of the resultant streams).
Benchmark results
We benchmarked the different implementations with Go 1.19.3 on an Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz running a Mac OS X
$ go test -benchmem -bench=. -benchtime 10s ./anafind/...
(...)
BenchmarkBaseline-12 62163 192633 ns/op 199315 B/op 2563 allocs/op
BenchmarkMariomac-12 59858 198622 ns/op 191516 B/op 2566 allocs/op
BenchmarkLambda-12 47329 257454 ns/op 243270 B/op 3812 allocs/op
BenchmarkGoio-12 17647 678838 ns/op 590703 B/op 14333 allocs/op
BenchmarkAutomi-12 28183 441176 ns/op 313544 B/op 4669 allocs/op
More graphically:
Conclusions
The tests demonstrated that mariomac/gostream is currently the most efficient functional library for functional-like in-memory stream composition. Both in terms of CPU and memory generation.
It was surprisingly near the baseline implementation. However, other dummy micro-benchmarks shown that a functional stream-based pipeline might be several times slower than a proper iterative implementation.
However, other libraries such as koss-null/lambda could beat mariomac/gostream if you enable parallelization, as this feature is not yet available in the later.
I could have missed some features improving the readability or performance of the rest of contenders, or there could be more stream-processing libraries around there that would beat any of the implementations of this blog post. In that case, feel free to leave a comment informing about them and I will do my best to update the post with the new alternatives and results.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK