Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

robin (1821)

robin
  (email not shown publicly)
about:blank

Journal of robin (1821)

Saturday September 01, 2001
08:14 AM

...

[ #730 ]

This is starting to sound repetitive, isn't it. Ah well - if I'd been keeping a Perl journal a few months ago, every entry would have been about B::Deparse :-)

Graham Barr pointed out that there's a flag you can set which instructs eval to catch its own errors, so that you don't have to. So I've changed A::FP to use that, instead. And I've uploaded it to the CPAN. I'm a bit nervous that I still haven't managed to get in touch with Matt Day: if you know how to get hold of him, please let me know.

Wednesday August 29, 2001
07:33 AM

Want 0.05

[ #718 ]

In Perl 5.6.1 and later, there are some quite strict compile-time checks on the return value from an lvalue subroutine. Because the checks are done at compile-time, it doesn't matter if you know at run-time that you're going to be in lvalue context.

So code like:

sub foo :lvalue {
  if (want('RVALUE')) {
    return 23;
  } else {
    $foo;
  }
}

won't even compile. The new version of Want adds a function rreturn which you can use for an rvalue return from an lvalue sub. So the above can be written as:

sub foo :lvalue {
  if (want('RVALUE')) {
    rreturn 23;
  } else {
    $foo;
  }
  return;
}

The compiler sadly doesn't realise that rreturn will actually return from the function, so you have to put the bare return; at the end to shut it up. But you can think of that like the 1; that you have to put at the end of a module: meaningless furniture that has to be there.

Actually, the check is obviously too strict, because something like:

sub foo :lvalue {
  if (something_bad()) {
    die "Something bad happened";
  } else {
    $foo;
  }
}

ought to be okay. But in Perl 5.6.1 it won't compile. Can't modify die in lvalue subroutine return. I'm not trying to modify it, you brain-damaged compiler!

Tuesday August 28, 2001
05:16 AM

bits & pieces

[ #714 ]

I've produced new versions of both Algorithm::PermuteInPlace and Algorithm::FastPermute.

They both had nasty bugs that would cause them to crash, and PermuteInPlace wouldn't work at all on any Perl version less than 5.7. Ah, the joys of the bleeding edge...

FastPermute uses a callback technique which I essentially stole from the first and reduce routines in List::Util. While I was testing FastPermute I noticed that exception handling doesn't work inside the callback. So code like this:

  permute { eval {die}; print "Got here!\n" } @array

will not continue past the die, even though the exception should have been caught. There followed a quick self-taught crash course in perl's exception handling mechanism. It's based around setjmp/longjmp, and like most of Perl's internals is simultaneously ingenious and baroque. When there's an exception, control immediately passes to the exception handler, whose responsibility it then is to continue if appropriate. Anyway after an intense few hours, FastPermute now deals politely and properly with exceptions. (Maybe I should fix up List::Util, now I've worked out how to do it.)

I'm still not quite sure whether the exception handling code, as it stands, makes FastPermute significantly slower. It now looks possible that it doesn't really; and that my comments in the README are misinformed.

Saturday August 25, 2001
07:23 AM

The need for speed

[ #703 ]

I've done it. Algorithm::FastPermute.

It can comfortably print all the permutations of ten elements in less than a minute, on my iBook. So it's almost four times as fast as Algorithm::Permute.

Since it's based on Matt Day's code, I should get his permission before releasing it properly. I also wonder if it could be incorporated into List::Util. Time to write some email.

Update: Email to mday@icon.com and mday@lachman.com is bouncing. Does anyone have his current email address?

Friday August 24, 2001
01:27 PM

Faster! Faster!

[ #699 ]
# The fastest Perl permutation algorithm I've yet found. It's only 20-30% slower
# than Algorithm::PermuteInPlace.
#
# Now if we implement _this_ in C, with a Perl callback for processing
# the permutation, we can probably get even faster than Algorithm::PermuteInPlace.
# (There are ways to invoke Perl callbacks without the normal subcall overhead.)

# Translated from the C code by Matt Day,
#     at http://www.cs.jyu.fi/~hirvonen/opk_2001_ratk/permu.txt

use strict;

sub permute {
    my ($aref, $level) = (@_, 0);
    my ($index, $copy, $printing) = ($level, [@$aref], $level+1 == @$aref);
    do {
        if ($printing) {
            print "@$copy\n";
        } else {
            permute($copy, 1+$level);
        }
        @$copy[$index-1, $index] = @$copy[$index, $index-1]
            if $index != 0;

    } while $index-- > 0;
}

permute([1..shift]);
11:52 AM

Algorithm::PermuteInPlace

[ #698 ]

Algorithm::PermuteInPlace 0.01 is making its way to the CPAN.

As an experiment, I used Inline rather than XS. It's just a proof of concept, but it performs okay - about twice as fast as the Perl version, in my tests.

My iBook can now print all the permutations of ten elements within 90 seconds.

Wednesday August 22, 2001
12:43 PM

Permutation benchmarks

[ #691 ]

I took a clutch of permutation routines and used them to print out all 10! permutations of the numbers (1..10). I ran them on my iBook with time perl permute-xx.pl > /dev/null. The results are stunning.

Both of the permutation routines here run faster than any of the alternatives.

The older pure-Perl algorithms are the slowest. The fastest of them is List::Permutor, at user 7m35.270s, sys 0m1.670s. The rest are a lot slower than that. The cookbook code seems to be even slower than the routine from perlfaq4, if the list is long (> 8 elements).

Algorithm::Permute, with its C implementation, fares rather better. It clocks in at user 2m59.160s sys 0m0.660s.

However, it's pipped by the loopless algorithm immediately below, at user 2m42.170s sys 0m0.430s. And the winning place is awarded to the code I posted here last month, which cruises home at user 2m18.920s sys 0m0.760s.

It's surprising that a pure Perl routine can be significantly faster than handcrafted C - a convincing testament to the power of in-place updates. Just wait until I get the same algorithm implemented in C ;-)

12:05 PM

In constant time!

[ #690 ]
# A loop-free implementation of the Johnson-Trotter permutation algorithm.
# Ehrlich is responsible for the idea[1]. This implementation is mine.
# [1] Journal of the ACM: 20, 3 (July 1973), 500-513
#
# next_perm runs in constant time, every time. A longer list won't make
# it slower. Cute trick, but in practice the looping version below seems
# to be faster.
#
# 2001-08-21 robin@cpan.org

use strict;
my (@array, @p, @a, @d, @u, @c);

sub init_perm {
    @array = @_;
    @p = (0..$#array);    # Element key => position
    @a = (0..$#array);    # Position => element key
    @d = (-1) x @array;   # Start off going left
    @c = (0..$#array);    # counter for each element
    @u = (0..$#array);    # which element to move when the counter expires
    print "@array\n";
}

sub next_perm {
    my ($l, $i) = (0, $u[$#u]);
    return if $i == 0;
    $u[$#u] = $#u;

    # Switch the element keyed by $i with the one to the left/right
    # of it, and update the @p and @a arrays to keep them in sync with @array.
    my ($x, $y) = ($p[$i], $p[$i]+$d[$i]);
    $p[$i] += $d[$i]; $p[$a[$p[$i]]] -= $d[$i];
    @array[$x,$y] = @array[$y,$x];  @a[$x,$y] = @a[$y,$x];

    # See if we're at one of the ends
    if (--$c[$i] == 0) {
        $c[$i] = $i;
        $u[$i] = $u[$i-1];
        $u[$i-1] = $i-1;
        $d[$i] = -$d[$i];
    }
    1;
}

init_perm(1..shift());
print "@array\n" while next_perm();
07:33 AM

Permute! Permute! Custom ops?

[ #689 ]

I've been working on various things recently, mostly not very Perl-related. I found an answer to the permutations problem mentioned below. It's in a twenty-year-old paper written by a Cameroonian mathematician, published in a Canadian journal, which I found in the British Library. On the second page of the paper is exactly the same diagram that I'd been using.

One thing I've realised is that good permutation algorithms are not at all well-known. The algorithm in perlfaq4 is devastatingly slow, and the Cookbook entry is only a slight improvement. Algorithm::Permute is somewhat better (and written in C), but there's plenty of room for improvement.

The only way to list permutations really fast is to permute the array in-place, rather than copying the elements each time. Good permutation algorithms are fast enough that the overhead of copying the elements completely swamps the time taken to calculate the permutation. In complexity terms, copying the elements means that your algorithm will never be faster than O(n) to get the next permutation. We can get that down to O(1). And we still only need O(n) space.

So I'm thinking of writing Algorithm::Permute::InPlace. We should be able to make it scream. But if we write it in C, the overhead of calling the XSUB will still be quite heavy. So I'm toying with the idea of building an interface that will allow C routines to be called directly from the optree by the red-hot op dispatcher. I think that's a lot easier than it sounds. It would be nice to integrate it with Inline too. I hope to have a working proof of concept soon.

Sunday August 05, 2001
01:20 PM

clean

[ #614 ]

Back in London - I've had a bath. My tent is drying in the garden. It's sad to have left: the conference was a delight.

I'm happy to have met two of the great artists who work in the medium of Perl: Philippe and Abigail. They both offered future works for sale at the conference auction. So Philippe is going to produce a work for Dave Cross, and Abigail is going to write one for Philippe. That makes me happy. It's just a shame that Erudil wasn't there as well :-)

Schwern organised a CPANTS hacking session last night. I only stayed around for a short while before heading into town, but I plan to contribute something B-related to help with gathering code metrics.

Don't miss Andy's journal. Love to everybody.