简明x86汇编语言教程(7)

核心提示：程序采用的是一个时间复杂度为O(n)的算法，不过，简明x86汇编语言教程(7)(2)，我们可以把他轻易地改为O(1)的算法： // 程序段2 (非规范改进) int GetFactorial(int k){ int i, j=1;

程序采用的是一个时间复杂度为O(n)的算法，不过，我们可以把他轻易地改为O(1)的算法：

// 程序段2 (非规范改进) int GetFactorial(int k){ 　int i, j=1; static const int FractorialTable[]={1, 1, 2, 6, 24, 　　120, 720, 5040, 40320, 362880, 3628800}; if((k<0) || (k>=10)) return -1; return FractorialTable[k]; }

这是一个典型的以空间换时间的做法。通用的编译器不会这么做——因为它没有办法在编译时确定你是不是要这么改。可以说，如果编译器真的这样做的话，那将是一件可怕的事情，因为那时候你将很难知道编译器生成的代码和自己想的到底有多大的差距。

当然，这类优化超出了本文的范围——基本上，我把它们归入“算法优化”，而不是“程序优化”一类。类似的优化过程需要程序设计人员对于程序逻辑非常深入地了解和全盘的掌握，同时，也需要有丰富的算法知识。

自然，如果你希望自己的程序性能有大幅度的提升，那么首先应该做的是算法优化。例如，把一个O(n2)的算法替换为一个O(n)的算法，则程序的性能提升将远远超过对于个别语句的修改。此外，一个已经改写为汇编语言的程序，如果要再在算法上作大幅度的修改，其工作量将和重写相当。因此，在决定使用汇编语言进行优化之前，必须首先考虑算法优化。但假如已经是最优的算法，程序运行速度还是不够快怎么办呢？

好的，现在，假定你已经使用了已知最好的算法，决定把它交给编译器，让我们来看看编译器会为我们做什么，以及我们是否有机会插手此事，做得更好。

5.1 循环优化：强度削减和代码外提

比较新的编译器在编译时会自动把下面的代码：

for(i=0; i<10; i++){ 　j = i; 　k = j + i; }

至少变换为

for(i=0; i<10; i++); j=i; k=j+i;

甚至

j=i=10; k=20;

当然，真正的编译器实际上是在中间代码层次作这件事情。

原理 如果数据项的某个中间值(程序执行过程中的计算结果)在使用之前被另一中间值覆盖，则相关计算不必进行。

也许有人会问，编译器不是都给咱们做了吗，管它做什么？注意，这里说的只是编译系统中优化部分的基本设计。不仅在从源代码到中间代码的过程中存在优化问题，而且编译器生成的最终的机器语言(汇编)代码同样存在类似的问题。目前，几乎所有的编译器在最终生成代码的过程中都有或多或少的瑕疵，这些瑕疵目前只能依靠手工修改代码来解决。

5.2 局部优化：表达式预计算和子表达式提取

表达式预先计算非常简单，就是在编译时尽可能地计算程序中需要计算的东西。例如，你可以毫不犹豫地写出下面的代码：

const unsigned long nGiga = 1024L * 1024L * 1024L;

而不必担心程序每次执行这个语句时作两遍乘法，因为编译器会自动地把它改为

const unsigned long nGiga = 1073741824L;

而不是傻乎乎地让计算机在执行到这个初始化赋值语句的时候才计算。当然，如果你愿意在上面的代码中掺上一些变量的话，编译器同样会把常数部分先行计算，并拿到结果。