How Quantify handles recursive functions

If a function does not call itself, the percentages listed in Contributions from descendants plus the function time itself, as a percentage of the function+descendants time, equals 100 percent. If the function calls itself recursively, the percentages displayed in the Function Detail window can exceed 100 percent. Although Quantify avoids double counting during arbitrarily complicated calling sequences, the Function Detail window can only display the contributions from all calling sequences in terms of the immediate descendants of those calling sequences. It cannot display the separate contributions from each unique calling sequence.

This display limitation is rarely a problem, since recursive calls occur infrequently. Quantify helps to identify these potentially confusing situations by reporting when a recursive call is made to a function by one of its descendants and marking these descendants with an asterisk (*). Quantify also displays a warning dialog when showing the first recursive function in the Function Detail window.

To understand why the combined percentages might exceed 100 percent, consider this function calling sequence:

In this sequence, function A calls itself through a call to B. The calls are shown as A1 and A2. The function time required by each function call is listed under each function name.

Quantify adds the call times for both of these calls and reports this value as the function time of A: 32 + 32 = 64 cycles. All other functions were called once, so their function times are the same as the call times.

In Quantify, no function is considered its own descendant. When a function calls itself, Quantify records only the subsequent call's contribution to the function time and does not double-count that time when distributing the counts as the contributions to its callers.

The total function+descendants time for A is its function time (64 cycles) plus the call times of all other descendants (17 + 23 + 14 = 54 cycles), which in this case is 64 + 54 = 118 cycles.

The Function Detail window for A shows:

Quantify does not list A as either a caller or descendant in this example. Quantify only shows the immediate callers and descendants of a function in the Function Detail window. If A had called itself directly, Quantify would have listed A as both a caller and a descendant. Notice the asterisk next to B indicating that a recursive call to A was made through the call to B.

The Distribution to callers shows 100 percent of the function+descendants time of A distributed to main. This makes sense since the time from everything to the right of main in the call graph comes from strict descendants of main.

The Function Detail window also shows a percentage of A's time distributed to C. This is because the second call to A distributed both D's time and its own time to C, since both A and D are strict descendants of C.

Turning next to the contributions from immediate descendants, computing the sum of the contribution percentages plus the function time as a percentage of the function+descendants time of A yields: 54.23% (64/118) + 45.76% (contribution from B) + 11.86% (contribution from D) = 111.85%. To understand why this happens, observe that B contributed time to A that includes B's own time plus C and D's time but, by Quantify's rule, does not include time from the second call to A.

In addition, A also received time directly from D, via the A2 call. In fact, the time contributed from D happens to be the same contribution from D that is included in the contribution from B.

Although it might appear that Quantify is double counting, in fact it is only double-displaying the contribution from D, not A. The first contribution is reported from the immediate call from A2 to D. The second contribution is reported when D's time is included with the time from B and C, but not from A2, as the contribution to A via the immediate call to B.

Consider the following call sequence:

In this sequence A still calls itself through a call to B. However, the first, not the second, call to A makes the call to D.

The total function time for A in this case is 36 + 29 = 65 cycles and the function+descendants time for A is 65 + (17 + 27 + 14) = 123 cycles. The Function Detail window for this calling sequence is:

The immediate calling relations are identical to the previous version. Function A still calls B and D and is called by C and main. B is still marked with an asterisk because A was called recursively through that call. In this case, however, the percentages add up to 100 percent: 52.85% (65/123) + 35.77% (contribution from B) + 11.38% (contribution from D) = 100.00%.

This is because D was not called by the recursive call to A. This critical difference in the calling sequence means that D's time is not displayed twice via A's call to B, as it was in the first call sequence.