Using Golang Iterators for Efficiency

TL;DR In this blog post, we will see how new golang iterators¹   enables us to write efficient code. Although, we talk about iterators in golang, same argument holds for other languages as well².

Traditional Approach

Consider a hypothetical example of writing powerset function to generate all possible subsets:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// We are using slice instead of set
func PowerSet[T any](values []T) [][]T {
	if len(values) == 0 {
		return nil
	}
	results := make([][]T, 0)
	for i := 0; i < int(math.Pow(2, float64(len(values)))); i++ {
		result := make([]T, 0)
		for j := 0; j < len(values); j++ {
			if i&(1<<j) != 0 {
				result = append(result, values[j])
			}
		}
		results = append(results, result)
	}
	return results
}

What is going on here:

• Power set of an array of size n contains $2^n$ elements.
• The element at index i is added to current sequence if the $i^{th}$ bit is set.

GitHub Reference

Problem

The above function makes an assumption that clients need all results and everything at once to perform whatever actions they need to do. However, in many cases, this assumption may not be true. Examples:

• May be clients need subset of results like first 10 or 100 results.
• May be this is part of web rest api request and we are tasked to provide next 100 elements on each request.

In above scenarios, computing entire result at once not only wastes cpu resources but also utilizes excessive memory³.

Rewriting using Iterator

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func PowerSetIter[T any](values []T) iter.Seq[[]T] {
	return func(yield func([]T) bool) {
		for i := 0; i < int(math.Pow(2, float64(len(values)))); i++ {
			result := make([]T, 0)
			for j := 0; j < len(values); j++ {
				if i&(1<<j) != 0 {
					result = append(result, values[j])
				}
			}
			if !yield(result) {
				return
			}
		}
	}
}

• This function is almost identical to traditional approach except core logic is moved inside an anonymous function that is returned to caller.
• Instead of accumulating the results, we use the callback yield⁴ function on line 10 to provide the current sequence.
• If the caller doesn’t need any more values (like breaking out of loop), then yield returns false indicating that we shouldn’t be generating any more values.

Github Reference

Example Usage

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

for value := range PowerSetIter([]int{9, 50, 99}) {
    fmt.Printf("value = %v\n", value)
}

// Prints
value = []
value = [9]
value = [50]
value = [9 50]
value = [99]
value = [9 99]
value = [50 99]
value = [9 50 99]

Before 1.23 release , there was no standardized way of implementing iterators. As a result, everyone implemented them in different ways and we couldn’t iterate using for range clause.

GitHub Reference

Standard Library Examples

maps.All, maps.Keys, maps.Values are examples of functions returning an iterator rather a slice.