Posts Tagged ‘Rakudo’

Rakudo and Speed

June 30, 2010

Saw a post / answer on Stack Overflow reporting a segmentation fault in Rakudo. Looking into it, I rewrote the code like this so it actually worked on the current build:

my %words;

for lines.split(/\s+/) { 
    %words{$_}++ 
}

for %words.pairs.sort: { $^b.value <=> $^a.value } -> $pair {
    say $pair
}

(This relies on the $*ARGFILES patch from yesterday, making lines basically the equivalent of while (<>) from Perl 5.)

That works, but takes 80 seconds to run on a 100 line source file on my MacBook Pro. That seems terribly slow. But for once, it’s only sort of the fault of Rakudo!

The first thing that made me suspicious was lines.split. lines returns a List of Str. How does .split, which takes a single Str as input, even work on that? Well, like many Cool methods, .split works on most fundamental Perl types; it just stringifies them first. So lines.split reads in the file line-by-line, then combines them into one enormous string.

So, let’s try replacing that with slurp.split, which reads the entire input into a single Str and then splits that. Errr, and immediately I run into problems — it doesn’t want to default slurp to anything. Weird, I would swear that was working a moment ago, but no matter. Replacing it with $*IN.slurp.split makes the code work drastically faster: 7.5 seconds. (Using $*IN.lines.split actually speeds up that version a little bit too, to 73 seconds.)

You can still get it a bit faster. words is actually the preferred way of getting all the non-whitespace bits out of a string in Perl 6 — it’s asking for what you want, rather than trying to specify what you don’t want. And it turns out it’s faster, too: $*IN.slurp.words makes the code execute in 7 seconds, shaving .5 seconds off from our best split version.

So, the good news here is that Rakudo is actually usably fast on this task. Yay! Here’s the faster version:

my %words;

for $*IN.slurp.words { 
    %words{$_}++ 
}

for %words.pairs.sort: { $^b.value <=> $^a.value } -> $pair {
    say $pair
}

The bad news is, Rakudo seems to have a pretty serious performance issue in the operation of stringifying the List of Str. I did a bit of timing, and 50 strings took 5.4 seconds, 100 took 17 seconds, and 200 took 77 seconds. At a very rough approximation, that’s O(N^2). Masak points out that this is an example of Schlemiel the Painter’s algorithm.

Trig Tests

June 23, 2010

When I originally wrote the expanded trig tests, the tests were very thorough. Given an angle, it would (say), test that angle in the default trig base, and then in radians, degrees, gradians, and “circles”. For three different ways to call it for Num, then for Rat, Complex, and Int. This led to a lot of trig tests: sin/asin had 1782 combined tests, for instance. But I still needed to add more tests! So I’ve known for a while I was going to have to reduce the number of tests. I just wasn’t sure how.

I played around with several different methods for reducing the count. I settled early on on the notion that the full tests would still be performed for the method forms of Num and Complex. That way we have confidence the underlying algorithms do work. My current effort is to get the code to automatically generate one test for each form for each type. So for instance

# Rat tests
is_approx((-3.9269908).Rat.sin, 0.7071067, "Rat.sin - -3.9269908 default");
is_approx((-0.625).Rat.sin(Circles), 0.7071067, "Rat.sin(Circles) - -0.625 default");
is_approx((-3.9269908).Rat.sin(:base(Radians)), 0.7071067, "Rat.sin(:base(Radians)) - -3.9269908 default");
is_approx(sin((-3.9269908).Rat), 0.7071067, "sin(Rat) - -3.9269908 default");
is_approx(sin((-225).Rat, Degrees), 0.7071067, "sin(Rat) - -225 default");
is_approx(sin(:x((-3.9269908).Rat)), 0.7071067, "sin(:x(Rat)) - -3.9269908 default");
is_approx(sin(:x((-250).Rat), :base(Gradians)), 0.7071067, "sin(:x(Rat), :base) - -250 default");

Except this is wrong: I want to test a different angle for each form. I need to do a bit of refactoring to make that possible, but I think I should be able to get it going today.

One trick I am using here might qualify as a new Perl 6 idiom. I have a list of angles to test, and a list of trig bases. I want to come up with lots of combinations. My solution has been to do something like this:

 my $base_list = (<Radians Degrees Gradians Circles> xx *).flat;

That gets you an infinite list that just repeats those four strings over and over again — you just .shift them off as needed. You could do the same thing with array indexing and modular arithmetic, but IMO this is more elegant. (Though now that I think about it, with the array I believe you could say something like @array[$count++ % *] and it would work.)

Thanks to The Perl Foundation and Ian Hague for supporting this work.

Laziness in Perl 6: Much Easier

June 20, 2010

Just saw a nice blog post from Tinydot on using laziness in Perl 5 (as compared to Haskell). Of course, laziness is also a key feature of Perl 6, so I thought it would be fun to rewrite the code for Rakudo.

First, here’s the Haskell version from that post:

positives = [0..]
is_even x = x `mod` 2 == 0
evens = filter is_even

main = mapM_ print
[ ("10 positives", take 10 positives)
, ("10 evens" , take 10 (evens positives) )
, ("evens < 10" , takeWhile (< 10) (evens positives) )
]

Here’s my Perl 6 translation (works with current Rakudo):

sub is_even($x) { $x !% 2 };
sub evens(@x) { @x.grep(&is_even); }

sub take-while(Mu $test, $data) {
    gather {
        for $data.list {
            if $_ ~~ $test {
                take $_;
            } else {
                last;
            }
        }
    }
}

say "10 positives ", ~(1..*).list.munch(10);
say "10 evens ", ~evens(1..*).munch(10);
say "evens < 10 ", ~take-while(* < 10, evens(1..*));

(Note that I took 1 to infinity as the positives — I think the Haskell takes 0 to infinity.)

I tried using @positives = 1..*, but apparently that usage isn’t lazy yet. Perl 6 doesn’t have a take-while method (so far as I know), so I had to write one — very straightforward. Note that this implementation is fully lazy. Other than those two things, and a little Haskell weirdness for output, this is basically a line-for-line translation of the Haskell version.

A word about the use of Mu in the take-while definition. That’s so that any kind of test can be passed, including junctions: you could say something like take-while(2|4|6|8, evens(1..*)). It is every bit as powerful as the built in grep method. (In fact, I actually copied grep’s source and modified it to get this sub.)

Update: Masak++ points out that there is some question whether @positives = 1..* is supposed to be lazy. It may be that the proper lazy way is @positives <== 1..*. This is an area of the Spec which is still in a bit of flux…

Announce: Rakudo Perl 6 development release #29 (“Erlangen”)

May 20, 2010

On behalf of the Rakudo development team, I’m pleased to announce the May 2010 development release of Rakudo Perl #29 “Erlangen”. Rakudo is an implementation of Perl 6 on the Parrot Virtual Machine (see http://www.parrot.org). The tarball for the May 2010 release is available from http://github.com/rakudo/rakudo/downloads .

Rakudo Perl follows a monthly release cycle, with each release named after a Perl Mongers group. The May 2010 release is code named “Erlangen” in recognition of Erlangen.pm and the Perl 6 talk that Moritz Lenz, one of our core developers, gave this month.

Some of the specific changes and improvements occurring with this release include:

* Lexical classes and roles were implemented. Additionally, anonymous classes — which were never quite right in alpha — are now implemented more correctly, and anonymous roles are also supported.

* Basic support for named enumerations of the form ‘enum Weekday ‘ has been restored.

* First cut of use Foo:from and eval(‘foo’, :lang); needs Blizkost[1] to be installed to work.

* Numeric / Real roles much closer to the spec now.

* As always, many additional small features and bug fixes make working with Rakudo more pleasant.

* Rakudo now passes 32,347 spectests. We estimate that there are about 39,500 tests in the test suite, so Rakudo passes about 82% of all tests.

For a more detailed list of changes see “docs/ChangeLog”.

The development team thanks all of our contributors and sponsors for making Rakudo Perl possible, as well as those people who worked on parrot, the Perl 6 test suite and the specification.

The following people contributed to this release:
Solomon Foster, Moritz Lenz, Jonathan Worthington, Martin Berends, chromatic, Carl Masak, snarkyboojum, Stefan O’Rear, Reini Urban, Jonathan Scott Duff, takadonet, Christoph Otto, isBEKaml, ash_, bubaflub, Jimmy Zhuo, Peter Lobsinger and Patrick Abi Salloum

If you would like to contribute, see http://rakudo.org/how-to-help , ask on the perl6-compiler@perl.org mailing list, or ask on IRC #perl6 on freenode.

The next release of Rakudo (#30) is scheduled for June 17, 2010. A list of the other planned release dates and code names for 2010 is available in the “docs/release_guide.pod” file. In general, Rakudo development releases are scheduled to occur two days after each
Parrot monthly release. Parrot releases the third Tuesday of each month.

Have fun!

[1] http://github.com/jnthn/blizkost


Follow

Get every new post delivered to your Inbox.