Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re^9: Specializing Functions with Currying

by jryan (Vicar)
on Aug 06, 2004 at 23:20 UTC ( [id://380768]=note: print w/replies, xml ) Need Help??


in reply to Re^8: Specializing Functions with Currying
in thread Specializing Functions with Currying

Hey, don't take me wrong, I'm all about elegance. My argument isn't against functional langauges (hell, I used reduce, which is the same thing in lisp! lisp, baby! how's that for functional!), it was that recursion in Perl is crazy inefficient, and to use it just because its "functional" is kind of silly. :) Tilly's point was about tail-recursion, which is an optimization that Perl doesn't support (for some reason, I honesetly don't have a clue why).

Replies are listed 'Best First'.
Re^10: Specializing Functions with Currying
by tilly (Archbishop) on Aug 06, 2004 at 23:39 UTC
    Tail recursion has a seldom-noted cost. Sure, it speeds up some recursive code. But it also means that if you get into trouble, a stack backtrace will be missing a lot of potentially useful context.

    That said, you can manually do tail-recursion in Perl with goto. Unfortunately it is not as efficient as it should be, and I'm not entirely sure why.

      That said, you can manually do tail-recursion in Perl with goto. Unfortunately it is not as efficient as it should be, and I'm not entirely sure why.

      I think that it basically comes down to the fact that goto is just not all that efficient, and the amount of bookkeeping code needed to do that (for non-trivial implementations) outweighed the benefits.

      -stvn
Re^10: Specializing Functions with Currying
by stvn (Monsignor) on Aug 06, 2004 at 23:37 UTC
    ... it was that recursion in Perl is crazy inefficient, ...

    Is it really? I mean, its certainly not as efficient as the equivalent iterative code. And I know that subroutine calls have a non-trivial overhead (setting up lexical scope and all), but being that perl does not tie itself to the C-stack like some other langauges do (*cough* Python *cough*) I would think that it wouldn't really be all that inefficient. Of course, I have never benchmarked it, so who knows.

    ... and to use it just because its "functional" is kind of silly ...

    But if we can't get silly with Perl at 7 o'clock (EST) on a Friday night, then what kind of world is this! ;-P

    about tail-recursion, which is an optimization that Perl doesn't support (for some reason, I honesetly don't have a clue why)

    I don't know why either, I once looked into trying to "implement" it with the B:: modules. But once was all it took for me to to decide that wouldn't work.

    -stvn

      Well, here's a benchmark. The first two are just normal factorial functions. The second two are factorial functions with a twist: a simple string gets created. Now, this string has to be created and saved on *every* recursive call, which should show the discrepancy a little more (as saving one little integer to the stack doesn't make much difference):

      use strict; use warnings 'all'; sub factorial_r { my ($n) = @_; return $n if ($n < 2); return $n * factorial_r($n-1); } sub factorial_i { my ($n) = @_; my $i = $n - 1; $n *= ($n - $i--) while $i > 1; return $n; } sub factorial_r_extra { my ($n) = @_; my $x = "blah" x 100; return $n if ($n < 2); return $n * factorial_r_extra($n-1); } sub factorial_i_extra { my ($n) = @_; my $x = "blah" x 100; my $i = $n - 1; $n *= ($n - $i--) while $i > 1; return $n; } use Benchmark qw(timethese); timethese(100000, { first => sub { factorial_r(50) }, second => sub { factorial_i(50) }, });

      The results:

      Benchmark: timing 100000 iterations of factorial_i, factorial_i_extra, + factorial_r, factorial_r_extra... factorial_i: 5 wallclock secs ( 4.94 usr + 0.00 sys = 4.94 CPU) @ 2 +0251.11/s (n=100000) factorial_i_extra: 6 wallclock secs ( 5.67 usr + 0.00 sys = 5.67 CP +U) @ 17633.57/s (n=100000) factorial_r: 6 wallclock secs ( 6.44 usr + 0.01 sys = 6.45 CPU) @ 1 +5496.67/s (n=100000) factorial_r_extra: 13 wallclock secs (11.98 usr + 0.00 sys = 11.98 CP +U) @ 8344.46/s (n=100000)

      P.S. : I'm still young and armed with a job with flextime - I don't wake up until about 1pm, so this is like early afternoon for me. :)

        I am not sure what you are trying to prove with this benchmark. Of course factorial_r_extra will take longer, it creates my $x = "blah" x 100 5,000,000 times, as opposed to factorial_i_extra which only creates it 100,000 times. That proves nothing about the inefficiency of recursion in perl, only that it takes longer to do something 50 times more, which is true regardless of whether you use iteration or recursion.

        -stvn

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://380768]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others browsing the Monastery: (8)
As of 2024-03-28 23:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found