Complexity-guided container replacement synthesis
summary
Cres automatically synthesizes container-type replacements using static, allocation-based and flow-sensitive points-to analysis to collect container properties and a cost model that combines amortized complexity classes and constant factors. Evaluation on 12 Java projects totaling 384.2 KLoC finishes in 14 minutes and finds 107 replacements across six categories with 71 accepted, producing an average runtime improvement of 8.1% while preserving input/output behavior.
AI-written summary · about
chapters (12)
- 0:00Container performance challenges
- 1:25Automatic container replacement
- 3:36Existing optimization limits
- 5:00Behavior equivalence goals
- 7:07Usage intentions decomposition
- 10:20Time complexity estimation
- 13:32Algorithm workflow
- 16:47Theoretical guarantees
- 18:36Experimental results
- 21:28Limitations and future
- 23:16Summary of contributions
- 23:37Q&A
related talks
52mCloud Native JVM. Cloud Compiler
22mBoosting Compiler Testing by Injecting Real-World Code
22mBeacons: An End-to-End Compiler Framework for Predicting and Utilizing Dynamic ...
21mFlow-Analysis-Based Closure Optimization
40mSuperfusion: Eliminating Intermediate Data Structures via Inductive Synthesis
24mEfficient Late Binding of Dynamic Function Compositions
14mOn-Stack Replacement for Program Generators and Source-to-Source Compilers
01h 01mMoving to C++20 for Fun, Beauty... and Results!