更新：コードを読んでください、それは1つのintのビットを数えることではありません
いくつかの巧妙なアセンブラを使用して、次のコードのパフォーマンスを向上させることは可能ですか？
uint bit_counter[64];
void Count(uint64 bits) {
bit_counter[0] += (bits >> 0) & 1;
bit_counter[1] += (bits >> 1) & 1;
// ..
bit_counter[63] += (bits >> 63) & 1;
}
Count私のアルゴリズムの最も内側のループにあります。
更新： アーキテクチャ：x86-64、Sandy Bridge、SSE4.2、AVX1、およびそれ以前の技術を使用できますが、AVX2またはBMI1/2は使用できません。
bits変数にはほぼランダムなビットがあります（半分のゼロと半分の1に近い）
反復ごとに4つの要素をインクリメントして、SSEでそれを試してみることができます。
警告：テストされていないコードが続きます...
#include <stdint.h>
#include <emmintrin.h>
uint32_t bit_counter[64] __attribute__ ((aligned(16)));
// make sure bit_counter array is 16 byte aligned for SSE
void Count_SSE(uint64 bits)
{
const __m128i inc_table[16] = {
_mm_set_epi32(0, 0, 0, 0),
_mm_set_epi32(0, 0, 0, 1),
_mm_set_epi32(0, 0, 1, 0),
_mm_set_epi32(0, 0, 1, 1),
_mm_set_epi32(0, 1, 0, 0),
_mm_set_epi32(0, 1, 0, 1),
_mm_set_epi32(0, 1, 1, 0),
_mm_set_epi32(0, 1, 1, 1),
_mm_set_epi32(1, 0, 0, 0),
_mm_set_epi32(1, 0, 0, 1),
_mm_set_epi32(1, 0, 1, 0),
_mm_set_epi32(1, 0, 1, 1),
_mm_set_epi32(1, 1, 0, 0),
_mm_set_epi32(1, 1, 0, 1),
_mm_set_epi32(1, 1, 1, 0),
_mm_set_epi32(1, 1, 1, 1)
};
for (int i = 0; i < 64; i += 4)
{
__m128i vbit_counter = _mm_load_si128(&bit_counter[i]);
// load 4 ints from bit_counter
int index = (bits >> i) & 15; // get next 4 bits
__m128i vinc = inc_table[index]; // look up 4 increments from LUT
vbit_counter = _mm_add_epi32(vbit_counter, vinc);
// increment 4 elements of bit_counter
_mm_store_si128(&bit_counter[i], vbit_counter);
} // store 4 updated ints
}
仕組み：基本的に、ここで行っているのは、元のループをベクトル化して、ループの反復ごとに1ではなく4ビットを処理することです。したがって、64ではなく16のループ反復があります。反復ごとに、から4ビットをロードしbits、を使用します。それらは、現在の4ビットの4つの増分のすべての可能な組み合わせを含むLUTへのインデックスとして使用されます。次に、これらの4つの増分をbit_counterの現在の4つの要素に追加します。
ロードとストアおよび追加の数は4分の1に削減されますが、これはLUTロードおよびその他のハウスキーピングによっていくらか相殺されます。ただし、2倍の速度が得られる場合があります。あなたがそれを試してみることにした場合、私は結果を知りたいと思います。
たぶん、8ビット間隔で8を取り、カウント用に8つのuint64を保持することで、一度に8を実行できます。ただし、これは単一のカウンターごとに1バイトしかないため、countこれらのuint64を解凍する前に、255回の呼び出ししか蓄積できません。
ビットをいじるハックを見てください
編集「ビット位置バケットの蓄積」（bit_counter[]）これはvalarrays+マスキングの良いケースかもしれないと私は感じています。ただし、これはコーディング+テスト+プロファイリングのかなりの部分になります。本当に興味があれば教えてください。
最近では、タイタプル（TR1、ブースト、またはC ++ 11）を使用してvalarrayの動作に非常に近づくことができます。読みやすく、コンパイルも遅くなる気がします。
どうやらこれは「垂直カウンター」で素早く行うことができます。@steikeによるビットトリック（アーカイブ）の現在は廃止されたページから：
ビットを水平方向に読み取る通常の整数配列について考えてみます。
msb<-->lsb x[0] 00000010 = 2 x[1] 00000001 = 1 x[2] 00000101 = 5垂直カウンターは、名前が示すように、垂直に数字を格納します。つまり、kビットカウンタはkワードにわたって格納され、各ワードに1ビットが含まれます。
x[0] 00000110 lsb ↑ x[1] 00000001 | x[2] 00000100 | x[3] 00000000 | x[4] 00000000 msb ↓ 512このように格納された数値を使用して、ビット演算を使用して、それらのサブセットを一度にインクリメントできます。
インクリメントするカウンターに対応する位置に1ビットのビットマップを作成し、LSBから配列をループして、ビットを更新します。1つの加算からの「キャリー」は、配列の次の要素の入力になります。
input sum -------------------------------------------------------------------------------- A B C S 0 0 0 0 0 1 0 1 sum = a ^ b 1 0 0 1 carry = a & b 1 1 1 1 carry = input; long *p = buffer; while (carry) { a = *p; b = carry; *p++ = a ^ b; carry = a & b; }64ビットワードの場合、ループは平均6〜7回実行されます。反復回数は、キャリーの最長チェーンによって決まります。
このように関数を展開できます。おそらく、コンパイラが実行できるよりも高速です。
// rax as 64 bit input
xor rcx, rcx //clear addent
add rax, rax //Copy 63th bit to carry flag
adc dword ptr [@bit_counter + 63 * 4], ecx //Add carry bit to counter[64]
add rax, rax //Copy 62th bit to carry flag
adc dword ptr [@bit_counter + 62 * 4], ecx //Add carry bit to counter[63]
add rax, rax //Copy 62th bit to carry flag
adc dword ptr [@bit_counter + 61 * 4], ecx //Add carry bit to counter[62]
// ...
add rax, rax //Copy 1th bit to carry flag
adc dword ptr [@bit_counter + 1 * 4], ecx //Add carry bit to counter[1]
add rax, rax //Copy 0th bit to carry flag
adc dword ptr [@bit_counter], ecx //Add carry bit to counter[0]
編集：
次のように、2倍の増分で試すこともできます。
// rax as 64 bit input
xor rcx, rcx //clear addent
//
add rax, rax //Copy 63th bit to carry flag
rcl rcx, 33 //Mov carry to 32th bit as 0bit of second uint
add rax, rax //Copy 62th bit to carry flag
adc qword ptr [@bit_counter + 62 * 8], rcx //Add rcx to 63th and 62th counters
add rax, rax //Copy 61th bit to carry flag
rcl rcx, 33 //Mov carry to 32th bit as 0bit of second uint
add rax, rax //Copy 60th bit to carry flag
adc qword ptr [@bit_counter + 60 * 8], rcx //Add rcx to 61th and 60th counters
//...
それぞれ異なるサイズのカウンターのセットを使用できます。最初に3つの値を2ビットカウンターに蓄積し、次にそれらを解凍して4ビットカウンターを更新します。15個の値の準備ができたら、バイトサイズのカウンターに解凍し、255個の値の後でbit_counter[]を更新します。
この作業はすべて、128ビットのSSEレジスタで並行して実行できます。最近のプロセッサでは、1ビットを2にアンパックするために必要な命令は1つだけです。PCLMULQDQ命令を使用して、ソースクワッドワードをそれ自体に乗算するだけです。これにより、ソースビットがゼロにインターリーブされます。同じトリックが2ビットを4にアンパックするのに役立つ場合があります。また、4ビットと8ビットのアンパックは、シャッフル、アンパック、および単純な論理演算を使用して実行できます。
平均的なパフォーマンスは良好のようですが、追加のカウンターと非常に多くのアセンブリコードの価格は120バイトです。
各オフセット（16の可能性）で各ニブル（16の可能性）が発生する頻度を数えると、結果を簡単に合計できます。そして、それらの256の合計は簡単に保持されます。
unsigned long nibble_count[16][16]; // E.g. 0x000700B0 corresponds to [4][7] and [2][B]
unsigned long bitcount[64];
void CountNibbles(uint64 bits) {
// Count nibbles
for (int i = 0; i != 16; ++i) {
nibble_count[i][bits&0xf]++;
bits >>= 4;
}
}
void SumNibbles() {
for (int i = 0; i != 16; ++i) {
for (int nibble = 0; nibble != 16; ++nibble) {
for(int bitpos = 0; bitpos != 3; ++bitpos) {
if (nibble & (1<<bitpos)) {
bitcount[i*4 + bitpos] += nibble_count[i][nibble];
}
}
}
}
}
一般的にこれに答える方法はありません。それはすべて、コンパイラと基盤となるアーキテクチャに依存します。知る唯一の本当の方法は、さまざまな解決策を試し、測定することです。（たとえば、一部のマシンでは、シフトは非常に高価になる可能性があります。他のマシンでは、そうではありません。）まず、次のようなものを使用します。
uint64_t mask = 1;
int index = 0;
while ( mask != 0 ) {
if ( (bits & mask) != 0 ) {
++ bit_counter[index];
}
++ index;
mask <<= 1;
}
ループを完全に展開すると、パフォーマンスが向上する可能性があります。アーキテクチャに応じて、を次のように置き換えifます。
bit_counter[index] += ((bits & mask) != 0);
良いかもしれません。さらに悪いことに...事前に知ることは不可能です。一部のマシンでは、体系的に下位ビットにシフトして、実行しているようにマスキングするのが最適な場合もあります。
一部の最適化は、一般的なデータがどのように見えるかにも依存します。ほとんどのワードに1ビットまたは2ビットしか設定されていない場合は、一度に1バイト、または一度に4ビットをテストし、すべてゼロであるものを完全にスキップすることで得られる可能性があります。
これはかなり速いです：
void count(uint_fast64_t bits){
uint_fast64_t i64=ffs64(bits);
while(i64){
bit_counter[i64-1]++;
bits=bits & 0xFFFFFFFFFFFFFFFF << i64;
i64=ffs64(bits);
}
}
64ビットのffsを高速に実装する必要があります。ほとんどのコンパイラとCPUの場合、これは単一の命令です。ループはワード内のビットごとに1回実行されるため、bits=0非常に高速になり、64ビットのビットは1低速になります。
私はこれをGCCを使用して64ビットUbuntuでテストしましたが、次のものと同じデータ出力が生成されます。
void Count(uint64 bits) {
bit_counter[0] += (bits >> 0) & 1;
bit_counter[1] += (bits >> 1) & 1;
// ..
bit_counter[63] += (bits >> 63) & 1;
}
1速度は、64ビットワードのビット数に基づいて可変です。