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

TY - GEN

T1 - CSSTs

T2 - 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2024

AU - Tunç, Hünkar Can

AU - Deshmukh, Ameya Prashant

AU - Çirisci, Berk

AU - Enea, Constantin

AU - Pavlogiannis, Andreas

N1 - Publisher Copyright: © 2024 Copyright held by the owner/author(s).

PY - 2024/4

Y1 - 2024/4

N2 - 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.

AB - 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.

KW - concurrency

KW - dynamic concurrency analyses

KW - dynamic reachability

KW - happens-before

KW - vector clocks

UR - http://www.scopus.com/inward/record.url?scp=85192201929&partnerID=8YFLogxK

U2 - 10.1145/3620666.3651358

DO - 10.1145/3620666.3651358

M3 - Article in proceedings

AN - SCOPUS:85192201929

VL - 3

SP - 223

EP - 238

BT - ASPLOS '24: Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems

PB - Association for Computing Machinery

CY - New York

Y2 - 27 April 2024 through 1 May 2024

ER -