分类： 服务器与存储
2012-03-26 09:01:25
什么是优化？优化就是为了得到更高效的程序。换而言之，就是更快以及（或者）更小的程序。
Optimization = more efficient code = faster code and/or compact code.
优化可以在四个层面上进行：算法层(Algorithm) ，语言层(Language)，汇编层(Assembly)，处理器层(Processor)。
算法层(Algorithmic)：
时间复杂度（Order of growth，大O）可以衡量一个算法的性能，包含常数阶(constant,O(1))，对数阶(logarithmic, O(log2n))，线性阶(linear,O(n))，线性对数阶(log-linear, O(n log2n))，K次方阶(to the power of K, O(nk))，指数阶(exponential, O(kn))。
语言层(Language):
语言的选择——解释型语言(Interpreters)：PHP、Perl、Ruby、JS；框架式语言(Frameworks)：.Net、Java； 面向对象语言(Objective)：C++、Objective-C；低级语言(Low Level)：C、fortran……；汇编(Assemblers)。语言的执行效率与开发难度都顺次递增。
利用语言的特性，比如关键字以及#pragma指令。
汇编层(Assembly)
一般交给编译器(Compiler)优化，不同的优化选项会得到不同的汇编。开发人员也可以自己编写汇编，比如在C语言中使用__asm{}直接编写汇 编。不同的CPU支持不同的指令集：MMX(Pentium)、MMX2(Pentium-II)、SSE(Pentium-II、Pentium- III)、SSE2(Pentium-III、Pentium-IV)、SSE3(Pentium-IV)。开发者可以根据目标CPU选择合适的指令。
处理器层(Processor)
绝大多数情况下由CPU完成优化，对开发者透明。CPU可以通过使用缓存(Caches)、寄存器(Registers)、分支(branching)、 管道(piplines)等方式优化程序。CPU也可以预取指令(pre-fetch)以及重新组织(re-organize)指令执行顺序来提高效率。 因为CPU包含许多子组件，比如ALU(Arithmetic Logic Unit, 算术逻辑单元)和FPU(Float Point Unit，浮点运算单元)，各组件是可以并行工作的，所以指令执行的顺序也影响程序的性能。
大多数程序员认为程序只能通过算法来优化，并且坚信算法复杂度是最重要的因素，算法复杂度越低则程序越高效。其实这种想法有两个误区，其一是优化可以在多 个层面进行；其二是复杂度只取最高指数项并省略掉前面的常数，设想n不超过1000时，一个复杂度为10000*n与复杂度为3*n2的算法哪个效率更高些？
优化的一个实例：排序(Sorting)
----------算法层-----------
首先是算法的选择：冒泡排序法(Bubble Sort)、堆排序法(Heap Sort)、基数排序法(Radix Sort)还是快速排序法(Quick Sort)?
| 算法 | 时间复杂度 | 空间复杂度 |
| Bubble Sort | O(n2) | 1 |
| Heap Sort | n log2n | 1 |
| Radix Sort | n | n |
| Quick Sort | n log2n | log2n |
如果我们选择第一种冒泡排序，并用C语言实现：
void bubbleSort(void *A) {
bool swapped = false;
do {-
lastSwap = 0
for (i = 0; i <= len(n) - 2; i++) {
if (greater(A[i], A[i+1])) {
swap(A[i], A[i+1]);
swapped = true;
} /* end if */
} /* end for each */
} while (swapped);
} /* end bubbleSort */
上述代码仍然可以在算法层进行优化：
void bubbleSort(void *A) {
bool swapped = false;
n = len(A); /* Saves n operations per iteration */
do {
lastSwap = 0;
for (i = 0; i <= len(n) - 2 n - 2; i++) {
if (greater(A[i], A[i+1])) {
swap(A[i], A[i+1]);
lastSwap = i + 1; /* Optimizes 50% Iterations */
swapped = true;
} /* end if */
} /* end for each */
n = lastSwap;
} while (swapped);while(n > 1);
} /* end bubbleSort */
上述代码做了两个优化：1、把len(A)从循环中提取出来，这样可以省去n次迭代；2、用lastSwap代替swapped，这样可以省去50%的迭代。(注：每次迭代中被交换到最后的最大值不需要进行下次迭代。）
----------语言层-----------
继续对上述代码优化：
inlinevoid bubbleSort(void *A) {
register n = len(A);
do {
lastSwap = 0;
for (i = 0; i <= n - 2; i++) {
if (greater(A[i], A[i+1])) {
swap(A[i], A[i+1]);
lastSwap = i + 1;
} /* end if */
} /* end for each */
n = lastSwap;
} while(n > 1);
} /* end bubbleSort */
利用C语言的关键字inline（严格意义上是C++的关键字）和register同样可以优化程序。inline关键字可以把函数展开而省去函数调用的 开销，而register关键字可以保证n的值每次都是从寄存器中读取/写入，从而省去读取内存的开销。（注：与register相对的是 volatile，告诉编译器不能把这个变量放入寄存器中，必须从内存中读取。）
swap函数的传统实现方式如下：
swap (void **a, void **b) {
void *t = *a;
*a = *b;
*b = t;
}
（注：此时调用者应该这么写：swap(&A[i], &A[i+1]);）
利用C语言的特性，我们可以这样改写：
Swap (void **a, void **b)
{
*a += *b; /* sets a to be (a + b) */
*b -= *a; /* b is b-(a+b) = -a */
*b = -*b; /* b is now a */
*a -= *b; /* a is now a + b - a = b */
}
这样的改写可以省去一个局部变量的开销，但是上面的代码有一个bug：因为指针是32位的值（在32位机上），两个32位值相加可能会有overflow的情况。解决这个bug的方法如下：
Swap (void **a, void **b)
{
*a ^= *b; /* sets a to be (a xor b) */
*b ^= *a; /* b is b xor (a xor b) = a */
*a ^= *b; /* a is (a xor b) xor a = b */
}
----------汇编层-----------
使用visual studio 2010的cl.exe对函数
swap (void **a, void **b) {
void *t = *a;
*a = *b;
*b = t;
}
进行汇编。（注：栈地址向下增长。）
若选项设为/O0（不优化），得到的汇编为：
PUBLIC _swap
; Function compile flags: /Odtp
_TEXT SEGMENT
_t$ = -4 ; size = 4
_a$ = 8 ; size = 4
_b$ = 12 ; size = 4
_swap PROC
; Line 2
push ebp
mov ebp, esp
push ecx
; Line 3
mov eax, DWORD PTR _a$[ebp] ; 把参数a放入寄存器eax
mov ecx, DWORD PTR [eax] ; 把eax所指值(*a)放入寄存器ecx
mov DWORD PTR _t$[ebp], ecx ; 把ecx的值(*a)放入局部变量t里，即t=*a
; Line 4
mov edx, DWORD PTR _a$[ebp] ; 把参数a放入寄存器edx
mov eax, DWORD PTR _b$[ebp] ; 把参数b放入寄存器eax
mov ecx, DWORD PTR [eax] ; 把(*b)放入寄存器ecx
mov DWORD PTR [edx], ecx ; 把ecx的值写入(*a)，即*a=*b
; Line 5
mov edx, DWORD PTR _b$[ebp] ; 把参数b放入寄存器edx
mov eax, DWORD PTR _t$[ebp] ; 把局部变量t放入寄存器eax
mov DWORD PTR [edx], eax ; 把eax的值(t)写入edx所指内存(*b)，即*b=t
; Line 6
mov esp, ebp
pop ebp
ret 0
_swap ENDP
_TEXT ENDS
END
如果设置优化选项为/O1（实际上设置为/O2、/Ox得到的结果是一样的），生成的汇编为：
PUBLIC _swap
; Function compile flags: /Ogspy
; COMDAT _swap
_TEXT SEGMENT
_a$ = 8 ; size = 4
_b$ = 12 ; size = 4
_swap PROC ; COMDAT
; Line 2
; 省略了push ebp以及mov ebp, esp
; Line 4
mov edx, DWORD PTR _b$[esp-4] ; 把参数b存入edx。因为没有把ebp压栈（需要4个字节），所以esp-4相当于优化前的ebp
mov eax, DWORD PTR _a$[esp-4] ; 把a存入eax
mov ecx, DWORD PTR [eax] ; 把*a存入ecx
push esi
mov esi, DWORD PTR [edx] ; 把*b存入esi
mov DWORD PTR [eax], esi ; 把*b存入*a，即*a=*b
; Line 5
mov DWORD PTR [edx], ecx ; 把*a（未赋值前）放入*b，即*b=*a。此处ecx充当了t的作用
pop esi
; Line 6
ret 0
_swap ENDP
_TEXT ENDS
END
可以看到优化后省略了一个ebp压栈操作，以及省略了局部变量t。生成的汇编指令更少，自然就更高效。
----------处理器层-----------
大多数情况下这层的优化是透明的，程序员很难预料CPU会作做什么优化，而且在多线程程序里CPU的一些优化可能会导致一些问题。
尽管如此，程序员仍然可以做一些优化，因为不同的CPU支持不同的指令集，所以可以根据目标CPU选择要生成的汇编指令集．如果目标CPU不定，比如某些 客户用PetiumIV，而有些用PetiumII，可以生成两个不同的dll，一个专门为PetiumIV进行优化，而另一个只运行在PetiumII 上而不做优化．在程序运行时，根据目标机的CPU类型（在Windows可以调用GetSystemInfo）调用合适的dll.
