我怎样才能加速这段代码（MWE！），例如使用限制
How can I accelerate this code (MWE!), e.g. using restrict
有什么办法可以加速这个功能：
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__ keyword/extension 可以提供帮助，但我不确定如何在此处应用它。例如，尝试将其放入 foo[k] = new double[...] 的定义中，我得到 error: '__restrict_ qualifiers cannot be applied to double。此外，我不知道我是否应该/如何声明 ids 和 ids[j], 1<= j<= J 为受限。
请注意，在我的实际代码中，我会在与我的 CPU 拥有的内核一样多的线程中并行执行此类任务。
我主要编写与 C 兼容的 C++，因此欢迎两种语言的解决方案。
https://en.cppreference.com/w/c/language/restrict 声称您可以像在 C99/C11:
中那样声明一个 restrict 指向 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 '*'
拒绝它
我们使用 __restrict 从这些编译器中获得基本相同的 C++ 行为，它们将其接受为具有与 C99 相同语义的 C++ 扩展 restrict。
作为一种解决方法，您可以在每次从 foo 读取时使用限定的临时指针，而不是 f[k][stuff]。 我认为这很有希望您通过 fk 引用的内存与您通过声明 fk 的块中的任何其他指针访问的内存不同。
double *__restrict fk = foo[k];
tmp *= fk[ stuff ];
我不知道如何向编译器保证 f[0..K-1] 指针中的 none 互为别名。我不认为这可以做到这一点。
这里不需要__restrict。
我在所有指针声明中添加了 __restrict，例如 int *__restrict *__restrict ids，它根本没有改变 asm，根据 Godbolt 编译器资源管理器上的差异窗格：https://godbolt.org/z/4YjlDA. 正如我们预期的那样，因为基于类型的别名让编译器假设 double 存储到 bar[] 不会修改 int *ids[] 的任何 int * 元素=]. 正如人们在评论中所说，这里没有编译器无法解决的别名。在实践中，它 确实 解决了问题，没有任何额外的指针重载。
它也不能为*foo[k]起别名，因为我们在这个函数中得到了那些带有new的指针。他们不能指向内部 bar[].
（所有主要的 x86 C++ 编译器（GCC、clang、ICC、MSVC）都支持 C++ 中的 __restrict，其行为与 C99 restrict 相同：对通过此存储的编译器的承诺指针不修改另一个指针指向的对象。
我建议 __restrict 而不是 __restrict__，至少如果您主要希望跨 x86 编译器的可移植性。我不确定外面的情况。）
您似乎是在说您试图将 __restrict__ 放入赋值中，而不是声明中 。那行不通，__restrict 应用于指针变量本身，而不是对它的单个赋值。
问题的第一个版本在内部循环中有一个错误：它有 K++ 而不是 k++，所以它是纯粹的未定义行为，编译器变得很奇怪。 asm 没有任何意义（例如，没有 FP 乘法指令，即使 foo[] 是函数 arg）。这就是为什么对数组维度使用 klen 之类的名称而不是 K 是个好主意。
在 Godbolt link 上修复后，在任何情况下，带/不带 __restrict 的 asm 仍然没有区别，但它更加理智。
顺便说一句，使 double *foo[] 成为一个函数 arg 可以让我们只查看主循环的 asm。您实际上需要 __restrict，因为 bar[] 的存储可以修改 foo[][] 的元素。这不会发生在你的函数中，因为 编译器知道 new 内存没有被任何现有指针指向 ，但它不知道如果 foo 是一个函数参数。
循环中有少量工作是符号扩展 32 位 int 结果，然后将它们用作具有 64 位指针的数组索引。这会在某个地方增加一个延迟循环，但不会增加循环携带的 FP 乘法依赖链，因此它可能无关紧要。您可以通过使用 size_t k=0; 作为最内层的循环计数器来摆脱 x86-64 上内层循环中的一条指令。 L[] 是一个 32 位数组，所以 i*L[k] 需要在循环内进行符号扩展。从 32 位到 64 位的零扩展在 x86-64 上免费发生，因此 i * (unsigned)L[k] 在指针追踪 dep 链中保存了一条 movsx 指令。然后 gcc8.2 进行的内部循环是所有必要的工作，这是您讨厌的数据结构/布局所必需的。 https://godbolt.org/z/bzVSZ7
我不知道这是否会产生影响。我认为导致缓存未命中的内存访问模式更有可能成为实际数据的瓶颈。
它也无法自动矢量化，因为数据不连续。但是，您无法通过遍历 j 或 i 获得连续的源数据。至少 i 将是一个简单的步骤，而无需重做 ids[j][k].
如果你生成 foo[k][...] 和 bar[...] 转置，所以你用 foo[k][ i + L[k] * ids[j][k] ] 索引，那么你在 src 和 dst 中会有连续的内存，所以你（或编译器）可以使用 SIMD 乘法。
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 条指令中执行（无函数序言和尾声的计算）
是不是更难理解？ - 绝对是的。但正如我所写，效率通常对人类来说意味着不那么容易。
有什么办法可以加速这个功能：
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__ keyword/extension 可以提供帮助，但我不确定如何在此处应用它。例如，尝试将其放入 foo[k] = new double[...] 的定义中，我得到 error: '__restrict_ qualifiers cannot be applied to double。此外，我不知道我是否应该/如何声明 ids 和 ids[j], 1<= j<= J 为受限。
请注意，在我的实际代码中，我会在与我的 CPU 拥有的内核一样多的线程中并行执行此类任务。
我主要编写与 C 兼容的 C++，因此欢迎两种语言的解决方案。
https://en.cppreference.com/w/c/language/restrict 声称您可以像在 C99/C11:
中那样声明一个restrict 指向 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 '*'
我们使用 __restrict 从这些编译器中获得基本相同的 C++ 行为，它们将其接受为具有与 C99 相同语义的 C++ 扩展 restrict。
作为一种解决方法，您可以在每次从 foo 读取时使用限定的临时指针，而不是 f[k][stuff]。 我认为这很有希望您通过 fk 引用的内存与您通过声明 fk 的块中的任何其他指针访问的内存不同。
double *__restrict fk = foo[k];
tmp *= fk[ stuff ];
我不知道如何向编译器保证 f[0..K-1] 指针中的 none 互为别名。我不认为这可以做到这一点。
这里不需要__restrict。
我在所有指针声明中添加了 __restrict，例如 int *__restrict *__restrict ids，它根本没有改变 asm，根据 Godbolt 编译器资源管理器上的差异窗格：https://godbolt.org/z/4YjlDA. 正如我们预期的那样，因为基于类型的别名让编译器假设 double 存储到 bar[] 不会修改 int *ids[] 的任何 int * 元素=]. 正如人们在评论中所说，这里没有编译器无法解决的别名。在实践中，它 确实 解决了问题，没有任何额外的指针重载。
它也不能为*foo[k]起别名，因为我们在这个函数中得到了那些带有new的指针。他们不能指向内部 bar[].
（所有主要的 x86 C++ 编译器（GCC、clang、ICC、MSVC）都支持 C++ 中的 __restrict，其行为与 C99 restrict 相同：对通过此存储的编译器的承诺指针不修改另一个指针指向的对象。
我建议 __restrict 而不是 __restrict__，至少如果您主要希望跨 x86 编译器的可移植性。我不确定外面的情况。）
您似乎是在说您试图将 __restrict__ 放入赋值中，而不是声明中 。那行不通，__restrict 应用于指针变量本身，而不是对它的单个赋值。
问题的第一个版本在内部循环中有一个错误：它有 K++ 而不是 k++，所以它是纯粹的未定义行为，编译器变得很奇怪。 asm 没有任何意义（例如，没有 FP 乘法指令，即使 foo[] 是函数 arg）。这就是为什么对数组维度使用 klen 之类的名称而不是 K 是个好主意。
在 Godbolt link 上修复后，在任何情况下，带/不带 __restrict 的 asm 仍然没有区别，但它更加理智。
顺便说一句，使 double *foo[] 成为一个函数 arg 可以让我们只查看主循环的 asm。您实际上需要 __restrict，因为 bar[] 的存储可以修改 foo[][] 的元素。这不会发生在你的函数中，因为 编译器知道 new 内存没有被任何现有指针指向 ，但它不知道如果 foo 是一个函数参数。
循环中有少量工作是符号扩展 32 位 int 结果，然后将它们用作具有 64 位指针的数组索引。这会在某个地方增加一个延迟循环，但不会增加循环携带的 FP 乘法依赖链，因此它可能无关紧要。您可以通过使用 size_t k=0; 作为最内层的循环计数器来摆脱 x86-64 上内层循环中的一条指令。 L[] 是一个 32 位数组，所以 i*L[k] 需要在循环内进行符号扩展。从 32 位到 64 位的零扩展在 x86-64 上免费发生，因此 i * (unsigned)L[k] 在指针追踪 dep 链中保存了一条 movsx 指令。然后 gcc8.2 进行的内部循环是所有必要的工作，这是您讨厌的数据结构/布局所必需的。 https://godbolt.org/z/bzVSZ7
我不知道这是否会产生影响。我认为导致缓存未命中的内存访问模式更有可能成为实际数据的瓶颈。
它也无法自动矢量化，因为数据不连续。但是，您无法通过遍历 j 或 i 获得连续的源数据。至少 i 将是一个简单的步骤，而无需重做 ids[j][k].
如果你生成 foo[k][...] 和 bar[...] 转置，所以你用 foo[k][ i + L[k] * ids[j][k] ] 索引，那么你在 src 和 dst 中会有连续的内存，所以你（或编译器）可以使用 SIMD 乘法。
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 条指令中执行（无函数序言和尾声的计算） 是不是更难理解？ - 绝对是的。但正如我所写，效率通常对人类来说意味着不那么容易。