Page 38 - 《软件学报》2024年第6期

2614 软件学报 2024 年第 35 卷第 6 期

要跟踪哪些“增量单元”已经被处理, 哪些还未被处理. 此外, 我们可能需要保存一些中间结果, 以便在后续过程中
使用. 因此, 我们需要一个高效、可靠且易于操作的信息管理的方式, 以支持复杂的查询和更新操作.
针对上述问题, 我们设计了一个高效且精确的、支持增量输入事实生成的前端. DDoop 的前端架构如图 2 所
示. 框架前端中分别给出了如下解决方案: 基于实证研究的增量单元粒度选择与确定, 基于程序性质与哈希的增量
单元摘要设计, 基于内存数据库的增量信息高效存储与管理. 在第 2.1.2–2.1.4 节, 我们将对各部分进行详细介绍,
而在第 2.1.5 节, 我们将对一个实现中的优化进行介绍.

待分析程序 类文件 类过滤器 变更类 增量事实
查询类摘要

查询方法摘要
个方法, 其中平均有
Redis 方法过滤器 变更方法 事实生成器

查询需删除事实、维护增量信息
图 2 框架前端架构

2.1.2 增量单元粒度选择
确定合适的增量单元粒度是解决增量问题的关键之一. 在 Java 增量分析中, 增量粒度可以有多种选择, 例如
编译单元级、类级、方法级、语句级甚至更加精细的表达式级. 在 Doop 框架中, 我们注意到, 它天生就在类级并
行, 因此可以直接排除粒度更粗的编译单元级增量粒度. 此外, 尽管 Doop 框架的并行处理粒度在类级别, 但其处
理逻辑中方法与方法之间仍然是独立的, 所以从实现的角度来说, 比方法级别更加精细的增量单元可能会引入相
当规模的强耦合关系, 不能做到增量单元间的高效并行.
因此, 在 Doop 框架设置下, 我们主要关注类级和方法级两种增量单元. 为了确定哪一种增量单元更加适合我
们的场景, 我们在一组基准项目上开展了关于增量单元粒度选择的实证研究, 通过简单的快速实验, 对比不同粒度
的增量单元对于增量输入事实生成的效率的影响.
我们在 DaCapo 基准 (如 xalan、Jedis、PMD 等) 和一些真实世界大型项目 (如 ErrorProne、ZooKeeper 等) 上
开展了实证研究. 我们发现, 对运行时 Soot 对象进行简单的哈希在多次运行中并不能保证幂等性, 因此我们选择
将其中的 SootMethod 对象转化为中间表示 (intermediate representation, IR). 我们认为, 如果 IR 表示不同, 则此方
法发生了变化 (关于增量单元摘要的设计细节, 见第 2.1.3 节). 在我们的两级摘要设计过程中, 我们首先会过滤出
那些内容存在变化的类, 之后才会对这些类中的每一个方法计算摘要以进一步缩小增量计算范围. 那么, 这一策略
要相较于基于类层级的增量方案节省时间, 就要求在变化过程中平均每一个类变化的方法数量相对有限. 不妨假
设我们发生变化的类中平均一共有 n x 个方法发生变化, 记单个类事实生成时间为 a, 生成摘
要信息为 b, 要让我们的二级摘要方案时间消耗更少, 即需要满足如下约束: a·n ⩾ b·n+a· x . 实证研究结果显示,
对每个方法做从 SootMethod 对象到摘要的转化操作平均需要 0.09 ms, 而为每个方法生成相应的事实平均需要
0.25 ms. 通过前述不等式约束可以得出结论: 类中少于 64% 的方法变化时我们的二级摘要可以节约时间.
根据实证研究的实验结果以及上述结论, 我们发现方法级别的增量单元能够更有效地处理这个问题, 因此我
们选择以方法作为 DDoop 前端的基本增量单元粒度.

2.1.3 增量单元摘要设计
为了标识一个增量单元在代码变更中是否发生变化, 我们需要为增量单元设计一种摘要机制以表征这种变
化. 我们设计了一种高效的两级摘要方案, 旨在平衡性能和增量粒度. 具体而言, 我们首先使用类的字节码文件对