Title: Data Race Detection on Compressed Traces,
Abstract: We consider the problem of detecting data races in program traces that have
been compressed using straight line programs (SLP), which are special
context-free grammars that generate exactly one string, namely the trace that
they represent. We consider two classical approaches to race detection ---
using the happens-before relation and the lockset discipline. We present
algorithms for both these methods that run in time that is linear in the size
of the compressed, SLP representation. Typical program executions almost always
exhibit patterns that lead to significant compression. Thus, our algorithms are
expected to result in large speedups when compared with analyzing the
uncompressed trace. Our experimental evaluation of these new algorithms on
standard benchmarks confirms this observation.