performance - 用于二进制相关的SSE向量的Popcount吗？

Question

我有一个简单的二进制相关方法，它比xcc和％25击败表查找和Hakmem位旋转方法要比GCC的__builtin_popcount好(我认为启用SSE4时它映射到popcnt指令。)

这是简化得多的代码:

int correlation(uint64_t *v1, uint64_t *v2, int size64) {
  __m128i* a = reinterpret_cast<__m128i*>(v1);
  __m128i* b = reinterpret_cast<__m128i*>(v2);
  int count = 0;
  for (int j = 0; j < size64 / 2; ++j, ++a, ++b) {
    union { __m128i s; uint64_t b[2]} x;
    x.s = _mm_xor_si128(*a, *b);
    count += _mm_popcnt_u64(x.b[0]) +_mm_popcnt_u64(x.b[1]);
  }
  return count;
}

我尝试展开循环，但我认为GCC已经自动执行此操作，因此最终获得了相同的性能。您是否认为在不使代码变得过于复杂的情况下进一步提高性能？假设v1和v2大小相同且大小相等。

我对它的当前性能感到满意，但我只是想知道它是否可以进一步改进。

谢谢。

编辑:修复了union中的一个错误，事实证明此错误使此版本比内置__builtin_popcount快，无论如何我再次修改了代码，它再次比内置快(15％)，但我认为这不值得为此花一些时间。感谢您的所有评论和建议。

for (int j = 0; j < size64 / 4; ++j, a+=2, b+=2) {
  __m128i x0 = _mm_xor_si128(_mm_load_si128(a), _mm_load_si128(b));
  count += _mm_popcnt_u64(_mm_extract_epi64(x0, 0))
        +_mm_popcnt_u64(_mm_extract_epi64(x0, 1));
  __m128i x1 = _mm_xor_si128(_mm_load_si128(a + 1), _mm_load_si128(b + 1));
  count += _mm_popcnt_u64(_mm_extract_epi64(x1, 0))
        +_mm_popcnt_u64(_mm_extract_epi64(x1, 1));
}

第二次编辑:事实证明，内置方法是最快的方法。特别是-funroll-loops和
-fprefetch-loop-arrays args。像这样的东西:

for (int j = 0; j < size64; ++j) {
  count += __builtin_popcountll(a[j] ^ b[j]);
}

第三编辑:

这是一个有趣的SSE3并行4位查找算法。想法来自 Wojciech Muła，实现来自Marat Dukhan的 answer。感谢@Apriori提醒我该算法。下面是算法的核心，它非常聪明，基本上是使用SSE寄存器作为16路查找表，使用低位半字节作为选择表单元的索引，以字节为单位对字节进行计数。然后对计数求和。

static inline __m128i hamming128(__m128i a, __m128i b) {
  static const __m128i popcount_mask = _mm_set1_epi8(0x0F);
  static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
  const __m128i x = _mm_xor_si128(a, b);
  const __m128i pcnt0 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(x, popcount_mask));
  const __m128i pcnt1 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(_mm_srli_epi16(x, 4), popcount_mask));
  return _mm_add_epi8(pcnt0, pcnt1);
}

在我的测试中，这个版本是同等的；与使用硬件popcount相比，在较小的输入上稍快一些，在较大的输入上稍慢一些。我认为，如果在AVX中实现，它应该会真正发光。但是我没有时间这样做，如果有人愿意的话，将很乐意听到他们的结果。

Answer 1

问题是popcnt(__builtin_popcnt在intel CPU上编译成的代码)在整数寄存器上运行。这导致编译器发出指令以在SSE和整数寄存器之间移动数据。我对非SSE版本的速度更快并不感到惊讶，因为在矢量寄存器和整数寄存器之间移动数据的能力非常有限/缓慢。

uint64_t count_set_bits(const uint64_t *a, const uint64_t *b, size_t count)
{
    uint64_t sum = 0;
    for(size_t i = 0; i < count; i++) {
        sum += popcnt(a[i] ^ b[i]);
    }
    return sum;
}

这大约运行。小数据集(适合高速缓存)中的每个循环2.36个时钟。我认为它运行缓慢是因为 sum上的“较长”依赖项链限制了CPU处理更多杂乱无章的事物的能力。我们可以通过手动对循环进行流水处理来改善它:

uint64_t count_set_bits_2(const uint64_t *a, const uint64_t *b, size_t count)
{
    uint64_t sum = 0, sum2 = 0;

    for(size_t i = 0; i < count; i+=2) {
        sum  += popcnt(a[i  ] ^ b[i  ]);
        sum2 += popcnt(a[i+1] ^ b[i+1]);
    }
    return sum + sum2;
}

每个项目的运行时间为1.75个时钟。我的CPU是Sandy Bridge型号(在2.4Ghz下固定为i7-2820QM)。

四向流水线怎么样？那是每件物品1.65个时钟。那八路呢？每件1.57个时钟。我们可以得出每个项目的运行时间为 (1.5n + 0.5) / n，其中n是循环中的管道数量。我应该指出，由于某种原因，当数据集增长时，8向流水线处理的效果比其他方法差，我不知道为什么。生成的代码看起来还不错。

现在，如果您仔细查看的话，每个项目有一个 xor，一个 add，一个 popcnt和一个 mov指令。每个循环也有一个lea指令(还有一个分支和减量，我忽略了，因为它们几乎是免费的)。

$LL3@count_set_:
; Line 50
    mov rcx, QWORD PTR [r10+rax-8]
    lea rax, QWORD PTR [rax+32]
    xor rcx, QWORD PTR [rax-40]
    popcnt  rcx, rcx
    add r9, rcx
; Line 51
    mov rcx, QWORD PTR [r10+rax-32]
    xor rcx, QWORD PTR [rax-32]
    popcnt  rcx, rcx
    add r11, rcx
; Line 52
    mov rcx, QWORD PTR [r10+rax-24]
    xor rcx, QWORD PTR [rax-24]
    popcnt  rcx, rcx
    add rbx, rcx
; Line 53
    mov rcx, QWORD PTR [r10+rax-16]
    xor rcx, QWORD PTR [rax-16]
    popcnt  rcx, rcx
    add rdi, rcx
    dec rdx
    jne SHORT $LL3@count_set_

您可以使用 Agner Fog's optimization manual来检查 lea整个时钟周期是半个时钟周期，而 mov/ xor/ popcnt/ add组合显然是1.5个时钟周期，尽管我不太清楚为什么会这样。

不幸的是，我认为我们被困在这里。 PEXTRQ指令通常用于将数据从向量寄存器移至整数寄存器，我们可以在一个时钟周期内将其与一条popcnt指令整齐地拟合在一起。添加一条整数 add指令，我们的流水线至少要长1.33个周期，并且我们仍然需要在其中某处添加向量加载和异或...如果intel提供了一次在向量和整数寄存器之间移动多个寄存器的指令，那将是一个不同的故事。

我手头没有AVX2 cpu(在256位向量寄存器上进行异或运算是AVX2的功能)，但是我的向量化加载实现在数据量较小的情况下执行效果很差，每项至少达到1.97个时钟周期。

供引用，这些是我的基准测试:

“管道2”，“管道4”和“管道8”是上述代码的2、4和8路流水线版本。 “sse负载”的不良显示似乎是 lzcnt/tzcnt/popcnt false dependency bug的一种表现，它通过使用相同的寄存器作为输入和输出来避免了gcc。以下是“sse负载2”:

uint64_t count_set_bits_4sse_load(const uint64_t *a, const uint64_t *b, size_t count)
{
    uint64_t sum1 = 0, sum2 = 0;

    for(size_t i = 0; i < count; i+=4) {
        __m128i tmp = _mm_xor_si128(
                    _mm_load_si128(reinterpret_cast<const __m128i*>(a + i)),
                    _mm_load_si128(reinterpret_cast<const __m128i*>(b + i)));
        sum1 += popcnt(_mm_extract_epi64(tmp, 0));
        sum2 += popcnt(_mm_extract_epi64(tmp, 1));
        tmp = _mm_xor_si128(
                    _mm_load_si128(reinterpret_cast<const __m128i*>(a + i+2)),
                    _mm_load_si128(reinterpret_cast<const __m128i*>(b + i+2)));
        sum1 += popcnt(_mm_extract_epi64(tmp, 0));
        sum2 += popcnt(_mm_extract_epi64(tmp, 1));
    }

    return sum1 + sum2;
}