Skip to content

Progress Report 2018.11.18

TimHe edited this page Feb 10, 2019 · 1 revision

1.阅读论文

Generating Performance Distributions via Probabilistic Symbolic Execution

ICSE 16

Bihuan Chen, Yang Liu @ Nanyang Technological University, Singapore

Wei Le @ Iowa State University, USA

在讲本文所研究的问题之前,首先需要讲一下本文提到的性能分布(Performance Distributions)指的是什么。本文的性能分布(Performance Distributions)是指:对于一段程序,执行所有可能输入,统计每个测试样例所用时间,得到的关于程序执行时间的密度分布二维直方图。横坐标为程序执行时间(划分若干区间),纵轴是频数。这个分布图可以告诉我们有百分之多少的测试样例的执行时间在a秒~b秒之间,又有百分之多少的测试样例的执行时间在b秒~c秒之间。

接下来正式讲本文所研究的问题:本文希望对程序构建上述性能分布(Performance Distributions),使得开发人员可以对程序的性能有一个overall的理解。换句话说,通过构建性能分布,使得开发人员可以知道一段程序在执行常规测试样例时大概需要多久,执行最坏/最好情况下的测试样例时大概需要多久。上述问题举个例子来说:对于下面这段程序:

#!c++
cin << a << b; // a, b < 100
for(int i=0; i<a; i++)
    for(int j=0; j<b; j++)
        foo();

其输入有100x100=10000个,那么要想得到这段程序的性能分布,就需要执行这10000个测试样例,得到每个样例的执行时间,然后可以发现这段程序的分布长这个样子(红色线): 屏幕快照 2018-11-17 下午3.19.16.png

上面说到得到这样的性能分布后可以让开发者对性能有overall的理解,那么具体可以有什么实际的作用呢?作者给出了下面几个应用场景:

(1) 可以让开发者知道一段程序在大多数/最好/最坏情况下所需的执行时间是多少。这个信息对于开发者编写、优化例如排序程序这样的程序时,可以整体的理解程序的性能。

(2) 可以通过对同一段程序的两个版本的性能分布进行对比进行bug修复验证。例如下图(关注红色实线和绿色实线):

屏幕快照 2018-11-17 下午3.27.18.png

红色实线是bug版的程序的性能分布,绿色实线是fix版的程序的性能分布。可以看出明显的性能提升,意味着这一bug被修复。(作者给的例子仅是很简单的情况)

(3) 可以通过对几个功能相同性能不同的程序分别构建性能分布,来选择合适与开发者当前需求的程序。例如下图中对不同排序算法构建出的性能分布(关注红实线、绿实线、黄实线):

屏幕快照 2018-11-17 下午3.32.12.png

可以看出冒泡排序的执行时间在多数情况下是比较长的,因此一般情况下程序员应当考虑使用快速排序或者merge排序算法。

本文工具实现部分:上述idea的核心在于对一段程序构建overall的性能分布,但是想要构建一个准确的性能分布需要对程序的所有可能输入进行测试(例如最一开始那段嵌套循环的10000组测试样例),有组合爆炸的问题。那么想要减少测试的输入样例,又能保证得到的分布不会出现偏差,作者提出了以下方法:用概率符号执行的方法分析待测程序段,例如前面嵌套循环的例子,从10000条执行路径中筛选出1000条路径(可调整),然后每条路径都可以对应一个测试样例,测这1000个测试样例的时间,构建性能分布,当作这段程序的性能分布。

作者的实验主要验证减少测1000个样例和全测(测10000个样例)得到的性能分布直方图差别大不大。结果表明不是很大,因此作者认为工具是高效又准确的。他选择的待测程序段都是非常小的程序,比如上面我给的例子、排序算法等等。

这篇文章证明了对一段程序进行少量次数的测试就可以构建出这段程序的性能分布,从而让开发者更好更全面的理解这段程序的性能。我比较质疑这篇文章的实际作用,因为对于很小的功能很简单的程序的确可以通过构建分布来理解整体性能,但是对于复杂一点的大软件,知道这个信息作用可能不大:比如对mysql的select构建性能分布,得到的很可能就是一个形状像正态分布图一样的性能分布图,这对开发者来说提供不了太多帮助。所以这个性能分布图只能服务于很小的一段功能程序。这样的话实际贡献就会打一些折扣。

我读这篇文章是因为这篇文章也提到了Performance Distributions。这篇文章的Performance Distributions和我的工作的Performance Distribution不是一个意思,而且从本文的contribution (1): introducing the concept of performance distribution 看出,performance distribution已经被他定义成了这个样子,而且被icse16录用,可能在业界形成了一定共识。因此我应该考虑换一个词。我认为performance model比较合适,当前一些做性能配置调优的工作里面也用了performance model这个概念,他们的这个概念就是指软件的性能关于软件的配置项的函数。

2. 测试软件得到正常情况下的分布

测正常分布的原因:想要说明性能bug的分布feature可以作为test oracle(比如‘突变点’这一特征),就必须要说明这种feature只有在发生性能bug时才会出现,而在正常情况下不会出现。我目前只是通过复现bug得到了一些bug的分布feature,还没有得到正常的分布feature。

这周我测了2个workload parameter + 3个configuration(concurrency相关)总共5个parameter 的进行读写操作的性能(9000个test cases)每个test case长这个样子:

#!bash

mysqld --config-one=10 --config-two=20 --config-three=30
sysbench oltp_read_and_write.lua --workload-param1=1000 --workload-param2=10 run

然后我用这些结果得到了2240个性能分布(每个分布都只有两个parameter作为自变量,剩下三个parameter的值固定。但我遍历了所有可能的组合:包括固定的parameter的取值组合和选取哪两个parameter作为自变量的组合。),全过程耗时60h左右,全部结果比较大,这里列一个例子(纵轴表示读写操作平均毫秒延时):

distribution_2285.png

左中右三个图中,左边第一个是散点图,没有弄成平面是因为会变得很乱。中间第二和右边第三个图是把第一个散点图分别按两个坐标轴方向连线得到的,只是为了便于看趋势。

其他例子:

distribution_430.png

distribution_1613.png

问题:

(1)测了配置还太少,下周继续测其他的。

(2)对配置项和负载parameter值的选取不太好,画到图上空还是有点多,我选值的时候是考虑一个配置在取1、2、3的时候可能变化比较大、取100,200,300的时候就没啥变化。下次等分值域试试看效果。

(3)有些性能分布是没有什么信息量的,比如:

distribution_416.png

就比较平。我想要测出的正常情况下的性能分布是软件达到一些性能瓶颈时的分布,因为用这样的性能分布和bug的性能分布的差异总结出的特征才更有说服力。但是怎么触发性能瓶颈又是一个问题,目前没有什么好办法,不过这个问题不是一个很大的问题。因为如果我全遍历各种配置的值和负载的值,总有一些是触发瓶颈的,只不过也会有很多上图这样的很平淡的。

现在对mariadb的自动化测试、构建性能分布图的工具基本成型,代码约500行(python)(其中上周写了生成测试样例、自动化测试的脚本(170行)这周写了结果入库、画图的代码(300+行))

Clone this wiki locally