Re: 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->();
    }
}
[download]

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)
[download]

------
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

Comment on Re: Why is goto &sub slow? Select or Download Code

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.	[reply] [d/l]
Re: Re: Re: Why is goto &sub slow? by dragonchild (Archbishop) on Mar 30, 2004 at 02:02 UTC
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->(); } }` [download] 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% + -- [download] 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% + -- [download] 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% + -- [download] 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	[reply] [d/l] [select]