数据库系统实现课程笔记之：提高程序性能

一：提高程序性能
1. 磁盘（Disk）未必比内存（Memory）慢。

原理：Memory的随机存取（random access）需要消耗大量时间，数量级大概是500+个cycle，也就是每次随机存取，CPU都要花时间等数据从内存读过来。而虽然磁盘一次读取的时间确实比内存慢很多，但是顺序读取的话，系统会自动预读下一个数据放在L2 cache里面，而从L2到CPU里面的时间只需一个cycle；也就是说，在磁盘顺序读取大量数据，忽略掉overhead，可以达到一个cycle一组数据的速度，如果你的硬盘速度是5G/s，那平摊速度也基本达到5G/s。当然这个还跟硬盘数据存储结构有关，硬盘有很多能平行存取的盘，横向存数据的话就能平行地同时读取下一组数据；如果数据是纵向存在同一个盘的就不行，但是如果两次读取之间的其他代码cycle足够多的话，还是一样省时间（不过内存的随机存取，有足够的代码塞在两次读取之间也可以避免浪费时间）。

应用举例：将磁盘里的数据依次读出放在链表（不放数组是因为有时候不知道数据长度）里面以便下次读取，不如在需要时直接从磁盘读取。

2. 条件语句极大降低运行速度。

原理：学过Architecture的应该知道，进行条件语句（branch，包括循环的条件）的执行时，由于系统要预先读入一定数量的命令来增加速度，便进行条件语句块的猜测（即猜测是否进入if块还是else块），如果真的执行到那个条件语句时发现猜测是错误的，就把之前预读预先执行的命令全部回退掉（flash），重新执行正确的部分。结果就是之前的那些cycle时间都浪费掉，而且命令也是从内存读入的，命令指针改变了，就需要等待新的地址下的命令（即随机读取，需要500cycle）。因此我们应该尽量避免使用条件语句，或者避免预测错误。另外提一下：条件语句块的猜测（branch predicate）第一次会进入else的部分，每次执行后会记录更改predicate table以便下次有数据参照进行预测，至于用什么策略进行猜测是系统决定的。

应用举例：写如下语句纯属浪费时间，直接一句 num = 0; 就好了。

if(num != 0)  
    num = 0;

另外应该尽量使预知第一次会进入的语句块放在else部分，并尽量避免多层的if-else语句。

for(int i=0; i<100; i++){  
    if( i != 0)  
        ; //nothing to do  
    else //i初始为0,会进入这部分语句块  
        Initialization();  
    if( i == 99)//前99次循环都不会试图进入这个语句块  
         Finalize();  
} 

3. 初学者式的代码能获得最快速度。

原理：因为人们在设计系统时就是假设程序员用很笨的方式写代码，而不可能要求程序员去了解底层实现来写适应于系统的巧妙代码。故不要变着花样写很聪明代码，其实说不定反而比笨的方法慢。这在编程里是个很著名的理论KISS，Keep it simple as stupid. 另外数组的顺序读取能获得最快的速度（一个cycle一句），系统会自动预读下一个数据，不要为了避免执行一些语句而不停地改变下标（index），尤其数组倒序读取是非常非常慢的，等于每一次都是随机存取（因为预读的都是不需要的，还占用缓存）。话说自从学了这门课，我非常热爱数组，有一次我把使用的某数据结构从链表改成数组，运行时间从2个多小时变成不到1小时。

应用举例：

int sum = 0;  
for(int i=0; i<100; i++){  
    if(a[i] >= 0)//不要写类似于if(a[i] <0) i++; 来跳过某些index的语句  
        sum += a[i];  
}  

4. 尽量避免多线程同步，避免来回new和delete对象。

原理：由于执行同步代码时，系统并不是真的把所有时间分配给正在执行的线程，而是当其他线程要执行时会不停不停地访问某个token是否有执行权限，一直到这个token被释放，这是一个非常浪费时间的操作。因此应该尽量避免使用多线程同步，避免在两个线程里读写同一个数据。当然这在某些情况下并不是那么容易做到，推荐的方法是，建立一个专门处理信息交换的类作为通道（就是将同步范围尽量降低），或者将需要读写的数据块分成不同部分单独分配给不同线程专门操作，比如将1000长度的需要排序的数组分成四个，每个线程250= =，处理后再合起来。避免来回new和delete也是同样避免同步的道理，某线程new和delete对象时所有线程都要等待，很消耗时间。推荐的方法是，将要delete的对象用专门的类管理起来，下次需要时再从中分配，直到真的不再需要时再delete。