A popular standard library staple of modern languages is the iterator interface. This API abstracts the notion of stepping through a sequence of items one at a time, much like a database cursor. Unfortunately, just like database cursors, the performance can be poor for many of the same reasons. In this post I’m going to cover one such issue; a “leaky abstraction” inherent to iterators that tends to cause repeated scans of the source data when used naively.
Unlike database cursors, which are a very primitive language element in typical SQL dialects, languages such as C# or Rust provide a wonderfully rich set of extensions on top of the basic “move to next item” iterator interface.
These simplify complex code down to short snippets that are not only terse, but also more readable than the original code.
Compare the following Rust snippet:
let mut iter = IntoIterator::into_iter(iterable);
let mut t = iter.next();
loop {
match (t,iter.next()) {
(Some(m),Some(i)) if i > m => { t = i; },
(_,None) => { break; }
_ => {}
}
}
With this much terser equivalent:
let t = iterable.iter().max();
In the first snippet it may not have been immediately obvious that the maximum was being computed. The second snippet is not only shorter, it is also much more readable.
The concept of iteration is extremely abstract, and can be applied to a huge variety of things. Its use is generally fine when applied to simple iterables such as arrays and container objects, but it can also be used with high-level interfaces such as database query results or even RPC or REST API wrappers. Unfortunately, in those cases many of the extended functions ignore the potentially very high cost of repeatedly iterating through a result set or the cost of a network round-trip for each next() call.
That is, the iterator interface does not correctly abstract away the cost of iteration.
I call this the “inefficient min/max” problem, which can be best illustrated by writing out an example problematic snippet of code:
let min = container.iter().min();
let max = container.iter().max();
If the container is a small array, this is reasonably efficient. The array will be scanned twice, but it’ll probably fit in L1 cache, and in the grand scheme of things this is no big deal. If we’re lucky, the compiler will vectorise this and it’ll be probably faster than we expect anyway, and it could even be optimal if we’re very lucky.
However, as soon as the data set exceeds the last-level CPU cache and needs to be streamed into the CPU from main memory, this is irritatingly inefficient, exactly halving the throughput that could be achieved. If networking is involved, then this snippet is almost certainly worth taking the time to optimise for better efficiency… but how?
We could write an explicit loop to simultaneously compute both the minimum and maximum of an iterator. This is a straightforward variant of the verbose code snippet above, but this solution throws away the benefits those wonderfully short and readable abstractions provided by the high-level iterator interface.
Computing the minimum and maximum of a block of data is a common pattern, used for all sorts of things. We could add a combo utility function such as:
let (min,max) = container.iter().range();
This is a lot better for performance, and potentially more efficient even in the case of small arrays, but it is too specific. It solves a single, “spot problem”, ignoring all of the other situations where we may be forced to iterate twice. Even in this trivial example, it’s obvious that we may want to also compute the average at the same time:
let (min,max,sum,count) = container.iter().measure();
let average = sum / count;
This quickly becomes problematic: Not all types support comparison. Not all types support addition. The temporary accumulator value for the sum needs to be a different type than the type being summed to account for overflow. Some of the return values are optional, but the length always exists. Squeezing all of this into a single function is non-extensible and generally not a good design.
We could implement arbitrary combinations of scanning across iterators using something like the fold() function, but again this is not quite right.
The minimum and maximum functions are best implemented with a variant called fold1(), which is more efficient, but the Rust Iterator type doesn’t expose this as a public function. (The .NET IEnumerable<T> also does not have this variant.) However, computing the length is required for the average, but is best implemented using the plain fold().
Either way, we’re back to manually writing out fiddly code which is almost the same as the original for loop we were trying to get away from!
Fundamentally, the problem is that functions such as sum() consume the iterator. What they ought to do is create a future and return an iterator that can then be chained into more computations.
In Rust-like pseudocode, it might look something like the following:
let (min,iter1) = container.iter().min();
let (max,iter2) = iter2.max();
let (sum,iter3) = iter3.sum();
let (count,iter4) = iter4.count();
iter4.consume();
let average = sum.await / count.await;
let range = (min.await, max.await);
Unfortunately, the temporary “iter” variables used to glue together the chain of computation is not very ergonomic.
Ideally, it would be nice to be able to use the chained function call notation, with some sort of let bindings for “out” parameters, however Rust does not currently allow this kind of notation:
container.iter()
.min( let min )
.max( let max )
.sum( let sum )
.count( let n )
.consume();
C# does allow inline variable bindings in function out parameters, so the desired syntax could be achieved with a set of extension methods along the lines of the following:
static IEnumerable<T> Max<T>( this IEnumerable<T> iter, out ValueTask<T?> max ) { ... }
static IEnumerable<T> Min<T>( this IEnumerable<T> iter, out ValueTask<T?> min ) { ... }
static IEnumerable<T> Count<T>( this IEnumerable<T> iter, out ValueTask<int> n ) { ... }
static IEnumerable<T> Consume<T>( this IEnumerable<T> iter ) { ... }
Which would then allow usage like the following snippet:
int[] demo = { 1, 2, 3 };
demo.Max(out var max)
.Min(out var min)
.Count(out var n)
.Consume(); // or use the iterator in a foreach loop...
if (n > 0)
{
int range = max.Result - min.Result;
int avg_gap = range / n.Result;
}
One issue with the above is that it pulls in the (relatively) complex ValueTask type, which is needed because the Min, Max, and Count functions return immediately, but don’t actually produce a result until the source iterator is stepped through.
(An interesting exercise is to try and implement the “future” out type using the lightest possible weight code, with the minimum overheads.)
The dual of the Iterator interface is the Observable interface. Iterators pull, Observables push.
The C# “out” parameter snippet above is almost identical if using the .NET implementation of the Rx library, and works as-is without needing any modifications:
int[] demo = { 1, 2, 3 };
var iter = demo.ToObservable();
var max = iter.Max();
var min = iter.Min();
var sum = iter.Sum();
var n = iter.Count();
iter.Subscribe(); // Consumes the observable
There is a catch though: This exercise is about optimimum performance! The goal is to do the minimum work to compute a set of results, not wasting any CPU time unecessarily with duplication or other overheads. The aim is to have a zero cost abstraction, or very nearly so.
Unfortunately, Rx is designed for asynchronous code and hence its implementation is littered with complex control flow designed to hook into schedulers. Even a very clever compiler would have little chance of optimising the above snippet, and it almost certainly couldn’t be automatically vectorised to take advantage of AVX SIMD instrunctions.
Rust could likely optimise this much better than C#, but as of this writing there is no Reactive Extensions library implementation for it. There was at least one attempt, but it seems to have been abandoned in 2018. As expected, it makes references to mutexes and spin locks, making it much more complex than the the iterator trait, which is featherweight in comparison.
The Rx interface provides a hint of how the iterator-based interface ought to be implemented. The issue with functions such as Min/Max/Sum/Fold/Count, etc… is that they consume the iterator and they return a value only at the end. However, a much more useful construct is to provide running minimums, maximums, sums, counts, etc… This is familiar to anyone who’s ever used a spreadsheet to compute a running total column.
This is also how SQL solves the inefficient min/max issues. It is a dedicated query language designed in the era of magnetic tapes spooling from reel to reel, so of course it provides the required language elements to avoid multiple-iteration performance issues. For example, the query below will perform a single pass over the source table in practically all database engines, and may utilise indexes to reduce this to efficient lookups in some cases:
SELECT MAX(c1), MIN(c1), COUNT(*) FROM "table"
This is extremely efficient, terse, and readable. Exactly what we’re looking for! Unfortunately, no popular imperative language supports this syntax.
The snippet above has an implicit “GROUP BY”, aggregating all rows of the source table. However, sometimes we want to return the rows and simultaneously compute aggregates over the result set. To cater for this scenario, modern SQL has been extended with the new OVER() keyword:
SELECT
MAX(c1) OVER () as "max",
MIN(c1) OVER () as "min",
COUNT(*) OVER () as "n",
*
FROM "table"
Unfortunately, the query above uses a complex query plan with three passes over the source data and two joins! This is required because the output of the aggregations can’t be deferred until the end. The query engine is forced to compute them first, and then join the aggregates to each of the rows. Oops.
@@@ picture
By computing the running totals instead, the database engine can process the data in a single pass:
SELECT
MAX(c1) OVER (ORDER BY id ROWS UNBOUNDED PRECEDING) as "max",
MIN(c1) OVER (ORDER BY id ROWS UNBOUNDED PRECEDING) as "min",
COUNT(*) OVER (ORDER BY id ROWS UNBOUNDED PRECEDING) as "n",
*
FROM "table"
To be honest, this syntax is repetitive, difficult to read, and its performance is not guaranteed. Database engines may use unexpected query execution plans, particularly if the rest of the rest of the query is more complex than a simple table scan.
However, this does provide the hint of what such functions ought to look like in our ideal Iterator trait or IEnumerable interface:
// Max and Min are structs implementing Iterator with an Item
// type of (Item,Item). This is a tuple combining the running max/min
// along with the current iterated value.
fn with_max( self ) -> Max<Self> {...}
fn with_min( self ) -> Min<Self> {...}
// This then allows code like the following, which is very similar
// to how the existing enumerate() function works.
fn main() {
let container = [1,2,3,4,5,6,3,4,0,2,7,4,5];
for (n,(max,i)) in container.into_iter().with_max().enumerate() {
println!("#{}: value={}, max={}", n, i, max);
}
}
Except that the snippet above is deceptive: we can’t chain these calls! While it’s possible to chain with_max() and enumerate(), the sought-after max and min combination can’t be used together as with the example above.
Somewhat unexpectedly though, this actually compiles and runs:
for (min,(max,i)) in container.into_iter().with_max().with_min() {
println!("value={:?}, min={:?}, max={:?}", i, min, max );
}
The output however reveals the issue:
value=3, min=(3, 3), max=3
value=2, min=(3, 2), max=3
value=3, min=(3, 2), max=3
value=4, min=(3, 2), max=4
value=5, min=(3, 2), max=5
The “min” value is now a tuple, not the expected scalar value. Oops!
This is wandering into the territory of monads and functors. What we want is the ability to define a wrapper around the iterator Item type that can still be fed into one or more functions such that they can reach through the wrapper and process the underlying wrapped item, instead of processing the wrapped type.
That is, we’re converting I into (I,I) and then we would like (I,(I,I)), (I,(I,(I,I))), etc… where the rightmost “I” is the underlying iterable Item and the ones on the left are the various min/max/sum/count wrappers. Instead with the code above we’re getting (I,I) followed by ((I,I),(I,I)), which is duplicating the first wrapper into the second wrapper. Additional uses of such incorrect code will cause a rapidly growing tree of wrappers.
Yes. Absolutely! The purpose of high level languages with zero-cost abstractions is to let us have our cake and eat it too: be able to write readable, elegant, declerative code and still get optimal performance as if we were hand-tuning the machine code.
As a real-world example, consider the computation of a bounding box and centre-of-mass for a set of points in 3D space, such as stars in an astronometric survery, or a point cloud computed from sterescopic images for photogramettry. In this case, we would like to compute:
It’s entirely conceivable that the data is being streamed in from disk, far too large to fit into memory. Or we could be dealing with bucketisation or some other algorithm that provides an opaque Iterator instead of neat little arrays that fit into cache.
We’re faced with a choice: Avoid using even the most basic functions in the standard library and roll our own loop manually, or a eat a tenfold hit in our performance as we scan the data repeatedly to calculate each of the above data points!
@@@ http://lafstern.org/matt/segmented.pdf https://www.reddit.com/r/rust/comments/5ez38g/rusts_iterators_are_inefficient_and_heres_what_we/