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组

Motivation

网页的page-load time很重要，一个网页的加载可以看作网页中每个元素的加载，每个元素的加载都涉及到全栈的操作（前端-后端-数据库）。现有的工作主要致力于研究“栈”某一层（如数据库、前端js）的性能，而少关注于全栈的性能。为什么全栈的性能很重要呢？因为用户在访问网页的时候想知道到底是网页中的拿个元素加载最慢，开发者在开发软件的时候也想知道拿个元素拖了整个页面的后腿。这样可以帮助开发者更好的在开发过程中权衡好功能和性能的trade-off。

想要帮助开发者做好这件事，作者认为应从两个方面着手：

• Understanding the performance cost behind every rendered web-page element 这一点比较好理解，就是如何分析出加载一个html元素所需要的时间。
• Exploring the performance-functionality trade-offs among different web-page designs 这一点意思是说：当前对于软件性能提升的工作主要集中于“性能bug”（即修复后不会对功能产生不利影响），但没有关注到那些需要牺牲一定功能才能提升性能的优化（比如一个很耗资源但没太大用处的功能应该被删掉）。ShanLu在之前调研ORM类软件性能bug的文章中指出“1/4的用户所报的软件性能问题最终的修复结果都是对软件功能进行了调整（或删除功能，或改变功能）”--实际上就是说这1/4性能bug的本质是开发者做出的、不好的、功能与性能的trade-off。所以作者认为在开发人员开发软件的过程中，如果能直观的展示一些这样的trade-off，就或许可以在开发时避免未来发生性能bug。

Solution