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

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

差异成本分析能够衡量代码变更在性能指标（如执行时间或内存/磁盘使用量）方面的成本。但界定代码变更成本是一个不可判定问题，意味着没有保证能给出答案的算法。先前的方法侧重于估计单个代码版本的成本，或假设能够以语法方式对齐代码变更。

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

方法实现

与先前方法不同，我们的实现能够计算从文献收集的程序版本对之间代码变更成本的紧界。特别地，我们能够在19个示例中的14个上提供紧界，这些示例包括对成本有影响的变更和需要复杂分析才能确定不影响成本的变更。

该方法专注于命令式程序（最熟悉的程序类型，明确指定每个计算步骤），具有整数变量和多项式算术。程序还可能具有非确定性元素，意味着相同输入可能产生不同输出。

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

该方法的关键方面是同时获得新程序版本的势函数和旧程序的反势函数的约束系统。通过将程序版本表示为转换系统（由一组程序状态和状态间有效转换组成的计算模型），并假设转换系统终止（即没有输入会导致它们永远运行），可以解决这些约束。

通过应用Handelman定理的结果，将这些约束转换为纯存在量化的线性约束系统。这种约束系统可以通过现成的线性规划求解器高效解决。这种约束表示还具有额外优势，能够验证符号阈值或优化具体阈值，从而产生尽可能紧的阈值t。

该方法使用当前文献中的19个C语言基准进行了验证。将这些程序转换为转换系统后，能够为其中17个计算阈值。在14种情况下阈值是最优的，更重要的是，在所有情况下都能在不到五秒的时间内提供阈值值。

相关会议：PLDI 2022

相关出版物：同时势函数与反势函数的差异成本分析