28

是否有任何可靠的方法可以强制 GCC（或任何编译器）在memcpy()循环外部排除运行时大小检查（其中该大小不是编译时常量，而是该循环内的常量），针对每个相关大小范围专门循环而不是反复检查里面的大小？

这是一个测试用例，从这里报告的性能回归中减少，这是一个开源库，旨在对大型数据集进行有效的内存分析。（回归恰好是因为我的一个提交......）

原始代码在 Cython 中，但我已将其简化为纯 C 代理，如下所示：

void take(double * out, double * in,
          int stride_out_0, int stride_out_1,
          int stride_in_0, int stride_in_1,
          int * indexer, int n, int k)
{
    int i, idx, j, k_local;
    k_local = k; /* prevent aliasing */
    for(i = 0; i < n; ++i) {
        idx = indexer[i];
        for(j = 0; j < k_local; ++j)
            out[i * stride_out_0 + j * stride_out_1] =
            in[idx * stride_in_0 + j * stride_in_1];
    }
}

步幅是可变的；通常，甚至不能保证数组是连续的（因为它们可能是较大数组的不连续切片。）但是，对于 c 连续数组的特殊情况，我已将上述优化为以下内容：

void take(double * out, double * in,
          int stride_out_0, int stride_out_1,
          int stride_in_0, int stride_in_1,
          int * indexer, int n, int k)
{
    int i, idx, k_local;
    assert(stride_out_0 == k);
    assert(stride_out_0 == stride_in_0);
    assert(stride_out_1 == 1);
    assert(stride_out_1 == stride_in_1);
    k_local = k; /* prevent aliasing */
    for(i = 0; i < n; ++i) {
        idx = indexer[i];
        memcpy(&out[i * k_local], &in[idx * k_local],
               k_local * sizeof(double));
    }
}

（原始代码中不存在断言；相反，它会检查连续性并在可能的情况下调用优化版本，如果不是，则调用未优化版本。）

这个版本在大多数情况下优化得非常好，因为对于 smalln和 large的正常用例k。然而，相反的用例也确实发生了（大n和小k），事实证明，对于n == 10000and的特定情况k == 4（不能排除它代表假设工作流的重要部分），memcpy()版本是 3.6 倍比原来慢。显然，这主要是因为它k不是编译时常数，这一事实证明了下一个版本的性能（几乎或完全取决于优化设置）以及原始版本（或有时更好），对于特殊情况k == 4：

    if (k_local == 4) {
        /* this optimizes */
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    }

显然，为 的每个特定值硬编码一个循环是不切实际的k，所以我尝试了以下方法（作为第一次尝试，如果它有效，以后可以推广）：

    if (k_local >= 0 && k_local <= 4) {
        /* this does not not optimize */
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    }

不幸的是，最后一个版本并不比原始memcpy()版本快，这让我对 GCC 优化能力的信心有些沮丧。

有什么方法可以给 GCC 额外的“提示”（通过任何方式），这将帮助它在这里做正确的事情？（更好的是，是否有“提示”可以可靠地跨不同的编译器工作？这个库是为许多不同的目标编译的。）

引用的结果适用于带有“-O2”标志的 32 位 Ubuntu 上的 GCC 4.6.3，但我也测试了具有相似（但不相同）结果的 GCC 4.7.2 和“-O3”版本。我已经将我的测试工具发布到LiveWorkspace，但是时间来自我自己的机器使用time(1)命令（我不知道 LiveWorkspace 时间有多可靠。）

编辑：我也考虑过为一些最小尺寸设置一个“幻数”来调用memcpy()，我可以通过重复测试找到这样一个值，但我不确定我的结果在不同编译器/平台上的通用性如何. 我可以在这里使用任何经验法则吗？

进一步编辑：实际上，在这种情况下，意识到k_local变量是无用的，因为不可能有别名；这是从我在可能的地方（k是全球性的）进行的一些实验中减少的，我忘记了我改变了它。忽略那部分。

编辑标签：意识到我也可以在较新版本的 Cython 中使用 C++，所以标记为 C++，以防 C++ 有任何帮助...

最终编辑：代替（现在）下降到专业memcpy()的组装，以下似乎是我本地机器的最佳经验解决方案：

    int i, idx, j;
    double * subout, * subin;
    assert(stride_out_1 == 1);
    assert(stride_out_1 == stride_in_1);
    if (k < 32 /* i.e. 256 bytes: magic! */) {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            subout = &out[i * stride_out_0];
            subin = &in[idx * stride_in_0];
            for(j = 0; j < k; ++j)
                subout[j] = subin[j];
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            subout = &out[i * stride_out_0];
            subin = &in[idx * stride_in_0];
            memcpy(subout, subin, k * sizeof(double));
        }
    }

这使用“幻数”来决定是否调用memcpy()，但仍然优化已知连续的小数组的情况（因此在大多数情况下它比原始数组更快，因为原始数组没有做出这样的假设）。

4

3 回答 3

7

最终，手头的问题是要求优化器基于多个变量对运行时行为做出假设。虽然可以通过在关键变量上使用 'const' 和 'register' 声明来为优化器提供一些编译时提示，但最终，您要依赖优化器来做出很多假设。此外，虽然 memcpy() 很可能是内在的，但不能保证它是内在的，即使/当它是，实现可能会有很大的不同。

如果目标是实现最大性能，有时您不必依赖技术来为您解决问题，而是直接进行。对于这种情况，最好的建议是使用内联汇编程序来解决问题。这样做可以让您避免“黑盒”解决方案与编译器和优化器的启发式方法互补的所有缺陷，并有限地陈述您的意图。使用内联汇编程序的主要好处是能够在解决内存复制问题时避免任何推送/弹出和无关的“泛化”代码，并且能够直接利用处理器解决问题的能力。不利的一面是维护，但考虑到您确实只需要解决英特尔和 AMD 即可覆盖大部分市场，这并非不可克服。

我还可以补充一点，如果/当可以并行复制并真正获得性能提升时，该解决方案可以很好地让您利用多个内核/线程和/或 GPU。虽然延迟可能会更高，但吞吐量也很可能会更高。例如，如果您可以在 GPU 存在时利用其优势，那么您可以在每个副本中启动一个内核，并在一次操作中复制数千个元素。

替代方法是依靠编译器/优化器为您做出最佳猜测，使用“const”和“register”声明，您可以在其中提供编译器提示并使用幻数基于“最佳解决方案”进行分支路径...但是，这将非常依赖于编译器/系统，并且您的里程会因平台/环境而异。

于 2013-03-22T00:45:24.473 回答
2

SSE/AVX 和对齐

例如，如果您使用的是现代英特尔处理器，则可以选择使用 SSE 或 AVX 指令。虽然不是专门关于 GCC，但请参阅此如果您有兴趣并刷新缓存，我认为英特尔为 Linux 和 Windows 提供了他们的编译器套件版本，我猜它带有自己的库套件。

还有这个帖子。

线程 (eek)

我最近就遇到过这类问题，memcpy() 花费了太多时间。在我的例子中，它是一个大的 memcpy() （1MByte 左右），而不是像你正在做的很多较小的。

通过编写我自己的多线程 memcpy()，我获得了非常好的里程，其中线程是持久的，并且通过调用我自己的 pmemcpy() 函数获得了一份工作的“任务”。持久线程意味着开销非常低。我得到了 4 核的 x4 改进。

因此，如果可以将您的循环分解为合理数量的线程（我为每个可用核心选择一个），并且您的机器上有几个备用核心，您可能会获得类似的好处。

实时人群做什么 - DMA

顺便说一句，我有幸玩弄一些相当奇特的 OpenVPX 硬件。基本上它是一个大盒子里的一堆板，它们之间有一个高速串行RapidIO互连。每块板都有一个 DMA 引擎，可将数据通过 sRIO 驱动到另一块板的内存。

我去的那个供应商在如何最大限度地利用 CPU 方面非常聪明。聪明的一点是 DMA 引擎非常聪明——它们可以被编程来做一些事情，比如动态矩阵转换、剥离挖掘、你想要做的事情等等。而且因为它是一个单独的硬件，所以 CPU在此期间没有被捆绑，因此可以忙于做其他事情。

例如，如果您正在执行诸如合成孔径雷达处理之类的事情，那么您最终总是会进行大矩阵变换。美妙之处在于，转换本身完全不需要 CPU 时间——您只需将数据移动到另一块板上，它就已经转换了。

无论如何，从这类事情中受益确实让人希望英特尔 CPU（和其他 CPU）具有能够工作内存内存而不仅仅是内存外围设备的板载 DMA 引擎。这将使像您这样的任务非常快。

于 2013-03-21T22:06:29.463 回答
2

我认为最好的方法是试验并找出最佳的“k”值，以便在原始算法（带有循环）和使用 memcpy 的优化算法之间切换。最佳的“k”会因不同的 CPU 而异，但不应有太大的不同；本质上它是关于调用 memcpy 的开销，memcpy 本身在选择最优算法（基于大小、对齐等）与带有循环的“幼稚”算法时的开销。

memcpy 是 gcc 的内在属性，是的，但它并没有什么魔力。它的基本作用是，如果 size 参数在编译时已知并且很小（我不知道阈值是多少），那么 GCC 将用内联代码替换对 memcpy 函数的调用。如果在编译时不知道 size 参数，将始终调用库函数 memcpy。

于 2013-03-22T13:49:07.210 回答