CMU 15-213 Intro to Computer Systems Lecture 10

课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一讲介绍了程序优化。

总览

程序性能不仅仅是渐进复杂度
常数项也很重要！
- 根据代码编写方式很容易产生10：1的性能范围
- 必须在多个级别进行优化：
  - 算法，数据表示，过程和循环
必须了解系统才能优化性能
- 程序如何编译和执行
- 现代处理器+内存系统如何运行
- 如何衡量程序性能并确定瓶颈
- 如何在不破坏代码模块化和通用性的情况下提高性能

编译器优化的局限性

在基本约束下运作
语言和编码风格可能会混淆对程序员而言显而易见的行为
大多数分析仅在程序内执行
大多数分析仅基于静态信息
如有疑问，编译器必须是保守的

通用优化方法

代码移动/预计算

移动代码
- 减少执行计算的频率
  - 如果计算产生相同的结果
  - 尤其是将代码移出循环

例如将代码

void set_row(double *a, double *b,
   long i, long n)
{
    long j;
    for (j = 0; j < n; j++)
		a[n*i+j] = b[j];
}

修改为

long j;
int ni = n*i;
for (j = 0; j < n; j++)
    a[ni+j] = b[j];

强度降低

用简单的方法代替昂贵的操作
移位，加而不是乘或除
- $\text{16 * x-> x << 4}$
- 取决于乘法或除法指令的成本
  - 在Intel Nehalem上，整数乘法需要3个CPU周期
识别乘法顺序

共享常用子表达式

例如将如下代码：

/* Sum neighbors of i,j */
up =    val[(i-1)*n + j  ];
down =  val[(i+1)*n + j  ];
left =  val[i*n     + j-1];
right = val[i*n     + j+1];
sum = up + down + left + right;

修改为

long inj = i*n + j;
up =    val[inj - n];
down =  val[inj + n];
left =  val[inj - 1];
right = val[inj + 1];
sum = up + down + left + right;

删除不必要的过程调用

考虑如下代码：

void lower(char *s)
{
  size_t i;
  for (i = 0; i < strlen(s); i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
      s[i] -= ('A' - 'a');
}

其时间复杂度的图像为：

图像中可以看出该图像不是线性的，不符合原始程序的预期，之所以产生该情形是因为每次循环都调用了strlen(s)，而该函数的时间的复杂度为$O(N)$，所以总体的时间复杂度为$O(N^2)$，高效的代码如下：

void lower(char *s)
{
  size_t i;
  size_t len = strlen(s);
  for (i = 0; i < len; i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
      s[i] -= ('A' - 'a');
}

两者的时间复杂度图像对比如下：

优化阻止者

过程调用

还是之前的例子：

void lower(char *s)
{
  size_t i;
  for (i = 0; i < strlen(s); i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
      s[i] -= ('A' - 'a');
}

不必要的内存引用

/* Sum rows is of n X n matrix a
   and store in vector b  */
void sum_rows1(double *a, double *b, long n) {
    long i, j;
    for (i = 0; i < n; i++) {
        b[i] = 0;
        for (j = 0; j < n; j++)
            b[i] += a[i*n + j];
    }
}

代码在每次迭代中更新$b[i]$
必须考虑这些更新将影响程序行为的可能性

注意每一轮调用$b[i]$是没必要的，所以优化后的代码如下：

/* Sum rows is of n X n matrix a
   and store in vector b  */
void sum_rows2(double *a, double *b, long n) {
    long i, j;
    for (i = 0; i < n; i++) {
        double val = 0;
        for (j = 0; j < n; j++)
            val += a[i*n + j];
            b[i] = val;
    }
}

利用指令级并行性

需要对现代处理器设计有一般的了解
- 硬件可以并行执行多个指令
性能受到数据依赖性的限制
简单的转换可以显着提高性能
- 编译器通常无法进行这些转换
- 浮点运算缺乏结合律和分布律

基准示例：向量的数据类型

/* data structure for vectors */
typedef struct{
	size_t len;
	data_t *data;
} vec;

/* retrieve vector element
   and store at val */
int get_vec_element
  (*vec v, size_t idx, data_t *val)
{
	if (idx >= v->len)
		return 0;
	*val = v->data[idx];
	return 1;
}

void combine1(vec_ptr v, data_t *dest)
{
    long int i;
    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++) {
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

其中data_t可以是如下几种数据类型之一：

int
long
float
double

OP是如下运算符之一：

$+ / 0$
$ * / 1$

为了描述性能，这里引入每个元素的周期数（Cycles Per Element，CPE）

表达对向量或列表进行操作的程序性能的便捷方法
长度$= n$
在我们的示例中：CPE=每个OP的周期
$T = CPE * n +\text{开销}$

示例的表现

combine1的效果如下：

接着考虑如下代码：

void combine4(vec_ptr v, data_t *dest)
{
  long i;
  long length = vec_length(v);
  data_t *d = get_vec_start(v);
  data_t t = IDENT;
  for (i = 0; i < length; i++)
    t = t OP d[i];
  *dest = t;
}

combine4的效果如下：

超标量处理器

定义：超标量处理器可以在一个周期内发出并执行多条指令。指令是从顺序指令流中检索的，通常是动态调度的。
好处：无需编程，超标量处理器就可以利用大多数程序具有的指令级并行性。
大多数现代CPU是超标量的。
英特尔：自奔腾（1993）。

例子

long mult_eg(long a, long b, long c) {
    long p1 = a * b;
    long p2 = a * c;
    long p3 = p1 * p2;
    return p3;
}

将计算分为阶段
逐阶段传递部分计算
一旦值传递给$i + 1$，我就可以开始新的计算阶段
例如，即使每个周期需要3个周期，也要在7个周期中完成3次乘法（假设可以并行执行两个操作）

图示如下：

循环展开

循环展开是指每轮循环中执行多次操作，例如如下代码：

void unroll2a_combine(vec_ptr v, data_t *dest)
{
    long length = vec_length(v);
    long limit = length-1;
    data_t *d = get_vec_start(v);
    data_t x = IDENT;
    long i;
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
		x = (x OP d[i]) OP d[i+1];
    }
    /* Finish any remaining elements */
    for (; i < length; i++) {
		x = x OP d[i];
    }
    *dest = x;
}

效果如下：

如果OP满足结合律，还可以将上述代码改写为

void unroll2aa_combine(vec_ptr v, data_t *dest)
{
    long length = vec_length(v);
    long limit = length-1;
    data_t *d = get_vec_start(v);
    data_t x = IDENT;
    long i;
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
		x = x OP (d[i] OP d[i+1]);
    }
    /* Finish any remaining elements */
    for (; i < length; i++) {
		x = x OP d[i];
    }
    *dest = x;
}

效果如下：

再来看一个例子：

void unroll2a_combine(vec_ptr v, data_t *dest)
{
    long length = vec_length(v);
    long limit = length-1;
    data_t *d = get_vec_start(v);
    data_t x0 = IDENT;
    data_t x1 = IDENT;
    long i;
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
       x0 = x0 OP d[i];
       x1 = x1 OP d[i+1];
    }
    /* Finish any remaining elements */
    for (; i < length; i++) {
		x0 = x0 OP d[i];
    }
    *dest = x0 OP x1;
}