不要轻易做所谓的“优化”工作 【二】

---

对于求多项式 $a_0+a_1x+a_2x^2+ \cdots +a_nx^n$
朴素的做法是：

double poly0(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;
    }
    return result;
}

这样做需要 n 个加法，2n 个乘法
然后会有人告诉你，可以利用 Horner's method 优化：$a_0+x(a_1+x(a_2+ \cdots +x(a_{n-1}+xa_n))$

double poly1(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;
}

这样做只需要 n 个加法，n 个乘法

【前方高能预警】

但其实“优化前“比“优化后”还快
因为“优化前”的一个循环里的一个加法和两个乘法是可以并行计算的，三个运算同时进行
而“优化后”的一个循环里的一个加法和一个乘法是不可以并行计算的，加法要等乘法完毕后才能开始
至于为什么，详见 CSAPP 5.7，下面简单说一下

• “优化前”：
  两个乘法可以并行是因为CPU里有两个 functional unit 可以进行浮点数乘法
  加法可以和乘法并行是因为当前循环的加法可以留待与下一循环的乘法并行
• “优化后”：
  很明显加法与乘法是互相依赖的
  当前循环的乘法依赖上一循环的加法
  当前循环的加法依赖当前循环的乘法
  下一循环的乘法又依赖当前循环的加法
  所以加法与乘法不能并行

@诟屍 这就是所谓的“毁三观”吗？哈哈。。。有意思。然而，是否可以并行，算不算需要考虑的因素？

@bintou 既然已经是在讨论常数时间复杂度了，并行是事实，CPU觉得可以并行的话，就会自动帮你并行，不考虑地话就脱离实际了

可是这使得我们落入猜测编译器（或cpu）会不会帮我们优化的窘境。。 我觉得，应该考虑单线程无并发的情况会简单一点。。 但又有点脱离实际了。
在CLRS里的ram模型就是那样的。

@ping1008 就是在单线程无并发的情况下了，几个运算并行是一个CPU核心内部的
当你要优化常数时，这些是必须要考虑的因素
CLRS 的重点不是常数，自然不会考虑这些