C++で32ビットループカウンタを64ビットに置き換えると、Intel CPUで_mm_popcnt_u64のパフォーマンスが異常になる問題

2024-07-27

この現象は、Sandy Bridge、Ivy Bridge、Haswell世代のIntel CPUで顕著にみられます。具体的には、ループカウンタを unsigned int 型から std::uint64_t 型に変更すると、パフォーマンスが半分近くになるケースがあります。

この問題の原因は、Intel CPUの popcnt 命令の動作と、コンパイラによるレジスタ割り当てに関連しています。

詳細な説明:

Intel CPUの popcnt 命令:
- popcnt 命令は、指定されたレジスタまたはメモリー内のビットが立っている個数をカウントします。
- この命令は、SSE2命令セット拡張の一部として導入されました。
- Sandy Bridge、Ivy Bridge、Haswell世代のCPUでは、popcnt 命令はAVX命令セット拡張の一部である _mm_popcnt_u64 命令として実装されています。
コンパイラによるレジスタ割り当て:
- 多くのコンパイラは、ループ変数などの頻繁にアクセスされる変数に対して、レジスタを割り当てようとします。
- レジスタは、メモリーよりも高速にアクセスできるため、パフォーマンスの向上が期待できます。
- しかし、レジスタは数が限られているため、すべての変数にレジスタを割り当てることはできません。
- レジスタが不足している場合は、コンパイラはメモリーを介して変数にアクセスする必要があり、これがパフォーマンスの低下につながります。
32ビットループカウンタの場合:
- ループカウンタが32ビットの場合、コンパイラは通常、32ビットレジスタに割り当てます。
- 32ビットレジスタは、x86 CPUで汎用的に使用されるため、レジスタ競合が起きにくく、パフォーマンスが安定します。
- しかし、64ビットレジスタは数が少なく、他の変数との競合が発生しやすくなります。
- 特に、Sandy Bridge、Ivy Bridge、Haswell世代のCPUでは、popcnt 命令は64ビットレジスタのみで実行できるため、レジスタ競合が顕著になります。
- このレジスタ競合により、_mm_popcnt_u64 命令のパフォーマンスが著しく低下する可能性があります。

解決策:

ループカウンタを32ビットのままにする:
- これは最も簡単な解決策ですが、64ビットの整数が必要な場合は使用できません。
ループをベクトル化:
- コンパイラは、ベクトル化されたループにおいて、レジスタをより効率的に利用することができます。
- ただし、ループベクトル化は、すべてのループで適用できるわけではありません。
別のビットカウント命令を使用する:
- popcnt 命令以外にも、ビットカウントを行う命令はいくつかあります。
- 例えば、popcnt 命令よりも古い popc 命令は、64ビットレジスタではなく32ビットレジスタで実行できます。
- しかし、popc 命令は popcnt 命令よりも精度が低いため、常に使用できるわけではありません。
アセンブリ言語でコードを書く:
- アセンブリ言語でコードを書くことで、レジスタの使用を完全に制御することができます。
- しかし、これは高度な技術であり、すべてのプログラマーが習得しているわけではありません。

C++でループカウンタを32ビットから64ビットに変更すると、Intel CPUで_mm_popcnt_u64のパフォーマンスが低下する可能性があります。

この問題を解決するには、ループカウンタを32ビットのままにする、ループをベクトル化する、別のビットカウント命令を使用する、アセンブリ言語でコードを書くなどの方法があります。

最適な解決策は、具体的な状況によって異なります。

[Replacing a 32-bit loop counter with 64-bit introduces crazy performance deviations with _mm_popcnt_u64 on Intel CPUs](https://stackoverflow.

#include <iostream>
#include <immintrin.h>

using namespace std;

int main() {
  // 32-bit loop counter
  for (unsigned int i = 0; i < 10000000; ++i) {
    _mm_popcnt_u64(_mm_set_epi64x(i, i));
  }

  // 64-bit loop counter
  for (std::uint64_t i = 0; i < 10000000; ++i) {
    _mm_popcnt_u64(_mm_set_epi64x(i, i));
  }

  return 0;
}

This code first performs the _mm_popcnt_u64 operation with a 32-bit loop counter, and then again with a 64-bit loop counter. As explained in the previous response, the performance of the second loop is significantly worse than the first loop.

Here is an explanation of the code:

The #include <iostream> statement includes the iostream header file, which is needed for input and output operations.
The #include <immintrin.h> statement includes the immintrin.h header file, which is needed for using SSE intrinsics.
The using namespace std; statement declares that all identifiers from the std namespace will be used without the std:: prefix.
The main() function is the entry point of the program.
The for (unsigned int i = 0; i < 10000000; ++i) loop iterates over 10 million values of the i variable.
The _mm_popcnt_u64(_mm_set_epi64x(i, i)) statement calls the _mm_popcnt_u64 intrinsic to count the number of set bits in the 64-bit value _mm_set_epi64x(i, i).
The std::uint64_t type is used for the loop counter in the second loop because unsigned int is a 32-bit type and cannot represent values larger than 4,294,967,295.

C++でビットカウントを行う代替方法

ループベクトル化

コンパイラは、ベクトル化されたループにおいて、レジスタをより効率的に利用することができます。ベクトル化により、複数のデータに対して同時にビットカウント処理を行うことができ、レジスタ競合を軽減することができます。

以下のコードは、__popcnt64 関数を使用してループをベクトル化する方法を示しています。

#include <immintrin.h>
#include <iostream>

using namespace std;

int main() {
  const int N = 10000000;
  __m256i v[N / 8];

  for (int i = 0; i < N; i += 8) {
    v[i / 8] = _mm256_set_epi64x(i, i + 1, i + 2, i + 3, i + 4, i + 5, i + 6, i + 7);
  }

  int count = 0;
  for (int i = 0; i < N / 8; ++i) {
    count += _mm256_reduce_add(_mm256_popcnt_epi64(v[i]));
  }

  cout << count << endl;

  return 0;
}

popcnt 命令以外にも、ビットカウントを行う命令はいくつかあります。例えば、popc 命令は popcnt 命令よりも古い命令ですが、64ビットレジスタではなく32ビットレジスタで実行できます。

以下のコードは、popc 関数を使用してビットカウントを行う方法を示しています。

#include <iostream>

using namespace std;

int popc(unsigned int n) {
  int count = 0;
  while (n) {
    count += n & 1;
    n >>= 1;
  }
  return count;
}

int main() {
  int count = 0;
  for (unsigned int i = 0; i < 10000000; ++i) {
    count += popc(i);
  }

  cout << count << endl;

  return 0;
}

ハードウェアビットカウント機能を使用する

最近のIntel CPUには、SSE4.2命令セット拡張の一部として popcnt 命令のハードウェア実装が導入されています。ハードウェア実装は、ソフトウェア実装よりも高速にビットカウントを実行することができます。

#include <immintrin.h>
#include <iostream>

using namespace std;

int main() {
  int count = 0;
  for (unsigned int i = 0; i < 10000000; ++i) {
    count += _popcnt(_mm_set_epi64x(i, i));
  }

  cout << count << endl;

  return 0;
}