Calling context trees (CCTs) associate performance metrics with paths through a program's call graph, providing valuable information for program understanding and performance analysis. In real applications, however, CCTs might easily consist of tens of millions of nodes, making them difficult to analyze and also hurting execution times due to poor access locality. For performance analysis, accurately mining only {em hot} calling contexts may be more useful than constructing an entire CCT with millions of uninteresting paths, since the distribution of context frequencies is typically very skewed. In this article we show how to exploit this property to considerably reduce the CCT size, introducing a novel run-time data structure, called Hot Calling Context Tree (HCCT), in the spectrum of representations for interprocedural control flow. The HCCT includes only hot nodes and their ancestors in a CCT, and can be constructed independently from it by using fast, space-efficient algorithms for mining frequent items in data streams. With this approach, we can distinguish between hot and cold contexts on the fly, while obtaining very accurate frequency counts. We show, both theoretically and experimentally, that the HCCT achieves a similar precision as the CCT in a space that is several orders of magnitude smaller, and roughly proportional to the number of hot contexts. Our approach can be effectively combined with previous context-sensitive profiling techniques, as we show for static bursting. We devise an implementation as a plugin for the gcc compiler that incurs a slowdown competitive with the gprof call-graph profiler while collecting finer-grained profiles.

Mining Hot Calling Contexts in Small Space / D'Elia, DANIELE CONO; Demetrescu, Camil; Finocchi, Irene. - In: SOFTWARE, PRACTICE AND EXPERIENCE. - ISSN 1097-024X. - STAMPA. - 46:8(2016), pp. 1131-1152. [10.1002/spe.2348]

Mining Hot Calling Contexts in Small Space

D'ELIA, DANIELE CONO
;
DEMETRESCU, Camil
;
FINOCCHI, Irene
2016

Abstract

Calling context trees (CCTs) associate performance metrics with paths through a program's call graph, providing valuable information for program understanding and performance analysis. In real applications, however, CCTs might easily consist of tens of millions of nodes, making them difficult to analyze and also hurting execution times due to poor access locality. For performance analysis, accurately mining only {em hot} calling contexts may be more useful than constructing an entire CCT with millions of uninteresting paths, since the distribution of context frequencies is typically very skewed. In this article we show how to exploit this property to considerably reduce the CCT size, introducing a novel run-time data structure, called Hot Calling Context Tree (HCCT), in the spectrum of representations for interprocedural control flow. The HCCT includes only hot nodes and their ancestors in a CCT, and can be constructed independently from it by using fast, space-efficient algorithms for mining frequent items in data streams. With this approach, we can distinguish between hot and cold contexts on the fly, while obtaining very accurate frequency counts. We show, both theoretically and experimentally, that the HCCT achieves a similar precision as the CCT in a space that is several orders of magnitude smaller, and roughly proportional to the number of hot contexts. Our approach can be effectively combined with previous context-sensitive profiling techniques, as we show for static bursting. We devise an implementation as a plugin for the gcc compiler that incurs a slowdown competitive with the gprof call-graph profiler while collecting finer-grained profiles.
2016
Performance profiling; dynamic program analysis; data streaming algorithms; frequent items; program instrumentation
01 Pubblicazione su rivista::01a Articolo in rivista
Mining Hot Calling Contexts in Small Space / D'Elia, DANIELE CONO; Demetrescu, Camil; Finocchi, Irene. - In: SOFTWARE, PRACTICE AND EXPERIENCE. - ISSN 1097-024X. - STAMPA. - 46:8(2016), pp. 1131-1152. [10.1002/spe.2348]
File allegati a questo prodotto
File Dimensione Formato  
DElia_Mining_2016.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.01 MB
Formato Adobe PDF
1.01 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/788263
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 5
social impact