我有2个数组，每个数组包含16个元素(字符)，我需要对其进行"比较"，看看两者之间有多少个元素相等。

该例程将被使用数百万次(通常运行大约60或者7,000万次)，因此我需要尽快。我正在使用C ++(C ++ Builder 2007，仅供记录)

现在，我有一个简单的方法：

matches += array1[0] == array2[0];

重复16次(剖析似乎比使用for循环快30％)

还有其他方法可以更快地工作吗？

有关环境和数据本身的一些数据：

• 我正在使用C ++ Builder，它没有考虑任何速度优化。我最终将尝试使用另一种编译器，但是现在我仍受此限制。
• 数据在大多数情况下会有所不同。 100％相等的数据通常非常罕见(可能少于1％)

解决方案

作为一个陈述，它更快吗？

matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;

如果我们有能力控制数组的位置，例如将一个数组紧挨着另一个放在内存中，则可能会导致它们在第一次访问时被加载到CPU的缓存中。

它取决于CPU及其缓存结构，并且在一台计算机之间会有所不同。

我们可以在Henessy＆Patterson的《计算机体系结构：定量方法》中阅读有关内存层次结构和缓存的信息。

如果编写该代码比编写一个简单的循环快16倍，则编译器很烂，或者我们没有打开优化功能。

简短的答案：没有更快的方法，除非我们在并行硬件上执行矢量运算。

神奇的编译器选项将大大改变时间。特别是使其生成SSE向量化可能会极大地提高速度。

如果我们需要绝对最低的占用空间，我将使用汇编代码。我已经有一段时间没有这样做了，但我敢打赌，MMX(或者更可能是SSE2 / 3)的说明可以使我们在很少的说明中就可以做到。

如果常见的情况是匹配，则尝试将值加载为32位整数而不是16位，这样我们可以一次性比较2个(并将其算作2个匹配项)。

如果两个32位值不相同，则必须分别测试它们(并从顶部和底部16位值中取出)。

代码会更复杂，但是应该更快。

如果我们针对的是64位系统，则可以使用64位整数进行相同的操作，如果我们确实想突破极限，那么可以考虑使用汇编程序并使用各种基于矢量的指令，这些指令可以使我们使用128位立刻。

尝试使用指针而不是数组：

p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.

当然，我们必须对照其他方法对此进行衡量，以了解哪种方法最快。

并且我们确定此例程是我们处理过程中的瓶颈吗？我们是否通过优化此方法实际上提高了整个应用程序的性能？再次，只有测量可以证明。

关键是使用CPU支持的最大寄存器进行比较，然后在必要时回退到字节。

下面的代码演示了如何使用4字节整数，但是如果我们在SIMD架构(任何现代的Intel或者AMD芯片)上运行，则可以在一条指令中比较两个数组，然后返回基于整数的循环。如今，大多数编译器都对128位类型具有内在支持，因此将不需要ASM。

(请注意，对于SIMD比较，数组必须对齐16字节，某些处理器(例如MIPS)要求数组进行4字节对齐才能进行基于int的比较。

例如。

int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];

int same = 0;

for (int i = 0; i < 4; i++)
{
  // test as an int
  if (array1[i] == array2[i])
  {
    same += 4;
  }
  else
  {
    // test individual bytes
    char* bytes1 = (char*)(array1+i);
    char* bytes2 = (char*)(array2+i);

    for (int j = 0; j < 4; j++)
    {
      same += (bytes1[j] == bytes2[j];
    }
  }
}

我不记得MSVC编译器完全支持SIMD了，但是我们可以执行类似的操作；

// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];

// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
    same = 16;
}
else
{
    // do int/byte testing
}

有什么方法可以修改数组的存储方式？考虑到我们可能正在使用32位编译器，一次比较1个字节非常慢。相反，如果我们将16个字节存储为4个整数(32位)或者2个long(64位)，则分别只需执行4或者2个比较。

要问自己的问题是将数据存储为4整数或者2长数组的成本是多少。我们需要多长时间访问一次数据等。

总是有很好的旧x86 REPNE CMPS指令。

更新：此答案已被修改，以使我的注释与下面提供的源代码匹配。

如果我们能够使用SSE2和popcnt指令，则可以进行优化。

16字节恰好适合SSE寄存器。使用c ++和assembly / intrinsics，将两个16字节数组加载到xmm寄存器中，然后对它们进行cmp。这将产生一个表示比较的真/假条件的位掩码。然后，使用movmsk指令将位掩码的位表示形式加载到x86寄存器中。这将成为一个位字段，我们可以在其中计算所有的1，以确定我们拥有多少个真实值。硬件popcnt指令可以是一种快速计数寄存器中所有1的方法。

这特别需要组装/内部知识，尤其是SSE。我们应该能够找到两者的网络资源。

如果在不支持SSE2或者popcnt的计算机上运行此代码，则必须迭代数组并使用展开循环方法计算差异。

祝你好运

编辑：
由于我们表示不了解汇编程序，因此下面是一些示例代码来说明我的答案：

#include "stdafx.h"
#include <iostream>
#include "intrin.h"

inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
    __m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
    __m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );

    return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}

int _tmain( int argc, _TCHAR* argv[] )
{
    unsigned count = 0;
    char    arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
    char    arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };

    count = __popcnt( cmpArray16( arr1, arr2 ) );

    std::cout << "The number of equivalent bytes = " << count << std::endl;

    return 0;
}

一些注意事项：此函数使用SSE2指令和Phenom处理器(我使用的机器)中引入的popcnt指令。我相信最近使用SSE4的Intel处理器也有popcnt。此功能不检查是否具有CPUID的指令支持；请参见第4章。如果在没有SSE2或者popcnt的处理器上使用该函数，则该函数未定义(我们可能会获得无效的操作码指令)。该检测代码是一个单独的线程。

我尚未定时此代码；我认为它更快的原因是因为它一次比较16个字节，无分支。我们应该对此进行修改以适合环境，并自行调整时间以查看它是否适合我们。我在VS2008 SP1上进行了编写和测试。

SSE倾向于在自然16字节边界上对齐的数据。如果可以保证，则应该进一步提高速度，并且可以将_mm_loadu_si128指令更改为_mm_load_si128，这需要对齐。

这是否必须独立于平台，还是此代码始终在相同类型的CPU上运行？如果将自己限制在现代x86 CPU上，则可以使用MMX指令，该指令应允许我们在一个时钟周期内对8个字节的数组进行操作。在AFAIK中，gcc允许我们将汇编嵌入到C代码中，并且Intel的编译器(icc)支持内在函数，内在函数是包装器，可让我们直接调用特定的汇编指令。其他SIMD指令集(例如SSE)也可能对此有用。

数组中的值之间是否有任何联系？有些字节比其他字节更可能相同吗？值中可能有一些内在顺序吗？然后，我们可以针对最可能的情况进行优化。

一个额外的可能的优化方法：如果我们期望大多数情况下数组是相同的，那么第一步是将memcmp()作为第一步，如果测试返回true，则将'16'设置为答案可能会更快一些。如果我们当然不希望阵列经常相同，那只会减慢速度。

如果我们解释了数据实际代表的内容，那么可能存在一种完全不同的方式来表示内存中的数据，这将使这种类型的暴力比较变得不必要。仔细说明数据实际上代表什么？