大多数时间,大家都在从设计和算法上优化效率(这类优化往往效果比较明显,比如一个二分查找可以轻易将时间复杂度降低为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的值定义为连续。