Abstract
Dynamic analyses are a standard approach to analyzing and testing concurrent programs. Such techniques observe program traces σ and analyze them to infer the presence or absence of bugs. At its core, each analysis maintains a partial order P that represents order dependencies between the events of σ . Naturally, the scalability of the analysis largely depends on maintaining P efficiently. The standard data structure for this task has thus far been Vector Clocks. These, however, are slow for analyses that follow a non-streaming style, costing O ( n ) time for inserting (and propagating) each new ordering in P , where n is the size of σ , while they cannot handle the deletion of existing orderings. In this paper we develop Collective Sparse Segment Trees ( CSSTs ), a simple but elegant data structure for maintaining a partial order P . CSSTs thrive when the width k of P is much smaller than the size n of its domain, allowing inserting, deleting, and querying for orderings in P to run in O (log n ) time. For a concurrent trace, k normally equals the number of its threads, and is orders of magnitude smaller than its size n , making CSSTs fitting for this setting. Our experiments confirm that CSSTs are the best data structure currently to handle a range of dynamic analyses from existing literature.
Funding Information
  • VILLUM FONDEN, and by a research grant from STIBOFONDEN (VIL42117)