 |
» |
|
|
|
When procedures in a program are recursive, the call structure at run
time (the dynamic call structure) can be more complex than the order of procedure
calls that is apparent before run time (the static call structure). The
Recursion Collapsing area of the Call Tree Analysis (Textual) window allows
you to specify how, if at all, you want Puma to collapse its reporting of
recursive routines.
Recursion Collapsing | |
A program with recursion can have a deceptively large call tree.
Showing the many paths to a given routine might give you more
information than you need while obscuring important patterns of
recursion.
Suppose, for example, you have a routine named main which calls
routine r; routine rcalls itself recursively to Level 3, and
r calls routine s. If you got one sample from each of the
possible stack traces, you would have the following:
main r
main r s
main r r
main r r s
main r r r
main r r r s
|
A straight hierarchical analysis might look like this:
Samples Samples
In or Under In Only
Raw Count Raw Count Level
----------- --------- -----
6 0 1 main
6 1 2 r
1 1 3 s
4 1 3 r
1 1 4 s
2 1 4 r
1 1 5 s
|
(This analysis uses the raw countfor clarity; the
percentage or parent percentage would not reflect a strictly
accurate picture, as the percentages are approximations. The
in-only raw counts of the nested procedures add up to the
in-or-under raw count of 6 for main.)
This analysis, although correct, does not properly summarize the
program's behavior. It does not show that three of the six
stack traces are of the form main [r...] r and three are of the
form main [r...] s. Recursion collapsing remedies this. When
you request recursion collapsing, Puma does not make a new node
in a tree of call chains if it encounters a recursive call.
Instead Puma creates a recursive stub that represents the
recursion and refers to the place higher up the call chain where
the same routine occurs. Puma then jumps up in the tree to that
point and continues playing out the stack trace. In effect, call
chains are truncated. The following sample analysis presents a
collapse of the recursion in the earlier example.
Samples Samples
In or Under In Only
Raw Count Raw Count Level
----------- --------- -----
6 0 1 main
6 3 2 r
1 (2) 3 3 s
3 r...
|
The first line of this analysis is the same as the earlier one.
The second line, for r, shows all three main [r...] r calls
attributed in the in-only column to r, since levels have been collapsed.
The third line shows three samples attributed to s. The
notation 1 (2) indicates one sample at this level and two at
lower levels. In other words, there were three stack traces that
passed through this point in the tree; one got there directly
through the ancestors as shown, while two got there after some
skipping through the recursive stubs. Note that only in-or-under
data is split up according to whether recursive stubs were
traversed; the in-only data is not. The fourth line, r...,
represents the recursive stub. It indicates that the parent
routine (r at Level 2) called the child (r at Level 3), and a
stub was built pointing up to the parent.
Puma Recursion Collapsing Options | |
There are four degrees of recursion collapsing to choose from in
a Puma analysis. They are, in order of increasing presence of
recursion collapsing:
- No collapse
Performs no recursion collapsing.
- Direct collapse
Performs recursion collapsing for direct
recursion (that is, if a routine calls itself directly).
- Conservative collapse
Performs recursion collapsing unless doing
so would omit any routine names out of the call chain.
- Full collapse
Performs recursion collapsing whenever it
encounters a routine for which there is a higher instance in the
call tree.
As its name implies, the No collapse option causes Puma to perform no
recursion collapsing at all. In the example above, No collapse would produce
the first of the two analyses.
The Direct collapse option indicates that a recursive stub
should be used only for direct recursion, that is, only if the
prior instance of a routine in the call tree is the immediate
parent of the current instance. For instance, the call chain
main a a a b would have a stub built from the second a and
would effectively be collapsed to main a b. However, the call
chain main a b a b would not have recursive stubs built,
because neither the recursive call to a nor the recursive call
to b is direct.
The Conservative collapse option builds recursive stubs in
more circumstances than the Direct collapse. It builds a
recursive stub if doing so would not lose any routine names out
of the call chain; that is, if the routines being cut out are
duplicated higher up in the stack trace. For instance, the call
chain main a b a b would not have a recursive stub built at the
recursive call to a, since the transformation from main a b a
to main a loses the only instance of b. However, it would
have a recursive stub at the recursive call to b, since the
collapsing of main a b a b to main a b loses an instance of
a, but leaves another one. As another example, the call chain
main a b c b a d c would not have any recursive stubs using
Conservative collapse. Building a stub at the recursive second
call to b would lose c; building one at the recursive second
call to a would lose b and c; and building one at the
recursive second call to c would lose d.
The Full collapse option causes a recursive stub to be built
whenever there is any higher instance of a routine in the call
tree. For example, for main a b c b a d c, the call chain
that is discussed above, a stub would be created
from the recursive call to b, and another at the recursive call
to a. There would not be one at the recursive call to c,
because after the other recursive jumps the other instance of c
is no longer higher in the tree. In particular, the analysis
just from this one stack trace would look like the following
example.
Samples Samples
In or Under In Only
Raw Count Raw Count Level
----------- --------- -----
1 0 1 main
1 0 2 a
1 0 3 b
1 0 4 c
5 b...
4 a...
0 (1) 0 3 d
0 (1) 1 4 c
|
|
When Puma encounters the second b in the call chain main a b c
b a d c, it builds a recursive stub (at Level 5 in the
analysis) up to the higher b (at Level 3). It then jumps up to
that b. When it comes to the second a, Puma builds a
recursive stub (the a at Level 4) as a child of the instance of
b at Level 3, and pointing up to the instance of a at Level
2. For d, Puma builds an ordinary node (not a recursive stub).
For the final c (the last line of the analysis), it does not
build a recursive stub, because the first c is not an ancestor
of the current node. The ancestors of the current node are d ,
a (at Level 2), and main (at Level 1). The last two lines
have 0 as their direct value and 1 as their indirect value,
because those nodes were reached only after traversing recursive
stubs. When a node, such as a at Level 2, is reached directly
and then again in the same stack trace through a recursive stub,
the direct arrival counts; that is why these lines have a direct
value of 1.
|
Printable version
