On Monday 11 July 2011, John Reiser wrote: > >> 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? > > If $pc is in C, and the next return address is in A, then there is > an arc A ==> C which should be charged (billed) accordingly.
This is key here: callgrind tries to come up with a sensible dynamic call graph for the execution of a program. A call graph does not have arcs for returns. Call graphs assume perfect nesting of function calls. In contrast, return arcs appear in control flow graphs, which are out-of-scope for callgrind. Obviously, call graphs only can represent limited control flow behavior, e.g. you can not represent tail recursion, longjmps, exception handling or co-routines. With tail recursion, longjmps and exception handling, callgrind tries to come up with sensible approximations. With co-routines, callgrind will blow up ;-) Call graphs are interesting for performance analysis because you can reason about the "inclusive" cost of a function call, thus allowing to have a nice top-down view of where performance cost was spent. Regarding above example, the call graph "A ==> B ==> C" is perfectly fine: the cost of C will be attributed to inclusive cost of B, because execution of C was a result of calling B. It does not matter whether the compiler was able to do tail recursion optimization or not. Call graphs are used since ages for that, such as in gprof. The IMHO most useful visualizations in KCachegrind are based on call graphs. Also, for performance analysis using call graphs, it does not really matter whether callgrind reconstructed direct recursion or just found a loop inside a function: the inclusive cost will be the same. So if we come back to were we started in this thread: "--ct-verbose=1" actually just prints out debugging information showing the approximations callgrind comes up with, to build the call graph. And that probably was the main misunderstanding. > > 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. > > Tail recursion necessarily introduces the concept of continuation. On the level of machine code, yes. But in the context of performance analysis, it does not matter. The incorrectly visualized additional returns have zero cost. > Trying to hide continuations causes problems, as you have noticed. It's a trade-off. Whether one can neglect continuations depends on the use-case. For performance analysis with languages such as C/C++, I think that is the case. 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
