code_optimization1_conditional_data_transfer.md

代码优化1:使用条件数据传送代替条件控制

本文是阅读深入理解计算机系统第六章的随笔,也就是如何优化代码.本来最开始谈谈如何优化循环,后来发现这个问题太大了,所以先讲讲简单条件数据传送

条件控制转移

条件控制转移指依据代码的条件结果来选择运行的路径。条件传送指先把结果运行，在依据条件结果选择结果值 在同样的情况下，条件传送性能比条件控制转移高.

我们看看下面的这个例子 这是使用条件控制转移

void minmax1(int a[], int b[], long n) {
  long i;
	for (i  =  0; i < n; i++) {
		if (a[i] > b[i]) {
			long t = a[i];
			a[i] = b[i];
			b[i] = t;
		}
	}
}

我们可以看到其中的实现是通过控制传送，也就是跳转来实现的，现代CPU使用多级流水线的方式工作，后面的指令不需要等待前面指令执行完成即可执行，那么CPU需要对cmpq的结果进行预测，选择一个分支执行，当预测错误时就要丢弃当前的工作，返回跳转处从新执行，这造成了CPU资源极大的浪费，CPU的预测无法保证较高的正确率，因为用户的程序是无法预知的。

汇编层上有两种move指令, 一种是普通的move,另一种是conditional move,三元运算符应用后者, if else应用前者。前者会破坏指令的流水线处理, 使得cache失效； 条件转移不会。

条件数据传送

条件数据传送,定义是我们想利用条件计算值,在用这些值来更新状态.

在上面的代码中我们先计算最大值,最小值.再来使用变更状态.

void minmax2(int a[], int b[], long n) {
  long i;
	for (i  =  0; i < n; i++) {
		long max = a[i]>b[i]?a[i]:b[i];
    long min = a[i]>b[i]?b[i]:a[i];
    a[i] = min;
    b[i] = max;
		}
	}
}

根据计算和上面的代码CPE值(单位周期运算值)从13降低到了4.原因在于第一个函数,预测正确的情况下运算需要3.5, 而一旦预测错误,则会发生20的错误惩罚.