9

给定数组：

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

在所有值的范围从 0 到 100的情况下，C++ 中添加这两个数组的最快方法是什么，以便画布中的每个单元格等于自身加上插件中的相应单元格值？

IE，我想实现类似：

canvas += another;

所以如果 canvas[0][0] =3 并且 addon[0][0] = 2 那么 canvas[0][0] = 5

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

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

4

6 回答 6

9

这是一个 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。

于 2010-06-03T08:19:52.420 回答
3

在 C++ 中，你不能做任何比循环更快的事情。您将需要使用一些特定于平台的向量指令。也就是说，您需要深入到汇编语言级别。但是，有一些 C++ 库会尝试为您执行此操作，因此您可以在高级别的地方编写代码，并让库负责执行适合您编译器所针对的任何架构的低级SIMD工作。

MacSTL是您可能想要查看的库。它最初是一个 Macintosh 特定的库，但现在它是跨平台的。有关更多信息，请参见他们的主页。

于 2010-06-02T16:22:36.760 回答
3

您在标准 C 或 C++ 中要做的最好的事情是将其重铸为 100 个数字的一​​维数组并将它们添加到循环中。（单下标将比双下标使用更少的处理，除非编译器可以对其进行优化。如果有影响的话，你要知道有多少影响的唯一方法是测试。）

您当然可以创建一个类，其中添加的内容将是一条简单的 C++ 指令 ( canvas += addon;)，但这不会加快任何速度。所发生的只是简单的 C++ 指令将扩展为上面的循环。

您需要进入较低级别的处理以加快速度。许多现代 CPU 上都有额外的指令来执行您可能可以使用的此类处理。您可能可以使用类似Cuda的东西在 GPU 上运行类似的东西。您可以尝试使操作并行运行并在多个内核上运行，但在如此小的实例上，您必须知道缓存如何在 CPU 上工作。

替代方案是改进您的算法（在背包类型的问题上，您可能能够以某种方式使用动态规划- 没有您提供的更多信息，我们无法告诉您），或者接受性能。对 10 x 10 数组的数千万次操作变成了对数的数千亿次操作，这不再像以前那样令人生畏了。当然，我不知道你的使用场景或性能要求。

于 2010-06-02T16:37:56.017 回答
2

两部分：首先，将您的二维数组 [10][10] 视为单个数组 [100]。C++ 的布局规则应该允许这样做。其次，检查您的编译器是否有实现某种形式的SIMD 指令的内在函数，例如英特尔的 SSE。例如，微软提供了一套. 我相信 SSE 有一些关于检查最大值的说明，如果你愿意，甚至可以钳制到最大值。

于 2010-06-02T16:21:25.890 回答
2

这是一个替代方案。

如果您 100% 确定所有值都在 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];
}

它可能不是最优雅的，但它可以帮助您避免使用特定于架构的代码。此外，如果你要这样做，我强烈建议你评论你在做什么以及为什么。

于 2010-06-08T14:39:18.807 回答
1

你应该看看 CUDA。这种问题就在CUDA的街道上。推荐Programming Massively Parallel Processors这本书。

但是，这确实需要支持 CUDA 的硬件，并且 CUDA 需要花费一些精力才能在您的开发环境中进行设置，所以这取决于这到底有多重要！

祝你好运！

于 2010-08-14T12:01:07.083 回答