这个功能是英特尔SIMD的理想选择吗？

Question

我正在尝试优化以下函数(简化了一下,但它是我的程序花了很多时间的循环):

int f(int len, unsigned char *p) {
  int i = 0;
  while (i < len && p[i] >= 32 && p[i] <= 127) {
      i++;
  }
  return i;
}

我认为可以使用向量指令进行优化,但是从一些研究来看,SSE似乎不适合在字节级工作.该程序仅针对OSX上的64位Intel CPU.有没有一个巧妙的比特伎俩,我没有看到它会让我一次只能处理64位？llvm与-O3没有做任何聪明的优化.

更新:

SIMD代码在我的基准测试中通常是最快的(取决于输入的大小),但由于某种原因,使用SIMD的应用程序总体上比使用简单的代码或比特笨拙的技巧更慢.对于上下文,应用程序在终端仿真器的输入流中查找ASCII字符串的子序列的长度.ASCII字符串得到特殊的"快速路径"处理.我只能将一个答案标记为正确,但两者都很棒.我确实做了一个改进的小改进,通过这样做删除if语句:

        while (i < len - 8) {
            uint64_t bytes = *(uint64_t *)(p + i);
            uint64_t middleBits = bytes & 0x6060606060606060;
            uint64_t highBits = bytes & 0x8080808080808080;
            middleBits |= (middleBits >> 1);
            middleBits &= ~(highBits >> 2);
            if ((middleBits & 0x2020202020202020) != 0x2020202020202020) {
                break;
            }
            i += 8;
        }

Answer 1

我不确定这是否是您问题的答案,也不是这会大大加快您的代码速度,但这是一个想法.由于32等于2 ^ 5,如果一个字节在32和128之间,它必须设置第6或第7位并清除第8位.您可以将测试扩展到64位整数,为我提供如下代码:

// check whether each byte is in range 32 - 128.
unsigned bytesInRange(unsigned long long x) {
    unsigned long long y, z;
    if ((x & 0x8080808080808080LL) != 0) return(0);
    y = x >> 1;
    z = x | y;
    if ((z & 0x2020202020202020LL) == 0x2020202020202020LL) return(1);
    return(0);
}

int f(int len, unsigned char *p) {
  int i = 0;
  int len8 = len / 8;
  unsigned long long *q = (unsigned long long *) p;
  while (i < len8 && bytesInRange(q[i])) {
    i++;
  }

  i = i * 8;
  while (i < len && p[i] >= 32 && p[i] <= 127) {
    i++;
  }
  return i;
}

对于需要对齐的架构,需要在第一个循环之前进行检查.

Answer 2

您可以使用 _mm_cmplt_epi8 和 _mm_cmpgt_epi8 （msvc 内在函数）对比较进行向量化。

然后，您可以对比较结果进行 AND 运算的结果使用 movemask。如果 movemask 的结果是 0xFFFF，则所有比较都通过。否则，您需要运行尾循环来找出测试失败的正确位置。您可以从掩码中找出这一点，但根据“len”的值，可能不值得付出努力。

如果“len”不是 16 的倍数，则还需要尾部的原始非矢量化循环。它可能会更快，也可能不会更快——您需要对其进行分析才能确定。

废弃它 - 比较对有符号值进行操作，但它不起作用。

下面的工作版本。

union UmmU8 {
    __m128i mm_;
    struct {
        unsigned char u8_;
    };
};

int f(int len, unsigned char *p) {
    int i = 0;
    __m128i A;
    __m128i B;
    __m128i C;
    UmmU8* pu = (UmmU8*)p;    
    int const len16 = len / 16;
    while (i < len16) {
        A = pu[i].mm_;
        B = _mm_slli_epi32(A, 1);
        C = _mm_slli_epi32(A, 2);
        B = _mm_or_si128(B, C);
        A = _mm_andnot_si128(A, B);

        int mask = _mm_movemask_epi8(A);
        if (mask == 0xFFFF) {
            ++i;
        }
        else {
            if (mask == 0) {
                return i * 16;
            }
            break;
        }
    }
    i *= 16;
    while (i < len && p[i] >= 32 && p[i] <= 127) {
        i++;
    }
    return i;
}

由于我的 PC 上没有 64 位操作系统，因此我无法进行适当的性能测试。然而，分析运行给出了：

• 朴素循环：30.44
• 64 位整数：15.22（在 32 位操作系统上）
• 上证指数：5.21

所以 SSE 版本比朴素循环版本快很多。我预计 64 位版本在 64 位系统上的性能会明显更好 - SSE 和 64 位版本之间可能没有什么区别。