Algorithmic Profiling for Real-World Complexity Problems

Boqin Qin, Tengfei Tu, Ziheng Liu, Tingting Yu, Linhai Song

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Complexity problems are a common type of performance issues, caused by algorithmic inefficiency. Algorithmic profiling aims to automatically attribute execution complexity to an executed code construct. It can identify code constructs in superlinear complexity to facilitate performance optimizations and debugging. However, existing algorithmic profiling techniques suffer from several severe limitations, missing the opportunity to be deployed in production environment and failing to effectively pinpoint root causes for performance failures caused by complexity problems. In this paper, we design a tool, ComAir, which can effectively conduct algorithmic profiling in production environment. We propose several novel instrumentation methods to significantly lower runtime overhead and enable the production-run usage. We also design an effective ranking mechanism to help developers identify root causes of performance failures due to complexity problems. Our experimental results show that ComAir can effectively identify root causes and generate accurate profiling results in production environment, while incurring a negligible runtime overhead.

Original languageEnglish
Pages (from-to)2680-2694
Number of pages15
JournalIEEE Transactions on Software Engineering
Issue number7
StatePublished - Jul 1 2022

Bibliographical note

Publisher Copyright:
© 1976-2012 IEEE.


  • Algorithmic complexity
  • Program analysis

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Algorithmic Profiling for Real-World Complexity Problems'. Together they form a unique fingerprint.

Cite this