优化索引数组求和

Question

我有以下C++代码：

const int N = 1000000
int id[N]; //Value can range from 0 to 9
float value[N];

// load id and value from an external source... 

int size[10] = { 0 };
float sum[10] = { 0 };
for (int i = 0; i < N; ++i)
{
    ++size[id[i]];
    sum[id[i]] += value[i];
}

我应该如何优化循环？

我考虑使用SSE将每4个浮点数加到一个sum中，然后在N次迭代后，总和就是xmm寄存器中4个浮点数的和，但是当源像这样被索引并且需要写出10个不同的数组时，这是不起作用的。

Answer 1

这种循环很难使用SIMD指令进行优化。不仅在大多数SIMD指令集中没有一种简单的方法来执行这种索引读取(“聚集”)或写入(“散布”)，即使有，这个特定的循环仍然存在这样的问题，即在一个SIMD寄存器中可能有两个值映射到相同的id，例如当

id[0] == 0
id[1] == 1
id[2] == 2
id[3] == 0

在这种情况下，最明显的方法(这里是伪代码)

x = gather(size, id[i]);
y = gather(sum, id[i]);
x += 1; // componentwise
y += value[i];
scatter(x, size, id[i]);
scatter(y, sum, id[i]);

也不会起作用！

如果可能的情况非常少(例如，假设sum和size各只有3个元素)，你可以通过暴力比较来解决，但这并不是真正的可伸缩性。

在不使用SIMD的情况下，有一种方法可以更快地实现这一点，那就是使用展开来打破指令之间的依赖关系：

int size[10] = { 0 }, size2[10] = { 0 };
int sum[10] = { 0 }, sum2[10] = { 0 };
for (int i = 0; i < N/2; i++) {
  int id0 = id[i*2+0], id1 = id[i*2+1];
  ++size[id0];
  ++size2[id1];
  sum[id0] += value[i*2+0];
  sum2[id1] += value[i*2+1];
}

// if N was odd, process last element
if (N & 1) {
  ++size[id[N]];
  sum[id[N]] += value[N];
}

// add partial sums together
for (int i = 0; i < 10; i++) {
  size[i] += size2[i];
  sum[i] += sum2[i];
}

不过，这是否有帮助取决于目标CPU。

Answer 2

那么，你在你的循环中调用了两次idi。您可以将其存储在一个变量中，如果您愿意，也可以存储在一个寄存器int中。

register int index;
for(int i = 0; i < N; ++i)
{
index = id[i];
++size[index];
sum[index] += value[i];
}

MSDN文档对寄存器作了如下说明：

关键字register指定变量将存储在机器寄存器中。特定于Microsoft

编译器不接受用户对寄存器变量的请求；相反，当全局寄存器分配优化(/Oe选项)打开时，编译器会自行选择寄存器。但是，将遵守与register关键字关联的所有其他语义。

Answer 3

您可以做的事情是使用-S标志编译它(如果您不使用gcc，则使用等效标志)，并使用-O、-O2和-O3标志比较各种汇编输出。优化循环的一种常见方法是进行某种程度的展开，例如(非常简单、幼稚的)示例：

int end = N/2;
int index = 0;
for (int i = 0; i < end; ++i)
{
    index = 2 * i;
    ++size[id[index]];
    sum[id[index]] += value[index];
    index++;
    ++size[id[index]];
    sum[id[index]] += value[index];
}

这将把cmp指令的数量减半。然而，任何不太好的优化编译器都能帮你做到这一点。