Re^2: Getting the size of the call stack (efficiently)

[Anno]

Out of curiosity (and for the good purpose of delaying more serious work) I ran some bechmarks to find the break-even point of kyle's logarithmic method. I found it at a depth of 15 on my machine, frankly much lower than I expected but still a bit high for practical purposes. Calls don't often nest that deep.

The relative efficiency varies from about 1:2 in favor of the linear method at depth 2 (the lowest that can be easily benchmarked), to, well, arbirtary much in favor of the logathithmic method. 1:3 at 100, 1:30 at 1000.

The full story is a bit lengthy

#!/usr/local/bin/perl
use strict; use warnings; $| = 1;
use Vi::QuickFix;
use Benchmark qw( cmpthese);

goto bench;

check: {
    printf "drwhy: %d, kyle: %d\n", depth_drwhy(), depth_kyle();
    for my $depth ( 0, 1, 2, 3, 4, 10, 100, 1000 ) {
        call_at_depth( $depth);
    }
}
exit;

bench: {
    for my $depth ( 0, 1, 8, 13, 98, 998 ) {
        cmp_at_depth( $depth);
    }
}
exit;

##################################################################

sub call_at_depth {
    no warnings 'recursion';
    my ( $depth) = @_;
    return call_at_depth( $depth - 1) if $depth;
    printf "drwhy: %d, kyle: %d\n", depth_drwhy(), depth_kyle();
}

sub cmp_at_depth {
    no warnings 'recursion';
    my ( $depth, $time) = @_;
    return cmp_at_depth( $depth - 1, $time) if $depth;
    defined $time or $time = 1;
    printf "at depth %d\n", depth_drwhy();
    cmpthese( -$time, {
            drwhy => \ &depth_drwhy,
            kyle  => \ &depth_kyle,
        },
    );
    print "\n";
}

sub depth_drwhy {
    my $depth = 0;
    ++ $depth while caller $depth;
    $depth;
}

sub depth_kyle {
    my $depth = 1;
    $depth *= 2 while ( caller $depth );
    my $max = $depth;
    my $min = $depth / 2;
    while ( $min < $max - 1 ) {
        my $mid = ($min + $max)/2;
        caller $mid ? $min : $max = $mid;
    }
    $max;
}

And the output...

at depth 2
         Rate  kyle drwhy
kyle  52194/s    --  -47%
drwhy 99211/s   90%    --

at depth 3
         Rate  kyle drwhy
kyle  51691/s    --  -43%
drwhy 91391/s   77%    --

at depth 10
         Rate  kyle drwhy
kyle  40959/s    --  -22%
drwhy 52193/s   27%    --

at depth 15
         Rate drwhy  kyle
drwhy 39267/s    --   -1%
kyle  39628/s    1%    --

at depth 100
         Rate drwhy  kyle
drwhy  4970/s    --  -77%
kyle  21290/s  328%    --

at depth 1000
        Rate drwhy  kyle
drwhy 94.2/s    --  -97%
kyle  3556/s 3673%    --