标题：关于常数优化的一点胡思乱想
出处：Felix021
时间：Wed, 08 Dec 2010 01:57:40 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1964

内容：
在有些算法中，比较关键的步骤包含了少量数据的处理。以拷贝为例，在这种情况下如果可以进行优化，也能带来不错的效率提升。

假设有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作为索引来进行调用。

思源枯竭，到此为止。


Generated by Bo-blog 2.1.0