从CPU层面谈谈优化

大多数时间，大家都在从设计和算法上优化效率（这类优化往往效果比较明显，比如一个二分查找可以轻易将时间复杂度降低为lg(n))。但是在实现上，却很少有人注重实现效率，而理由是反正每年都会有更高频率的CPU出现，我何必花那个心思呢（Java程序员尤其擅长使用这个理由@_@)。

我个人不是完全同意上面的说辞，在不影响代码的可读性和花费不高的代价下，我习惯性的会写最我当前所知道的性能最高的写法。

在很早以前，我一度只有在编写汇编时才可以计算出汇编条数。随着代码量的增加，我慢慢意识到，这种想法是错误的。即使在写C语言时，其实生成的汇编也时有迹可寻的。

程序中所有代码一般都分为三个步骤（有些汇编指令会合并其中的某几步)。

1. 从内存读到寄存器（有可能直接从cache读）
2. 操作寄存器进行运算,并将结果保存在寄存器
3. 将结果写入内存（有可能会同时写入cache)

一般步骤1和3是对称的，只要步骤1的效率高，步骤3会同样高效。因此下面只分析步骤1和步骤2。

先来定义几个数据结构：

struct foo {
    int b;
    int a;
};
struct bar {
    struct foo f;
    struct foo *fp; //assume fp = &f
};

影响访问内存效率的第一个因素，汇编条数：

int access1(struct bar *b)
{
    return b->f.a;
}
int access2(struct bar *b)
{
    return b->fp->a;
}

在上面代码中access1比access2快一倍，这是因为结构体嵌套，不论嵌套多少层，其子成员偏移量都是常量。因此`b->f.a` 等价于`int a = *(int*)((unsigned char *)b + 4)`，所以这句代码翻译成汇编就是`movl 4(%rdi),%eax`(这里%rdi就是b的值)。

而access2就必须要经过两次内存访问, `struct foo *p = ((unsigned char *)b + 8); int a = *(int)((unsigned char *)p + 4)`。 翻译成汇编就成了`movq 8(%rdi),%rax, movl 4(%rax), %eax`(这里%rdi同样是参数b）。

因此当你写出类似下面代码时请慎重。

b->fp->a = xx;
b->fp->b = xx;
b->fp->c = xx;
b->fp->d = xx;
b->fp->e = xx;

反观下面的代码，除了代码前缀长一点，却并不会产生什么问题。

b->fp.a = xx;
b->fp.b = xx;
b->fp.c = xx;
b->fp.d = xx;
b->fp.e = xx;

影响访问内存效率的第二个因素, 访问内存的频率。 也许很多人都写过类似下面的代码:

void test(struct bar *b)
{
    int i;
    for (i = 0; i < b->foo.a; i++)
        do_something()
}

编译器在执行优化时，一般不会使用寄存器缓存指针指向的内容和函数调用的返回结果（这个不同的编译器实现可能不太一样，至少我使用的GCC在O2的情况下并不会做此优化），我称之为指针不可优化原则。因为从理论上来讲内存是整个进程共享的，而进程中到底会有多少个线程编译器并不知晓，它并不知道在执行for期间，b->foo.a是否会被其他线程修改。函数调用也是同理。

这也意味着每执行一次do_somthing之后都会先去访问b->foo.a的值，再来比较。这会增加访存次数, 即使有cache的存在，也没有直接访问寄存器来的快。因此这时我们可以向编译器做个暗示(增加一个局部变量，告诉编译器，我们需要的这个值，在for循环期间不会变化)，比如像下面这样。

void test(struct bar *b)
{
    int i, n = b->foo.a;
    for (i = 0; i < n; i++)
        do_something()
}

影响访问内存效率的第三个因素, CPU CACHE。

数据结构的设计与CPU CACHE的命中率其实是息息相关。

由于Cache要远小于内存，因此一般会采用某种映射算法进行映射（是的，上学时“计算机组成原理”上讲的都是真的）。

然而不论CPU采用何种算法，Cache line的概念是不变的。即在Cache miss时，是按Cache line的模式来加载的.

比如在X86架构上Cache line一般为64字节，我们在访问内存地址0x100时，CPU会自动将0x100 ~ 0x140的内存全部载入Cache。

假如我们需要频繁在一个链表中，查出某几个结点进行数据修改，下面的数据结构就是低效的。

struct node {
    struct node *next;
    int select;
    char buffer[128];
};
void test(struct node *head, int select)
{
    struct node *h;
    for (h = head; h != NULL; h = h->next) {
        if (h->select == select) {
            cook(h->buffer, sizeof(h->buffer));
            break;
        }
    }
}

很显然，从上面的算法来看，在for循环时我们现关心node.next 和 node.select字段，node.buffer只有在最后一步时才会访问，而上面的代码每访问一次h->select的值，都会使Cache line充满了node.buffer的值，而这个值我们是不需要的。

因此我们需要优化struct node的内存布局，以使链表中所有的node.next, node.select 尽可能的排布在一起，以便可以充分使用Cache line的预加载功能。

最后，再简单看一下运算过程中的两个优化（并不是只有两个，而是我只会这几个:D)

一个是比较功能，在所有比较中，与0比较是最快的，因为大部分CPU的指令都会影响ZF标准位。比如下面代码:

void test1(struct foo *f)
{
        if ((f->a & 0xf) == 0)
                do_something();
}
int test2(struct foo *f)
{
        if ((f->a & 0xf) == 1)
                do_something();
}

test1函数比test2函数快3倍，因为test1函数可以直接用test指令然后判断ZF标准位，而test2需要先将f->a取出来，然后做and, 最后做compare操作。也许直接上汇编会更能说明问题。

//test1
testb   $15, 4(%rdi)
je      LBB3_2
//test2
movl    4(%rdi), %eax
andl    $15, %eax
cmpl    $1, %eax
jne     LBB4_1

再一个就是switch功能。

在写switch语句时，如果case的值是连续的, 则编译器会采用跳转表的形式来直接jmp, 时间复杂度为O(1)。

如果值是不连续的，编译器默认会采用二分查找法来进行，时间复杂度为O(lgn)。因此如果有可能，应该尽可能将case的值定义为连续。