Faster and more accurate techniques for finding statements of Java Programs that run in parallel

What is it about?

May Happen in Parallel (MHP) analysis identifies which statements in a concurrent program can execute simultaneously. To perform this analysis, the program is first converted into an abstract graph that represents all threads, their execution flows, and synchronization mechanisms. Historically, applying MHP analysis to real-world Java applications has been impractical. The program graphs created by previous works were bloated, making the computationally intensive analysis too slow to run in a reasonable time. This paper introduces GRIP-MHP, a novel technique that aggressively compresses these program graphs. By retaining only the statements that actually affect MHP information, our approach reduces the graph size far more effectively than previous methods, drastically cutting down the overall analysis time. Furthermore, we identified that previous works fail to produce precise results for common programming patterns, such as starting and joining threads inside loops. They also lack support for modern Java concurrency constructs. GRIP-MHP provides concrete solutions to these issues, delivering a fast and precise MHP analysis

Featured Image

Photo by orbtal media on Unsplash

Photo by orbtal media on Unsplash

Why is it important?

To the best of our knowledge, no existing May Happen in Parallel (MHP) analysis could handle large, real-world Java applications without severe limitations. Previous methods struggled to execute within a reasonable timeframe, and their outputs were often overly conservative and imprecise—falsely reporting that statements could run in parallel when they actually could not. Our research resolves these core issues through GRIP-MHP, massively reducing analysis times and significantly improving precision, especially for commonly used Java concurrency patterns. By providing a scalable and precise MHP analysis, this development enables far better analysis of concurrent programs. Writing bug-free concurrent programs is hard. However, with our highly accurate MHP output, developers and tool builders can now more reliably identify complex bugs, such as data races or accidental serialization. Furthermore, a highly precise MHP analysis inherently improves the quality and performance of downstream static analyses.

Perspectives