1. 现代处理器
2. 处理器的抽象模型-关键路径
3. 循环展开
4. 并行计算
5. 优化的限制因素
6. 内存性能
7. 章节总结

现代处理器

1. 整数运算, 浮点乘, 整数和浮点数除法, 分支
2. 整数运算, 浮点加, 整数乘, 浮点乘
3. 加载, 地址计算
4. 加载, 地址计算
5. 存储
6. 整数运算
7. 整数运算, 分支
8. 存储, 地址计算

处理器的抽象模型-关键路径

练习 5.5 求多项式的和转换成程序的效率

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 = xpwr * x;
    }
    return result;
}

练习 5.6 改进的多项式算法

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;
}

循环展开

void combine5(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = v->data;

    data_t acc = IDENT;

    //按照步长2来循环, 为了控制循环不用越界, 必须将length-1之后和i比较, 这样在处理循环尾部的时候可以方便.
    for (i = 0; i < limit; i += 2) {
        acc = (acc OP data[i]) OP data[i + 1];
    }

    //如果limit是奇数比如5, 则原始length是6, 从0开始0, 2 , 4, 6 , 到 i= 6 的时候就会结束循环, 此时会正常加完了 i[0]到i[5]
    //如果limit是偶数比如4, 则原始length是5, 从0开始0, 2, 4, 到i=4的时候就会结束循环, 此时已经加完了i[0]到i[3], 还差一个i[4], 所以要处理一下循环尾部
    for (; i < length; i++) {
        acc = acc OP data[i];
    }

    *dest = acc;
}

并行计算

void combine6(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = v->data;

    //两个临时变量
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;

    //依然按照2次循环展开
    for (i = 0; i < limit; i += 2) {
        acc0 = acc0 OP data[i];
        acc1 = acc1 OP data[i + 1];
    }

    //循环结束的时候加在哪一个变量上都行, 因为是可结合可交换的
    for (; i < length; i++) {
        acc0 = acc0 OP data[i];
    }

    //将两个临时变量拼起来
    *dest = acc0 + acc1;

}

for (i = 0; i < limit; i += 2) {
    acc = (acc OP data[i]) OP data[i + 1];
}

for (i = 0; i < limit; i += 2) {
    acc = acc OP (data[i] OP data[i + 1]);
}

练习题5.8 不同指令的计算效率

double aprod(double a[], long n) {
    long i;
    double x, y, z;
    double r = 1;
    for (i = 0; i < n - 2; i += 3) {
        x = a[i];
        y = a[i + 1];
        z = a[i + 2];
        r = r * x * y * z;
    }

    for (; i < n; i++) {
        r *= a[i];
    }
    return r;
}

1. r = ((r * x) * y) * z;
2. r = (r * (x * y)) * z;
3. r = r * ((x * y) * z);
4. r = r * (x * (y * z));
5. r = (r * x) * (y * z);

1. 很显然, 关键路径上临时变量被计算了三次乘法, 考虑到这是三次循环展开, 所以总的计算次数是n次, 而且没有并行, 因此CPE下限就是5
2. 这相当于3 x 1a 展开, 关键路径上临时变量只计算了两次, 因此理论性能是 CPE* 2/3 = 3.33
3. 这相当于充分的利用了并行能力, 因此CPE的极限是 5/3 = 1.67
4. 这种情况和上一个是相同的
5. 这个也是计算了两次, 和第二种情况相同

优化的限制因素

1. 寄存器溢出. 如果并行所需的变量超过了寄存器的存储能力, 寄存器会和内存通信用栈来存储变量, 那么维护多个临时变量用于并行计算的效果就会变差, 因为与内存通信的周期在200左右, 相比寄存器0-1周期的速度, 要差很多.
2. 分支预测错误惩罚, 对于一般像判断数组越界的调用, 处理器可以有效的将判断设置为预测判断成功, 这样只有最后一次会导致错误惩罚, 这就是为什么再一开始减少过程调用发现并没有改善性能的原因. 如果一个分支可以合理的预测(比如循环多次直到满足某个条件才结束的循环, 一般处理器都会预测每次是成功的.), 则这个地方一般不会构成性能瓶颈.
3. 将条件跳转改成条件传送, 这个需要单独说一下.

练习5.9 重写更高效的代码

//合并归并排序的数组
void merge(long src1[], long src2[], long dest[], long n) {
    long i1 = 0;
    long i2 = 0;
    long id = 0;

    //将两个数组的元素按照大小顺序放进dest[]
    while (i1 < n && i2 < n) {
        if (src1[i1] < src2[i2]) {
            dest[id++] = src1[i1++];
        } else {
            dest[id++] = src2[i2++];
        }
    }

    //两个数组比较完成之后, 将剩余的部分按顺序放进去
    while (i1 < n) {
        dest[id++] = src1[i1++];
    }

    while(i2 < n) {
        dest[id++] = src2[i2++];
    }
}

while (i1 < n && i2 < n) {
    dest[id++] = src1[i1] < src2[i2] ? src1[i1++] : src2[i2++];
}

内存性能

练习 5.10 内存引用对于性能的影响

void copy_array(long *src, long *dest, long n){
    long i;
    for (i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

练习5.11 为何性能很差?

.L5:                                        loop:
    vmovss -4(%rsi, %rax, 4), %xmm0             Get p[i-1]
    vaddss (%rdi, %rax, 4), %xmm0, %xmm0        Add a[i]
    vmovss %xmm0, (%rsi, %rax, 4)               Store at p[i]
    addq   $1, %rax                             Increment i
    cmpq   %rdx, %rax                           Compare i:cnt
    jne    .L5                                  If !=, goto loop

练习 5.12 改写代码

vomvss -4(%rsi, %rax, 4), %xmm0             进入循环之前读取p[i-1]
.L5:
    vaddss (%rdi, %rax, 4), %xmm0, %xmm0    p[i-1]+=a[i]
    vmovss %xmm0, (%rsi, %rax, 4)           存入p[i]
    addq   $1, %rax                         i++
    cmpq   %rdx, %rax                       比较
    jne    .L5                              循环

总结

1. 消除连续和反复的函数调用
2. 消除不必要的内存引用
3. 展开循环
4. 使用多个累积临时变量, 充分利用机器的吞吐和指令级并行
5. 重写条件操作为条件传送指令