-2

有什么办法可以加速这个功能：

void task(int I, int J, int K, int *L, int **ids, double *bar){ 
    double *foo[K];
    for (int k=0;k<K;k++)
        foo[k] = new double[I*L[k]];
        // I am filling these arrays somehow
        // This is not a bottleneck, hence omitted here        
    for (int i=0;i<I;i++)
        for (int j=0;j<J;j++){
            double tmp = 1.;
            for (int k=0;k<K;k++)
                tmp *= foo[k][i*L[k]+ids[j][k]]; //ids[j][k]<L[k]
            bar[i*J+j] = tmp;
        }
}

典型值为：I = 100,000, J = 10,000, K=3, L=[50,20,60].

我读到__restrict__关键字/扩展名可能会有所帮助，但不确定如何在此处应用它。例如，试图将其放入foo[k] = new double[...]I get 的定义中error: '__restrict_ qualifiers cannot be applied to double。此外，我不知道我是否应该/如何声明ids和ids[j], 1<= j<= J限制。

需要注意的是，在我的实际代码中，我在与我的 CPU 内核一样多的线程中并行执行此类任务。

我主要编写与 C 兼容的 C++，因此欢迎使用两种语言的解决方案。

4

2 回答 2

2

https://en.cppreference.com/w/c/language/restrictrestrict声称您可以在 C99/C11 中声明一个指向 double的指针数组：

typedef double *array_t[10];
restrict array_t foo;        // the type of a is double *restrict[10]

但只有 gcc 接受。我认为这是一个 GCC 主义，而不是有效的 ISO C11。（gcc 也接受
array_t restrict foo_r;，但没有其他编译器接受。）

ICC警告"restrict" is not allowed，clang拒绝它

<source>:16:5: error: restrict requires a pointer or reference ('array_t' (aka 'double *[10]') is invalid)
    restrict array_t foo_r;
    ^

MSVC 拒绝它error C2219: syntax error: type qualifier must be after '*'

我们从这些带有 的编译器中获得了基本相同的 C++ 行为__restrict，它们接受为具有与 C99 相同语义的 C++ 扩展restrict。

作为一种解决方法，您可以在每次读取时使用合格的临时指针foo，而不是f[k][stuff]. 我认为这保证了您引用的内存fk与您通过声明的块中的任何其他指针访问的内存不同fk。

double *__restrict fk = foo[k];
tmp *= fk[ stuff ];

我不知道如何向编译器保证没有一个f[0..K-1]指针相互别名。我不认为这可以做到这一点。

您在这里不需要 __restrict。

根据 Godbolt 编译器资源管理器上的差异窗格： https ://godbolt.org/z/4YjlDA，我添加__restrict了所有指针声明，就像int *__restrict *__restrict ids它根本没有改变 asm 。 正如我们所期望的那样，因为基于类型的别名让编译器假设store into不会修改. 正如人们在评论中所说，这里没有编译器无法解决的别名。在实践中，它似乎确实对其进行了排序，没有任何额外的指针重新加载。doublebar[]int *int *ids[]

它也不能 alias ，因为我们在这个函数中*foo[k]得到了那些指针。new他们不能指着里面bar[]。

（所有主要的 x86 C++ 编译器（GCC、clang、ICC、MSVC）__restrict在 C++ 中都支持与 C99 相同的行为restrict：对通过此指针存储的编译器的承诺不会修改另一个指针指向的对象。我'会推荐__restrictover __restrict__，至少如果你最想要跨 x86 编译器的可移植性。我不确定除此之外。）

看起来您是在说您尝试进行__restrict__分配，而不是声明。那是行不通的，它是指针变量本身__restrict适用，而不是对它的单个赋值。

该问题的第一个版本在内部循环中有一个错误：它有K++而不是k++，所以它是纯粹的未定义行为，编译器变得很奇怪。asm 没有任何意义（例如，没有 FP 乘法指令，即使foo[]是函数 arg）。这就是为什么最好使用类似的名称klen而不是K数组维度的原因。

在Godbolt链接上修复它之后，__restrict在所有东西上使用/不使用asm仍然没有区别，但它更加理智。

顺便说一句，创建double *foo[]一个函数 arg 会让我们只查看主循环的 asm。而且您实际上需要__restrict，因为商店bar[]可以修改foo[][]. 这不会在您的函数中发生，因为编译器知道new内存不是由任何现有指针指向的，但它不知道 iffoo是一个函数 arg。

循环中的少量工作是在将 32 位int结果用作具有 64 位指针的数组索引之前对它们进行符号扩展。这会在某处增加一个延迟周期，但不会增加循环承载的 FP 乘法依赖链，因此它可能无关紧要。size_t k=0;您可以通过使用作为最内层循环计数器 来摆脱 x86-64 上内层循环中的一条指令。L[]是一个 32 位数组，因此i*L[k]需要在循环内进行符号扩展。从 32 位到 64 位的零扩展在 x86-64 上是免费的，因此在指针追踪 dep 链中i * (unsigned)L[k]保存了一条指令。movsx然后 gcc8.2 制作的内部循环是您讨厌的数据结构/布局所需的所有必要工作。 https://godbolt.org/z/bzVSZ7

我不知道这是否会有所作为。我认为导致缓存未命中的内存访问模式更有可能成为您处理真实数据的瓶颈。

它也不能自动矢量化，因为数据不连续。但是，您无法从循环中获取连续的源数据jor i。至少i会是一个简单的大步而不必重做ids[j][k]。

如果您生成foo[k][...]并bar[...]转置，因此您使用 进行索引foo[k][ i + L[k] * ids[j][k] ]，那么您将在 src 和 dst 中拥有连续的内存，因此您（或编译器）可以使用 SIMD 乘法。

于 2019-01-06T10:03:43.747 回答
0

restrict在这种情况下没关系。

您的算法很垃圾，并且不允许使用长向量运算（因此微优化在这里根本没有帮助）。

您需要找到内部循环中的元素占用数组索引的连续块的方式。正如现在所做的那样，编译器必须从数组中的不同位置读取每个元素，它使编译器免受循环展开和更长的向量指令的影响。它也可能对缓存非常不友好。

首先重新考虑算法 - 如果算法效率极低，过早的优化将无济于事

编辑

在 OP 评论之后，我只想向他展示“天真”和更高效（不那么天真但更难理解）之间的区别

让我们考虑 32 位无符号值的奇偶校验。天真的方法：

int very_naive_parity(const uint32_t val)
{
    unsigned parity = 0;
    
    for(unsigned bit = 0; bit < 32; bit++)
    {
        if(val & (1U << bit))
        {
            parity = !parity;
        }
    }
    return parity;
}

它很容易编写和理解，但效率极低。至少将执行 288 条指令来计算该奇偶校验。

更高效：

int parity(const uint32_t val)
{
    uint32_t tmp = val;
    
    tmp ^= tmp >> 16;
    tmp ^= tmp >> 8;
    tmp ^= tmp >> 4;
    return (0b110100110010110 >> (tmp & 0x0f)) & 1;
}

将在 9 条指令中执行（没有函数序言和结语的计算）是不是更难理解？- 绝对是的。但正如我写的那样，效率通常对人类来说意味着不那么容易。

于 2019-01-06T10:34:17.873 回答