Property-Aware Program Sampling

By: Harish Narayanappa, Mukul S. Bansal, and Hridesh Rajan

Abstract

Monitoring or profiling programs provides us with an understanding for its further improvement and analysis. Typically, for monitoring or profiling, the program is instrumented to execute additional code that collects necessary data. A problem is that program instrumentation is often reported to cause between 10% and 390% time and space overhead. A number of techniques based on statistical sampling have been proposed to reduce the instrumentation overhead. Statistical sampling based instrumentation techniques, although effective in reducing the overall overhead, often lead to poor coverage or less accurate results. In this work, we present a profiling technique based on property-aware program sampling. The key ideas are (i) to use program slicing to narrow down the scope of instrumentation to the sections of program relevant to the property of interest, (ii) to decompose large program slices into logically related slice fragments, and (iii) to apply statistical sampling on the set of slice fragments. Our experimental results show that our technique can collect profiles at high assurance levels, at a significantly lower overhead.

ACM Reference

Narayanappa, H. et al. 2010. Property-Aware Program Sampling. Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE, Toronto, Ontario, Canada (2010), 45–52.

BibTeX Reference

@inproceedings{NarayanappaBansalRajan2010,
  author = {Harish Narayanappa and Mukul S. Bansal and Hridesh Rajan},
  title = {Property-Aware Program Sampling},
  booktitle = {Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE, Toronto, Ontario, Canada},
  pages = {45--52},
  year = {2010},
  publisher = {{ACM}},
  editor = {Sorin Lerner and Atanas Rountev},
  doi = {10.1145/1806672.1806682},
  abstract = {
  Monitoring or profiling programs provides us with an understanding for its
  further improvement and analysis. Typically, for monitoring or profiling, the
  program is instrumented to execute additional code that collects necessary
  data. A problem is that program instrumentation is often reported to cause
  between 10% and 390% time and space overhead. A number of techniques based on
  statistical sampling have been proposed to reduce the instrumentation
  overhead. Statistical sampling based instrumentation techniques, although
  effective in reducing the overall overhead, often lead to poor coverage or
  less accurate results. In this work, we present a profiling technique based on
  property-aware program sampling. The key ideas are (i) to use program slicing
  to narrow down the scope of instrumentation to the sections of program
  relevant to the property of interest, (ii) to decompose large program slices
  into logically related slice fragments, and (iii) to apply statistical
  sampling on the set of slice fragments. Our experimental results show that our
  technique can collect profiles at high assurance levels, at a significantly
  lower overhead.},
}