一句话：提出 Cres，结合静态分析与复杂度引导的合成，为程序中每个容器方法调用自动选择时间复杂度更低的容器实现，在保持行为的同时提升运行性能。
容器（如列表、映射）是现代编程语言中的基础数据结构，但容器类型选择不当会带来严重的性能问题。本文提出 Cres，一种自动合成容器替换以提升运行时性能的方法。其合成算法与静态分析技术协同工作：静态分析识别容器在程序中的使用方式，合成算法则针对每个容器方法调用，尝试选择一个时间复杂度更低的方法实现。该方法能在保持程序行为不变的前提下，有效抓住降低执行时间的机会，且对一般输入同样适用。作者实现了 Cres 并在 12 个真实 Java 项目上进行评估，结果表明 Cres 能在 14 分钟内为总计 384.2 KLoC 的项目合成容器替换，发现六类容器替换，平均获得 8.1% 的性能提升。
Containers, such as lists and maps, are fundamental data structures in modern programming languages. However, improper choice of container types may lead to significant performance issues. This paper presents Cres, an approach that automatically synthesizes container replacements to improve runtime performance. The synthesis algorithm works with static analysis techniques to identify how containers are utilized in the program, and attempts to select a method with lower time complexity for each container method call. Our approach can preserve program behavior and seize the opportunity of reducing execution time effectively for general inputs. We implement Cres and evaluate it on 12 real-world Java projects. It is shown that Cres synthesizes container replacements for the projects with 384.2 KLoC in 14 minutes and discovers six categories of container replacements, which can achieve an average performance improvement of 8.1%.
@article{paperbot1521,
title = {Complexity-guided container replacement synthesis},
author = {Chengpeng Wang and Peisen Yao and Wensheng Tang and Qingkai Shi and Charles Zhang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {OOPSLA1},
year = {2022},
doi = {10.1145/3527312}
}