强制GCC执行memcpy运行时大小检查的循环非开关？

Question

有没有什么可靠的办法迫使海湾合作委员会(或编译器)中分解出运行时的大小检查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));
    }
}

(断言不存在于原始代码中;而是检查连续性并在可能的情况下调用优化版本,如果不可能则调用未优化版本.)

在大多数情况下,此版本优化得非常好,因为正常使用情况如果是小型n和大型k.然而,相反的使用情况下不会发生的,以及(大n,小k),而且事实证明了的具体情况n == 10000和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()或没有,但仍然可以优化已知是连续的小数组的情况下(因此它比原来快了,在大多数情况下,由于原没有这样的假设).

Answer 1

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

如果目标是实现最高性能,有时您只需要依靠技术来为您解决问题,而不是直接进行.针对这种情况的最佳建议是使用内联汇编程序来解决问题.这样做可以避免"黑匣子"解决方案的所有陷阱,对编译器和优化器的启发式方法进行补充,并有限地说明您的意图.使用内联汇编程序的主要好处是能够避免在内存复制问题的解决方案中出现任何推/弹和无关的"泛化"代码,并能够直接利用处理器解决问题的能力.缺点是维护,但考虑到你真的需要只针对大部分市场的英特尔和AMD,它并非不可克服.

我也可以补充一点,这个解决方案可以很好地利用多个核心/线程和/或GPU(如果/可用的话)并行进行复制并真正获得性能提升.虽然延迟可能更高,但吞吐量很可能也会高得多.例如,如果你可以利用GPU,你可以在每个副本上启动一个内核,并在一次操作中复制数千个元素.

替代方法是依赖于编译器/优化器为您做出最好的猜测,使用'const'和'register'声明,您可以在其中提供编译器提示并使用幻数基于"最佳解决方案"进行分支路径......然而,这将依赖于编译器/系统,并且从一个平台/环境到另一个平台/环境,您的里程会有很大差异.