Archive for July, 2010

A more complete design

July 28, 2010

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.

Optimizing Range Iteration, Part 2

July 28, 2010

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.

Optimizing Range Iteration

July 28, 2010

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.

Vector.pm working again

July 24, 2010

I went to announce on #perl6 that I had Last of the Careless Men’s Vector class running on modern Rakudo (finally), and literally in the middle of typing the announcement there was a massive net spasm of some sort and I was kicked off the channel. Sigh.

Anyway, thanks to a timely patch from jnthn++ and a bit of rearranging things on my part, Vector.pm works again, or at least passes all the current tests in its 01-basic.t. I will try to get the rest of the code in that package working again in time for R*. The only major caveat at this point is that the op= metaoperator does not work for the Vector-specific operators. Apparently this is because of a known bug.

Fun with series

July 20, 2010

On #perl6 this morning, rokoteko was curious about doing Taylor series in Perl 6. This sort of thing fascinates me, so I quickly coded up this:

sub sine-power($x) { 
    my $sign = 1; 
    gather for 1, 3 ... * -> $n { 
        take $sign * $x ** $n / [*] (1 ... $n); 
        $sign *= -1; 
    } 
}

That works, and is pretty straightforward. However, it’s got one big glitch in it, IMO. Even if you feed it a Rat input, it will always return a list of Nums, because $x ** $n returns a Num. (Hmmm…. might that be worth changing?)

No problem, you just need to complicate the function a bit by keeping running products for the numerator and denominator:

sub sine-power($x) { 
    my $sign = 1;
    my $x-part = $x;
    my $denom = 1;
    gather for 3, 5 ... * -> $n {
        take $sign * $x-part / $denom;
        $sign *= -1;
        $x-part *= $x * $x;
        $denom *= $n * ($n - 1);
    } 
} 

As a bonus, the new version should be faster.

Let’s see if it works:

> say sine-power(0.1).munch(4).perl;
(1/10, -1/6000, 1/12000000, -1.98412698412698e-11)

> say ([+] sine-power(0.1).munch(3)).perl;
1198001/12000000

> say [+] sine-power(0.1).munch(3);
0.0998334166666667

say sin(0.1);
0.0998334166468282

As you can see, this generates a Rat approximation for sin(0.1) which is accurate to 10 decimal places. Not bad!

rand and srand

July 16, 2010

This morning I bit the bullet and revamped srand and rand. srand now takes a Real argument, as per the spec, though it casts it to Int internally. There is also a new version of srand which takes an Any argument and numifies it before calling srand again.

The rand method was worked over to make it work like the other Real methods do now: there’s a Cool version that numifies its argument and calls the rand method on that, a Real version that calls .Bridge on its argument and calls the rand method on that, and a Num version that does the actual work. I also updated the spec to include the rand method, since both the spectests and Rakudo used it, and it seemed to fit with our current way of doing things pretty well.

I’m spectesting these changes as we speak. Assuming no further issues — well, I think I need a little patch to make sure calling srand or rand on a Complex doesn’t cause an infinite loop — I believe the only work remaining for the numeric grant is to tweak the spec a bit to talk about what is expected from Numeric and Real objects in terms of available operators. As always, thanks to The Perl Foundation and Ian Hague for supporting this work.

Trig Tests

July 14, 2010

Overhauling the trig tests turned out to be much more epic than I had intended. Guess that’s one of the hazards of writing the test generating code in Perl 6 while Rakudo is still under heavy development.

The old test code was very, very thorough in testing each configuration. Basically, we looped through a list of angles, and tested each angle with every possible way it could be called for each type we wanted to test. So say the angle is 45 degrees. Then for the Num type, we’d call 45.Num.sin(Degrees), sin(45.Num, Degrees), and sin(:x(45.Num), Degrees), and then we’d call the same for the equivalent of 45 in Radians, Gradians, and Circles. Then we’d start it all over again using Rat instead of Num. And so on and so forth.

In practice, any implementation is likely to redispatch the trig functions to two basic sets of methods, one for reals and one for complex. So that’s exactly what the tests do now (leaving out the complex case because it is long:

for TrigTest::cosines() -> $angle
{
    my $desired-result = $angle.result;

    # Num.cos tests -- very thorough
    is_approx($angle.num(Radians).cos, $desired-result, 
              "Num.cos - {$angle.num(Radians)} default");
    for TrigTest::official_bases() -> $base {
        is_approx($angle.num($base).cos($base), $desired-result, 
                  "Num.cos - {$angle.num($base)} $base");
    }
}

Then, instead of trying to exhaustively test the rest of the cases, we try to generate one test for each case, and leave it at that. For instance, here’s the Rat tests for cos:

# Rat tests
is_approx((-0.785398163404734).Rat(1e-9).cos, 0.707106781186548, "Rat.cos - -0.785398163404734");
is_approx((0).Rat(1e-9).cos(Circles), 1, "Rat.cos(Circles) - 0");
is_approx((0.785398163404734).Rat(1e-9).cos(:base(Radians)), 0.707106781186548, "Rat.cos(:base(Radians)) - 0.785398163404734");
is_approx(cos((1.57079632680947).Rat(1e-9)), 0, "cos(Rat) - 1.57079632680947");
is_approx(cos((135).Rat(1e-9), Degrees), -0.707106781186548, "cos(Rat, Degrees) - 135");
is_approx(cos(:x((3.14159265361894).Rat(1e-9))), -1, "cos(:x(Rat)) - 3.14159265361894");
is_approx(cos(:x((250).Rat(1e-9)), :base(Gradians)), -0.707106781186548, "cos(:x(Rat), :base(Gradians)) - 250");

The use of .Rat(1e-9) is to ensure we have a Rat argument — longer decimal numbers may become Nums otherwise. This tests an additional case (Rat.cos(:base(Radians))) that was never actually tested before. Despite that, the number of Rat tests overall goes from something like 160 to 7.

That’s good, because I added three more types to be tested. Two represent generic Cool types: Str and NotComplex. Str is used to test real numbers in a non-Numeric Cool type. NotComplex is a non-Numeric Cool type which returns a Complex which you call .Numeric on it. The final type, DifferentReal, is a Real type which is not built-in.

Much to my surprise, I actually turned up a couple of bugs in Rakudo’s trig implementation when I tried this testing approach with atan2, the oddball trig function which normally takes two real arguments. First, we were not being generous enough on what the second argument would accept, which was easily corrected. Second, our fake enum standing in for TrigBase looks exactly like an Int to Rakudo. So 2.atan2(Degrees) is indistinguishable from 2.atan2(1), which is definitely not what the user wants. Luckily that’s a pretty silly way to call atan2 anyway.

The process of getting this to work turned up a few Rakudo bugs in the non-trig code, which have been reported. I won’t go into the details here.

By my reckoning, this means there is only one thing left on my list for the numeric grant, srand and rand. I will try to finish them off tomorrow. Thanks to The Perl Foundation and Ian Hague for supporting this work.

Off the map

July 3, 2010

I’m heading off on a nine day fishing vacation tomorrow morning. I’m hauling along my laptop, and I’m planning on getting some Rakudo hacking in. Things I’m hoping to do:

  • Finish the trig test overhaul (now that we have reasonable precision for decimal numbers).
  • Figure out what (if anything) needs to be done to rand and srand.
  • Move as much as possible of the improved decimal number code to compile-time.

Other things I’ll look at if I get the chance:

  • Getting LastOfTheCarelessMen’s ABC module working under current Rakudo. (The tests aren’t going to pass until the ABC::Blah syntax works in regexes, but the core of the module should still work, as far as I know.)
  • Messing around with a memoize sub. (Okay, this should be done with the “is cached” property in the long run.)
  • Look at the recent changes in the Hyper spec. (I don’t recall what the story is, but at the time I noted something needed to be changed in the code.)

I hope everyone has a happy and productive week while I am gone! I can’t imagine how much is going to get done in that time at the Rakudo team’s current rate…


Follow

Get every new post delivered to your Inbox.