Progress Report 2019.03.24

1.阅读论文

Redundant Loads: A Software Inefficiency Indicator

• 会议：ICSE 2019
• 作者：威廉玛丽的刘旭组 这位老师发的会议主要集中在“计算机体系结构/并行与分布计算/存储系统”领域的A会里面

Motivation

软件性能问题很严重，为了解决性能问题，编译器优化可以帮助开发者找到并优化一些低效代码，但只能局限于静态分析出的低效代码；profile方法可以找到耗时最久的代码但无法判别其是“fruitful”（我感觉这个词比lushan的“consume”要好）还是“waste”；Whole-program fine-grained monitoring的方法（通过动态监测程序对内存的读写模式来识别是否存在低效情况）可以解决上述两种方法解决不了的问题。然而当前Whole-program fine-grained monitoring的研究工作只能解决下面这几种问题：

• symbolic equivalence
• dead memory stores（e.g. 对某个变量写了一个数据后还没读过又写了另一个数据）
• operations writing same values to target registers or memory locations（e.g. 总是把同样的一个结果赋值给某个变量）
  却忽略了一种情况：

// 修复前
while (t < threshold) {
    t = 0;
    for(i = 0; i < N; i++)
        t += A[i] + B[i] * delta; // 低效的代码段，A[i]和B[i]被反复读取，然后被计算 N*m次。其中m是while循环的次数
    delta -= 0.1 * t;

// 修复后
for (i = 0; i < N; i++)
{
    a += A[i];
    b += B[i];  // A[i],B[i]只会被读取N次，也只会被计算N次
}
while (t < threshold) {
    t = a + b * delta;
    delta -= 0.1 * t;
}

在这类情况中，某个变量只是被读取了多次（正如如论文题目“Redundant Loads”），那么是否被读取了多次就真的如上面这个例子一样，意味着代码就是低效了呢？作者就假设是这样的，因为读取变量就意味着要进一步进行计算，读的太频繁很有可能就是计算得复杂度过高，实际上，作者也举了更多的例子证明这一点：

It is easy to imagine how redundant loads happen: repeatedly accessing immutable data structures or algorithms employing memoization. It is equally easy to see how inefficient code sequences show up as redundant loads: missed inlining appears as repeatedly loading the same values in a callee, imperfect alias information shows up as loading the same values from the same location via two different pointers, redundant computations show up as the same computations being performed by loading unchanged values, algorithmic defects, e.g., frequent linear searches or hash collisions, also appear as repeatedly loading unchanged values from the same locations.

Solution

动态监测程序运行过程中的redundant loads现象即可。其中，redundant load有两个小类分别是：

• Temporal Load Redundancy：如上例子中所示，两个load操作L1和L2，读取了同一个变量A的值，读到的值V1和V2是相等的。
• Spatial Load Redundancy：两个load操作L1和L2，读取了同一个类的实例A不同成员的值，读到的值V1和V2是相等的。（e.g. 挨个读取稀疏矩阵的每个值）
  然后统计Redundancy Fraction（即bytes_redundantly_loaded/total_bytes_loaded_in_the_entire_execution）。然后通过实验来验证假设“Large redundancy fraction in the execution profile of a program is a symptom of some kind of software inefficiency.”是否正确。

实验结果

• 实验对象是大量的CPU benchmark程序
• 新发现了14个性能bug，bug的分类就是上面那大段引用文字里粗斜体的几个
• 修复这几个bug均使得整个程序得到 10%～900%不等的提升（多数提升在10%～50%之间）

View-Centric Performance Optimization for Database-Backed Web Applications

• 会议：ICSE 2019
• 作者：Shan Lu组