22

我正在尝试编写非常有效的汉明距离代码。受Wojciech Muła极其聪明的 SSE3 popcount实现的启发，我编写了一个 AVX2 等效解决方案，这次使用 256 位寄存器。 l 基于所涉及操作的双倍并行度，我预计至少有 30%-40% 的改进，但令我惊讶的是，AVX2 代码慢了一点（大约 2%）！

有人可以告诉我为什么我没有获得预期的性能提升的可能原因吗？

展开，两个 64 字节块的 SSE3 汉明距离：

INT32 SSE_PopCount(const UINT32* __restrict pA, const UINT32* __restrict pB) {

   __m128i paccum  = _mm_setzero_si128();

   __m128i a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA));
   __m128i b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB));
   __m128i err     = _mm_xor_si128   (a, b);
   __m128i lo      = _mm_and_si128   (err, low_mask);
   __m128i hi      = _mm_srli_epi16  (err, 4);
           hi      = _mm_and_si128   (hi, low_mask);
   __m128i popcnt1 = _mm_shuffle_epi8(lookup, lo);
   __m128i popcnt2 = _mm_shuffle_epi8(lookup, hi);
           paccum  = _mm_add_epi8(paccum, popcnt1);
           paccum  = _mm_add_epi8(paccum, popcnt2);

           a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 4));
           b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 4));
           err     = _mm_xor_si128   (a, b);
           lo      = _mm_and_si128   (err, low_mask);
           hi      = _mm_srli_epi16  (err, 4);
           hi      = _mm_and_si128   (hi, low_mask);
           popcnt1 = _mm_shuffle_epi8(lookup, lo);
           popcnt2 = _mm_shuffle_epi8(lookup, hi);
           paccum  = _mm_add_epi8(paccum, popcnt1);
           paccum  = _mm_add_epi8(paccum, popcnt2);

           a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 8));
           b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 8));
           err     = _mm_xor_si128   (a, b);
           lo      = _mm_and_si128   (err, low_mask);
           hi      = _mm_srli_epi16  (err, 4);
           hi      = _mm_and_si128   (hi, low_mask);
           popcnt1 = _mm_shuffle_epi8(lookup, lo);
           popcnt2 = _mm_shuffle_epi8(lookup, hi);
           paccum  = _mm_add_epi8(paccum, popcnt1);
           paccum  = _mm_add_epi8(paccum, popcnt2);

           a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 12));
           b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 12));
           err     = _mm_xor_si128   (a, b);
           lo      = _mm_and_si128   (err, low_mask);
           hi      = _mm_srli_epi16  (err, 4);
           hi      = _mm_and_si128   (hi, low_mask);
           popcnt1 = _mm_shuffle_epi8(lookup, lo);
           popcnt2 = _mm_shuffle_epi8(lookup, hi);
           paccum  = _mm_add_epi8(paccum, popcnt1);
           paccum  = _mm_add_epi8(paccum, popcnt2);

           paccum  = _mm_sad_epu8(paccum, _mm_setzero_si128());
   UINT64  result =  paccum.m128i_u64[0] + paccum.m128i_u64[1];
   return (INT32)result;
}

使用 AVX 的 256 位寄存器的未展开等效版本：

INT32 AVX_PopCount(const UINT32* __restrict pA, const UINT32* __restrict pB) {
   __m256i paccum =  _mm256_setzero_si256();

   __m256i a       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pA));
   __m256i b       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pB));
   __m256i err     = _mm256_xor_si256   (a, b);
   __m256i lo      = _mm256_and_si256   (err, low_mask256);
   __m256i hi      = _mm256_srli_epi16  (err, 4);
           hi      = _mm256_and_si256   (hi, low_mask256);
   __m256i popcnt1 = _mm256_shuffle_epi8(lookup256, lo);
   __m256i popcnt2 = _mm256_shuffle_epi8(lookup256, hi);
           paccum  = _mm256_add_epi8(paccum, popcnt1);
           paccum  = _mm256_add_epi8(paccum, popcnt2);

           a       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pA + 8));
           b       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pB + 8));
           err     = _mm256_xor_si256   (a, b);
           lo      = _mm256_and_si256   (err, low_mask256);
           hi      = _mm256_srli_epi16  (err, 4);
           hi      = _mm256_and_si256   (hi, low_mask256);
           popcnt1 = _mm256_shuffle_epi8(lookup256, lo);
           popcnt2 = _mm256_shuffle_epi8(lookup256, hi);
           paccum  = _mm256_add_epi8(paccum, popcnt1);
           paccum  = _mm256_add_epi8(paccum, popcnt2);

           paccum  = _mm256_sad_epu8(paccum, _mm256_setzero_si256());
           UINT64  result =  paccum.m256i_i64[0] + paccum.m256i_u64[1] + paccum.m256i_i64[2] + paccum.m256i_i64[3];
   return (INT32)result;
}

我已经验证了编译器发出的输出汇编代码，它看起来不错，预期将内在指令直接转换为机器指令。我唯一注意到的是，在 AVX2 版本上，累积 4 个四字的人口计数的最后一行，它生成的代码比 SSE3 版本更复杂（只需累积 2 个四字即可获得人口计数），但是我仍然希望吞吐量更快。

为四字累加生成的 AVX2 代码

vextractf128 xmm0, ymm2, 1
psrldq  xmm0, 8
movd    ecx, xmm2
movd    eax, xmm0
vextractf128 xmm0, ymm2, 1
psrldq  xmm2, 8
add eax, ecx
movd    ecx, xmm0
add eax, ecx
movd    ecx, xmm2
add eax, ecx

为四字累加生成的 SSE3 代码

movd    ecx, xmm2
psrldq  xmm2, 8
movd    eax, xmm2
add eax, ecx

我的测试程序调用每个例程 100 万次，使用不同的输入值，但重用两个静态缓冲区来保存pA和pB参数的数据。在我对 CPU 架构的有限理解中，这个局部性（一遍又一遍地重用相同的内存缓冲区）应该很好地预热 CPU 缓存，并且不受内存带宽问题的束缚，但除了可能的内存带宽之外，我不明白为什么没有性能改进。

测试例程

int _tmain(int argc, _TCHAR* argv[]) {

   lookup = _mm_setr_epi8(
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4
    );
   low_mask = _mm_set1_epi8(0xf);

   lookup256 = _mm256_setr_epi8(
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4,
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4
    );

   low_mask256 = _mm256_set1_epi8(0xf);


   std::default_random_engine generator;
   generator.seed(37);
   std::uniform_int_distribution<UINT32> distribution(0, ULONG_MAX);
   auto dice = std::bind( distribution, generator);


   UINT32 a[16];
   UINT32 b[16];

   int count;
   count = 0;
   {
      cout << "AVX PopCount\r\n";
      boost::timer::auto_cpu_timer t;
      for( int i = 0; i < 1000000; i++ ) {
         for( int j = 0; j < 16; j++ ) {
            a[j] = dice();
            b[j] = dice();
         }
         count+= AVX_PopCount(a, b);
      }
   }

   cout << count << "\r\n";


   std::default_random_engine generator2;
   generator2.seed(37);
   std::uniform_int_distribution<UINT32> distribution2(0, ULONG_MAX);
   auto dice2 = std::bind( distribution2, generator2);


   count = 0;
   {
      cout << "SSE PopCount\r\n";
      boost::timer::auto_cpu_timer t;
      for( int i = 0; i < 1000000; i++ ) {
         for( int j = 0; j < 16; j++ ) {
            a[j] = dice2();
            b[j] = dice2();
         }
         count+= SSE_PopCount(a, b);
      }
   }
   cout << count << "\r\n";

   getch();
   return 0;
}

测试机器是 Intel Corei7 4790，我使用的是 Visual Studio 2012 Pro。

4

2 回答 2

17

除了注释中的小问题（为 编译/arch:AVX）之外，您的主要问题是在每次迭代时生成随机输入数组。这是您的瓶颈，因此您的测试无法有效地评估您的方法。注意 - 我没有使用 boost，但GetTickCount可以用于此目的。只考虑：

int count;
count = 0;
{
    cout << "AVX PopCount\r\n";
    unsigned int Tick = GetTickCount();
    for (int i = 0; i < 1000000; i++) {
        for (int j = 0; j < 16; j++) {
            a[j] = dice();
            b[j] = dice();
        }
        count += AVX_PopCount(a, b);
    }
    Tick = GetTickCount() - Tick;
    cout << Tick << "\r\n";
}

产生输出：

AVX PopCount
2309
256002470

所以需要 2309 毫秒才能完成……但是如果我们完全摆脱您的 AVX 例程会发生什么？只需制作输入数组：

int count;
count = 0;
{
    cout << "Just making arrays...\r\n";
    unsigned int Tick = GetTickCount();
    for (int i = 0; i < 1000000; i++) {
        for (int j = 0; j < 16; j++) {
            a[j] = dice();
            b[j] = dice();
        }           
    }
    Tick = GetTickCount() - Tick;
    cout << Tick << "\r\n";
}

产生输出：

只是制作数组...
2246

那个怎么样。这并不奇怪，真的，因为您生成 32 个随机数，这可能非常昂贵，然后只执行一些相当快的整数数学运算和洗牌。

所以...

现在让我们再增加 100 次迭代，让随机生成器脱离紧密循环。在此处禁用优化的编译将按预期运行您的代码，并且不会丢弃“无用”的迭代 - 大概我们在这里关心的代码已经（手动）优化！

    for (int j = 0; j < 16; j++) {
        a[j] = dice();
        b[j] = dice();
    }

    int count;
    count = 0;
    {
        cout << "AVX PopCount\r\n";
        unsigned int Tick = GetTickCount();
        for (int i = 0; i < 100000000; i++) {           
            count += AVX_PopCount(a, b);
        }
        Tick = GetTickCount() - Tick;
        cout << Tick << "\r\n";
    }

    cout << count << "\r\n";

    count = 0;
    {
        cout << "SSE PopCount\r\n";
        unsigned int Tick = GetTickCount();
        for (int i = 0; i < 100000000; i++) {
            count += SSE_PopCount(a, b);
        }
        Tick = GetTickCount() - Tick;
        cout << Tick << "\r\n";
    }
    cout << count << "\r\n";

产生输出：

AVX PopCount
3744
730196224
SSE PopCount
5616
730196224

所以恭喜 - 你可以拍拍自己的背，你的 AVX 例程确实比 SSE 例程快大约三分之一（在这里在 Haswell i7 上测试）。教训是要确保你实际上是在分析你认为你正在分析的东西！

于 2015-07-17T13:04:06.103 回答
12

您应该考虑使用通常的_mm_popcnt_u64指令，而不是在 SSE 或 AVX 中破解它。我彻底测试了所有 popcounting 方法，包括 SSE 和 AVX 版本（这最终导致了我或多或少著名的关于 popcount的问题）。_mm_popcnt_u64明显优于 SSE 和 AVX，尤其是当您使用可以防止在我的问题中发现的 Intel popcount 错误的编译器时。没有这个错误，我的 Haswell 能够弹出 26 GB/s 几乎达到总线带宽。

更快的原因_mm_popcnt_u64仅仅是因为它一次弹出 64 位（因此已经是 AVX 版本的 1/4），同时只需要一个廉价的处理器指令。它只花费几个周期（延迟 3，英特尔的吞吐量 1）。即使您使用的每条 AVX 指令只需要一个周期，由于 popcounting 256 位所需的指令数量过多，您仍然会得到更差的结果。

试试这个，应该是最快的：

int popcount256(const uint64_t* u){ 
    return _mm_popcnt_u64(u[0]);
         + _mm_popcnt_u64(u[1]);
         + _mm_popcnt_u64(u[2]);
         + _mm_popcnt_u64(u[3]);
}

我知道这并不能回答您为什么 AVX 较慢的核心问题，但是由于您的最终目标是快速 popcount，因此 AVX <-> SSE 比较是无关紧要的，因为两者都不如内置的 popcount。

于 2015-07-17T13:18:03.887 回答