13

512 バイト以上の大きなバッファーでポップカウントする最速の方法を探しています。必要なアラインメントはすべて保証でき、バッファ サイズは常に 2 のべき乗です。バッファはブロック割り当てに対応するため、通常、ビットはすべて設定されているか、何も設定されていないか、バッファの「左」を優先してほとんどが設定されています。たまに穴。

私が検討したいくつかの解決策は次のとおりです。

私は最速のソリューションに興味があります.core2以降に属する32ビットx86チップセットで動作する必要があります。SSE と SIMD は非常に興味深いものです。次のクアッドコア CPU でテストします。

matt@stanley:~/anacrolix/public/stackoverflow$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
stepping        : 11
cpu MHz         : 1600.000
cache size      : 4096 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 10
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm tpr_shadow vnmi flexpriority
bogomips        : 4800.21
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:
4

4 に答える 4

5

1 つの実装については、 AMD ソフトウェア最適化ガイドの 195 ページの 32 ビット バージョンを参照してください。これにより、x86 のアセンブリ コードが直接得られます。

Stanford bit-twiddling hacksでバリアントを参照してください 。 Stanford バージョンは、私には最高のもののように見えます。x86 asm としてコーディングするのは非常に簡単に見えます。

どちらも分岐命令を使用しません。

これらは 64 ビット バージョンに一般化できます。

32 ビットまたは 64 ビット バージョンでは、SIMD バージョンの実行を検討できます。SSE2 は、一度に 4 つのダブルワードまたは 2 つのクワッドワード (いずれかの方法で 128 ビット) を処理します。やりたいことは、利用可能な 2 つまたは 4 つのレジスタのそれぞれに 32 ビットまたは 64 ビットの popcount を実装することです。完了すると、XMM レジスターに 2 組または 4 組のポップカウントができます。最後のステップは、それらの popcount を保存して追加し、最終的な答えを取得することです。推測すると、2 つの並列 64 ビット ポップカウントではなく、4 つの並列 32 ビット ポップカウントを実行する方がわずかにうまくいくと思います。後者は、各反復で 1 つまたは 2 つの追加の命令を必要とする可能性が高く、4 つの 32 ビットを簡単に追加できるためです。最後に一緒に値します。

于 2010-09-13T01:39:38.710 に答える
2

以下に、人口カウント/大きなバッファーのハミング重みについて見つけた最適な C/アセンブリ関数の概要を示します。

最速のアセンブリ関数は、こちらssse3_popcount3で説明されています。これには、Intel Core 2 以降で利用可能な SSSE3 と、2011 年に登場する AMD チップセットが必要です。SIMD命令を使用して、16 バイトのチャンクでポップカウントし、一度に 4 つのループ反復を展開します。

最速の C 関数は、こちらpopcount_24wordsで説明されています。ビットスライスアルゴリズムを使用しています。注目すべきは、clangが実際に適切なベクトル アセンブリ命令を生成できることを発見したことです。これにより、パフォーマンスが大幅に向上しました。これはさておき、アルゴリズムは依然として非常に高速です。

于 2011-02-21T14:14:44.957 に答える
1

Hacker's Delightの最適化された 32 ビット popcnt ルーチンの 1 つを実装することをお勧めしますが、SSE ベクトル内の 4 x 32 ビット整数要素に対して実行してください。その後、反復ごとに 128 ビットを処理できます。これにより、最適化された 32 ビット スカラー ルーチンと比較して約 4 倍のスループットが得られます。

于 2010-09-12T17:02:04.383 に答える