64位程序开发中的性能优化技巧

这几天同事们正在讨论PowerPC上的一些优化，其中之一就是利用E500中的64位浮点寄存器来进行优化，正好看到这篇文章，顺手转来作为参考。

在64位计算已越来越近的今天，越来越多的程序已开始考虑利用64位所带来的强大优势，其中，64位寻址对那些需要处理大量数据的应用程序来说尤为重要， 如：工程与科学计算程序、大型数据库之类，现在已有许多的CPU及操作系统可本地支持64位计算，但它们带来的最大好处也许还是巨大的寻址空间，程序在其 中可分配大于4GB的内存，更容易管理大文件等等。如果要充分发挥64位CPU的威力，应用程序还必须要利用64位中更宽的机器字，在本文中，将集中讨论 64位上的程序性能优化。

　　64位的差异

　　不幸的是，如今的大多数软件都没有充分利用64位微处 理器，以至于不能在64位模式下编译和运行，从而，软件被迫运行在32位兼容模式中--真是对硅的浪费。此外，还有很多程序员在用C语言编程时"玩忽职 守"，脑袋中想像着64位CPU，却用32位系统的模式来编程，以下是常见的情况：

　　·以为指针与int大小一样。在64位系统中，sizeof(void *) == 8，而sizeof(int) == 4。如果忘记了这个，将导致不正确的赋值以致程序崩溃。

　　·依赖于某一机器字架构的特定字节序。

　　·使用long类型并假定它总是与int有同样大小。由此的直接赋值将导致数值截断，并且问题很难察觉。

　　·堆栈变量的对齐方式。在一些情况中，堆栈变量也许不是按8字节边界对齐，如果你把这些变量转换成64位变量，在某些系统上，将会遇到一些麻烦。但是如果你在堆栈上放置一个64位变量（long或double），这保证是对齐的；还有，堆中分配的内存也是对齐的。

　　·不同的对齐方式决定了结构与类的对齐。在64位架构上，结构成员通常对齐于64位边界，当在通过IPC、网络、或磁盘共享二进制数据时，就会有些问题；另外在包装数据结构以便存储资源时，没有考虑到对齐方式，同样也会有问题。

　　·指针算法。当把一个64位指针像32位指针那样递增时（反之亦然），64位指针每次递增8字节，而32位指针每次递增4字节。

　　·在缺少函数原型的情况下，返回值一般为int，这在某些时候也会导致数值截断。

　　并行编程：充分利用每次循环

　　64位C语言编程的高性能关键所在，是更宽的整数与FPU寄存器。CPU寄存器位于"食物链"的顶层--也是计算机存储器最昂贵部分所在，在64位CPU上，寄存器字宽通常为8字节，而对应的是常见的128位或256位内存总线带宽。

　　图1表示了32位系统的典型操作，CPU一次只都处理4字节内存中的数据。图2显示了有着更宽寄存器的64位系统，一次能处理8字节。 bainei.com

图1

图2

　　例1在某一内存块上进行XOR操作，其表示了一个基于整数的位集，你能在64位模式中对此进行优化。例2依赖于long long的C语言类型，但不会被某些编译器所支持。正如你所看到的，此处没有改变位集的总体大小，即使只花了较少的两次操作来重组矢量。例2有效地减少了 循环的开销，相当于带系数2的循环展开，而只有一小点不利之处，就是它是纯64位的，如果在32位系统上编译，将会因为long大小的不同而给出错误的结 果。

　　例1：

{
　int a1[2048];
　int a2[2048];
　int a3[2048];

　for (int i = 0; i ＜ 2048; ++i)
　{
　　a3[i] = a1[i] ^ a2[i];
　}
}

　　例2： bainei.com

{
　long long a1[1024];
　long long a2[1024];
　long long a3[1024];

　for (int i = 0; i ＜ 1024; ++i)
　{
　　a3[i] = a1[i] ^ a2[i];
　}
}

　　你还能作进一步的修改，如例3所示，其利用了更宽的寄存器在32位和64位CPU上做同样的工作，在做如此的类型转换时，请注意指针对齐方式。 如果你只是盲目地把int指针转换为64位long指针，指针地址将不会是8字节对齐的，在某些架构的机器上，还可能导致程序崩溃，或者带来性能损失。例 3中的代码是不安全的，因为放置在堆栈中的32位int变量有可能4字节对齐，由此导致程序崩溃，如果在堆中分配（malloc），就能防止此类事情的发 生。

　　例3： bainei.com

{
　int a1[2048];
　int a2[2048];
　int a3[2048];

　long long* pa1 = (long long*) a1;
　long long* pa2 = (long long*) a2;
　long long* pa3 = (long long*) a3;

　for (int i = 0; i ＜ sizeof(a1) / sizeof(long long); ++i)
　{
　　pa3[i] = pa1[i] ^ pa2[i];
　}
}

位计数算法

　　在位集算法中最重要的一个操作是在位串中计算1位的数量，默认的操作方法是把每一个整数分成4个字符，并在一张预先计算好的位计数表中依次查 找。这种线性操作的方法能用一种16位宽的表格加以改进，所付出的代价是表格可能要更大才行。此外，更大的表格很可能会产生一些额外的内存取数操作，由此 影响CPU缓存命中率，结果并没有带来想象中的性能提升。

　　作为另一个可供选择的方法，例4就没有使用查找表，但却一次并行计算两个int。 bainei.com

　　例4：

int popcount(long long b)
{
　b = (b & 0x5555555555555555LU) + (b ＞＞ 1 & 0x5555555555555555LU);
　b = (b & 0x3333333333333333LU) + (b ＞＞ 2 & 0x3333333333333333LU);
　b = b + (b ＞＞ 4) & 0x0F0F0F0F0F0F0F0FLU;
　b = b + (b ＞＞ 8);
　b = b + (b ＞＞ 16);
　b = b + (b ＞＞ 32) & 0x0000007F;

　return (int) b;
} 

　　位串词典比较

　　可进行64位优化的另一种程序是位集中的词典比较，其最直接的实现是每次从位序列中取出两个字，并一位一位地转换进行比较，此迭代算法具有 O(N/2)的复杂度，此处的N是总的位数。例5中演示了两个字的迭代比较法；此算法并不能通过64位并行化处理极大地提高性能。然而，例6演示了另一种 可供选择的算法，其复杂性与机器字（不是位）数除以2成正比，其在64位上极具潜力。

　　例5：

int bitcmp(int w1, int w2)
{
　while (w1 != w2)
　{
　　int res = (w1 & 1) - (w2 & 1);
　　if (res != 0)
　　　return res;
　　　w1 ＞＞= 1;
　　　w2 ＞＞= 1;
　}
　return 0;
} bainei.com

　　例6： bainei.com

int compare_bit_string(int a1[2048], int a2[2048])
{
　long long* pa1 = (long long*) a1;
　long long* pa2 = (long long*) a2;

　for (int i = 0; i ＜ sizeof(a1) / sizeof(long long); ++i)
　{
　　long long w1, w2, diff;
　　w1 = a1[i];
　　w2 = a2[i];
　　diff = w1 ^ w2;
　　if (diff)
　　{
　　　return (w1 & diff & -diff) ? 1 : -1;
　　}
　}
　return 0;
}

bainei.com

　　面临的问题 bainei.com

　　问题来了，为了64位，我们犯得着这样吗？当代的32位CPU都是超标量、推理性执行机器，具有在几个执行区域中并行乱序地同时执行几条指令的 能力，而不需要程序员的干预；反观64位处理器只展示了其具有同样的性能--但只是在纯64位中；话说回来，在如Intel Itanium（安腾处理器）特别强调并行编程的某些架构上，并且在编译器级别显式地进行了优化的情况下，程序代码适合于64位，并且已为64位优化就显 得尤为必要。

bainei.com

　　还有一点，程序的性能不只是受限于CPU的MHz表现，而且也受限于CPU的内存带宽--其又受限于系统总线，总之，上述的算法不可能总是表现 出最高性能，这也是不可改变的一个事实，并且硬件设计师也非常了解。当然，我们也看到了双通道内存控制器所带来的效率上的提高，并且内存速度也在稳步向前 发展，这在一定程度上减轻了系统总线成为瓶颈的可能性，面对当今发展越来越快的硬件，经过优化的64位算法将会有更好的表现。

算法优化及二进制位距

　　另一个可进行64位优化之处是在位串中计算（二进制）位距。二进制位距常用于进行分类与查找对象的相似之处的数据采集与AI（人工智能）程序，其通常表示为二进制描述符（位串）。此处优化的重点是位距算法，因为它会在系统中每对对象之间重复执行。

bainei.com

　　最知名的位距度量算法是加重平均位距，其是位中的一个最小数，并能被改变以转换为另一个位串。换句话来说，你可以使用XOR位运算符来结合位串，并利用得到的结果计算出位数。 bainei.com

　　如例7中采用了如上算法的程序，最明显的优化之处是去掉了临时位集，并同时计算XOR与总数量。而临时文件的产生是C++编译器的"内部运动"，且因为内存的复制与重分配，降低了程序效率，请看例8：

　　例7：

#include ＜bitset＞
using namespace std;

const unsigned BSIZE = 1000;
typedef bitset＜BSIZE＞ bset;

unsigned int humming_distance(const bset& set1, const bset& set2)
{
　bset xor_result = set1 ^ set2;
　return xor_result.count();
} bainei.com

　　例8：

{
　unsigned int hamming;
　int a1[2048];
　int a2[2048];
　long long* pa1;
　long long* pa2;

　pa1 = (long long*) a1; pa2 = (long long*) a2;
　hamming = 0;

　for (int i = 0; i ＜ sizeof(a1) / sizeof(long long); ++i)
　{
　　long long b;
　　b = pa1[i] ^ pa2[i];

　　b = (b & 0x5555555555555555LU) + (b ＞＞ 1 & 0x5555555555555555LU);
　　b = (b & 0x3333333333333333LU) + (b ＞＞ 2 & 0x3333333333333333LU);
　　b = b + (b ＞＞ 4) & 0x0F0F0F0F0F0F0F0FLU;
　　b = b + (b ＞＞ 8);
　　b = b + (b ＞＞ 16);
　　b = b + (b ＞＞ 32) & 0x0000007F;

　　hamming += b;
　}
}

　　这种优化立竿见影地达到了几个目标：与内存通信量的减少、更好地复用了寄存器，当然，最重要的是64位并行处理（参见图3）。此结果的本质是改进了CPU操作与内存负载的平衡，这是通过结合例3与例4的算法来达到的。

图3 bainei.com

　　这种优化技术还能作进一步的扩展，以用作任何"逻辑操作或位计数"的位距度量。其令人感兴趣之处在于，如Tversky Index、Tanamoto、Dice、Cosine函数等等更复杂的度量方法，现在也能更容易表达了。

　　为了进一步加深理解，来看一下Tversky Index：

TI = BITCOUNT(A & B) / [a*(BITCOUNT(A-B) + b*BITCOUNT(B-A) + BITCOUNT(A & B)]

　　公式中包含了三个操作，BITCOUNT_AND(A, B)、BITCOUNT_SUB(A, B)、BITCOUNT_SUB(B, A)。三个操作能被结合成一条流水线操作，见图4。这种技术改进了数据存储位置，更好的复用了CPU缓存，也意味着减少CPU延迟及提高程序性能，见例 9：

　　例9： 

{
　double ti;
　int a1[2048];
　int a2[2048];
　long long* pa1;
　long long* pa2;

　pa1 = (long long*) a1; pa2 = (long long*) a2;
　ti = 0;

　for (int i = 0; i ＜ sizeof(a1) / sizeof(long long); ++i)
　{
　　long long b1, b2, b3;
　　b1 = pa1[i] & pa2[i];
　　b2 = pa1[i] & ~pa2[i];
　　b3 = pa2[i] & ~pa1[i];

　　b1 = popcount(b1);
　　b2 = popcount(b2);
　　b3 = popcount(b3);

　　ti += double(b1) / double(0.4 * b2 + 0.5 * b3 + b1);

　}
}

图4 bainei.com

　　64位之后还有什么？

　 　上述的大多数算法都能通过基于矢量的指令加以编码--如单指令多数据（SIMD）。带有SIMD功能的CPU含有特殊的扩展寄存器（64位或128位） 或执行单元，能一次载入几个机器字，并对它们进行一些并行的操作。最流行的SIMD引擎是Intel的SSE；AMD的3DNow!；Motorola、 Apple、IBM的AltiVec。SIMD寄存器与通用寄存器不同，它们不允许你执行诸如IF这样的流量控制操作，这也使SIMD编程更加困难。不难 看出，基于SIMD代码的可移植性也是有限的。可是，一个并行的64位优化算法能在概念上很容易地被转换为一个128位的SIMD算法；请参见例10，其 使用SSE2指令集实现了一个XOR算法，此处使用了Intel C++编译器的内部兼容性。
　
　　例10：

void bit_xor(unsigned* dst, const unsigned* src, unsigned block_size)
{
　const __m128i* wrd_ptr = (__m128i*)src;
　const __m128i* wrd_end = (__m128i*)(src + block_size);
　__m128i* dst_ptr = (__m128i*)dst;

　do
　{
　　__m128i xmm1 = _mm_load_si128(wrd_ptr);
　　__m128i xmm2 = _mm_load_si128(dst_ptr);

　　__m128i xmm1 = _mm_xor_si128(xmm1, xmm2);
　　__mm_store_si128(dst_ptr, xmm1);
　　++dst_ptr;
　　++wrd_ptr;

　} while (wrd_ptr ＜ wrd_end);
} 

　　既然在64位上数值优化有这些好处，那你还等什么呢？