Department of Computer Science and Technology

Technical reports

Dynamic analysis for concurrency optimisation

Indigo J. D. Orton

August 2022, 166 pages

This technical report is based on a dissertation submitted October 2021 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Hughes Hall.

DOI: 10.48456/tr-974

Abstract

Modern software engineering is, broadly, a continuous activity - many pieces of industrial software are constantly developed, they are never “finished”. This process of continuous improvement necessitates small, incremental changes to ensure stability and maintainability of the software and its codebase. This includes incremental changes to improve performance. In this thesis I focus on improvements to the efficiency of concurrency usage, at a source-code level, within a piece of software. These improvements are challenging to indentify and implement as cuncurrency and performance behaviour is only exhibited at runtime, thus requiring dynamic analysis, whilst making incremental changes requires static source-code patches. The challenge is compounded as a codebase evolves, as the efficiency of various concurrency uses may change - an instance of concurrency that was previously beneficial may become inefficient due to the evolution of the software. I present an automatic-program-analysis methodology to indentify potential performance improvements, estimate their quantitative effect, and generate static source-code patches to implement them. Using a proof-of-concept implementation, I present evaluations that demonstarate the methodology’s efficacy.

Multicore processors are the default for modern computers and leveraging this concurrency is a key aspect of modern software. Effective use of concurrency can significantly improve software performance, though the inverse is also true - ineffective use can impair software performance. However, as the saying goes “concurrency is hard”; it is fundamentally difficult to statically reason about, let alone optimise. Indeed, many of its properties, especially those related to performance, are only exhibited at runtime.

In this thesis I explore the use of dynamic analysis for concurrency optimisation. I argue this field is under-explored, yet represents a substantial opportunity for improving software performance. A key challenge within this field, and one that extends beyond concurrency, is the generation of static changes (e.g. source-code changes) from dynamic analysis. The gap between static and dynamic domains is well studied in terms of using static analysis to improve dynamic analysis efficiency and using dynamic analysis to confirm static analysis hypothesises (e.g. race-condition detection), however, I argue the gap is understudied when transitioning from the dynamic to the static domain.

Full text

PDF (1.7 MB)

BibTeX record

@TechReport{UCAM-CL-TR-974,
  author =	 {Orton, Indigo J. D.},
  title = 	 {{Dynamic analysis for concurrency optimisation}},
  year = 	 2022,
  month = 	 aug,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-974.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-974},
  number = 	 {UCAM-CL-TR-974}
}