Archive for March, 2011

Pieces of Pi

March 28, 2011
13:36	shortcircuit	http://rosettacode.org/wiki/Pi
13:37	* shortcircuit	things Perl6 should implement that task as a sequence.
13:37	shortcircuit	*thinks

Well, can’t turn down a challenge like that.

The task is to create a program to continually calculate and output the next digit of pi. The program should continue forever (until it is aborted by the user) calculating and outputting each digit in succession. The output should be a decimal sequence beginning 3.14159265 …

First, research.

Ah, not only is it a cool project, but it is a chance to rework some Haskell code into Perl 6. Shiny!

So, it looks like the core of their approach is this function:

> stream :: (b->c) -> (b->c->Bool) -> (b->c->b) -> (b->a->b) -> 
>           b -> [a] -> [c] 
> stream next safe prod cons z (x:xs) 
>   = if safe z y 
>     then y : stream next safe prod cons (prod z y) (x:xs) 
>     else stream next safe prod cons (cons z x) xs 
>       where y = next z 

You know, some algorithms make more sense when they are made recursive. Maybe it’s just because I’m not a hardcore functional programmer, but in this case recursion mostly serves to obfuscate the code. Here’s my attempt to rewrite it in Perl 6:

sub stream(&next, &safe, &prod, &cons, $z is copy, @x is copy) {
    gather loop {
        my $y = next($z);
        if safe($z, $y) {
            take $y;
            $z = prod($z, $y);
        } else {
            $z = cons($z, @x.shift)
        }
    }
}

To my mind, even though this is longer, it’s vastly clearer. There is one major problem, however: it doesn’t actually work. That @x is copy there is not guaranteed to work when you pass in an infinite list; and the entire point of this routine is to pass in infinite lists! I don’t know of a graceful way to handle this in Perl 6. This next works:

sub stream(&next, &safe, &prod, &cons, $z is copy, @x) {
    my $x-list = @x.iterator.list;
    gather loop {
        my $y = next($z);
        if safe($z, $y) {
            take $y;
            $z = prod($z, $y);
        } else {
            $z = cons($z, $x-list.shift)
        }
    }
}

It feels like there should be some more automatic way to do that in p6. Maybe something like “@x is ro-iterator”? (Yeah, that’s an ugly name.)

Update: Ugly &s deleted from the sub bodies at moritz_++’s suggestion.

Testing

March 24, 2011

I’m afraid I don’t have any great Perl 6 news to report. But I wanted to share this brilliant non-Perl programming post on testing.

Also, if anyone wonders what I’m up to, a lot of my current $work is being described on a new blog of mine, and a lot of my current play is at another. But mostly for the last week I’ve been a dad, as my wife is recovering from surgery and is physically unable to lift our 2.5-year-old.

More on masak’s p5

March 9, 2011

So, I left the benchmark code running with a couple more strings last night before I went to bed. Here are the results I got:

taaatatattgtttcatagtcgtaccacccaacacattgtcctcacg
cataaccggcggctcgtggctttctgtagaccgaatcttcgctgtttgctctg
p5-moritz.pl: 5.3499312
p5-fox.pl: 5.5914252
p5-colomon.pl: 9.0103538
p5-util.pl: 12.8984396
p5-matthias.pl: 26.1100836
There were nobles, who made war against each other; there was the king,
who made war against the cardinal; there was Spain, which made war against the king.
p5-fox.pl: 9.0724477
p5-moritz.pl: 10.4737434
p5-colomon.pl: 12.4736412
p5-matthias.pl: 25.980024
p5-util.pl: 32.2906812

(That’s the same test as the previous post, but I re-ran it again.)

In those times panics were common, and few days passed without some city or other registering in its archives an event of this kind.
There were nobles, who made war against each other; there was the king, who made war against the cardinal; there was Spain, which made war against the king.
p5-colomon.pl: 20.1296963
p5-fox.pl: 29.2432603
p5-moritz.pl: 33.6600319
p5-util.pl: 119.7950674
p5-matthias.pl: 139.7882468

If people have suggestions for more strings to run, I’d be happy to test them, but bear in mind that the benchmark script runs each test 10 times and averages the results, so it may take some time to get results.

UPDATE: I’ve added three more tests. I also added a new and somewhat novel routine from mberends which wasn’t part of masak’s competition. First, mberends’s results on the above tests:

dna, p5-mberends.pl: 25.846477
dumas-1, p5-mberends.pl: 52.3829865
dumas-2, p5-mberends.pl: 208.6451586
accgccaaccggaaagaatgtcctcccaccacaaatgtacgctcgcatggcggttgtcgagtctatgtcggttgcgctatactacatgataatggacgcc
ttacttacccaaagtagaaataagctcgtctttgagaaccgtggactggtactacctatttttagtcaaactcatgactcgcgcctagcccacatacaat
p5-moritz.pl: 15.4340812
p5-colomon.pl,: 16.0729917
p5-fox.pl: 19.6679714
p5-util.pl: 49.7325891
p5-mberends.pl: 107.7859086
p5-matthias.pl: 174.7841558
accgccaaccggaaagaatgtcctcccaccacaaatgtacgctcgcatggcggttgtcgagtctatgtcggttgcgctatactacatgataatggacgccttacttacccaaagtagaaataagctcgtctttgagaaccgtggactggtactacctatttttagtcaaactcatgactcgcgcctagcccacatacaat
tttgtccctggccacgacgttctactatatgttaatgaaacgtaaggaattgcgttggccaagaaacgtccttttcacagatacccgtcgtacctgattaccgctgtagggcgctttttccggctggggcgcgcgtgtctgttggccgggccctacgtaggcctataacggaaagatttgtaccaaattctactacgagg
p5-colomon.pl: 40.274496
p5-moritz.pl: 64.2675568
p5-fox.pl: 88.9493287

(Apologies that I didn’t time all the codes for that one, but it was very obvious the others were much slower, and I needed the Linux box for $work.)

In those times panics were common, and few days passed without some city or other registering in its archives an event of this kind. There were nobles, who made war against each other; there was the king, who made war against the cardinal; there was Spain, which made war against the king.
Then, in addition to these concealed or public, secret or open wars, there were robbers, mendicants, Huguenots, wolves, and scoundrels, who made war upon everybody. The citizens always took up arms readily against thieves, wolves or scoundrels, often against nobles or Huguenots, sometimes against the king, but never against cardinal or Spain. It resulted, then, from this habit that on the said first Monday of April, 1625, the citizens, on hearing the clamor, and seeing neither the red-and-yellow standard nor the livery of the Duc de Richelieu, rushed toward the hostel of the Jolly Miller. When arrived there, the cause of the hubbub was apparent to all.
p5-colomon.pl: 167.9458936
p5-fox.pl: 467.1575598
p5-moritz.pl: 858.1724499
p5-util.pl: 2079.24607
p5-mberends.pl: 3054.501836
p5-matthias.pl: 4872.900568

Benchmarking p5

March 9, 2011

So, matthias’s results in masak’s p5 challenge had me utterly baffled. Anyone with much Rakudo programming experience knows that something like

gather for @strA[$i..*-1] Z @strB[$j..*-1] -> $a, $b

in your inner loop is DOOM speed-wise. How could that possibly be a world-beater?

Well, the answer is that it all depends on the strings you are searching for common substrings. I’d asked masak about what test he was using a few days ago (trying to figure out the weird performance of my code) and gotten his routine:

    my $n = 160;
    my $a = <0 1 2 3 4>.roll($n).join;
    my $b = <5 6 7 8 9>.roll($n).join;

    # "N" case is testing this $a versus this $b

    my $ra = (0..$n - 10).pick;
    my $rb = (0..$n - 10).pick;
    $a = $a.substr(0, $ra) ~ 'flirtation' ~ $a.substr($ra + 10);
    $b = $b.substr(0, $rb) ~ 'flirtation' ~ $b.substr($rb + 10);

    # "Y" case is testing this $a versus this $b

If you look at that, what should jump out at you is, in the “N” case, the two strings have no characters at all in common with each other! matthias’s code is nearly perfectly optimized for this case, as the slow inner loop will never execute. The “Y” case will be nearly as good for it.

So, what happens if we use normal text to seed this? Luckily I just got some benchmarking code going. So if the strings are

There were nobles, who made war against each other; there was the king,
who made war against the cardinal; there was Spain, which made war against the king.

what are the timings like? Sorted from best to worse:

p5-fox.pl: 9.0981144
p5-moritz.pl: 10.4469054
p5-colomon.pl: 12.5152087
p5-matthias.pl: 25.9988418
p5-util.pl: 32.1561981

More strings and timings coming soon….

PS I should add I love the style of matthias’s code. It combines a lot of elegance with a clever Perl-ish and p6-ish approach to the problem. If I hadn’t stumbled across the suffix tree solution, I suspect my code would have looked a lot like an uglier version of his.

First Benchmark Results

March 6, 2011

I’ve gotten smash++’s Rakudo benchmarks running again, and I’m trying to get a full set of benchmark graphs generated. While moritz and I are debugging the graphing program, here are the first results. (Assuming I can get them to display here!)

Okay, two days later, I’ve finally got inkscape running again to generate PNG versions of the graphs. And with any luck, here they are:

Update: I forgot people who weren’t familiar with the original benchmarks would be reading this. All graphs are labeled with the number of seconds on the left hand side. Times given are the average execution time (including Rakudo start-up and compiling the benchmark code) over ten runs, on my reasonably fast 64-bit Linux machine. The benchmark scripts are at https://github.com/perl6/bench-scripts, and are a fairly random bunch at the moment. Contributions of new scripts would be gladly accepted.

As for the meaning of the results, I haven’t had time to analyze them in any depth. latest-rakudo seems pretty consistently a bit slower than the latest Rakudo Star, which makes me wonder if there are some different flags set in the build process for each. (I used the default build process for both R* and latest-rakudo, but they are two different build methods and might have some different compiler flags.) It also looks like a couple of the benchmarks have backslid very badly in the last two months. Certainly a full investigation is warranted.


Follow

Get every new post delivered to your Inbox.