recursiveiter

Overview ¶

Package recursiveiter defines an Analyzer that checks for mistakes in iterators for recursive data structures.

Analyzer recursiveiter ¶

recursiveiter: check for inefficient recursive iterators

This analyzer reports when a function that returns an iterator (iter.Seq or iter.Seq2) calls itself as the operand of a range statement, as this is inefficient.

When implementing an iterator (e.g. iter.Seq[T]) for a recursive data type such as a tree or linked list, it is tempting to recursively range over the iterator for each child element.

Here's an example of a naive iterator over a binary tree:

type tree struct {
	value       int
	left, right *tree
}

func (t *tree) All() iter.Seq[int] {
	return func(yield func(int) bool) {
		if t != nil {
			for elem := range t.left.All() { // "inefficient recursive iterator"
				if !yield(elem) {
					return
				}
			}
			if !yield(t.value) {
				return
			}
			for elem := range t.right.All() { // "inefficient recursive iterator"
				if !yield(elem) {
					return
				}
			}
		}
	}
}

Though it correctly enumerates the elements of the tree, it hides a significant performance problem--two, in fact. Consider a balanced tree of N nodes. Iterating the root node will cause All to be called once on every node of the tree. This results in a chain of nested active range-over-func statements when yield(t.value) is called on a leaf node.

The first performance problem is that each range-over-func statement must typically heap-allocate a variable, so iteration of the tree allocates as many variables as there are elements in the tree, for a total of O(N) allocations, all unnecessary.

The second problem is that each call to yield for a leaf of the tree causes each of the enclosing range loops to receive a value, which they then immediately pass on to their respective yield function. This results in a chain of log(N) dynamic yield calls per element, a total of O(N*log N) dynamic calls overall, when only O(N) are necessary.

A better implementation strategy for recursive iterators is to first define the "every" operator for your recursive data type, where every(f) reports whether an arbitrary predicate f(x) is true for every element x in the data type. For our tree, the every function would be:

func (t *tree) every(f func(int) bool) bool {
	return t == nil ||
		t.left.every(f) && f(t.value) && t.right.every(f)
}

For example, this use of the every operator prints whether every element in the tree is an even number:

even := func(x int) bool { return x&1 == 0 }
println(t.every(even))

Then the iterator can be simply expressed as a trivial wrapper around the every operator:

func (t *tree) All() iter.Seq[int] {
	return func(yield func(int) bool) {
		_ = t.every(yield)
	}
}

In effect, tree.All computes whether yield returns true for each element, short-circuiting if it ever returns false, then discards the final boolean result.

This has much better performance characteristics: it makes one dynamic call per element of the tree, and it doesn't heap-allocate anything. It is also clearer.