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.

About these ads

3 Responses to “Optimizing Range Iteration, Part 2”

  1. Brett Diamond Says:

    Go for it! I cannot speak for everybody, but providing a 70% speed increase for a commonly used mechanism is a good thing in my book. As I see it, one of the reasons of getting Rakudo Star out the door is to show the world that Perl 6 is real and is worth the wait. To do that, it should be impressive, not just in its ability to provide new and elegant ways of addressing computational problems, but also by being able to work through those problems quickly.

    Then again, if you wait, then you can show how much work is going into Rakudo development by having the next release execute 70% faster…

  2. Perl6 fan Says:

    This seems to be orders of magnitude off. Equivalent perl 5 code
    takes 0.002 seconds.

    • colomon Says:

      Nope, the timings are right. Rakudo is slow right now. Perl 5 has had fifteen years of optimizations. Rakudo has had maybe a week’s worth so far. To the best of my knowledge, my work in the last 24 hours is the first time anyone has tried to optimize this section of Rakudo. I intend to be looking at this sort of thing a lot over the next six months…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: