13

我有 2 个包含 16 个元素（字符）的数组，我需要“比较”并查看两者之间有多少元素相等。

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

现在，我有一个简单的：

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

重复 16 次（分析它似乎比使用 for 循环快 30%）

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

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

  • 我正在使用 C++Builder，它没有考虑任何速度优化。我最终会尝试使用另一个编译器，但现在我被这个编译器困住了。
  • 大多数时候数据会有所不同。100% 相等的数据通常非常罕见（可能少于 1%）
4

15 回答 15

17

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

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

16 个字节恰好适合 SSE 寄存器。使用 c++ 和汇编/内在函数，将两个 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 的英特尔处理器也有 popcnt。此函数不检查 CPUID 的指令支持；如果在没有 SSE2 或 popcnt 的处理器上使用该函数是未定义的（您可能会得到一个无效的操作码指令）。该检测代码是一个单独的线程。

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

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

于 2008-09-22T18:30:55.593 回答
7

关键是使用 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
}
于 2008-09-22T18:23:05.893 回答
2

如果您有能力控制数组的位置，例如在内存中一个接一个地放置，它可能会导致它们在第一次访问时被加载到 CPU 的缓存中。

它取决于 CPU 及其缓存结构，并且会因一台机器而异。

您可以在Henessy & Patterson 的计算机体系结构：定量方法中阅读有关内存层次结构和缓存的信息

于 2008-09-22T18:12:43.703 回答
2

如果您需要绝对最小的占用空间，我会使用汇编代码。我已经有一段时间没有这样做了，但我敢打赌 MMX（或者更可能是 SSE2/3）的指令可以让你在很少的指令中做到这一点。

于 2008-09-22T18:15:20.500 回答
2

如果匹配是常见情况，则尝试将值加载为 32 位整数而不是 16，这样您就可以一次比较 2（并将其计为 2 个匹配）。

如果两个 32 位值不相同，那么您将不得不分别测试它们（并得出顶部和底部 16 位值）。

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

如果你的目标是 64 位系统，你可以用 64 位整数做同样的技巧，如果你真的想突破极限，那么看看进入汇编程序并使用各种基于向量的指令，这可以让你使用 128 位立刻。

于 2008-09-22T18:18:17.467 回答
1

神奇的编译器选项会在时间上有很大的不同。特别是让它生成 SSE 矢量化可能会给你带来巨大的加速。

于 2008-09-22T18:15:15.663 回答
1

这是否必须与平台无关，或者此代码是否总是在相同类型的 CPU 上运行？如果您将自己限制在现代 x86 CPU 上，您可以使用MMX指令，它应该允许您在一个时钟周期内对 8 个字节的数组进行操作。AFAIK，gcc 允许您在 C 代码中嵌入汇编，并且英特尔的编译器 (icc) 支持内部函数，这些内部函数是允许您直接调用特定汇编指令的包装器。其他 SIMD 指令集，例如 SSE，也可能对此有用。

于 2008-09-22T18:32:05.513 回答
1

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

于 2008-09-22T19:09:17.983 回答
1

如果您解释数据实际代表什么，那么可能有一种完全不同的方式来表示内存中的数据，这将使这种类型的蛮力比较变得不必要。想详细说明数据实际代表什么？

于 2008-09-23T01:00:05.597 回答
0

它作为一个语句更快吗？

matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;
于 2008-09-22T18:12:05.563 回答
0

如果写这 16 倍比一个简单的循环快，那么你的编译器要么很糟糕，要么你没有打开优化。

简短的回答：没有更快的方法，除非您在并行硬件上进行矢量运算。

于 2008-09-22T18:14:58.987 回答
0

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

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

当然，您必须根据其他方法来衡量这一点，看看哪种方法最快。

你确定这个程序是你处理过程中的瓶颈吗？您是否真的通过优化来提高整个应用程序的性能？同样，只有测量才能说明问题。

于 2008-09-22T18:19:19.617 回答
0

有什么方法可以修改数组的存储方式吗？考虑到您可能使用的是 32 位编译器，一次比较 1 个字节非常慢。相反，如果您将 16 个字节存储在 4 个整数（32 位）或 2 个长整数（64 位）中，则只需分别执行 4 或 2 次比较。

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

于 2008-09-22T18:25:12.050 回答
0

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

于 2008-09-22T18:26:40.877 回答
0

一个额外的可能优化：如果您期望大多数时间数组是相同的，那么在第一步执行 memcmp() 可能会稍微快一些，如果测试返回 true，则将“16”设置为答案。当然，如果您不希望数组经常相同，那只会减慢速度。

于 2008-09-22T21:34:23.297 回答