Methods for analyzing dynamic program behavior using user-defined classifications of an execution trace

[0002] 1. Field of Invention

[0003] This invention generally relates to methods for analyzing the execution behavior of software programs. More specifically the present invention relates to methods embodied in software tools by which a user may interactively explore information gathered during a program's execution.

[0004] 2. Prior Art

[0005] Given only a program's source code (its static description), the behavior of the program as it runs (its dynamic behavior) can often be very difficult to predict. Programs often run incorrectly, more slowly, or use more system resources than a programmer expected. Diagnosing these problems, which requires understanding the dynamic behavior of the program, can be a difficult task even for the most experienced programmer.

[0006] Various categories of software tools, such as profilers, debuggers, and program visualizers allow the user to study a program's behavior in different ways. These tools are helpful at times, but they are often ill-suited to both the complexity of the program being analyzed and to the nature of the analysis process. As a result, programmers work slowly with existing tools, construct their own ad hoc tracing schemes in order to analyze a specific problem, or just work “in the dark” much of the time.

[0007] Dynamic behavior may be studied by collecting a program trace for analysis, containing information about events that occurred and resources used during the program run. The analysis may be done after the run has completed, or it may be integrated with the collection process.

[0008] Even relatively simple programs will often involve a lot of internal activity, and more typical programs can generate extremely large and complex traces that can be overwhelming for the analyst to study. As in other fields where large amounts of information are studied, analysis tools must provide ways to organize the information: to filter out irrelevant information, and to group related information so that fewer, higher-level units may be studied. These organizing abstractions may then be used to compute summary measurements, or for structuring or rendering elements in visualizations.

[0009] Because of the complexity of programs, a central problem when analyzing their behavior is that information of interest is often intertwined with unrelated information. The problem may manifest itself as visual clutter in detailed graphical views, or as numerical summaries skewed by the inclusion of irrelevant information. In either case, key information needed for analysis can remain hidden without the right organization. The choice of organizing abstraction at each step in an analysis is crucial for enabling the user to work with the information productively.

[0010] A number of organizing abstractions are currently provided by various tools, and have proven useful for many situations. These include organization based on static units, for example threads, classes, methods, and instances when analyzing a Java program, and certain types of organization based on dynamic information, such as call trees and patterns. There are many important cases, however, where the information of interest does not line up with these organizational schemes, and the most appropriate organization will be based on more complex combinations of static and dynamic criteria. Here are a few examples:

[0011] 1. The user would like to study a functional aspect of the program, not represented formally in the static structure of the program, involving a few methods from a number of different classes.

[0012] 2. The user would like to contrast the behavior of the slowest 10% of invocations of a given method with the fastest 10%, to understand the difference.

[0013] 3. The user would like to study only the instances of a given class that were used in a particular way, such as all the Java Vectors that were created in the course of a specific sequence of method calls.

[0014] In general, it is necessary to provide the user the flexibility to filter and group the information as needed for a particular problem being studied. This must be in addition to other, more fixed, organizational schemes, which are also useful. Note that flexibility in organizing the information, while enabling the analysis, potentially introduces additional usability difficulties in specifying complex filtering and grouping criteria. It is important to address these difficulties as well.

[0015] In addition to the complexity of the data being studied, the analysis process is often a long and unpredictable process. The user may or may not know in advance what questions he or she needs answered. The user is just as likely to be searching for clues that will give insight into a problem as trying to obtain answers to precise questions to verify a hypothesis. It is therefore essential for an analysis tool to support many styles of analysis. The user may, for example, use graphical views to gain an overall understanding of the flow of events, discover patterns, or spot anomalies. At other times the user may need to make quantitative comparisons of resource usage. User-defined filtering and grouping units must be usable for all of these types of study.

[0016] Many different types of views will usually be needed within a single study, in order to study a problem from different angles. The user must be able to maintain a consistent context across these various views. This context would include not just different presentations of the same information, but different types of information as well. For example, the user may start by identifying a certain group of instances as an aspect of the execution to study. In one view, the user may then want to see how much time each thread spends on activity related to these instances, and in another view see the detailed sequence of method calls against the instances to understand when and how they are used. It is important that the user be able to maintain a consistent context while working with different types of information. It is important that the user be able to move from one type of information to another, without having to restate complex filtering and grouping criteria.

[0017] Analysis is often a lengthy, experimental process. At a given stage, the user may have a particular focus of study and an organization of the information based on a hypothesis on where the problem may lie. The user may then study the problem within this framework, using various views over various types of information, as discussed above. In the process, the user may make discoveries that will change the course of the investigation. The user may decide, for example, to refine the focus of study, or organize the information differently based on new information. The user may also want to try out a hypothesis, with the ability to backtrack to an earlier stage of analysis if the hypothesis is incorrect. The user may also want to try out multiple alternative analysis paths simultaneously focusing on different aspects or using different organizational schemes and compare the results. In general, it would be helpful for an analysis tool to maintain multiple working contexts for the user, to help structure the larger analysis process.

[0018] An object of the present invention is to enable the analysis of dynamic program behavior for problem diagnosis.

[0019] Another object of this invention is to provide a method that enables the analysis of dynamic program behavior for problem diagnosis, and that is also applicable to other applications of dynamic program behavior analysis, such as program maintenance, testing, and program characterization.

[0020] These and other objectives are attained with a method and system for analyzing dynamic behavior of a computer program using user-defined classifications of an execution trace. The method comprises the step of forming a database describing the executions of the program. The database includes stat information obtained from the program source, and dynamic information describing particular executions of the program. The database is structured into entities, and each of the entities is comprised of a single type of information about the program execution. Each entity is comprised of elements representing individual program elements of said single type, and each element has attributes with values describing the element. The database is augmented by classifying every element of the database as a member of zero or more user defined execution slices; and dynamic behavior of the program is analyzed using the execution slices.

[0021] The preferred embodiment of the invention is for use with a database describing a program's execution, containing both static information (obtainable from the program source) and dynamic information (describing a particular execution of the program). The database is structured into entities, each containing a single type of information about the program execution (for example threads, classes, method invocations). Each entity consists of elements representing the individual program elements of that type (for example, an element may represent an individual thread, class, or method invocation). Each element has attributes with values that describe that element of the program execution. Some attributes are relationship attributes, whose values relate an element to one or many other elements. Some attributes are summary attributes, whose values are aggregations of attribute values from a number of other elements.

[0022] In accordance with the present invention, the user may augment the database by classifying each element of the database as a member of zero or more user-defined execution slices. Each execution slice is based on an arbitrary combination of static and dynamic criteria, and represents an aspect of interest to the user for analysis.

[0023] The set of execution slices serves as an additional dimension with which to access information in the database, independent of the predefined entity structure. Each execution slice may thus be used as a lens through which to access the entire database. This mediated view of the database will have the following properties:

[0024] 1. the structure (of entities and attributes, including relationship attributes) will be identical to the original database structure

[0025] 2. only elements that are members of the given execution slice will be present

[0026] 3. the values of many-valued relationship attributes will vary depending upon the given execution slice

[0027] 4. the values of summary attributes will vary depending upon the given execution slice.

[0028] In effect, summary attributes become multidimensional summary attributes, summarizing information by both an element of the database and an execution slice.

[0029] Execution slices may be arranged as a hierarchy, where the root execution slice contains every element in the database describing the program execution. The elements of each execution slice are a subset of the elements of its parent execution slice.

[0030] Execution slices may be used to filter the elements presented in views. Execution slices may also be used to visually classify the elements presented in a view. Execution slices may also be used to filter the information used as the basis for summary computations. In addition, execution slices may be used to perform comparisons of multidimensional summary information.

[0031] An execution slice (the base) and its immediate child slices in the hierarchy (the subsets) may be used together in a single view to provide a combination of filtering and visual classification. An execution slice (the base) and its immediate child slices in the hierarchy (the subsets) may be used together in a single view to provide comparison of multidimensional summary information of the subsets against the base.

[0032] Recasting rules are introduced to simplify the specification of execution slices. Execution slices are defined by a combination of filtering queries and recasting rules. For a given execution slice, a filtering query on each entity specifies which elements of that entity will be a member of the execution slice. Recasting rules interpret these queries to cause additional related elements to be included in or excluded from the execution slice.

[0033] In addition to allowing the user to specify the query criteria directly, we allow the user to define a set of execution slices by interactively selecting elements of the database. Alternatively, the user may define a set of execution slices by selecting an attribute. The values of the attribute will be used as the basis for classification into a set of execution slices.

[0034] Also disclosed herein is a method for the user to structure and manage a lengthy, experimental analysis process using execution slices. A workspace may be defined consisting of an execution slice (the base) and its immediate children (subsets). Using a workspace, the user can perform an analysis using any number of views, and they will share a consistent information context of these base and subset slices. The base slice is used to set the overall scope by filtering out irrelevant information in each of the workspace's views, while the subset slices are groupings of information within the limited scope of the base slice.

[0035] The user may work with multiple workspaces simultaneously, allowing multiple experimental contexts to be maintained.

[0036] The user may select a number of elements in one view, and navigate to other views to study related elements. A temporary execution slice is used to automatically recast the information for presentation in views over related information.

[0037] Further benefits and advantages of the invention will become apparent from a consideration of the following detailed description, given with reference to the accompanying drawings, which specify and show preferred embodiments of the invention.

[0038] FIG. 1 is a diagram of the data model used in a preferred embodiment of the invention.

[0039] FIGS. 2-5 identify and describe various entities and attributes that may be used in the practice of this invention.

[0040] FIG. 6 lists a set of recasting rules that may be used in the present invention.

[0041] FIG. 7 illustrates the architecture of a visualizer that may be used in this invention.

[0042] FIG. 8 outlines a procedure for the validation of an execution slice.

[0043] FIGS. 9, 10 and 11 show an execution slice membership algorithm.

[0044] FIGS. 12 and 13 show an algorithm to compute membership of invocations in an execution slice.

[0045] FIGS. 14-17 show an algorithm to compute and save stored summary attributes.

[0046] The Java program being analyzed (the target program) is run using a specially instrumented Java Virtual Machine (JVM) which produces trace information. The user studies the program's behavior using a visualizer, which loads the trace information and presents to the user various interactive views for exploring the information. The trace information may be saved in a file for later analysis, or it may be sent over a live connection to a visualizer for analysis while the target program is running. With respect to the functionality described herein, the operation of the visualizer is identical in either case.

[0047] The trace consists of two broad types of information: event traces and memory snapshots. An event trace contains method call and return, class load and unload, object creation and garbage collection, and thread creation and termination information. A memory snapshot contains information about the existence and identity of objects and the references among them, at a given moment in time chosen by the user. The user has control over generating only a subset of the trace information for a given run of the target program.

[0048] As the information is loaded into the visualizer, it is converted into a database of information that is used in the various views and analysis features of the visualizer. The conceptual structure of the database, the data model, is described below. The following terminology is used herein to describe the database:

[0049] An element describes a single element of the target program execution, such as a Java class, class instance, method, method invocation, thread, or package.

[0050] An entity is a collection of the same type of element (i.e. all having the same attributes).

[0051] An attribute property of an element. For example, “class name” is an attribute of an element describing a Java class. Each element will have multiple attributes.

[0052] An attribute value is the value of an attribute for a specific element.

[0053] An attribute may be:

[0054] A relationship attribute, referring to one or many related elements (known as a 1-to-1 or 1-to-many relationship, respectively). The elements for a given relationship attribute will all be from the same entity.

[0055] A simple attribute, gathered directly from the trace, or computed from such information from a number of elements related via 1-1 relationships.

[0056] A summary attribute, computed by aggregating information from a number of elements related directly or indirectly via 1-many relationships.

[0057] FIG. 1 shows a diagram of the data model. Entities are drawn as rectangles and relationship attributes are shown as arrows. FIG. 1 shows package 12, classes 14, methods 16, instances 20, invocations 22, and threads 24. FIG. 2-5 describes the entities and attributes in detail. The following terms are used in describing summary attributes:

[0058] Base time of a method invocation is time just in that invocation, excluding anything it calls

[0059] Cumulative time of a method invocation is the sum of time in that invocation and every invocation it calls

[0060] Total base time is the sum of base time spent in a set of invocations

[0061] Total cumulative time is the aggregate of cumulative time spent in a set of invocations. Note that this is not a strict sum of the cumulative times of the individual invocations, but rather it takes into account the fact that methods in the set may directly or indirectly call each other.

[0062] An execution slice is a subset of the database containing zero or more elements of each entity. All information in the database may be accessed through the lens of a particular execution slice, as follows:

[0063] Any element of the database may be classified as being or not being a member of a given execution slice. Note that execution slices may overlap, i.e. each element may be a member of more than one execution slice.

[0064] Attributes of each element are evaluated relative to a given execution slice. The values of some attributes will depend upon the execution slice. These attributes are known as slice-dependent attributes; others as slice-independent attributes. Summary attributes and 1-to-many relationship attributes are slice-dependent; simple attributes and 1-to-1 relationship attributes are slice-independent.

[0065] The value of a 1-to-many relationship attribute relative to a given execution slice consists of the related elements which are also members of the given execution slice. For example, if S is an execution slice containing only methods that are constructors, then evaluating the attribute methods for a class, relative to S, will return all the constructors of that class.

[0066] The value of a summary attribute relative to a given execution slice is determined by aggregating only those elements which both contribute to the summary computation and are a member of the given execution slice. For example, if S is an execution slice containing only methods that are constructors, then evaluating the attribute number_of_calls for a thread, relative to S, will return the number of constructor calls made in that thread.

[0067] All of the execution slices in a visualizer session are arranged as a hierarchy. The execution slice at the root of the hierarchy contains all of the information collected from tracing the target program.

[0068] The content of an execution slice is determined as follows:

[0069] 1. An execution slice contains a subset of the elements of its parent execution slice

[0070] 2. the content of an execution slice is further restricted by the following:

[0071] Queries, one per entity, which define filtering criteria for the entity, based on static and dynamic attributes of this and related entities.

[0072] Recasting rules, which determine how the queries are extended over related information.

[0073] Note that an execution slice's content is determined by its queries and rules, but these concepts are not necessarily visible to the user defining the content of a particular execution slice.

[0074] A query specifies the filtering of the elements of a particular entity. A query is a Boolean expression that combines query expressions with the operators NOT, AND, OR, and grouping using parentheses.

[0075] Each query expression takes the following form:

[0076] <attribute> [<operator> <operands>]

[0077] where, <attribute> is any attribute of the entity associated with the query, the optional <operator> is an operator appropriate for the datatype of the attribute, and <operands> are determined by the <operator>.

[0078] The following are the operators appropriate for each type of attribute:

[0079] The following are the operands appropriate for each operator:

[0080] A subquery takes the same form as a query, and may appear as the operand of a WHERE operator within a query expression over a relationship attribute. For a 1-to-1 relationship, the WHERE operator evaluates to true if the subquery evaluates to true for the single related element. For a 1-to-many relationship, the WHERE operator evalutes to true if the subquery evaluates to true for at least one of the related elements.

[0081] When a slice-dependent attribute (i.e. a summary attribute or a 1-to-many relationship attribute) appears in a query expression, its value is determined using the parent slice of the slice in which the query appears.

[0082] Recasting rules, shown in FIG. 6 determine how the filtering criteria of queries on each entity will be applied to related information in that and other entities. The purpose of these rules is to allow the user to specify filtering criteria simply, and have the system fill out more detail of the criteria, for common analysis tasks. Some of these rules are restrictive rules, further filtering out information, while others are inclusive rules, causing additional elements to be added to the execution slice. The system provides a fixed set of rules. Each rule may be individually enabled or disabled by the user for each execution slice.

[0083] The recasting rules interact with each other and with the query evaluation. In this description, we label rules and query evaluation with step numbers, to illustrate the order of evaluation required to achieve the proper result. Note that these are functional but not necessarily actual steps; the implementation optimizes the process in various ways. Evaluation of queries on each entity is step 1.

[0084] A workspace may be defined over an execution slice (known as the workspace base) and its immediate children (subsets) in the hierarchy of execution slices. Using a workspace, the user can perform an analysis using any number of views, and they will all share a consistent information context of base and subset execution Slices. The user may work with multiple workspaces simultaneously. By default, the visualizer creates an initial workspace whose base slice contains the entire database of trace information.

[0085] Slice Specification Techniques

[0086] We provide various techniques for specifying execution slices, with the goal of allowing the user great flexibility in their definition in a way that is easy to use for common analysis tasks. Execution slices are defined by a combination of filtering queries and recasting rules. The recasting rules take the place of potentially complex query criteria for the most common cases. This is particularly important since a single execution slice will span all types of information (i.e. all the entities) in the database. The recasting rules help the user study different types of information as they pertain to the execution slice without having to restate the query criteria over each type of information.

[0087] We provide the user a fixed set of predefined recasting rules. When the user first creates an execution slice, a subset of the rules is enabled for that execution slice by default. The user may adjust the specification of the execution slice by enabling or disabling individual rules.

[0088] The query portion of the definition may be specified in one of three ways. The above discussion of recasting rules applies in all three cases.

[0089] One way to specify an execution slice is to interactively select elements of interest from any of the views. The system will automatically construct query criteria that match the selection. Static structural elements such as classes and methods, as well as dynamic elements such as individual instances or method invocations may be chosen as the basis for an execution slice. Elements may also be selected for exclusion from an execution slice. This is useful for filtering out cases known to be outliers. For example, if we are studying a method that is invoked many times, we may want to exclude the first invocation if it is much more expensive due to initialization costs.

[0090] Attribute values can be useful as dimensions for categorizing information. For example, to analyze a method with many repeated invocations, we can categorize each invocation based on its base time as being slow, medium, or fast. If we create an execution slice for each of these categories, we can then compare the slow and fast cases from various angles to understand what is causing the slow cases. Similarly, to diagnose a complex memory leak in a long-running application, we can classify the objects into a number of distinct periods by creation time. We could then define an execution slice for each of these groups of objects, to measure the memory used per class during each time period. To define a set of execution slices based on values of an attribute, the user may select the attribute, and the system will group the values of the attribute into buckets. The user is presented with a number of options to control how the buckets are determined. The system will automatically create an execution slice for each bucket, with query criteria that correspond to that bucket.

[0091] To specify more complex criteria the user may specify the queries directly using an interactive query editor. The user may create new execution slices from scratch using this editor, or use it to fine tune the filtering criteria of execution slices created in other ways. Note that the query editor does requires more knowledge of the data model and some database concepts than the other specification techniques. However, since the recasting rules still apply, the specification is still much simpler than it would have been with a pure query-based approach.

[0092] Analysis Techniques Using Execution Slices

[0093] Execution slices may be used in views in a number of ways: for filtering information, for visual classification of information, and as a basis for multidimensional computations, as we describe below. All of these techniques may be used, separately or in combination, in various ways in different types of views to allow the user to perform higher-level analysis tasks, such as making visual and numerical comparisons, spotting patterns, trends and exceptions, discovering correlations, and verifying hypotheses.

[0094] An execution slice may be used in views to filter the elements which will appear. For example, in a tabular view where each row shows information about a class and each column is an attribute of that class, an execution slice that contains only a few classes may be used to filter this view to show only the rows for those particular classes. The purpose of filtering elements is to remove extraneous information so the user can focus on a particular set of information. In some views, it makes sense to still render the elements that are filtered out, but render them in such a way (for example, in a faintly visible color) that they don't distract the viewer from studying the elements of interest.

[0095] An execution slice may also be used to filter the information on which summary computations are based. For example, a view showing information about the total cumulative time spent in method calls on each instance may compute this attribute relative to a particular execution slice.

[0096] A set of execution slices may be used to visually classify information. For example, given a set of execution slices representing different functional areas of a program, a graphical view showing the detailed sequence of method invocations may color the invocations based on membership of each invocation in one or more execution slices. Note that coloring is only one technique for visually classifying information. Other visual aspects of a view, such as the placement of graphical objects in a layout, could be based on execution slice membership as well.

[0097] A set of execution slices may be used to display multidimensional summary attributes. For example, in a tabular view where each row shows a class, and each column represents one of the execution slices, each cell may show the value of an attribute for a particular class relative to a particular execution slice. This allows the user to compare measurements across both user-defined and predefined dimensions.

[0098] In a view containing a base execution slice and a number of subset execution slices which are children of the base in the execution slice hierarchy, we may combine the above techniques in a number of ways. We may use the base for filtering elements which appear in the view, and visual classify the remaining elements according to their membership in the base and subset execution slices. This allows the user to filter out irrelevant information, and see the remaining information classified according to user-defined groupings.

[0099] We may also present quantitative information in a view containing a base execution slice and subset execution slices, as follows. The view may show multidimensional summary attributes computed relative to the base and each of the subset slices. This allows the user to filter out extraneous information and compare the remaining information not just among the user-defined groupings, but of each grouping against the base. For a given element, such a view may show a summary attribute value relative to one of the subsets as an absolute number or as a percentage of the corresponding value computed relative to the base.

[0100] Analysis With Multiple Views

[0101] The user may work with multiple views simultaneously, where the views may show the information in different ways, show different elements, or show different types of elements. All of these views may use a common set of execution slices, in the various ways described above, allowing the user to study a set of user-defined aspects of the program execution from various angles.

[0102] The user may interactively select a set of elements in one view, and “drill down” to another view of related information. The system automatically constructs an execution slice that recasts the selected information into its new form. This execution slice is automatically used as the basis for filtering elements in the new view.

[0103] Supporting the Larger Analysis Process

[0104] Program analysis can be an iterative, experimental process. We introduce workspaces to explicitly address the needs of this larger process. A workspace allows the user to set up a filtering and grouping framework for a given stage of analysis. This framework may then be used to explore many aspects of the program execution, without requiring the user to restate the framework in each view. A workspace is composed of a base execution slice establishing the scope of the study, a set of execution slices which are subsets of this base in the hierarchy of execution slices, and any number of views which may make use of these execution slices. The workspace also provides consistent visual cues for the execution slices across multiple views, by assigning each execution slice a color for its use across all views in the workspace.

[0105] The system allows multiple workspaces to be active concurrently, supporting a number of common analysis scenarios. One such scenario is progressive refinement, where the user is iteratively narrowing a problem down to a smaller and smaller area that appears to be the likely cause. This can be an experimental process in which the user may need to backtrack. Workspaces may be used to save the state at each stage of refinement. An important special case of progressive refinement is where the user has created execution slices grouping information according to alternative hypotheses about where a problem might lie. To study one of these areas in more depth, the user can open a new workspace whose base is one of these execution slices. The user could then continue to break this area of activity down along some other lines by defining execution slices relative to this new workspace's base.

[0106] In another scenario, the user may not know in advance what the right organization of information is that will illuminate the cause of a problem. He or she may want to explore multiple hypotheses simultaneously, and compare results of the same information analyzed along different lines, using views from two different workspaces.

[0107] The visualizer is built entirely in Java. FIG. 7 shows the architecture of the system 100, identifying major areas of functionality, each comprised of various components. The major areas of functionality of the visualizer are discussed below.

[0108] A system-wide event notification mechanism handles some of the communication among components. A component may broadcast any type of event, and may register to receive specific types of events.

[0109] The transceiver 104 reads the trace information from a file, or from a live connection to a JVM running the target program. The transceiver parses the trace information and issues calls and events which cause the database 106 to be populated.

[0110] The database 106 is a custom-designed in-memory database of program information. Each entity in the data model is represented as a Java class, and each element in the database is represented as a Java object of one of these classes. Herein, we refer to each of these Java classes by prepending a “J” to the type of element, e.g. JThread is the class representing a target program thread. Each adheres to the data interface, providing the following functions:

[0111] 1. storage and retrieval of execution slice 110 membership information for each object,

[0112] 2. access to a data wrapper 112 formalizing access to the objects of the class (see below)

[0113] Each of the database classes provides for either storage or on-demand (“lazy”) evaluation of its attribute values. Relationship attributes are represented as single Java references for 1-1 relationships, or as a set of Java references for 1-n relationships. Relationship attributes for the root execution slice, representing the original trace, are stored explicitly in the database objects. Slice-dependent evaluation of 1-n relationship attributes is performed on demand; these values are not stored in the database.

[0114] There is a thin data wrapper class for each entity, allowing formal database-style access to Java objects. The data wrappers enable dynamic access to attributes for such purposes as query evaluation, presentation, and sorting. Each attribute is assigned a unique identifier, a constant determined at compile time of the visualizer. At run time this identifier may be used to obtain description information about an attribute, such as its name, its Java datatype, whether it is slice-dependent, and whether it should be cached by higher levels because its value is expensive to retrieve. An attribute identifier is also used to obtain an attribute value for a given element relative to a given execution slice. Note that this approach does not rely on Java reflection or introspection mechanisms, and therefore avoids their performance cost. Note also that there are many features of the visualizer that do not require formal access to the data; these features access the database objects' Java methods directly.

[0115] The execution slices provide query evaluation, membership evaluation, and calculation of most summary attribute values (described in detail below). There is also a data wrapper for execution slices themselves, allowing the attributes of execution slices to be presented in various views as if the execution slices themselves were an entity.

[0116] Data tables 114 provide an intermediate level of data management needed by some of the views 116. A data table manages data from the database for a view in progress, and provides a programming interface to access the data as a set of rows (elements) and columns (attributes). Data tables provide:

[0117] 1. row filtering, so a view may display a subset of an entity's elements,

[0118] 2. row sorting, by arbitrary columns,

[0119] 3. value caching, if the underlying attribute is expensive to retrieve,

[0120] 4. flattening of combinations (slice-dependent attributes x execution slices) into a single dimension of columns

[0121] Views 116 present the information to the user using various visualization techniques, and provide interaction, as well as navigation to other views. Views access information from data tables, from the data wrappers, and from the database classes directly.

[0122] Workspaces 120 maintain a consistent data context of a base and subset execution slices for a set of views. Each workspace has an associated filter mapping 122 that maintains consistent visual cues (i.e. names and colors) for representing the execution slices in each view in the workspace.

[0123] For a given execution slice, membership information and the values of most summary attributes are computed and saved for the entire database in a process known as validation, which is done before the execution slice can be used. This batch approach is desirable since many of the computations require traversal of all of the calling hierarchies in their entirety. This approach also matches typical usage, where a user will specify filtering and grouping criteria first and then interactively explore the information from many angles using various views.

[0124] With reference to FIG. 8, validation, represented at 140, occurs only as needed for each execution slice, in response to the execution slice's creation 142, a change in its definition 144, or the validation of its parent. For the root execution slice representing the complete trace, validation will also occur after a new batch of trace information has been loaded 146 into the visualizer. Validation 140 itself is done in two phases. First, membership information is evaluated and saved 150. After that, most summary attributes are computed and saved 152. Once validation has completed for the execution slice, a validation event is broadcast. As represented at 154, any filter mapping that uses this execution slice will in turn broadcast an event to inform all views of its workspace to redisplay using the updated execution slice as represented at 156.

[0125] To conserve space and avoid unnecessary computations, the computation of some detailed summary attributes, such as summaries by individual invocations, are not done at validation time, but are postponed until values for specific elements and relative to specific execution slices are needed in a view. Of these attributes that are not stored in the database, the ones that are expensive to recompute are marked as such so that their values can be cached by the data tables of active views.

[0126] Storage of execution slice membership information is distributed throughout the database. Each Java object representing a database element has a bitmap describing which execution slices it belongs to. This element-centric rather than slice-centric representation matches the usage of the system, where the user is typically asking about a specific element as seen through the lens of various execution slices. This enables fast computations of membership for a given element, needed for computing summary values, coloring views based on membership, and supporting the hierarchy of slice filtering. This approach is space-efficient as well, since we expect the number of execution slices in a given analysis session to be relatively small, for example, on the order of tens, or hundreds.

[0127] FIGS. 9-13 show the algorithm for computing membership information for the entire database relative to a given execution slice. The algorithm takes advantage of recasting rules to optimize certain common usage cases. All of the rules are incorporated into the algorithm with just a single pass traversal of each of the calling trees. The various parts of the algorithm are shown in FIGS. 9-13. In particular, FIGS. 9, 10 and 11 show the execution slice membership algorithm, and FIGS. 12 and 13 show the algorithm to compute membership of invocations in an execution slice.

[0128] Query Evaluation

[0129] Evaluation of a query against an element consists of evaluating the boolean combination of query expressions against that element. For query expressions containing a subquery on a 1-1 relationship attribute, the subquery is evaluated against the element obtained by navigating the relationship (i.e. the attribute value). To evaluate a subquery on a 1-n relationship attribute, the related elements (i.e. the attribute values) are each evaluated against the subquery until at least one of them satisfies the criteria. Query optimization techniques such as reordering of terms, use of indexes, or converting subqueries into equivalent recasting rules are not currently used when evaluating queries.

[0130] FIGS. 14-17 describes the algorithm for computing all of the stored summary attributes in the database, relative to a given execution slice. The algorithm requires a single pass over all the invocations of the database.

[0131] Algorithm to Compute and Save Stored Summary Attributes Derived from Invocations

[0132] This algorithm, shown in FIGS. 15-17, is a recursive algorithm computing stored summaries of execution-related measures for instances, methods, classes, and packages, based on a call tree rooted at a given invocation, relative to a given execution slice. The algorithm traverses the call tree depth-first in a single pass.

[0133] Attributes other than total cumulative time are computed as follows: on each visit to an invocation during the traversal, the appropriate summary attributes of elements related to that invocation are incremented if the invocation is in the given execution slice.

[0134] Cumulative time is computed on the way back up the tree, based on the currently visited invocation and the total cumulative time passed up from visiting the callees. The algorithm computes the cumulative time of each invocation relative to a given execution slice as follows. If the current invocation is in the given execution slice, then its cumulative time is computed by subtracting from the invocation's cumulative time the time that each of its callees spends that is not in the execution slice. If the current invocation is not in the execution slice, then its cumulative time is simply the sum of the time spent in the execution slice by each callee.

[0135] Within each grouping of invocations for which we are computing total cumulative time (by instance, by method, by method class, etc.) there will often be invocations that call each other either directly or indirectly. The computation of total cumulative time must therefore make sure not to count time in an invocation more than once. This is accomplished by keeping counters with each instance, method, class, and package to record if invocations are currently in progress in the tree traversal for that grouping. There are separate counters associated with each total cumulative time attribute when there is more than one such attribute in the same entity. For example, JClass has two total cumulative time attributes (representing time in methods of the class and time in instances of the class); each JClass will have a counter for each of these attributes.

[0136] To compute total cumulative time attributes for instances, methods, and classes, the counters work as follows. Each counter represents the number of invocations in progress in the tree traversal that, on their own, would have been included in the attribute computation. These counters are incremented on the way down the tree and decremented on the way back up. An invocation's time is allocated to a summary attribute only if its corresponding counter is 1.

[0137] An additional complication is required for packages, since summary attributes for a package include that package's entire hierarchy of subpackages. The algorithm avoids the costly process of traversing all the way up the package containment hierarchy for each invocation as follows. Each counter represents the number of that package's immediate children (i.e. classes or subpackages) that have at least one invocation in progress in the tree traversal. Only transitions between 0 and 1 in the counter for a class or package triggers an update to the containing package's counter. When time is allocated to a class (i.e. when its counter is 1), the time will be allocated to packages reached by traversing up the containment hierarchy only up to but not including the first package whose counter is greater than 1.

[0138] As mentioned above, a number of systems use queries of execution information to let the user filter out extraneous information and to group together elements into user-defined units. The Desert system (disclosed in “Software Visualization in the Desert Environment,” Reiss, B. S., SCM PASTE 1998, Montreal, Quebec, Canada, 1998, pp. 59-66) provides a powerful query capability against static and dynamic information for various types of program understanding applications, as does the Hy+/GraphLog system (disclosed in Visualizing and Querying Distributed Event Traces with Hy+,” Consens, M. P., et al., Lecture Notes in Computer Science, Vol. 819, Springer Verlag, 1994, pp. 123-141) for analyzing distributed and parallel programs. Snodgrass (“Relational Approach to Monitoring Complex Systems,” Snodgrass, R. A., ACM Transactions on Computer Systems, Vol.6, No. 2, May 1988, pp. 157-196) allows queries to be used for analyzing operating system behavior, and Lencenvicius (“Dynamic Query-Based Debugging,” Lencenvicious R., et al., ECOOP 1999, June 1999, Lisbon, Portugal, in Lecture Notes in Computer Science, Vol. 1628, Springer Verlag, pp. 135-160) uses queries of dynamic program information for the debugging of live programs. These systems all provide a great deal of flexibility, but differ from the approach of the present invention in significant ways.

[0139] First, the above systems use queries to produce a single result set of elements of a database entity or of a new type created as a result of the query. In either case, result sets based on queries differ significantly from execution slices, which use queries to create an independent dimension classifying the entire database of information. Classifying the entire database into execution slices provides the following advantages:

[0140] 1. Execution slices may be automatically reused in many different views for different purposes (such as filtering, visual classification, and computation of measurements), and across many different types of information, giving the user a single consistent handle on an aspect of the program without requiring the user to restate the criteria.

[0141] 2. Because execution slices maintain the structure but alter the apparent content of the database, they may be used to structure larger studies into workspaces, allowing the entire database to be studied as a unit under different filtering and grouping scenarios. Again, this could only be done in pure query-based systems by having the user restate the criteria in every view in every workspace.

[0142] Moreover, pure query-based approaches leave the user exposed to many details in order to apply the power of queries in visualizations and computations. In general, it is difficult to provide flexibility without introducing usability difficulties. Pure query-based approaches require the user to understand the intricacies of the data model, and complex query language concepts, to express common cases. With execution slices, however, recasting rules hide much of this complexity from the user, obviating the need for the user to specify complex subqueries in many common cases. In addition, execution slices provide additional task-oriented specification techniques that are not available in general purpose database systems. All of this is important within a single view, and, as mentioned above, it is of even greater value since the user will be studying the same information in many ways.

[0143] Computations of summary measures over tree-structured information, where there may be overlap in the resource being summarized, can be extremely difficult to express in general-purpose query-based systems, which are not designed for aggregating hierarchical information. Expressing computations of multidimensional measures, of fixed units against user-defined units, is even more difficult for the user to express in these systems. The problem is further compounded if the user needs to measure the same aspect against a number of different dimensions. Execution slices, designed specifically for the domain of program analysis, hide all of this detail from the user. In addition, the performance of the computations is highly optimized compared to general-purpose database systems.

[0144] OLAP systems (“OLAP Solutions: Building Multidimensional Information System,” Thomsen, E., Wiley Computer Publishing ISBN 0-471-14391-4), which are more general purpose tools to analyze large databases in other problem domains, have some capabilities that are similar to the approach disclosed herein, but at the same time there are also significant differences. Filtering and drilling down to narrow a problem space are common features of OLAP systems, as are multidimensional reports, allowing the user to study summary measures at multiple levels of aggregation. Execution slices, however, provide both greater flexibility, and important advantages over OLAP systems specifically for analyzing programs. Execution slices provide the ability to pivot along a user-defined dimension of the trace information; OLAP systems do not provide the flexibility for users to define new dimensions based on arbitrary criteria. OLAP systems are also not capable of performing the type of computations required over hierarchical data such as call trees.

[0145] While it is apparent that the invention herein disclosed is well calculated to fulfill the objects stated above, it will be appreciated that numerous modifications and embodiments may be devised by those skilled in the art, and it is intended that the appended claims cover all such modifications and embodiments as fall within the true spirit and scope of the present invention.