On Monday 11 July 2011, John Reiser wrote: > ... > >> Adopting the "subroutine outlook" also favors a loop over recursion. > >> The "subroutine outlook" knows only what is [scheduled] to be done > >> in the future; what has happened in the past is not relevant and > >> cannot be known. Thus the current recursion level always equals > >> the number of pending return addresses. The disadvantage is that > >> traceback "through" a tail recursion elides some names, in much the same > >> way that visible state at a debugger breakpoint shows only the _next_ > >> instruction to be executed, and not the previous instruction pointer. > > > > Sorry, I don't get your point here. > > The point is: if the number of pending return addresses does not change > then the recursion depth does not change, so don't change the indentation > when printing the nesting. In particular, if consecutive lines of the > nesting display would designate the same subroutine with the same number > of return addresses pending on the stack, then it's a loop and not > a [full] recursion.
>From my example in my last mail, you can see that a recursive implementation can produce the same code as a loop-based one. So you can never say with certainty that some machine code was programmed as a loop. Up to now, Callgrind tries to reconstruct what the programmer has coded. Which means that it tries to reconstruct recursive behavior even when the compiler did tail recursion optimization (and the number of pending returns do not change). I see that your main criteria is: "if the number of pending returns doesn't change, it is a loop". The problem is highlighted exactly with your example: > Consider the source-code call chain A ==> B ==> C where B ==> C is > a tail recursion which the compiler recognizes and implements. During > execution of C, then the actual dynamic _return_ chain is C ==> A. Typo: "A ==> C". > B has been erased by the tail recursion. The stack contains no record > of B ever having been invoked. So the effective dynamic call chain > [backtrace] at this point is A ==> C. This is impossible to represent in one single call graph for the execution of the program. C is either called from B or from A. The latter would mean an abstract return from B to A before A calls C. This of course is possible, but as you say yourself: > This may surprise the programmer > who never wrote any call from A to C, but this is much the same as > stopping at a breakpoint immediately after a taken branch. > You know where you are [$pc], and where you're going (the backtrace of pending > _return_s), but not every detail of how you got here (taken branches > or tail recursions are not known.) But you simple can not compare it with debugging, as Callgrind wants to come up with that single call graph. For this call graph, I much prefer Callgrind to use "A ==> B ==> C". The whole point of Callgrind/KCachegrind is to present performance metrics attributed to call graphs in a top-down way. Your suggestion seems incompatible to that goal. > > There is a similar scenario: machine code can have jumps between > > functions (e.g. as result of a tail recursion optimization, or hand crafted > > assembler). Callgrind output is about call relationship. There is no way > > to reason about jumps between functions. Thus, callgrind has to map a > > jump between functions either to a "call" (with an additional return when > > returning from the function jumped to) or a "return/call" pair. > > It is better to think of this as a _continuation_, for which > some programmers might use the idea of "return+call" as a crutch > until they become familiar with continuations. In many cases > it is important to realize that a principle side effect during > execution is the dynamic writing of the program which constitutes > the continuation from the current subroutine. Of course, this > "program of continuations" is the stack. And how to map this to a call graph? Do you suggest introducing nodes which are continuations of multiple functions? I think this would be even more confusing, as regular programming languages do not allow to code continuations, so programmers usually don't know this concept. Josef ------------------------------------------------------------------------------ All of the data generated in your IT infrastructure is seriously valuable. Why? It contains a definitive record of application performance, security threats, fraudulent activity, and more. Splunk takes this data and makes sense of it. IT sense. And common sense. http://p.sf.net/sfu/splunk-d2d-c2 _______________________________________________ Valgrind-users mailing list Valgrind-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/valgrind-users
