cormanaz has asked for the wisdom of the Perl Monks concerning the following question:

Howdy Monks. The code below in Perl takes about 160 seconds to run on a test file I have. I know someone who has implemented the same algorithm (from the same pseudocode) in compiled Pascal, and it runs on the same test file in about 1 second. The two implementations produce identical results.

Now I expect interpreted Perl to be slower than compiled Pascal, but not 160x slower. So I am wondering if I have done something to make this extra slow. For example is pushing onto an array slice (as in line 21) an especially slow operation or something? I'm at a bit of a loss to understand the slowness.

Thanks........

Steve 

for my $s (0..$#a) { 
    @stack = ();
    @p = ();
    @delta = @sigma = @sigmainit;
    $sigma[$s] = 1;
    @d = @dinit;
    $d[$s] = 0;
    @queue = ();
    push(@queue,$s);
    while(@queue) {
        $v = shift(@queue);
        push(@stack,$v);
        for $w (0..$#a) {
            if ($a[$v][$w]) { 
                if ($d[$w] < 0) {
                    push(@queue,$w);
                    $d[$w] = $d[$v] + 1;
                }
                if ($d[$w] == $d[$v]+1) {
                    $sigma[$w] += $sigma[$v];
                    push(@{ $p[$w] },$v); 
                }
            }
        }
    }
    while (@stack) {
        $w = pop(@stack);
        foreach $v (@{ $p[$w] }) { 
            $delta[$v] += ($sigma[$v]/$sigma[$w]) * (1 + $delta[$w]);
        }
        if ($w != $s) {
            $b[$w] += $delta[$w];
        }
    }
}

[download]

Replies are listed 'Best First'.
Re: Sloooooow algo in Perl
by tlm (Prior) on Mar 26, 2005 at 15:24 UTC

    A factor of 160 doesn't seem to me too implausible, even with reasonably well-written Perl code; Perl is more efficient at some things than others. It looks like this is a matrix manipulation of some sort. Raw Perl is not great with matrices and vectors; that's why people use PDL when they want to do this sort of thing with Perl.

    the lowliest monk

[reply]
Re: Sloooooow algo in Perl
by cog (Parson) on Mar 26, 2005 at 15:06 UTC
    If you could explain what your algo is supposed to do in English, perhaps you could get some more help :-)
[reply]

      Yeah, and while you're at it, give us typical values for the inputs (@a, @sigmainit, @dinit, and whatever else this algorithm needs to run).

      the lowliest monk

[reply]
[d/l]
[select]
Re: Sloooooow algo in Perl
by perlfan (Parson) on Mar 26, 2005 at 18:01 UTC
    By inspection, your implementation is O(n^3), and this is assuming that nothing is pushed back onto @queue inside of the most inner for-loop.

    You say it is the same algorithm as the one implemented in Pascal, but is it the same IMPLEMENTATION of this algorthm, and is there anyway to reduce the complexity? Perhaps you can post some psuedo code of the algorithm or the pascal code.

[reply]
Re: Sloooooow algo in Perl
by Joost (Canon) on Mar 26, 2005 at 15:10 UTC
[reply]
Re: Sloooooow algo in Perl
by ambs (Pilgrim) on Mar 26, 2005 at 15:10 UTC

    Looking to your code, you don't have nothing I can say: LOOK THERE! IT'S SLOW! Unfortunately. This way can't help you much.

    First questions... what is the magnitude order for your @a? Also, your @delta = @sigma = @sigmainit is not efficient if these are big arrays. Also, I can't see where @sigmainit come from.

    Also, in your foreach, if @{$p$w} is a big array, a while look is faster.

    Hope this all helps you a bit. But It's hard to look to your algorithm without more information and understand what it should do.

    Alberto Simões

[reply]
Re: Sloooooow algo in Perl
by cormanaz (Deacon) on Mar 26, 2005 at 16:33 UTC
    Sorry for the cryptic post. I didn't want to ask people to look at the whole body of code (which is traversing a graph, adding up dependencies). I was mainly trying to inquire whether I was using some kind of known-slow operation in there. It sounds like not, so thanks for the looks. I will hook up Time::HiRes and start timing the loops to find out what's going on. Happy Saturday..... Steve
[reply]
      Not so fast, there, pal :-)

      I was mainly trying to inquire whether I was using some kind of known-slow operation in there.

      Well, it seems you're not, but don't despair just yet. Instead, explain your code in English. Really. You're probably just using a much more complicated algorithm that your Pascal friend is...

      If you explain what you want to do, people here might be able to help you :-) (and probably feel good about it)

[reply]
      I will hook up Time::HiRes and start timing the loops

      You might want to look up Devel::Dprof instead. It's part of the core distribution, and it gives you a nice breakdown of where the time goes. In a nutshell: 

       perl -d:Dprof your_script

 # wait 160 seconds or whatever...
 
 dprofpp

      [download]
      (the "dprofpp" tool should be in the same path where perl was installed). To get the best use out of it, you might want to split up your code to put one or more of the inner loops into separate subroutines, to get better granularity on the timing analysis.

      (While breaking things up that way, who knows... you might figure out some other way to do it -- then you can use Benchmark to compare which approach is best, in case it's not immediately obvious. :)

[reply]
[d/l]
        You might want to look up Devel::Dprof instead.
        For line-by-line profiling, I've found Devel::SmallProf very useful. It's used much the same way.

        # wait 160 seconds or whatever...
        Actually, I found with both Dprof and SmallProf that the wallclock time is significantly longer than the "profiled" time. For Dprof, I recall 5x; for SmallProf, more like 10x.

        -QM
        --
        Quantum Mechanics: The dreams stuff is made of

[reply]
      What I belive that anyone wants to say (but dont know why they havent said it that clearly) is that you cant use same pseudo code for both Perl and Pascal (or any other prog. languages). These two languages are very different, and their logic is different. If you do so, like in your case, you are not using strengths of the Perl. And I find it quite common that your code is much slower than one in pascal, as that pseudo code was probably writen with Pascal style programming on mind. Shure, Perl (should not be that big problem in upcoming version 6 as it alows you to define type for a variable) is a bit slow with number crunching and lot's of loops. Post the real problem, in english, and we will see what we can do.
[reply]
Re: Sloooooow algo in Perl
by belg4mit (Prior) on Mar 26, 2005 at 21:56 UTC
    1. for $w (0..$#a) How big is a? This could be mighty slow
    2. I'd consider using local instead of duplicating arrays
    3. References aren't free. If you are doing *a lot* of dereferencing it can be a good idea to assign something like $a[$v] to a temporary value outside of the the inner for loop, and referencing $temp[$w] instead.

    --
    I'm not belgian but I play one on TV. On dit que je parle comme un belge aussi.

[reply]
[d/l]
[select]
Re: Sloooooow algo in Perl
by tilly (Archbishop) on Mar 28, 2005 at 07:51 UTC
    I'll second what everyone else has said (in particular sprinkling "my" generously would be good) but on a more practical note would suggest factoring common operations out of loops. The Pascal compiler will do that for Pascal, but Perl's does not. It adds up.

    For instance in the first set of loops rather than looking up $a[$v][$w] repeatedly, store $a[$v] into $a_v and then lookup $a_v->[$w]. Removing the repeated lookup will eliminate half the work of that tight inner loop on the elements that require no further calculation. And on the second set of loops once you know $w you can calculate (1 + $delta[$w])/$sigma[$w] once and avoid all of those lookups and that math in the tight loop.

    Doing that should give a considerable speedup. But this kind of stack manipulation is always going to be slower in Perl than Pascal. Where Perl does well is when its complex built-in operations (eg regular expressions, hash lookups) avoid a lot of explicit low-level code. That is obviously not the case here.

[reply]
[d/l]
[select]
Re: Sloooooow algo in Perl
by demerphq (Chancellor) on Mar 27, 2005 at 20:51 UTC

    Turn on strictures and warnings and then make sure all of the vars used are lexicals. Furthermore avoid multiple derefs when possible. Just from switching away from using package vars you should see a noticable speedup.

    ---
    demerphq

[reply]
Re: Sloooooow algo in Perl
by heathen (Acolyte) on Mar 28, 2005 at 14:39 UTC
    Presizing the arrays can offer a performance improvement. Continually pushing things onto the stack can be inefficient when working w/ large arrays.
[reply]
      Can you offer an example where this inefficiency is significant?

      Perl's dynamic allocation algorithm is designed so that the average cost of resizing and reallocating works out to be a constant amount per push. I'm not sure that avoiding that cost only to have to keep track of what index you're on will be a win.

[reply]

Back to Seekers of Perl Wisdom