如何快速找到向量和的最大元素？

Question

我在程序的最内层循环中有以下代码。

struct V {
  float val [200]; // 0 <= val[i] <= 1
};

V a[600];
V b[250];
V c[250];
V d[350];
V e[350];

// ... init values in a,b,c,d,e ...

int findmax(int ai, int bi, int ci, int di, int ei) {
  float best_val = 0.0;
  int best_ii = -1;

  for (int ii = 0; ii < 200; ii++) {
    float act_val =
      a[ai].val[ii] +
      b[bi].val[ii] +
      c[ci].val[ii] +
      d[ci].val[ii] +
      e[ci].val[ii];

    if (act_val > best_val) {
      best_val = act_val;
      best_ii = ii;
    }
  }

  return best_ii;
}

我不在乎使用什么聪明的算法（但这可能是最有趣的），或者一些C ++技巧或内置函数或汇编语言，但我需要让findmax函数更加高效。

提前致谢。

编辑: 看起来分支操作是最慢的（误判？）。

- Łukasz Lew

---

你能告诉我们更多关于外层循环的信息吗？也许结合这个，有更多的优化可能性。 - SebastianK

微优化，指的是它可能会被编译器处理，但并不会真正造成损害。我曾经看到过一些令人惊讶的基准测试结果，有时候这样微小的变化可以带来很大的差异：将 "switch i++" 改为 "++i"。这样在递增之前不会复制该值。 - krdluzni

Answer 1

如果编译器在跳转时遇到困难，可能会有所帮助：

int findmax(int ai, int bi, int ci, int di, int ei) {
  float best_val = 0.0;
  int best_ii = -1;

  float* a_it = &a[ai].val[0]
  float* b_it = &b[bi].val[0]
  float* c_it = &c[ci].val[0]
  float* d_it = &d[di].val[0] // assume typo ci->di
  float* e_it = &e[ei].val[0] // assume typo ci->ei

  for (int ii = 0; ii < 200; ii++) {
    float act_val = *(a_it++) + *(b_it++) + *(c_it++) + *(d_it++) + *(e_it++);
    best_val =  (act_val <= best_val) ? best_val : act_val; // becomes _fsel
    best_ii  =  (act_val <= best_val) ? best_ii : ii; // becomes _fsel
  }

  return best_ii;
}

生成汇总表在缓存未命中方面可能更快，稍后我会发布这个内容：

int findmax(int ai, int bi, int ci, int di, int ei) {
  float best_val = 0.0;
  int best_ii = -1;

  float* its[] = {&a[ai].val[0], &a[bi].val[0], &a[ci].val[0], &a[di].val[0], &a[ei].val[0] };

  V sums;
  for (int ii = 0; ii < 200; ii++) {
    sums.val[ii] = * (++its[0]);
  }

  for (int iter = 1 ; iter < 5; ++iter)  {
      for (int ii = 0; ii < 200; ii++) {
        sums.val[ii] += * (++its[iter]);
      }
    }
  }
  for (int ii = 0; ii < 200; ii++) {
    best_val =  (sums.val[ii] <= best_val) ? best_val : sums.val[ii]; // becomes _fsel
    best_ii  =  (sums.val[ii] <= best_val) ? best_ii : ii; // becomes _fsel
  } 
  return best_ii;
}

- Charles Beattie

---

如果您不喜欢我的方法，请尝试使用_fsel方法来设置bet_val和best_ii。 - Charles Beattie

Answer 2

除非编译器为您进行优化，否则在循环中计算 a [ai] 等将花费一些时间（尽管很少），因为它们在 findmax 的持续时间内是固定的。考虑到这一点，您可能会尝试类似以下的代码：

int findmax(int ai, int bi, int ci, int di, int ei) {
    float    best_val = std::numeric_limits<float>::min();
    int      best_ii = 0;
    const V& a(a[ai]);
    const V& b(b[bi]);
    const V& c(c[ci]);
    const V& d(d[di]);
    const V& e(e[ei]);

    for (int ii = 0; ii < 200; ++ii) {
        float act_val = a.val[ii] + b.val[ii] + c.val[ii] +
                        d.val[ii] + e.val[ii];

        if (act_val > best_val) {
            best_val = act_val;
            best_ii = ii;
        }
    }

    return best_ii;
}

改善代码的其他方法可能是改变数据表示方式，从而导致不同（但更快）的findmax算法。

- fbrereto

---

同意，函数内部并没有太多的优化空间，但也许你会多次寻找相同的最大值，或者数据布局使得你可以找到捷径，这些都是应该加速整个代码的事情。 - DeusAduro

任何一个合理的编译器都会自动地为您执行此优化。 - Mark Ransom

best_val 应该被初始化为负无穷。 - Jason S

Answer 3

我没有看到任何不检查每个总和的方法，这使得它成为O(n)问题。但由于您的数据是线性布置的，因此Intel/AMD MMX或SSE指令可能会有帮助。请参阅此链接以获取Microsoft内部函数的实现： http://msdn.microsoft.com/en-us/library/y0dh78ez(VS.71).aspx

- Mark Ransom

---

具体而言，您需要使用addps（打包添加）指令，它将同时执行4个浮点加法运算，并将结果转储到一个XMM寄存器中，相当于一个float [4]。如果您存储了一些这样的值，那么还可以使用maxps（打包最大值）进行并行比较，从而获得收益。显然，最后几次比较必须使用单个浮点运算而不是SSE。 - Steve Jessop

Answer 4

我认为在算法上没有明显的优化空间。理论上，只有计算五个向量的总和直到明显无法达到最大值，但这会增加太多的开销，仅仅是为了求和五个数字。你可以尝试使用多个线程并将范围分配给线程，但当你只有 200 个非常短的工作项时，必须考虑线程创建的开销。

所以，我倾向于说，在 x86 上使用 Assembler 和 MMX 或 SSE 指令，或者使用（机器特定的）C++ 库提供对这些指令的访问是最好的选择。

- Daniel Brückner

---

你只有200个非常短的工作项。虽然他说代码在最内部循环中，所以如果他正在为许多不同的ai、bi等组合进行计算，那么也许他可以多线程并在比这个函数更高的级别上分解工作。这取决于向量内容和每组5个参数是否取决于先前计算的结果。此外，它不是线程创建开销，而是线程通信开销，因为您可以维护一个工作线程池而不是每次调用都创建它们。 - Steve Jessop

如果你要引入线程，你还必须考虑这是否真的有帮助，这取决于应用程序的更大目的以及它将在哪里运行。 - krdluzni

话虽如此，多线程不会使这个算法“更有效”，只有可能更快。它不会减少计算结果所需的 CPU 循环/操作次数。如果机器上有空闲核心，多线程通常只有帮助作用，在运行大量应用程序的服务器上，可能没有空闲核心。 - Steve Jessop

Answer 5

尝试一次迭代所有向量。以下是两个向量的示例：

for (float *ap = a[ai].val, *bp = b[bi].val; ap - a[ai].val < 200; ap++, bp ++) {
    float act_val = *ap + *bp;
    // check for max and return if necessary
}

- P Shved

Answer 6

看一下循环展开（以及Duff的设备作为一个具体但更复杂的例子）。这些是我能想到的唯一真正的算法优化。

循环展开

Duff的设备

- krdluzni

---

当循环长度始终相同时（在本例中为200），实际上不需要使用Duff的设备。可以使用200的因子作为展开的长度，或者使用非因子但从单个goto进入循环的中间开始。 - Steve Jessop

你说得对，其实不需要，但我认为这可以作为展示 unwinding 的有趣例子。但说实话，Duff's 设备比普通的 unwind 要复杂得多，我正在考虑从我的帖子中删除它。 - krdluzni

我完全赞成每个人都能够看到达夫设备，只要他们知道除非绝对必要，否则不要使用它。甚至可能连那个时候也不要使用 :-) - Steve Jessop

Answer 7

如果没有关于存储在a、b、c、d和e中的数据（值）的其他信息，你实际上无法更快地获得更多。你必须检查每个总和以确定哪一个最大。

对于第N个元素查询，情况会变得更糟，但幸运的是，您没有提出这个问题。

- MSN