A more complete design

Okay, here’s what I have at the moment, which passes some basic tests. First, the quad iterator.

class FiniteIntRangeQuadIter 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 + 4;
                $!nextIter =
                    $s < $!max
                        ?? FiniteIntRangeQuadIter.new( :value($s),
                                                       :max($!max) )
                        !! EMPTY;
            } else {
                $!nextIter = EMPTY;
            }
        }
        $!value, $!value + 1, $!value + 2, $!value + 3, $!nextIter;
    }
}

For simplicity and speed, this only works if the number of iterations is divisible by four. So we need some other mechanism to handle the remaining 1-3 elements. Introducing a very simple iterator:

class ConsIter is Iterator {
    has $!value-parcel;
    has $!nextIter;

    method infinite() { $!nextIter ~~ EMPTY ?? False !! $!nextIter.infinite; }

    method reify() {
        &infix:<,>(|$!value-parcel, $!nextIter);
    }
}

This just takes a Parcel and another iterator. When you iterate it, it returns the Parcel first, then the other iterator. The reify method probably could be more efficient, but then, it should only get called once for the entire iteration. Then you just need a way to use the two iterators together:

sub MakeSmartIter($a, $b) {
    return EMPTY if ($b < $a);
    
    my $mod = ($b - $a + 1) % 4;
    if $mod == 0 {
        FiniteIntRangeQuadIter.new(:value($a), :max($b));
    } else {
        my @parcel-to-be;
        my $i;
        loop ($i = 0; $i < $mod; $i++) {
            @parcel-to-be.push($a + $i);
        }
        
        my $parcel = &infix:<,>(|@parcel-to-be);
        my $next-iter = $a + $mod < $b ?? FiniteIntRangeQuadIter.new(:value($a + $mod), 
                                                                     :max($b))
                                       !! EMPTY;
        ConsIter.new(:value-parcel($parcel), 
                     :nextIter($next-iter));
    }
}

There absolutely has to be a better way to build a Parcel, but I wasn’t able to figure it out, and this one works. Again, this code only gets called once for the entire iteration. It’s probably enough of a speed hit that it should only be used for longer lists; more timing is required to figure out where the sweet spot is to switch over. (Though come to think of it, it’s probably worth letting people more familiar with the ins and outs of Parcels go over this code a few times before trying to figure out where that sweet spot is.)

As it stands now, it takes 27.3 seconds to execute 2..10000 in Rakudo. Switching to this iterator, it takes 8.1 seconds. (Note that 2..10000 is the worst case for the slow bits of the new code; 1..10000 shaves a tenth of a second or so off the time.)

It would be fairly straightforward to convert the Range to use this code for Int iteration. The big thing at this point would be generating enough tests for it. This is the sort of code in which off-by-one errors lurk, and this would be a terrible place to let such an error creep into Rakudo.

Update: Thanks to jnthn++, the Parcel-making code is now

        my $parcel := pir::new__Ps('Parcel'); 
        my $i;
        loop ($i = 0; $i < $mod; $i++) {
             pir::push($parcel, $a + $i);
        }

That ought to be about as efficient as it can get without going entirely into PIR, I think.

About these ads

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: