Getting the size of the call stack (efficiently)

[DrWhy]

The discussion started at Getting size of call stack describes a straightforward way to get the current call stack size:

for ($depth = 0; caller $depth; $depth++) {1}

(That's my own implementation of the algorithm.)

This is a pretty inefficent way to get the stack depth. For implementations where this is only needed once, e.g. as part of generating a die message, that's not much of an issue. I have a tracing module that produces lots of debugging output, and I'd like to add an indication of the stack depth to each line of debug output -- that would lead to alot of repetition of this loop.

Does anyone know of a more efficient method for finding just the stack depth without using multiple calls to caller() each time you need that number?

[kyle]

Without knowing any magic, you could check at intervals other than 1.

my $depth = 1;
$depth *= 2 while ( caller $depth );
my $max = $depth - 1;
my $min = $depth / 2 + 1;

Then do a binary search from there. You can probably get a bit faster if you know in advance about where your depth will be.

Update: Set starting depth to nonzero as suggested by Anno (though maybe 2 is a better value than 1 so that $depth / 2 + 1 is an integer).

[Anno]

That looks promising (except the starting value for $depth should be nonzero :).

Anno

[kyle]

Good catch! Fixed, thanks.

[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

Read more... but here it is: (2 kB)

[grinder]

What's so inefficient about it? The fact that there appears to be a lot of make-work code? I think you'll find that there are already modules available which will do what you want, Devel::StackTrace and Devel::CallerItem spring to mind, but I suspect they call caller under the covers themselves.

You could use them as building blocks, and then there wouldn't be as much visible caller-frame-grovelling code in your own code.

Or you could turn the problem on its head and use Hook::WrapSub to track your caller stack yourself, by writing push and pop wrappers that maintain a stack, around the functions you're interested in tracking.

Apart from that, I'm not surprised you find your code as shown to be slow... it has an infinite loop! update: err, no you're right it hasn't. Nonetheless, C-style for loops are so rare in Perl that I probably won't be the only person who gets confused by it (... I was looking for a last somewhere I guess).

You should I think it would be more readable to recast it as something like:

my $level = 0;
while (my @frame = caller($level++)) {
    # do stuff with the current frame
}

update: I didn't realise at first that you only cared about the depth, not what's at each level. In which case, the following snippet will be pretty efficient (since it is blockless):

my $level = 0;
1 while caller(++$level);

I wouldn't worry about it being too slow, and least not right away. Make it readable first.

[DrWhy]

Apart from that, I'm not surprised you find your code as shown to be slow... it has an infinite loop! You should recast it as something like: ...

Um. No? I've played around with my implementation a couple of different ways. I've not yet encountered it failing to terminate with the desired result.

update: I didn't realise at first that you only cared about the depth, not what's at each level. In which case, the following snippet will be pretty efficient (since it is blockless):

Ah, yeah that's a little faster, about 15% faster than the version with the block.

By the way, in benchmarking these two methods I found that getting the stack depth (either way) is really quite fast, I had to do a million repetitions of my test code (each run had a stack depth of 3). That's much less overhead than my naive expectations would have predicted.

Update: I played around with the two versions a little more and found that really the difference between the block and the inline versions is only about 4%. My block implementation had some extra overhead unrelated to the 'blockiness' of it.

[xdg]

Does anyone know of a more efficient method for finding just the stack depth without using multiple calls to caller() each time you need that number?

I think you'd would have to implement it in XS and adapt the underlying code for caller. Looking at pp_ctl.c in the source, it looks like caller is just walking the stack itself, but someone with more knowledge of XS and Perl guts would have to advise you on just what you need to do.

[DrWhy]

Thanks for the pointer. I've just tried an implementation of my module using the simpleminded algorithm and I find it's working acceptably quickly, so I don't have the motivation at this point to delve into XS, but I'll keep that in mind for later maybe.

[Moron]

The call stack depth as a whole is not usually what interests me but more often the depth of recursion, which more often corresponds with the depth of something in the input.

In that case it's a simple matter of incrementing a depth counter on entry and decrementing it just before the return, e.g.

sub gettag {
    my $self = shift;
    ($self -> { THIS }{ DEPTH } ||= 0)++;
    my $tagref = { SUBTAG => [] };
    # ...
    while ( !/<\// ) {
        push @{$tagref -> { SUBTAG }},
          $self -> gettag(); # recursive call
    }
    # ...
    $self -> { THIS }{ DEPTH }--;
    return $tagref;
}