Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Why is goto &sub slow?

by dragonchild (Archbishop)
on Mar 29, 2004 at 01:36 UTC ( [id://340468]=note: print w/replies, xml ) Need Help??


in reply to Why is goto &sub slow?

What about:
{ my ($end, $curr, $result); my $_factorial; $_factorial = sub { return $result if $curr > $end; $result *= $curr++; $_factorial->(); }; sub fact4 { ($end, $curr, $result) = (shift, 1, 1); $_factorial->(); } }

My benchmarking indicates that my version is 30% faster than the standard recursion and 6 times faster than goto.

dragonchild: 4 wallclock secs ( 3.19 usr + 0.00 sys = 3.19 CPU) @ 1 +22695.46/s (n=392012) lexical: 3 wallclock secs ( 3.10 usr + 0.00 sys = 3.10 CPU) @ 21 +976.48/s (n=68215) recursion: 3 wallclock secs ( 3.08 usr + 0.00 sys = 3.08 CPU) @ 91 +202.59/s (n=281360) typeglob: 4 wallclock secs ( 3.14 usr + 0.00 sys = 3.14 CPU) @ 21 +142.77/s (n=66494)

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

Replies are listed 'Best First'.
Re: Re: Why is goto &sub slow?
by jdporter (Paladin) on Mar 29, 2004 at 22:53 UTC
    But that's still full recursion, not tail call elimination, which is what goto &sub is.

    jdporter
    The 6th Rule of Perl Club is -- There is no Rule #6.

      Ok. fine.
      { my ($end, $curr, $result); my $_factorial; $_factorial = sub { return $result if $curr > $end; $result *= $curr++; goto &$_factorial; }; sub fact5 { ($end, $curr, $result) = (shift, 1, 1); $_factorial->(); } }

      And, the benchmarking goes something like:

      Timing factorial of 5 Benchmark: running dragonchild1, dragonchild2, lexical, recursion, typ +eglob for at least 3 CPU seconds... dragonchild1: 3 wallclock secs ( 3.19 usr + 0.00 sys = 3.19 CPU) @ +106369.76/s (n=339745) dragonchild2: 3 wallclock secs ( 3.05 usr + 0.00 sys = 3.05 CPU) @ +89930.56/s (n=274558) lexical: 3 wallclock secs ( 3.06 usr + 0.00 sys = 3.06 CPU) @ 29 +376.63/s (n=90010) recursion: 4 wallclock secs ( 3.19 usr + 0.00 sys = 3.19 CPU) @ 68 +035.79/s (n=216694) typeglob: 3 wallclock secs ( 3.01 usr + 0.00 sys = 3.01 CPU) @ 27 +140.10/s (n=81556) Rate typeglob lexical recursion dragonchild2 dr +agonchild1 typeglob 27140/s -- -8% -60% -70% + -74% lexical 29377/s 8% -- -57% -67% + -72% recursion 68036/s 151% 132% -- -24% + -36% dragonchild2 89931/s 231% 206% 32% -- + -15% dragonchild1 106370/s 292% 262% 56% 18% + --

      In other words, my tail-call is 90k/second, straight recursion is 70k/second, but my straight recursion is 105k/second. The regular tail-call are in the 25-30k/second. I lose about 10% going from recursion to tail-call.

      Now, when I shift from factorial(5) to factorial(15) and factorial(25), the benchmarking looks something like:

      Timing factorial of 15 Benchmark: running dragonchild1, dragonchild2, lexical, recursion, typ +eglob for at least 3 CPU seconds... dragonchild1: 3 wallclock secs ( 3.00 usr + 0.00 sys = 3.00 CPU) @ +47052.93/s (n=141347) dragonchild2: 3 wallclock secs ( 3.18 usr + 0.00 sys = 3.18 CPU) @ +40502.36/s (n=128595) lexical: 4 wallclock secs ( 3.24 usr + 0.00 sys = 3.24 CPU) @ 11 +222.80/s (n=36418) recursion: 3 wallclock secs ( 3.12 usr + 0.00 sys = 3.12 CPU) @ 26 +999.68/s (n=84104) typeglob: 3 wallclock secs ( 3.10 usr + 0.00 sys = 3.10 CPU) @ 10 +381.32/s (n=32234) Rate typeglob lexical recursion dragonchild2 dr +agonchild1 typeglob 10381/s -- -7% -62% -74% + -78% lexical 11223/s 8% -- -58% -72% + -76% recursion 27000/s 160% 141% -- -33% + -43% dragonchild2 40502/s 290% 261% 50% -- + -14% dragonchild1 47053/s 353% 319% 74% 16% + -- ------------------------------------ Timing factorial of 25 Benchmark: running dragonchild1, dragonchild2, lexical, recursion, typ +eglob for at least 3 CPU seconds... dragonchild1: 3 wallclock secs ( 3.01 usr + 0.00 sys = 3.01 CPU) @ +29099.20/s (n=87705) dragonchild2: 3 wallclock secs ( 3.12 usr + 0.00 sys = 3.12 CPU) @ +25319.04/s (n=79122) lexical: 4 wallclock secs ( 3.30 usr + 0.00 sys = 3.30 CPU) @ 68 +28.22/s (n=22499) recursion: 4 wallclock secs ( 3.23 usr + 0.00 sys = 3.23 CPU) @ 16 +312.62/s (n=52755) typeglob: 3 wallclock secs ( 3.23 usr + 0.00 sys = 3.23 CPU) @ 61 +14.10/s (n=19773) Rate typeglob lexical recursion dragonchild2 dr +agonchild1 typeglob 6114/s -- -10% -63% -76% + -79% lexical 6828/s 12% -- -58% -73% + -77% recursion 16313/s 167% 139% -- -36% + -44% dragonchild2 25319/s 314% 271% 55% -- + -13% dragonchild1 29099/s 376% 326% 78% 15% + --

      I have no idea why my recursion is still beating my tail-call. The ratio is mostly staying the same, at least between my versions. At 80, this is what happens:

      Timing factorial of 80 Benchmark: running dragonchild1, dragonchild2, lexical, recursion, typ +eglob for at least 3 CPU seconds... dragonchild1: 4 wallclock secs ( 3.18 usr + 0.00 sys = 3.18 CPU) @ +8834.80/s (n=28130) dragonchild2: 4 wallclock secs ( 3.17 usr + 0.00 sys = 3.17 CPU) @ +7694.39/s (n=24422) lexical: 3 wallclock secs ( 3.11 usr + 0.00 sys = 3.11 CPU) @ 20 +67.44/s (n=6438) recursion: 3 wallclock secs ( 3.25 usr + 0.00 sys = 3.25 CPU) @ 50 +47.46/s (n=16379) typeglob: 3 wallclock secs ( 3.32 usr + 0.00 sys = 3.32 CPU) @ 18 +79.40/s (n=6249) Rate typeglob lexical recursion dragonchild2 dr +agonchild1 typeglob 1879/s -- -9% -63% -76% + -79% lexical 2067/s 10% -- -59% -73% + -77% recursion 5047/s 169% 144% -- -34% + -43% dragonchild2 7694/s 309% 272% 52% -- + -13% dragonchild1 8835/s 370% 327% 75% 15% + --

      I'm not sure what all those numbers really mean, but there they are. :-)

      ------
      We are the carpenters and bricklayers of the Information Age.

      Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

Log In?
Username:
Password:

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

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

    No recent polls found