从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的值定义为连续。



发表评论