System and method for characterizing program behavior by sampling at selected program points

• US 7,103,877 B1
• Filed: 11/01/2000
• Issued: 09/05/2006
• Est. Priority Date: 11/01/2000
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Arnold, Matthew R., Hind, Michael J., Sweeney, Peter F., Grove, David P., Fink, Stephen J.
• Primary Examiner(s): STEELMAN, MARY J
• Application Number:
  US09/703,527
• Time in Patent Office: 2,134 Days
• Field of Search: 717/133, 717/148, 717/128, 717/127, 717/130, 714/37, 714/35
• US Class Current: 717/130
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3471 Address tracing
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 8/41 Compilation

Abstract

A system and method for characterizing runtime behavior of a computer program executing in an execution environment, the method comprising: identifying one or more instances of yield points in a program to be executed, each yield point indicating a potential sampling operation during program execution; during program execution, in response to an identified yield point instance, ascertaining a state of the execution environment for indicating whether a sampling operation is to be performed; and, when the state of the execution environment indicates a sampling operation, recording relevant information for characterizing behavior of the execution environment. Relevant information for characterizing program behavior includes frequencies of methods executed in the program, and calling context associated with methods called by the program. Different mechanisms are provided for determining the sampling condition including the setting of a trigger bit by a runtime system, or, determining a sampling operations based on a fixed percentage of all executed yield points taken.

Claims

1. A method for characterizing runtime behavior of a computer program executing in an execution environment, said method comprising:

a) inserting yield points comprising code to be executed at distinguished locations of a program to be executed, each said yield point indicating a conditional sampling operation during execution of said program;

b) during program execution, unconditionally executing a yield point instance and, in response to executing said yield point instance, ascertaining a state of said execution environment for indicating whether the conditional sampling operation is to be performed; and

,

c) when a state of said execution environment indicates a condition for performing said sampling operation, recording relevant information for characterizing behavior of said execution environment, whereby conditional sampling operations performed at unconditionally executed yield points occur at a subset of the executions of yield points.

2. The method as claimed in claim 1, wherein said sampling operation includes identifying a method currently executing in said program, said method including tracking frequencies of methods executed in said program for characterizing said program behavior.

3. The method as claimed in claim 2, wherein said step of identifying a currently executing method comprises determining an instruction address at which the yield point was taken and mapping that address to a called method.

4. The method as claimed in claim 2, wherein said sampling operation includes identifying a calling context associated with methods called by said program, said method including tracking calling context frequency for characterizing said program behavior.

5. The method as claimed in claim 4, wherein said step of identifying a calling context associated with methods comprises inspecting a call-stack runtime data structure for tracking methods currently active in said executing program.

6. The method as claimed in claim 1, wherein said sampling operation includes identifying current program variable values, said program variable values being tracked for characterizing said program behavior.

7. The method as claimed in claim 1, wherein said sampling operation includes identifying basic blocks executed in said program, said method including tracking a frequency of basic blocks for characterizing said program behavior.

8. The method as claimed in claim 1, wherein when said state of said execution environment does not indicate a sampling operation, the step of executing a next instruction in said executing program after said identified yield point.

9. The method as claimed in claim 1, wherein said step b) of ascertaining a state of said execution environment includes checking status of a trigger bit set by said execution environment to indicate performance of said sampling operation.

10. The method as claimed in claim 1, wherein said trigger bit status is set periodically by said executing environment.

11. The method as claimed in claim 10, further including the steps of:

invoking a runtime system interrupt at periodic time intervals; and

,

implementing an interrupt handler mechanism for catching said interrupt and setting said trigger bit.

12. The method as claimed in claim 1, further including the step of implementing a compiler device for inserting one or more yield points in said program.

13. The method as claimed in claim 1, further including the step of implementing an interpreter device for ensuring execution of said yield points in said program.

14. The method as claimed in claim 1, wherein said yield points are inserted in one or more program locations including:

a method prologue and a loop back edge.

15. A method for characterizing runtime behavior of a computer program executing in an execution environment, said method comprising:

a) inserting yield points comprising code to be executed at distinguished locations of a program to be executed, each said yield point indicating a conditional sampling operation during execution of said program;

b) during program execution, unconditionally executing a yield point instance;

c) counting a number of executed yield points;

d) comparing said number against a predetermined threshold; and

,

e) in response to meeting said threshold, performing a sampling operation of said executing program, and, recording relevant information for characterizing behavior of said execution environment in response to said sampling, whereby conditional sampling operations performed at unconditionally executed yield points occur at a subset of the executions of yield points.

16. The method as claimed in claim 15, wherein said sampling operation includes identifying a method currently executing in said program, said method including tracking frequencies of methods executed in said program for characterizing said program behavior.

17. The method as claimed in claim 16, wherein said sampling operation includes identifying a calling context associated with methods called by said program, said method including tracking calling context frequency for characterizing said program behavior.

18. The method as claimed in claim 17, wherein said step of identifying a calling context associated with methods comprises inspecting a call-stack runtime data structure for tracking methods currently active in said executing program.

19. The method as claimed in claim 16, wherein said step of identifying a currently executed method comprises determining an instruction address at which the yield point was taken and mapping that address to a called method.

20. The method as claimed in claim 15, wherein said sampling operation includes identifying current program variable values, said program variable values being tracked for characterizing said program behavior.

21. The method as claimed in claim 15, wherein said sampling operation includes identifying basic blocks executed in said program, said method including tracking a frequency of basic blocks for characterizing said program behavior.

22. The method as claimed in claim 15, wherein said step c) includes the steps of:

initializing a counter to said predetermined threshold; and

, for each identified yield point instance,

decrementing said counter until said counter is zero, whereby said sampling operation is arranged such that a fixed percentage of all executed yield points are taken.

23. The method as claimed in claim 15, further including the step of implementing a compiler device for inserting one or more yield points in said program, said yield points being in one or more program locations including:

a method prologue and a loop back edge.

24. The method as claimed in claim 15, further including the step of implementing an interpreter device for ensuring execution of said yield points in said program.

25. A system for characterizing runtime behavior of a computer program executing in an execution environment, said system comprising:

a) means for inserting yield points comprising code to be executed at distinguished locations of a program to be executed, each said yield point indicating a conditional sampling operation during execution of said program;

b) mechanism for unconditionally executing instances of yield points inserted in said executing program;

c) control device for determining a condition for performing a sampling operation of said executing program at an executed yield point instance; and

,

d) sampling device for performing said sampling operation of said executing program upon satisfaction of said condition, and recording relevant information for characterizing behavior of said execution environment in response to said sampling, whereby conditional sampling operations performed at unconditionally executed yield points occur at a subset of the executions of yield points.

26. The system as claimed in claim 25, wherein said sampling device includes mechanism for identifying a method currently executing in said program;

said sampling device comprising mechanism for tracking frequencies of methods executed in said program for characterizing said program behavior.

27. The system as claimed in claim 26, wherein said sampling device includes mechanism for identifying a calling context associated with methods called by said program, said tracking mechanism further tracking calling context frequency for characterizing said program behavior.

28. The system as claimed in claim 27, wherein said mechanism for identifying a calling context associated with methods comprises inspecting a call-stack runtime data structure for tracking methods currently active in said executing program.

29. The system as claimed in claim 26, wherein said mechanism for identifying a currently executed method comprises includes determining an instruction address at which the yield point was taken and mapping that address to a called method.

30. The system as claimed in claim 25, wherein said sampling operation includes mechanism for identifying current program variable values, said tracking mechanism further tracking said program variable values for characterizing said program behavior.

31. The system as claimed in claim 25, wherein said sampling device includes mechanism for identifying basic blocks executed in said program, said tracking mechanism further tracking a frequency of basic blocks for characterizing said program behavior.

32. The system as claimed in claim 25, further including:

a system location for storing a trigger bit; and

,

a runtime system for said executing environment, said runtime system setting said trigger bit to indicate performance of said sampling operation;

wherein, said control device ascertains a state of said system bit for determining said sampling condition.

33. The system as claimed in claim 32, wherein said runtime system includes:

interrupt mechanism for generating timer interrupt signal; and

,

interrupt handler mechanism for catching said interrupt and setting said trigger bit.

34. The system as claimed in claim 25, wherein said control device comprises:

counter device for counting a number of identified yield points; and

,

device for comparing said number against a predetermined threshold value, wherein, in response to meeting of said threshold, said control device initiating performing of said sampling operation.

35. The system as claimed in claim 25, further including a compiler device for inserting one or more yield points in said program.

36. The system as claimed in claim 25, further including an interpreter device for ensuring execution of said yield points in said program.