优化程序性能 tips

【引用】编写高效程序需要做到以下几点：

必须选择适当的算法和数据结构；
必须编写出编译器能够有效优化以转换成高效可执行代码的源代码；
针对处理运算量特别大的计算，将一个任务分成多个部分，这些部分可以在多核和多处理器的某种组合上并行地计算。

对于新手程序员来说，不断修改源代码，试图欺骗编译器产生有效的代码，看起来很奇怪，但是这确实是编写高性能程序的方式。（但是，写出奇怪的代码就不好维护吧？）

消除循环的低效率

直接看例子：

 // 把一个字符串中所有的大写字母转化成小写字母

 void lower1(char *s) {
    long i;

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

void lower2(char *s) {
    long i;
    long len = strlen(s);

    for (i = 0; i < len; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= ('A' - 'a');
        }
    }
}

size_t strlen(const char *s) {
    long length = 0;
    while (*s != '\0') {
        s++;
        length++;
    }
    return length;
}

C 语言中执行获取 stelen 的时间为 O(n), 因此在 for 循环中每次循环都执行 strlen 将使得程序运行时间为 O(n^2), 但是对于其他语言，例如 Swift，string.length 是其一个常量。因此可以在 for 循环中调用 string.length 而不会拖慢程序运行速度。 这就要求我们对诸如语言标准库等的 API 比较熟悉。

类似于 lower* 这样的函数，有可能在工程里调用无数次。而 lower1 和 lower2 之间看似无足轻重的区别，效率却可能千差万别。有经验的程序员的工作的一部分就是避免引入这样的渐进低效率的代码。

减少过程调用

消除不必要的内存引用

data_t *get_vec_start(vec_ptr v) {
  return v->data;
}

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

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

combine3 和 combine4 之间的区别，主要是 combine4 将结果累计在临时变量中，消除了每次循环迭代中从内存中读取并将更新值写回内存的需要。

题外话：combine3 用带命令行选项 “-O2” 的 gcc 编译时，性能远好于使用 “-O1”

现代编译器的优化能力有时会掩盖不同水平程序员之间的差异

理解现代处理器

循环展开

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

循环展开能从两方面改进程序的性能：

它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。
它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上操作数量。

void combine5(vec_ptr v, data_t *dest) {
  long i;
  long length = vec_length(v);
  long limit = length - 1;
  data_t *data = get_vec_start(v);
  data_t acc = IDENT;
  
  for(i = 0; i < limit; i+=2) {
    acc = (acc OP data[i]) OP data[i+1];
  }
  for(; i < length; i++) {
    acc = acc OP data[i];
  }
	
  *dest = acc;
}

旁注：编译器很容易地执行循环展开。只要优化级别设置得足够高，许多编译器都能例行公事地做到这一点。用 -O3 或者更高等级调用 GCC，它就会执行循环展开。