广告：
网页制作参考
千千学园
雨路开发频道
雨路技术文档
技术问答
编程技术

　　在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字节。

图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：

{ 　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：

{ 　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。

　　例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; }

　　例6：

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; }

　　面临的问题

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

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

　　算法优化及二进制位距

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

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

　　如例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(); }

　　例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

　　这种优化技术还能作进一步的扩展，以用作任何"逻辑操作或位计数"的位距度量。其令人感兴趣之处在于，如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

　　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位上数值优化有这些好处，那你还等什么呢？