Dec 8

关于常数优化的一点胡思乱想 不指定

felix021 @ 2010-12-8 01:57 [IT » 程序设计] 评论(3) , 引用(0) , 阅读(6540) | Via 本站原创 | |
在有些算法中,比较关键的步骤包含了少量数据的处理。以拷贝为例,在这种情况下如果可以进行优化,也能带来不错的效率提升。

假设有2个数组 int a[100], b[100]; 想把a的数据拷贝到b中去,作为一个ACMer可能会想用最简洁的方式来实现:
memcpy(b, a, sizeof(a));

这一句最便捷了,不过效率上应当是不如一个循环(后注:这里可能有误导,参见后文):
for (i = 0; i < 100; i++) b[i] = a[i];
毕竟这个只需要100个循环,每次拷贝sizeof(int)个字节,而memset则是执行100*sizeof(int)个字节。

循环的效率是比较低的。由此可以想到,如果每次循环的时候拷贝多一点,减少循环次数,也能够提高效率。假设是32bit的机器,用int拷贝基本上就把CPU指令集的效率挖得差不多了(如果不考虑SIMD指令的情况),更进一步的话,则考虑用顺序结构取代循环:
for (i = 0; i < 100; )
    b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++;

当然,极端情况可以写100个顺序语句出来,就是繁琐了一点,这里取4,主要是方便演示代码。对于n比较大的情况,全部写出来效果不一定好(不一定所有代码/数据都能放进CPU的一级缓存);如果n特别大,基本上取决于内存的限制,这个优化就不明显了。对于不够整(n % 4 != 0)的情况,可以先把整的那一部分拷贝完毕,然后再用一个小循环把剩余的拷贝完:
int loops = n - n % 4, i = 0;
while (i < loops)
    b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++;
for (i = loops * 4; i < n; i++) b[i] = a[i]

看到这里可能你就会想起duff's device(达夫设备),思路上与上面的代码一致,就是实现起来很独特:
void* duffcpy(char *to, char *from, int count) {
    register int n = (count + 7) / 8; /* 假定 count > 0 */
    switch (count % 8) {
        case 0:do { *to = *from++;
        case 7: *to = *from++;
        case 6: *to = *from++;
        case 5: *to = *from++;
        case 4: *to = *from++;
        case 3: *to = *from++;
        case 2: *to = *from++;
        case 1: *to = *from++;
        } while (--n > 0);
    }
    return to;
}
p.s. 这个代码虽然很奇怪(如果你之前没看过,建议再看一遍),但是 是可以编译运行的;拷贝并修改自 http://c-faq-chn.sourceforge.net/ccfaq/node380.html;这是某次极限编程比赛的代码,比较有争议,如果你觉得很有意思,可以看看这里进一步的说明和比较:
    http://triviasecurity.com.ru/file/Exploitation/Generic%20Programming%20Typed%20Buffers.htm
这个链接里面提到一个关于memcpy的情况:对于x86 CPU,memcpy很可能是使用REP STOS这样的指令实现的,效率应当比一个简单的for循环要高。

以上是对于较小的n的说明,关于大量拷贝更细致的优化,可以参考Glibc中qsort的实现。在一些情况下,我们会遇到很小的n,比如小于10。这时如果不写循环,而是直接写死代码,是个可行的优化。举个例子:
int sum = 0;
for (i = 0; i < 4; i++)
    for (j = i + 1; j < 4; j++)
        sum += x[i][j];
在这段代码中,实际只需要执行6次加法运算,但是却有两层循环,在循环上带来了大量的开销。如果把循环直接展开,则会得到很好的效果:
sum = x[0][1]+x[0][2]+x[0][3]+x[1][2]+x[1][3]+x[2][3];

但是对于可能会变化的n值呢?这时候如果能够允许程序在执行过程中生成可执行代码,是最好不过了,不过对于编译型的代码,这个实现起来比较有难度;而解释型的语言,这个优化又不是很有必要。想了想,在C中的一个替代方案是,写n个函数,保存在函数指针数组中,n作为索引来进行调用。

思源枯竭,到此为止。



欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
sandy
2011-1-4 11:41
很久之前就给你提起过,不要试图优化memcpy或CopyMemory或者其它系统级别的内存拷贝函数,在大多数情况下你搞不过它的。实际上影响拷贝效率的因素比你这里想到的要多很多,比如内存换页问题,比如缓存失效问题。这些东西都是[b]系统[/b]能相对方便的优化而[b]你[/b]很难做到的。

某b公司内部的某*sl库,自己实现了一个xmemcpy,使用的是32或64字节为单位进行批量拷贝,这是考虑到当前使用的CPU的缓存组大小问题,在特定情况下可以有比(老版本的Glibc的)memcpy高好几倍的效率,但具有非常强的针对性,其它环境未必有效。


最后关于你说的那个循环展开问题,这个在C++里面都被许多蛋疼的人用烂了。在C中难以实现的自动代码生成,在C++中用模板可以轻易的实现,网上类似的例子以及效率对比一搜一大堆,我就不浪费唾沫了~~
3Stone
2010-12-9 17:21
die楼上也真是的,何必事实求其功利呢?且不管这些优化到底如何,但是其中的匠心独运不是很令人enjoy吗?特别那duffcpy函数!!
WindyWinter Email Homepage
2010-12-8 15:54
大多数“常数优化”没有任何意义,相反会破坏编译器的编译优化和CPU的指令级优化,还会使得代码难以维护。所以现代编程理念里,可维护性第一,编码效率第二,效率最次。
felix021 回复于 2010-12-8 18:45
在有些情况下还是有意义的,尤其是,就算O(N)的情况下仍然要耗大量时间,进行常数优化可以很大程度上提高UI的使用体验。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]