一句话：提出 CSSTs 数据结构，以 O(log n) 维护并发执行分析中的偏序，支持插入、删除和查询。
并发程序动态分析通常根据执行轨迹维护事件间的偏序 P，其可扩展性取决于偏序维护效率。传统 Vector Clocks 在非流式分析中插入和传播一个序关系需 O(n)，且不支持删除。本文提出 Collective Sparse Segment Trees（CSSTs），当偏序宽度 k 远小于轨迹规模 n 时，可在 O(log n) 时间内完成插入、删除和查询；并发轨迹的 k 通常等于线程数，远小于 n，故特别适用。实验表明，CSSTs 是当前处理多种已有动态分析的最佳数据结构。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{abs-2403-17818,
title = {CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis},
author = {Hünkar Can Tunç and Ameya Prashant Deshmukh and Berk Cirisci and Constantin Enea and Andreas Pavlogiannis},
booktitle = {ASPLOS},
year = {2024},
doi = {10.1145/3620666.3651358}
}