SIMD 线性搜索比展开循环慢

Question

我正在开发一个高度优化的线性搜索将对整体性能产生重大影响的应用程序，我的任务是尽可能提高性能。

我运行搜索一个由 10,000 个元素组成的向量，最后以标记值为界，我运行在与目标元素的某个恒定距离处进行线性搜索，并且测量找到元素所花费的时间。我从元素集中随机选择目标元素，这些元素位于距数组开头的恒定距离之后，以允许开始搜索。我正在使用 Google's benchmark framework.

来衡量性能

我收集的结果让我吃惊。我预计在某些时候 SIMD 会在性能上击败展开的循环，但随着阵列行进所需距离的增加，两者之间的差距似乎越来越大。此外，我不确定为什么展开 8 次的循环运行s 在较短的距离上比展开 32 次的循环要快。

Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
BM_Search<linUnroll<8>>/2             86 ns         86 ns    7699241
BM_Search<linUnroll<8>>/4            103 ns        103 ns    6797378
BM_Search<linUnroll<8>>/16           650 ns        650 ns    1079095
BM_Search<linUnroll<8>>/64          1365 ns       1365 ns     514196
BM_Search<linUnroll<8>>/256         3558 ns       3558 ns     196519
BM_Search<linUnroll<8>>/1024       12358 ns      12358 ns      56635
BM_Search<linUnroll<8>>/4096       47341 ns      47341 ns      14780
BM_Search<linUnroll<8>>/8192       95029 ns      95030 ns       7367
BM_Search<linUnroll<32>>/2           131 ns        131 ns    5337221
BM_Search<linUnroll<32>>/4           131 ns        131 ns    5329296
BM_Search<linUnroll<32>>/16          291 ns        291 ns    2404646
BM_Search<linUnroll<32>>/64          836 ns        836 ns     831093
BM_Search<linUnroll<32>>/256        2776 ns       2776 ns     252901
BM_Search<linUnroll<32>>/1024      10962 ns      10962 ns      63828
BM_Search<linUnroll<32>>/4096      41312 ns      41312 ns      16941
BM_Search<linUnroll<32>>/8192      83303 ns      83304 ns       8401
BM_Search<linSIMD>/2                 163 ns        163 ns    4304086
BM_Search<linSIMD>/4                 208 ns        208 ns    3354716
BM_Search<linSIMD>/16                366 ns        366 ns    1912122
BM_Search<linSIMD>/64                871 ns        871 ns     803854
BM_Search<linSIMD>/256              3333 ns       3334 ns     210159
BM_Search<linSIMD>/1024            11262 ns      11262 ns      62157
BM_Search<linSIMD>/4096            42656 ns      42656 ns      16413
BM_Search<linSIMD>/8192            87824 ns      87824 ns       7970

我运行正在使用 i5-4570，并且我已遵守 clang 5.0.0。 quick-bench 没有 AVX，而且 clang 在 3.8 版中没有完全展开，但它应该是运行nable。我也尝试展开 SIMD，以及转到 AVX256 指令，但两者都使性能变差。为什么展开的循环要快得多？为什么展开次数多的循环比展开次数少的循环执行得差得多？

SIMD 的经典诊断是您在 SIMD 方面做得不够，但我认为我在这里做得足够多。

#include <vector>
#include <cinttypes>
#include <immintrin.h>
typedef int V;
typedef std::vector<V> vi;

long linSIMD(const vi& arr, const long guessIx, const V x) {
  using v4 = V __attribute__ ((vector_size (4*4)));
  using dv2 = int64_t __attribute__ ((vector_size (4*4)));
  constexpr int roll = 4;
  constexpr union {
    int32_t i32[2];
    int64_t i64;
  } skip = {-2,-2};
  v4 xVec = {x,x,x,x};
  for (int i = guessIx;; i += roll) {
    v4 arrVec;
    for (long j = 0; j < 4; j++) arrVec[j] = arr[i+j];
    union {
        v4 i32;
        dv2 i64;
    } cmpVec = {arrVec < xVec};
    v4 cmpVec2 = {cmpVec.i32[3], cmpVec.i32[2], cmpVec.i32[1],cmpVec.i32[0]};
    cmpVec.i32 += cmpVec2;
    if (cmpVec.i64[0] == skip.i64) continue;
    return i - cmpVec.i32[0] - cmpVec.i32[1];
  }
}

long linUnroll32(const vi& arr, const long guessIx, const V x) {
  constexpr int roll = 32;
  for (long i = guessIx;; i += roll)
    for (long j = 0; j < roll; j++)
        if (arr[i+j] >= x) return i+j;
}

http://quick-bench.com/_x_v_WXLWtwvvLsObNlIxjXxS_g https://godbolt.org/g/Wyx2pS

Answer 1

在 SIMD 案例的循环中使用更大的批次。

例如对4个SIMD寄存器进行比较，然后将16次比较结果放入一个SIMD寄存器中。然后在上面放一个分支（如果找到匹配项，则从循环中中断）。这样，您将拥有：

分支较少
编译器有更多可能的并行化机会 & CPU

跳出循环后，您需要在 16 个可能的条目中找到匹配项的索引。您可以使用 SIMD 或您喜欢的任何方法来完成。

这种方式应该比您当前的实现（对于大型数组）更快。

Answer 2

我能做的最好的（查看 quick-bench 上的结果）就是这样，

int linSIMD4(const vi& arr, const int guessIx, const int x) {
  auto vecX = _mm_set1_epi32(x - 1);
  const int *ptr = arr.data();
  int i = guessIx;
  // unaligned start
  int misalignment = (uintptr_t)(ptr + i) & 15;
  auto arrVec = _mm_loadu_si128((__m128i*)(ptr + i));
  auto cmp = _mm_cmpgt_epi32(arrVec, vecX);
  int mask = _mm_movemask_ps(_mm_castsi128_ps(cmp));
  if (mask)
    return i + __builtin_ctz(mask);
  // continue with aligned part
  i += (16 - misalignment) / 4;
  for (; ; i += 16) {
    auto av0 = _mm_load_si128((__m128i*)(ptr + i));
    auto av1 = _mm_load_si128((__m128i*)(ptr + i + 4));
    auto av2 = _mm_load_si128((__m128i*)(ptr + i + 8));
    auto av3 = _mm_load_si128((__m128i*)(ptr + i + 12));
    auto cmp0 = _mm_cmpgt_epi32(av0, vecX);
    auto cmp1 = _mm_cmpgt_epi32(av1, vecX);
    auto cmp2 = _mm_cmpgt_epi32(av2, vecX);
    auto cmp3 = _mm_cmpgt_epi32(av3, vecX);
    auto cmp = _mm_packs_epi16(_mm_packs_epi32(cmp0, cmp1), _mm_packs_epi32(cmp2, cmp3));
    int mask = _mm_movemask_epi8(cmp);
    if (mask)
      return i + __builtin_ctz(mask);
  }
}

这基本上就是 geza 所描述的内容，但我添加了一个特殊的第一次迭代以便对齐主循环的数据。跨越缓存行边界（或页面边界）的加载速度较慢，这消除了它们。对于小距离（没有足够慢的负载），开销是不值得的，另一方面，对于小距离（小于 4），它应该再次更快。

我也尝试过翻转条件 (linSIMD5)，使用 (a >= b) = !(b > a)，使用非破坏性 AVX 编码，允许合并 vcmpgtd 和负载（减少 µops在融合域中），但 quick-bench 不执行 AVX，所以忽略结果并自己尝试。

底部有一个 AVX2 版本，我没有尝试或对它进行基准测试。它不使用 load/compare-merging 技巧（可能有帮助也可能没有帮助）但很容易适应。

SIMD 线性搜索比展开循环慢

SIMD Linear Search Slower than Unrolled Loop

c++

performance

search

sse

simd