代码变更差异成本计算技术解析

代码变更差异成本计算方法

修改计算机代码可能会对程序性能产生意外影响。例如，修改特定程序中的循环或更改数据结构可能导致执行时间、内存或磁盘使用量增加。我们将此类性能指标的变化称为代码修改的差异成本。

差异成本分析指对代码变更成本进行推理的能力。在某中心，能够在部署新版本程序代码之前执行此类分析尤为重要，因为这不仅能提升客户体验，还能减少资源消耗和碳足迹。

技术突破

在今年的ACM SIGPLAN编程语言设计与实现会议上，我们提出了一种克服这些挑战的差异成本分析方法。该方法基于联合计算势函数和反势函数的思想，分别提供成本变化的上界和下界。

与现有方法不同，该实现能够计算文献中收集的程序版本对代码变更成本的紧致边界。特别是在19个示例中，能够为14个示例提供紧致边界，这些示例既包含影响成本的变体，也包含不影响成本但需要复杂分析才能确定的变体。

关键技术细节

该方法专注于以下代码分析问题：给定程序的旧版本和新版本，以及感兴趣的成本指标（如运行时间、内存、线程数、磁盘空间），需要计算数值边界阈值t，使得满足：cost_new - cost_old ≤ t。

研究针对具有整数变量和多项式算术的命令式程序（最熟悉的程序类型，明确指定每个计算步骤）。程序可能还具有非确定性元素，即相同输入可能产生不同输出。

反势函数（计算下界）捕获程序运行所需支付的最小成本。如果用φ表示程序的势函数，用χ表示其反势函数，则程序新旧版本间成本变化的阈值可通过φ_new - χ_old近似计算。

约束求解创新

该方法的关键在于同时为新程序版本的势函数和旧程序版本的反势函数获取约束系统。通过应用Handelman定理将涉及通用量词和多项式变量的约束转换为纯存在量词的线性约束系统，此类约束系统可通过现成的线性规划求解器高效求解。

该约束表示的额外优势是能够验证符号阈值或优化具体阈值，从而获得尽可能紧致的阈值t。

验证结果

使用当前文献中的19个C语言基准测试验证该方法。其中17个程序能够计算阈值，14个案例中阈值达到最优，且所有案例均能在5秒内提供阈值计算结果。