算法性能黑洞

在软件层面分析一个program/function性能效率的时候，我们都会用算法分析中O(n)， Θ(n)，Ω(n)分别来描述算法在最差情况，平均情况，最好情况时的执行效率。但是如果算法量级相差常数级别的情况下，例如，O(2n)和O(n)，反而会出现O(2n)的实际执行时间比O(n)时间短。这是因为我们只做了算法层面的分析，但是源代码如何被编译器编译的，处理器怎么处理指令的完全没有考虑。尤其是现代处理器中超标量，乱序执行以及编译器的优化技术会使得一些在算法层面明显快的，反而没有好的性能。接下来我们用一个多项式求值的例子，先进行算法分析，再给出实验结果，然后从处理器层来简单地解释下原因。

任务

实现对degree为n的多项求值的函数。

degree为n的多项式

普通实现

double poly(double a[], double x, long degree)
{
    long i;
    double result = a[0];
    double xpwr = x;
    for (i = 1; i <= degree; i++) {
        result += a[i] * xpwr;
        xpwr = x * xpwr;
    }
    return result;
}

这个实现，循环内一共2次乘法，1次加法，一共degree次循环。算法复杂度O(2*degree*a + degree*b). 其中a为一次加法执行的时间，b为一次乘法执行的时间，并且我们有理由认为b > a;

Horner 法

对多项式进行改变

Horner法

double polyh(double a[], double x, long degree)
{
    long i;
    double result = a[degree];
    for (i = degree - 1; i >= 0; i--)
        result += a[i] + x * result;
    return result;
}

这个实现，循环内一共1次乘法，2次加法，一共degree次循环。算法复杂度O(degree*a + 2*degree*b). 显然乘法次数少了，比普通实现是要快的。

计时实验代码

/*
 * degree = 1e6
 * a[] =  1000以内随机double浮点数
 * x = 1234.3
 */
int main()
{
    const long degree = 1e6;
    int i;
    double a[degree+1];
    double x;
    clock_t start, end;

    srand((unsigned) time(NULL)); 
    for (i = 0; i < degree + 1; i++)
        a[i] = rand() / ( (double)RAND_MAX/1000.0 );
;
    x = 1234.3; 
   
    start = clock();
    poly(a, x, degree);
    end = clock();

    printf("method 1: %lf\n", (double)(end - start)/CLOCKS_PER_SEC);

    start = clock();
    polyh(a, x, degree);
    end = clock();

    printf("method 2: %lf\n", (double)(end - start)/CLOCKS_PER_SEC);

    return 0;
}

• 实验平台
  OS：macOS10.13
  CPU：Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz
• 编译工具以及指令
  clang
  cc source.c # cc = clang 没有任何优化选项
• 实验结果

method 1: 0.003716
method 2: 0.005242

我们可以看到，Horner法实现的算法明显优于普通实现，但是实际执行就是慢了。接下来我们从处理器层分析为什么慢了！

处理器层分析

首先我们之前假设了乘法比加法要慢，但是由于现代处理器的乱序执行，使得指令能够并行执行。数据与控制无关的指令，只要功能单元足够，就可以并行执行。由于普通版的实现，下一次迭代要等待上一次迭代的xpwr计算出来才能进行。因此如果用CPE表示性能，那么普通版的CPE=b（请注意， x * result 和 result += 可以分别通过指令并行和循环展开解决）。而Horner法实现的，循环内部也有数据相关，而且无法通过循环展开解决。（a[i] + 依赖于 x * result 的结果，所以得先乘法做完，再做加法）因此Horner法的CPE=a+b；

因此我们可以解释Horner法在当前处理器，机器，编译条件下为什么比普通实现慢了。当然，我们稍微改动下编译选项 ，实验结果截然不同。下面是不同编译选项下的实验结果

• 实验结果

实现方法	-Og	- O1	-O2	-O3
普通版本	0.000002	0.000002	0.000002	0.000003
Horner法	0.000000	0.000002	0.000002	0.000001

总结

软件层面的算法相差常数数量级的时候，并不代表着常数低的算法性能好。利用不同编译优化规则，甚至在不同处理器上运行，性能结果都有不同。

参考

Computer Systems: A Programmer's Perspective (3rd Edition)