Efficient Timestamping for Sampling-Based Race Detection
summary
Proposes a sampling-aware timestamp scheme that replaces full vector-clock updates with a freshness timestamp and an ordered vector clock data structure, proving instance-optimality and bounding work to O(S·T²) versus the naïve Θ(N·T). Implements the algorithm in ThreadSanitizer, runs on 64 threads with random sampling (S ≈ 3.3%), reduces monitoring overhead by ~37% on average and up to 70% on some benchmarks, skips 50–70% of communications, and traverses 3–6 vector entries per communication.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:52Dynamic analysis and race detection
- 3:17Sampling-based race detection
- 5:46Problem and algorithmic goal
- 7:57Evaluation and performance gains
- 11:29Vector clocks foundations
- 12:34Optimization key observations
- 15:04Enhanced vector clock structure
- 16:51Shallow copy and implementation
- 17:33Experimental setup and profiling
- 18:15Future work and conclusion
related talks
22mData race detection
23mDynamic Race Detection with O(1) Samples
19mRuntime Detection of Data Races in OCaml with ThreadSanitizer
21mWhat happens-after the first race? enhancing the predictive power of dynamic race detection
01h 04mDebugging data races
18mOptimal Prediction of Synchronization-Preserving Races
07mRace Conditions in Details
31mRace Conditions - Practical Tools & Techniques for Testing, Preventing, and Debugging C++/C Code