CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis

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 𝑃 that represents order dependencies between the events of 𝜎 . Naturally, the scalability of the analysis largely depends on maintaining 𝑃 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 𝑂 (𝑛) time for inserting (and propagating) each new ordering in 𝑃, where 𝑛 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 𝑃. CSSTs thrive when the width 𝑘 of 𝑃 is much smaller than the size 𝑛 of its domain, allowing inserting, deleting, and querying for orderings in 𝑃 to run in 𝑂 (log 𝑛) time. For a concurrent trace, 𝑘 normally equals the number of its threads, and is orders of magnitude smaller than its size 𝑛, 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.

• Software and its engineering → Software verification and validation; • Theory of computation → Theory and algorithms for application domains; Program analysis.