对数组进行比较（逐个元素）

Question

我正在使用的算法在比较一个数组和矩阵的一行时花费了大量时间。如果任何第 ith 个元素相同，则该算法调用过程 A，否则调用过程 B。例如：

[1, 4, 10, 3, 5] 和 [5, 3, 0, 3, 0] 调用 A()，因为在第 4 个位置，两个数组的值都是 3。

[1, 4, 10, 3, 5] 和 [5, 3, 0, 1, 0] 调用 B()，因为在同一位置上，值从来不相同。

请注意：(1) 数组和矩阵行始终具有相同的大小 N，以及 (2) 当至少有一个值匹配时，该算法调用 A()。

在 C 语言中实现最简单但非常 naive 的方法是：

for(int i=0; i<N; i++)
   if( A[i] == B[i] ){
      flag = 1;
      break;
   }

这种方法仍然非常低效。在最坏的情况下，我将进行 N 次比较。真正的问题在于算法要进行数万亿次这样的比较。

数组/矩阵的大小 N 变化范围在100到1000之间。我想加速这个过程。我研究了向量化，并发现我可以使用cmpeq_pd。然而，向量化仍然会受限，因为所有条目都是longs。有没有人有主意？也许我可以应用掩码等操作？

更多信息/背景：

• 这是一种迭代算法。 在每次迭代中，我会递增矩阵的一行并多次检查整个矩阵。 我可能还会更新几行。
• 匹配的可能性不取决于位置。
• 为了极大地加快这个过程，我愿意有误报和漏报。
• 如果有匹配，那么确认匹配的位置不相关（我只需要知道是否有匹配的位置）。
• 最大数量（约70％）的比较不会产生匹配。
• 并行化是在不同的级别上完成的，即此内核无法并行化。

- a3mlord

---

你能跟踪差异吗？这样，对于所有行，您都可以记录相等元素的计数，当您更新矩阵单元格或数组元素时，您会更新它。 （当然，这仅适用于某些情况。） - M Oehm

需要提供更多与矩阵和数组内容相关的信息，包括它们更新的频率（这对于查找结果而非重新计算很重要），在数组的开头或结尾是否有更高的匹配可能性，以及您是否愿意接受误报或漏报（例如，当应该调用B时却调用了A，反之亦然）。任何优化方法都依赖于能够采取一些快捷方式，并且您并没有给出任何基础可以允许一些快捷方式。 - Peter

匹配元素的实际位置重要吗？也就是说，当找到匹配项时，它是否会传递给A()？你的意思是当找到匹配项时调用A()还是B()？你声称两者都是... - unwind

@a3mlord，关于找到匹配项时调用哪个函数存在矛盾，正如我在20分钟前指出的那样。 - unwind

我并不是算法大师，但如果数据没有排序，除了与算法本身无关的优化之外，我真的看不出你如何进一步加快速度。 - Lundin

Answer 1

我不知道你正在开发的应用程序是否适用，但在大型数组上进行操作通常可以在GPU上得到很好的加速。您可以期望比CPU快10-20倍的吞吐量速度提升。如果您的应用程序可以在CUDA上运行关键部分，那将产生巨大的差异。

- Michael

---

@a3mlord 如果可能的话，请尝试早些时候使用OpenCL SDK来处理您的CPU，并比较元素+并行前缀和，然后将其发送回主机代码。这应该可以很好地实现多核，但最终您的内存带宽受到严重限制。我能想到的唯一可能的节省是如果您的数据是准静态或静态的，那么在GPU上进行比较/求和将为您提供每秒数十亿字节的内存带宽，比英特尔PC强大20倍 - 但PCIe带宽是PC内存带宽的四分之一。 - Jason Newton

Answer 2

虽然您的Sandy Bridge CPU只支持256位SIMD（而不是AVX2），因此缺少对4路SIMD 64位整数操作的支持，但我认为您仍然可以使用AVX浮点指令实现4路SIMD，具体如下：要比较两个64位整数值的256位向量v1，v2：

__m256d vcmp = _mm256_xor_pd(v1, v2); // use XOR rather than compare, so we are not 
                                      // affected by values which map to NaNs
vcmp = _mm256_cmp_pd(vcmp, _mm256_setzero_pd(), _CMP_EQ_OQ);
                                      // now we can do a valid comparison as if the
                                      // data really is double precision float
int mask = _mm256_movemask_pd(vcmp);  // extract the sign bits
bool any_eq = (mask != 0);            // if any elements matched then mask
                                      // will be non-zero

这是一个用于测试和说明目的的示例程序：

#include <stdio.h>
#include <stdint.h>
#include <immintrin.h>

int test(__m256d v1, __m256d v2)
{
    __m256d vcmp = _mm256_xor_pd(v1, v2);
    vcmp = _mm256_cmp_pd(vcmp, _mm256_setzero_pd(), _CMP_EQ_OQ);
    return _mm256_movemask_pd(vcmp);
}

int main()
{
    int64_t a1[4] = { 3098, 3860, 405, 3308 };
    int64_t a2[4] = { 1930, 1274, 2195, 2939 };
    int64_t a3[4] = { 1930, 1274, 405, 2939 };

    __m256i v1 = _mm256_loadu_pd((double *)a1);
    __m256i v2 = _mm256_loadu_pd((double *)a2);
    __m256i v3 = _mm256_loadu_pd((double *)a3);

    printf("mask = %d (should be == 0)\n", test(v1, v2));

    printf("mask = %d (should be != 0)\n", test(v1, v3));

    return 0;
}

测试:

$ gcc -Wall -mavx a3mlord2.c && ./a.out 
mask = 0 (should be == 0)
mask = 4 (should be != 0)

- Paul R

---

Paul，请问你能发一下加载指令吗？我用的是“__m256d v1 = _mm256_loadu_ps((float *)&array[index] );”，但我觉得这是错误的。谢谢。 - a3mlord

由于这是64位数据，您可能想使用_mm256_loadu_pd。 - Paul R

谢谢Paul，非常完美。我现在正在使用__m256d v1 = _mm256_loadu_pd((const double *)&array[index] );。然而，这给了我一个不同的输出结果。我会尝试找出问题所在。 - a3mlord

我刚刚在这里尝试了ICC 13，发现了同样的问题 - 我会看看是否能找到解决方法... - Paul R

不好意思 - 在ICC 13中似乎存在_mm256_cmp_pd的一个错误。如果我能够获得较新版本的ICC，我会尝试使用它，但目前我看不到任何解决此问题的方法。 - Paul R

Answer 3

在C语言中最简单但非常幼稚的方法是使用：
正如您在问题中暗示的那样，根据此语句提供的代码示例可能从可读性的角度来看很简单，但是否一旦编译就转换为比较数据的最简单、最有效的方法呢？

建议尝试块比较：
数据用于比较的方式可以促进比较的速度和效率。将值加载到单独的变量中（分配给使用单独寄存器的变量），然后比较这些寄存器。

long a1 = A[0];
long a2 = A[1];
long a3 = A[2];
long a4 = A[3];
...
long an = A[n];

long b1 = B[0];
long b2 = B[1];
long b3 = B[2];
long b4 = B[3];
...
long bn = B[n];

if ((a1 == b1) || (a2 == b2) || (a3 == b3) || (a4 == b4) ... || (an == bn))
{
   //do something
}
else
{
   //do something else
}

要真正知道一个方法是否最快，需要编写代码，查看它所生成的汇编代码，或者进行基准测试。就像你在帖子中建议的那样，循环遍历数组元素可能不是最有效的方法。

编辑：一个斜线的想法：Matlab以包含一些最快的数组比较例程而闻名，而且它还具有Matlab到C转换能力。如果您或同事拥有Matlab的副本，可以尝试使用Matlab创建的算法进行速度测试，然后将其转换为C以观察它所创建的内容。我以前使用过这个功能，它所产生的C结构不好看，但通常非常高效（从速度上来看）。

- ryyker

---

考虑到我将有数百或数千个元素，我在赋值之前重新编写寄存器，这样不会影响比较吗？ - a3mlord

是的，每次调用此段代码时都会执行。我想上面的示例会更长，但尽管很丑陋，一长串顺序赋值语句，然后进行块比较将比循环遍历一系列数组元素比较更有效率。为了可读性（但减少了调试能力），您可以在头文件中定义宏。但从C编码的角度来看，我认为这种方法将比循环比较增加一定程度的效率。顺便说一下，这是一个非常好的问题。 - ryyker

Answer 4

每当您寻找优化时，面前就有不同的路径：

- 算法优化：通常是使用排序算法，在您的情况下可以使用一些依赖于行之间或行内的规则，仅测试一些情况而非N个值。您没有提供可用于此的任何信息，但也许您知道这样的规则 - 这种优化可获得数量级的收益。 - 中等级别的优化：一旦选择了算法，请检查如何组织循环和测试 - 在这里，我不知道可以做什么 - 收益通常在10%左右，除非实现非常糟糕。 - 低级别的优化：试图比优化编译器更聪明通常会使您失去优势，但在某些情况下，对不同实现进行基准测试可能会获得一些百分点的增益。 - 并行化：如果算法支持，则将总处理量分配到多个核心或处理器上。预期的收益通常略低于同时线程的数量。

根据您所说，唯一可能的优化是将处理并行化到n个核心上，每个核心（减一）处理一部分行，另一个核心处理这些第一次比较的结果。但正如之前所说，如果数据中存在规则，则收益可能会高得多。

- Serge Ballesta

Answer 5

SIMD处理不太可能有所帮助：您有一个相当小的循环，涉及大量数据（每次迭代16字节）。即使在没有SIMD的情况下运行，这也很可能会饱和内存总线。

在我看来，您有两个基本选择：

1. 使用更多/更宽的内存总线。
   这可以通过使用多个核心或GPU来实现。

2. 尝试减少比较的数量。
   从您的问题中不清楚是否可能实现，但如果您的算法多次执行相同的比较，则可以通过缓存比较结果来重构您的算法。根据算法，这可以显着提高速度。

- cmaster - reinstate monica

Answer 6

如果你正在使用gcc且在x86平台上，你的代码可能会从使用memcmp()取代“自制”的for循环中受益。 memcmp()（以及其内建副本）进行了一些相当智能的优化。

- mfro

---

OP 想要查看数组中是否有任何一个元素相等。这将告诉我们是否所有元素都相等。 - Degustaf

据我所知，就长数组而言，memcmp的优化并不起作用。 - LPs