Performance comparison of Go functional stream libraries. Mario Macias' handcrafted blog

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:

	mariomac / gostream	primetalk / goio	vladimirvivien / automi	koss-null / lambda
Stars	58	52	774	114
Contributors	1	1	3	1
Generics	✅	✅	❌	✅
Parallelization	❌	✅	❌	✅

We found some 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.

Update (Dec 5th 2022)

A reader of this article kindly contributed with another library that seems to outperform by a smidgen the Gostream library, in terms of speed, with similar memory generation: github.com/kamstrup/fn.

The API looks slightly different:

func Fn(words []string) map[string]map[string]struct{} {
	wordsLower := fn.ArrayOf(words).
		Where(MoreThanOneChar).
		Shape(strings.ToLower)
	singleWords := fn.MapOf(wordsLower, SingleWordToMap)
	return fn.Into(Anagrams{}, Accumulate, singleWords)
}

In their own words:

I think the primary difference between our approaches is that you seem closer to Java Streams, and I am a bit closer to Clojure. Fx. my Seq API is designed to work on "immutable sequences", ie you get a head+tail back when you walk a Seq, and the underlying Seq is stateless. Whereas your stream lib keeps a stateful iterator.

Digging into its code, I also see another basic difference: while mariomac/gostream is designed for lazy evaluation of each stream's element, kamstrup/fn performs eager evaluation.