Optimizing Range Iteration, Part 2

So, continuing from my last post. Here’s our starting point for the third round of optimization:

for 1..10000 { 
    my $a = $_ + 1; 
}

That takes 26.5 seconds. (Note that’s already about 10s faster than before optimizing the Int comparisons.)

This requires a more complicated iterator.

class FiniteIntRangeIter is Iterator {
    has $!value;
    has $!max;
    has $!nextIter;

    method infinite() { False }

    method reify() {
        return ($!value,) if $!value ~~ EMPTY;
        unless $!nextIter.defined || $!nextIter ~~ EMPTY {
            if $!value != $!max {
                my $s = $!value.succ;
                $!nextIter =
                    $s < $!max
                        ?? FiniteIntRangeIter.new( :value($s),
                                                   :max($!max) )
                        !! EMPTY;
            } else {
                $!nextIter = EMPTY;
            }
        }
        $!value, $!nextIter;
    }
}

This is basically the current RangeIter with the non-Int bits removed as well as “excludes max” (as that is just the same as iterating to $max – 1 for Ints). Pretty straightforward, and it takes 11.6 seconds to execute.

Unfortunately, returning more than one value at a time is much more complicated for the finite case. Ooo, unless it’s not! You can write the iterator to alway go up by two, and then create a special iterator to handle the first iteration if the overall number is odd. We’re obviously getting into the realm of tricky code here. But the double iterator approach gets us to 9.5 seconds, and an even crazier quad iterator gets it to 7.8. The code is getting ugly, but it’s a big improvement over the our starting point.

What to do with this? Unfortunately, the best of the optimizations are on the tricky side, and code freeze for Rakudo Star is supposed to be in about 15 hours. I’m not terribly comfortable overhauling the Range iteration code this close to the release. On the other hand, 26.5 seconds to 7.8 seconds is a pretty big improvement. And this is a core feature that is likely to be used a lot by people trying out Rakudo for the first time.

I think I’m going to sleep on it.