Optimizing Range Iteration

I wasn’t planning on doing any more work on Rakudo before Rakudo Star, but the conversation on #phasers today got me thinking. On the one hand, I’m somewhat opposed to the idea of the Range-specific RangeIter iterator, as Range and the series operator are supposed to behave identically. On the other hand, the idea of creating a special case for RangeIter to handle the super-common Int iteration case seemed very appealing. So I thought I’d poke around a little and see what I could do.

I’m going to tell this story backwards of the way I actually did it, because I flailed around a lot at the beginning. My goal was to focus on a construct like

for 1..10000 {
   # do something 
}

But in the process of my flailing, I thought that switching from before to < made the code go slower, so I thought I might focus on that.

So here’s the first bit of code I’m going to talk about optimizing:

my $i;
loop ($i = 0; $i < 10000; $i++) {
    my $a = $i + 1;  # this line just to give the loop something to do!
}

That took 7.4 seconds to execute on my MacBook Pro. Much faster than a loop using 1..10000, but still awfully slow.

Well, < didn’t have a specific version for Int. It relied on the Real version to convert the arguments to Num and delegate to that version of <. It was very easy to code up an Int specific version of < which calls down into PIR. And with that in place, the above code runs in 4.0 seconds. So, this simple change pretty much doubles the speed of the most basic loop. (That time includes Rakudo’s start up, after all.)

So, sort of the next logical step turns out to be to look at the infinite case. Let’s look at a slightly different piece of code:

for 1..* {
    last if $_ > 10000;
}

That takes 19.1 seconds on my MBP. So, here’s a new iterator type crafted specifically for infinite Ranges:

class InfiniteIntRangeIter is Iterator {
    has $!value;
    has $!nextIter;

    method infinite() { True; }

    method reify() {
        unless $!nextIter.defined {
            $!nextIter = InfiniteIntRangeIter.new( :value($!value.succ) );
        }
        $!value, $!nextIter;
    }
}

Using that instead of the default RangeIter completes the above sample loop in 10.6 seconds.

But wait! pmichaud says iterators will be more efficient if they return more than one value at a time. Basically, the above version constructs an iterator object for each iteration. If we return two values at a time, we can cut the number of objects created in half. Seems like that ought to be a win. Here’s the new source:

class InfiniteIntRangeIter is Iterator {
    has $!value;
    has $!nextIter;

    method infinite() { True; }

    method reify() {
        unless $!nextIter.defined {
            $!nextIter = InfiniteIntRangeIter.new( :value($!value + 2) );
        }
        $!value, $!value + 1, $!nextIter;
    }
}

That’s 9.5 seconds, another 10% shaved off. Returning four values at a time gets it to 8.7 seconds. Eight gets us 8.2 seconds, and it seems like we are into diminishing returns.

But wait! The loop code uses >, which I haven’t optimized yet. Switch it to use the already optimized <, and the runtime is down to 4.8 seconds. Seems like fine progress!

This blog post is probably already too long, so I’ll stop it short here.

About these ads

One Response to “Optimizing Range Iteration”

  1. b Says:

    Hmm. I would imagine that all the iterator-calling code produces quite a lot of overhead, and that the code would run much faster if all the iterator code was inlined by the compiler and optimized until the compiled code is not much more complicated than a “for” loop written in PIR, i.e. without any calls to library functions. The last time I tested it, a simple integer loop in PIR was almost as fast as in C.

    So, the question that comes to mind is whether the compiler will be able to achieve this at some point.

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: