Re: [Valgrind-developers] Re: kcachegrind patch for valgrind-HEAD?

[Jeremy F. <je...@go...>]

On Fri, 2002-10-04 at 11:24, Josef Weidendorfer wrote:
> > index % time    self  children    called     name
> > [1]    100.0    0.03    0.23       1+2       <cycle 1 as a whole> [1]
> >                 0.02    0.23       2             A <cycle 1> [3]
> 
> Why isn't "B <cycle1>" shown as child of <cycle1> ?

Because [1] is the entry for "cycle 1 as a whole"; A is considered to be
the head of the cycle (which is then described in [3]).

[2] is the linear part of the call graph to A through main.

> > [Handwave mode:] For the purposes of displaying a profile as a TreeMap,
> > it seems to me that you need to break the graph up into strongly
> > connected subgraphs, and display each of those as a node in your tree.
> 
> The subgraphs being the cycles with its children?

Yes.  "Strongly connected graph" is graph-theory talk for a graph with
internal cycles.  For example:

    A                           A'
    |            -->            |
    v                           v
    B <=> C                    BC'

B <=> C is a simple cycle, and so is a strongly connected subgraph. You
can rewrite the overall graph so that strongly connected subgraphs are
collapsed into a single node.

> I think I'm doing exactly this: Stop drawing at recursions...
> And the problem is: I don't know what the cost of the recursive function 
> should be. I don't have the gprof results, but only my own logging.
> I think I will have to dive into gprof algorithms a little bit...
> As I understand at the moment, gprof never talks about recursive calls, but
> makes "cycles" with subobjects.

http://citeseer.nj.nec.com/graham82gprof.html should explain the
algorithm.

	J