查看固定长度数组之间有多少字节相等的最快方法

Question

我有两个16个元素(字符)数组,我需要"比较",看看两者之间有多少元素相等.

这个例程将被使用数百万次(通常运行大约60或7000万次),所以我需要它尽可能快.我正在研究C++(C++ Builder 2007,用于记录)

现在,我有一个简单的:

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

重复16次(因为分析看起来比使用for循环快30%)

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

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

• 我正在使用C++ Builder,它没有任何速度优化需要考虑.我将最终尝试使用另一个编译器,但是现在我仍然坚持使用这个.
• 大多数时候数据会有所不同.100%相等的数据通常非常罕见(可能低于1%)

Answer 1

更新:此答案已被修改,以使我的评论与下面提供的源代码相匹配.

如果您有能力使用SSE2和popcnt指令,则可以进行优化.

16个字节恰好适合SSE寄存器.使用c ++和assembly/intrinsics,将两个16字节数组加载到xmm寄存器中,然后cmp它们.这会生成一个表示比较的真/假条件的位掩码.然后使用movmsk指令将位掩码的位表示加载到x86寄存器中; 这就变成了一个小字段,你可以计算所有的1来确定你有多少真值.硬件popcnt指令可以快速计算寄存器中的所有1.

这需要了解装配/内在和SSE的知识.您应该能够找到两者的Web资源.

如果在不支持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的英特尔处理器也有其优势.该函数不检查CPUID的指令支持; 如果在没有SSE2或popcnt的处理器上使用该函数,则该函数是未定义的(您可能会得到无效的操作码指令).该检测代码是一个单独的线程.

我还没有计时这段代码; 我认为它更快的原因是因为它一次比较16个字节,无分支.您应该修改它以适应您的环境,并自己计时以查看它是否适合您.我在VS2008 SP1上编写并测试了这个.

SSE更喜欢在自然的16字节边界上对齐的数据; 如果你可以保证那么你应该获得额外的速度改进,并且你可以将_mm_loadu_si128指令更改为_mm_load_si128,这需要对齐.

Answer 2

关键是使用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
}