How slow is channel-based iteration?

We're building Go to build Dolt, the world's first and only version-controlled SQL database. The database's query execution engine uses an iterator type to spool rows between different layers of the execution stack, which looks like this:

This is a great general-purpose interface that has served us well for years, but of course we sometimes need to add an adapter layer when using libraries that use different approaches to iteration. A few weeks ago I shared a solution I came up with when I needed to adapt a b-tree library to this interface. The issue was that the library wants to iterate all elements in a range scan in a single function call, like this:

That iterator callback function gets called for every element in range in the tree. But I needed elements one at a time, once every time Next() is called on my iterator struct. My solution was to use a channel to bridge this impedance mismatch, which worked pretty well. You can read the original blog for details, or just keep reading for a summary.

I hadn't really considered the performance impact of using channels this way, since the per-item cost of iteration it was unlikely to be a major bottleneck in this part of a codebase. But several commenters pointed out that channels are pretty slow when used for iteration in this way. That got me curious: how much slower are they? And what's a better option in a case like this?

Luckily a reader was kind enough to provide just such an option, which uses the iter package introduced in Go 1.23, which we covered when it was released. Keep reading for details on that solution, which is in fact better and (spoiler) faster.

Let's talk about our experimental setup and then look at the different iterators we'll be benchmarking.

We'll use the same btree package and write several iterators over a tree. We'll seed the tree and the ranges we scan in it like this.

So the tree has 10,000 element in it, and we're going to scan randomly sized ranges of them. We're generating these ranges ahead of time in an init block so that random number generation doesn't pollute the benchmark measurement.

Now that we have a tree and ranges to scan, we'll iterate over those ranges like this:

On to the measurements.

Here's the original iterator implementation, which uses a goroutine to send values from btree.AscendRange over a channel to the next invocation of Next().

Why do I call this leakyChannelIter? After our last publication, a fan of the blog pointed out that this implementation can leak a goroutine and channel if the iterator isn't fully drained. Thanks for the bug report! We fix that issue in the next version.

Here's the bug fix for the goroutine leak.

We stop the leak by stopping iteration in the callback to AscendRange during Close(), triggered by closing a new stop channel.

This fixes the potential for a goroutine leak but comes at a price, as we'll see in a second.

Another helpful reader commented that we should be using iter.Pull method instead, which is much faster and easier. And he was right on both counts. Here's an iterator that uses iter.Pull.

This is quite a bit cleaner. It avoids starting a new goroutine, so there's no worry about leaking one. If a caller doesn't remember to clean up an iterator with Close() in the case they don't fully drain it, the channel-based iterator leaks a goroutine. The iter.Pull based iterator handles a similar concern by calling stop() in Close(), but based on a reading of the go docs I don't think this is actually necessary to avoid a leak. I would need to dig deeper to confirm this though.

Which brings up an interesting topic: why didn't this solution, which struck many people as obvious, occur immediately to me as well? My blog on the topic of range iterators is currently the #3 Google search result for the term "golang range iterators", so while I'm not an expert I certainly know more about this than most people. So why the blind spot?

Frankly I didn't see how it could be possible to accomplish this feat at all without either caching the values, or spinning up a goroutine. And I was pretty sure nothing in the iter package creates goroutines for iteration. But as it turns out, this is only mostly true. iter.Pull doesn't use goroutines, but it does use a form of coroutine. From the go source:

This is the magic that lets iter.Pull transfer control between the current goroutine's execution and the yield function: it calls coroswitch and does some fun unsafe.Pointer operations to jump between two function stacks in the same goroutine.

Pretty neat! But coroswitch is only for the go runtime and core libraries, if you try to use them the linker will refuse to build the binary.

That was a long aside. Let's look at the benchmarks for these three different implementations.

I ran the benchmark 10 times:

Then I used the benchstat tool to crunch the averages for me.

So the iter.Pull method of iteration is about 2x faster than a potentially leaky channel-based approach and over 3x faster than one that doesn't leak. It also allocates dramatically less memory.

But interestingly, while the speed advantage remains constant with smaller collections, the memory advantage actually reverses. Here's 1,000 elements:

And here's 100:

Since it's a fair bet that most readers want an iterator implementation that can't leak goroutines when used correctly (even if it's slower), we'll disregard that implementation and only compare the two safe ones. Here it is graphically, note the log scale.

The small advantage in allocations for channel-based iteration at smaller iteration sizes probably isn't worth the massive difference in speed for most applications. It's hard to say definitively until you profile on your workload, but it's clear that for most developers, using channels is a worse choice.

You can find the full code for the benchmark here if you want to play with it yourself.

The haters are right: using channels for iteration is slow. I knew this was likely to be the case, but I was surprised by how dramatic the difference is. Whether this is a deal breaker for your use case is pretty subjective, but in general I would consider it a pattern to avoid where possible.

Have a question about iteration in Go, or about Dolt? Come by our Discord and talk to our engineering team. We hope to see you there.