C++快速将2个数组相加

Question

给定以下数组：

int canvas[10][10];
int addon[10][10];

当所有值的范围在0-100之间时，C++中最快的方法是什么，以便将这两个数组相加，使画布中的每个单元格等于自身加上附加单元格的值？

例如，我想实现以下功能：

canvas += another;

如果canvas[0][0]=3且addon[0][0]=2，则canvas[0][0]=5。

速度在这里至关重要，因为我正在编写一个非常简单的程序来暴力解决背包问题，并且将有数千万种组合。

作为一个小额外问题（如果您能帮忙，谢谢！）检查canvas中的任何值是否超过100的最快方法是什么？循环很慢！

- Tom Gullen

---

为什么你要对背包问题进行暴力破解？有更快的动态规划解决方案。通常改进算法比使用代码黑科技更好。 - IVlad

额外的速度有多重要？如果问题开始变得组合极大，您可能需要考虑将代码并行化。此外，您是否特别想要暴力求解问题？如果不是，我建议您研究混合整数规划和分支定界算法。 - shuttle87

你是在寻找一个直接的C/C++方案吗？如果你愿意针对某个体系结构将其降级，那么我会查看是否有类似SSE的SIMD风格指令可以帮助并行化操作（虽然我不确定具体如何工作）。 - Michael Burr

速度非常重要，如果没有任何启发式算法，我们将面临从几亿到高达100亿个可能的解决方案。现在所需的唯一计算是将数组相加，然后计算是否有任何值超过100。这是一个装箱/背包问题，因此保证最佳解决方案的唯一方法是采用蛮力算法，并且我需要每次找到最佳解决方案。 - Tom Gullen

感谢您的评论，我并不是很擅长C++，但我可以编写类似这样的程序，我几年前写了一个类似的程序，用于暴力破解扑克牌手统计数据，它是世界上最快的之一，但是在这种情况下，我不知道许多这些术语（SIMD/Parallizing/SSE）的含义:(我只是希望有一个简单的内存块加法指令或类似的东西。 - Tom Gullen

Answer 1

这里有一个SSE4实现，应该在Nehalem（Core i7）上表现得相当不错：

#include <limits.h>
#include <emmintrin.h>
#include <smmintrin.h>

static inline int canvas_add(int canvas[10][10], int addon[10][10])
{
    __m128i * cp = (__m128i *)&canvas[0][0];
    const __m128i * ap = (__m128i *)&addon[0][0];
    const __m128i vlimit = _mm_set1_epi32(100);
    __m128i vmax = _mm_set1_epi32(INT_MIN);
    __m128i vcmp;
    int cmp;
    int i;

    for (i = 0; i < 10 * 10; i += 4)
    {
        __m128i vc = _mm_loadu_si128(cp);
        __m128i va = _mm_loadu_si128(ap);

        vc = _mm_add_epi32(vc, va);
        vmax = _mm_max_epi32(vmax, vc);   // SSE4 *

        _mm_storeu_si128(cp, vc);

        cp++;
        ap++;
    }
    vcmp = _mm_cmpgt_epi32(vmax, vlimit); // SSE4 *
    cmp = _mm_testz_si128(vcmp, vcmp);    // SSE4 *
    return cmp == 0;
}

使用 gcc -msse4.1 ... 或者在您的特定开发环境中使用等效命令进行编译。

对于旧的没有SSE4指令集（且具有更昂贵的非对齐加载/存储）的CPU，您需要（a）使用适当的SSE2 / SSE3内嵌函数组合来替换标有*的SSE4操作，并且最好（b）确保您的数据是16字节对齐并使用对齐加载/存储（_mm_load_si128/_mm_store_si128）代替_mm_loadu_si128/_mm_storeu_si128。

- Paul R

Answer 2

你不能在C++中比循环更快。你需要使用一些特定于平台的向量指令，也就是说，你需要下到汇编语言级别。然而，有些C++库尝试为你做到这一点，因此你可以高层次地编写代码，并且让库来处理针对你所选用的编译器体系结构适当的低级SIMD工作。 MacSTL 是一个你可能想看看的库。它最初是一个特定于Macintosh的库，但现在是跨平台的。请访问他们的主页了解更多信息。

- A. Levy

---

感谢您的帮助。在解决我的另一个优化问题时，我发现如果您知道数组大小，则手动编码加法：a[0] = a[0] + b[0]; a[1] = a[1] + b[1]; .... a[20] = a[20] + b[20];比使用循环遍历大量解集要快得多。 - Tom Gullen

@Tom：对于小数组大小，那几乎肯定是正确的。如果你把它们做得太大，可能会遇到缓存未命中的问题。 - David Thornley

@Tom：如果有适当的标志，编译器也可能能够自动展开循环为类似于这样的内容，这样可以使代码更清晰而不牺牲性能。 - Grizzly

Answer 3

在标准的C或C++中，最好的方法是将其转换为一个包含100个数字的一维数组，并在循环中添加它们。(单个下标将使用比双下标更少的处理，除非编译器可以将其优化掉。要知道是否有影响以及影响程度，唯一的方法就是进行测试。)

你当然可以创建一个类，在这个类中加法将成为一个简单的C++指令(canvas += addon;)，但这不会加速任何东西。所有会发生的事情就是简单的C++指令会扩展到上面的循环中。

为了加速这个过程，你需要进入更低级别的处理。许多现代CPU都有额外的指令来执行此类处理，你可能可以使用它们。你可以尝试在GPU上运行像Cuda这样的东西。你可以尝试使操作并行化并在几个核心上运行，但在这样一个小的实例上，你必须知道你的CPU上缓存的工作方式。

其他选择是改进你的算法(在背包问题上，你可能可以以某种方式使用动态规划——没有更多的信息，我们无法告诉你)，或者接受性能。在一个10x10的数组上进行数千万次操作，会变成对数字进行数百亿次操作，这并不像以前那样令人畏惧。当然，我不知道你的使用场景或性能要求。

- David Thornley

Answer 4

这里提供一种替代方案。

如果您确定所有值都在0到100之间，可以将类型从int更改为uint8_t。然后，您可以使用uint32_t将其中的4个元素相加，而不必担心溢出问题。

也就是说...

uint8_t  array1[10][10];
uint8_t  array2[10][10];
uint8_t  dest[10][10];
uint32_t *pArr1 = (uint32_t *) &array1[0][0];
uint32_t *pArr2 = (uint32_t *) &array2[0][0];
uint32_t *pDest = (uint32_t *) &dest[0][0];

int  i;

for (i = 0; i < sizeof (dest) / sizeof (uint32_t); i++) {
    pDest[i] = pArr1[i] + pArr2[i];
}

它可能不是最优雅的方法，但它可以帮助您避免编写针对特定架构的代码。此外，如果您这样做，我强烈建议您注释您正在做什么以及为什么要这样做。

- Sparky

Answer 5

两个部分：首先，将您的二维数组[10][10]视为单个数组[100]。C++的布局规则应该允许这样做。其次，检查您的编译器是否具有实现某种形式的 SIMD指令的内置函数，例如英特尔的SSE。例如 Microsoft提供了一套。我相信SSE有一些指令可以用来检查最大值，甚至在需要时将其限制到最大值。

- Mark Ransom

---

@Tom Gullen，最好的感谢方式是点击答案旁边数字上方的向上箭头。 - Mark Ransom

它不让我做，因为我是新手，但我会尽力的！ - Tom Gullen

Answer 6

你应该看看CUDA。这种问题正是CUDA所擅长的。推荐Programming Massively Parallel Processors这本书。

然而，这需要具备CUDA能力的硬件，并且在开发环境中设置CUDA需要一些努力，所以这取决于这个问题的重要性！

祝你好运！

- user206705