com.arsdigita.developersupport
Class CallTree

java.lang.Object
  extended bycom.arsdigita.developersupport.CallTree

public final class CallTree
extends Object

A debugging tool that helps you capture call sites of a method.

To elaborate, suppose you have a method foo() that is called from many different places in your code. You'd like to know what foo callers are and how frequently foo() is called.

One possible way to do this is to capture the stack trace every time foo() is called. Like so:

   public void foo() {
       Thread.dumpStack();
       // or, better:
       Logger.getLogger("foo").debug("foo called", new Throwable());
   }
 

The problem with this approach is that if foo() is called one thousand times, you'll get 1000 stack traces that need to be aggregated and analyzed.

This class essentially performs such aggregation for you. To switch to a concrete example, consider the reduce(String) method in PNSystem.java. If we want to figure out this method's callers (and its callers' callers), we would instrument it as follows.

  1. Instrument the entry point into the program.

    In this case, the natural entry point is the run method.

       public void run() {
           CallTree tree = CallTree.getThreadLocal();
           tree.start(4); // peek 4 levels deep into the stack
           if ( checksOutOK() ) {
              ...
           }
           log(tree.upsideDown(0)); // show all execution paths
       }
    
     
  2. Instrument the studied method.

       private String reduce(String str) {
           CallTree.getThreadLocal().capture("reduce");
           ...
       }
     

With this instrumentation in place, running the program would yield the following output.

 $ java -classpath $MYCP PNSystem 1000100101 0111011010

 thread1: 0111011010 --> loops starting with 011011101110100 at position 31
 with a period of 6. (Rule 1 applied 13 times, Rule 2 applied 18 times.)
 reduce
  32: PNSystem.reduce(PNSystem.java:109)
   1: PNSystem.run(PNSystem.java:82)
    1: java.lang.Thread.run(Thread.java:479)
   13: PNSystem.rule1(PNSystem.java:133)
    13: PNSystem.reduce(PNSystem.java:125)
     1: PNSystem.run(PNSystem.java:82)
     7: PNSystem.rule2(PNSystem.java:138)
     5: PNSystem.rule1(PNSystem.java:133)
   18: PNSystem.rule2(PNSystem.java:138)
    18: PNSystem.reduce(PNSystem.java:127)
     7: PNSystem.rule1(PNSystem.java:133)
     11: PNSystem.rule2(PNSystem.java:138)

 thread0: 1000100101 --> loops starting with 011011101110100 at position 25
 with a period of 6. (Rule 1 applied 10 times, Rule 2 applied 15 times.)
 reduce
  26: PNSystem.reduce(PNSystem.java:109)
   1: PNSystem.run(PNSystem.java:82)
    1: java.lang.Thread.run(Thread.java:479)
   15: PNSystem.rule2(PNSystem.java:138)
    15: PNSystem.reduce(PNSystem.java:127)
     1: PNSystem.run(PNSystem.java:82)
     5: PNSystem.rule1(PNSystem.java:133)
     9: PNSystem.rule2(PNSystem.java:138)
   10: PNSystem.rule1(PNSystem.java:133)
    10: PNSystem.reduce(PNSystem.java:125)
     6: PNSystem.rule2(PNSystem.java:138)
     4: PNSystem.rule1(PNSystem.java:133)
 

Several observations can be made. By passing two arguments to PNSystem's main method, we start two separate execution threads. Our CallTree class keeps track of these two threads separately. Hence the two separate call tree traces. To remind users of the fact that stack trace gathering is scoped to the current thread, the method name for obtaining an instance of CallTree is called getThreadLocal().

Let's examine the first trace. The trace is structured as a tree, with child nodes indented relative to their parent node. Each node in this tree is a call site, prefixed with the number of times this call site has been reached. The children of a node are its callers. The number of times a call site has been reached is the sum total of the numbers of times its immediate child nodes have been reached. This invariant holds at all levels of the tree (but see the caveat below).

For example, the first line says that the reduce method has been called 32 times: once from main, 13 times from rule1, and 18 times for rule2.

You may sometimes observe seeming violations of the above invariant due to the following reasons. You can limit the depth of captured stack traces. That's what the tree.start(4) call does in the above example.

If you want to trim down the aggregated tree to only show the most frequent callers, you can pass an integer parameter to the upsideDown(int, int) method, telling it to filter out those callers that account for less than the specified percentage of calls. In the above example, we called tree.upsideDown(0). This essentially tells CallTree to display all execution branches.

Had we specified tree.upsideDown(50), the output would have looked like so:

 $ java -classpath $MYCP PNSystem 1000100101 0111011010
 thread1: 0111011010
 reduce
  32: PNSystem.reduce(PNSystem.java:109)
   18: PNSystem.rule2(PNSystem.java:138)
    18: PNSystem.reduce(PNSystem.java:127)
     11: PNSystem.rule2(PNSystem.java:138)

 thread0: 1000100101
 reduce
  26: PNSystem.reduce(PNSystem.java:109)
   15: PNSystem.rule2(PNSystem.java:138)
    15: PNSystem.reduce(PNSystem.java:127)
     9: PNSystem.rule2(PNSystem.java:138)
 

This doesn't show any execution paths that account for less than 50% of calls to their parent nodes.

Let's switch gears one more time.

If you are using this class to debug web applications, what would you use as an entry point for instrumentation? One good candidate is the BaseServlet's internalService method.

This class is meant to complement rather than replace "real" profilers such as OptmizeIt or JFluid. Once you've found a hot spot with a profiler, you can instrument it with CallTree in order to get an aggregated snapshot of your program's execution paths that lead to the hot spot.

This API is subject to frequent change and should only be used for transient debugging sessions.

Since:
2004-02-09
Version:
$DateTime: 2004/04/07 16:07:11 $ $Revision: #16 $
Author:
Vadim Nasardinov (vadimn@redhat.com)

Nested Class Summary
static class CallTree.Guard
           
 
Method Summary
 void capture(String siteName)
          Captures the current stack trace for later display.
 void end(CallTree.Guard guard)
          Stops the stats gathering process.
static CallTree getThreadLocal()
          Returns an instance scoped to the current thread.
 String rightSideUp(int relativeThreshold, int absoluteThreshold)
           
 CallTree.Guard start(int maxDepth)
          Specifies the maximum depth to which captured stack traces should be examined.
 String toString()
           
 String upsideDown(int relativeThreshold, int absoluteThreshold)
          Returns an aggregated, printable view of the stack traces captured via capture(String).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Method Detail

getThreadLocal

public static CallTree getThreadLocal()
Returns an instance scoped to the current thread.


start

public CallTree.Guard start(int maxDepth)
Specifies the maximum depth to which captured stack traces should be examined. For example, if you specify 10 and the actual stack trace captured by capture(String) is 20 levels deep, then half the stack trace will be discarded.

Returns:
a guard object to protect against reentrant calls. Hold on to the return value, because you will need to pass it to end(CallTree.Guard).
Throws:
IllegalArgumentException - if maxDepth < 1
See Also:
end(CallTree.Guard)

end

public void end(CallTree.Guard guard)
Stops the stats gathering process.


capture

public void capture(String siteName)
Captures the current stack trace for later display.

Parameters:
siteName - a short, human-readable name for the call site at which the stack trace is captured
Throws:
NullPointerException - if siteName is null.
See Also:
upsideDown(int, int)

toString

public String toString()

upsideDown

public String upsideDown(int relativeThreshold,
                         int absoluteThreshold)
Returns an aggregated, printable view of the stack traces captured via capture(String). To display all captured execution paths, pass in 0 as the threshold. To display only those call sites that account for, say, 25% of calls to their callee, pass in 25. The greater the threshold, the more trimmed down the resulting tree.

Parameters:
relativeThreshold - if a node's subtree accounts for less than relativeThreshold percent of the node's number of calls, this subtree is filtered out of the tree rendering.
absoluteThreshold - works similar to relativeThreshold. If a node accounts for fewer than absoluteThreshold calls, the node and its subtree are filtered out. Pass in Integer.MAX_VALUE if you don't want to filter by absoluteThreshold.
Throws:
IllegalArgumentException - if relativeThreshold < 0 || relativeThreshold > 100 || absoluteThreshold < 1.

rightSideUp

public String rightSideUp(int relativeThreshold,
                          int absoluteThreshold)
See Also:
upsideDown(int, int)


Copyright (c) 2004 Red Hat, Inc. Corporation. All Rights Reserved. Generated at July 21 2004:2337 UTC