Long.bitCount の最適化

StackOverflow https://stackoverflow.com/questions/4839128

質問

Long.bitCount() への呼び出しを膨大な数行うプログラムがあります。呼び出しが多すぎて、1 つの CPU コアでサイクルの 33% を消費しています。Sun JDK バージョンよりも高速に実装する方法はありますか?

私が試してみました：

  • このアルゴリズム (これはまさに JDK の実装方法だと思います)
  • 2 つの間のさまざまなサイズのルックアップ テーブル8 そして222 (一度に数ビットを調べて結果を追加します)

でも2以上の成績は出せなかった16-手動でアンロールされたループを含むエントリ ルックアップ テーブル (CPU の約 27%)
これを Java 用に最適化するには他にどのような方法があるでしょうか?

注記:この質問は Java 固有の最適化に関するものですが、 この同様の（言語に依存しない）質問 他にも多くのアルゴリズムがあります。

役に立ちましたか？

解決

最近のX86 CPUに参加している場合、これの指示があります。

Javaの最近のバージョンでは、Long.bitcount（）がこの命令を使用しています。 -xx：+usepopcountinstructionを使用するだけです（これは最近のバージョンのデフォルトです）

ただし、JRE 6.0_U18から7.0_U5にはいくつかのバグがあります。http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7063674

他のヒント

これは、GPUが取り組むのに最適な問題の1つのようです。それはあなたの時間を数桁削減できるはずです。

そうでなければ、あなたはそれをより高いレベルで処理しなければならないかもしれないと思います。一度にデータのさまざまなセグメントで動作する複数のスレッド（すでに行っていると確信しています）、データを収集中に処理し、複数のシステムを中心に作業を共有します。

マシンには、64ビット（SSE2やVMXなどのSIMDとも呼ばれる）の一部よりも広いデータを処理できる整数ALUがある場合、複数の64ビット要素でビットカウントを一度に計算できます。

残念ながら、これにはJavaよりも低レベルの言語で機械固有の実装を提供する必要があります。

私はあなたのアプリがCPUバウンドではなくメモリバウンドであると思われます。つまり、それは彼らのビットをカウントするよりも、メモリから値を取得する時間をより多く費やしています。その場合、作業セットのサイズを縮小するか、アクセスローカリティを改善してキャッシュミスを減らすようにしてください（アルゴリズムが許可する場合）。

私はこの分野の専門家ではありませんが、これらのページをまだ見ていない場合は、次のページが役立つかもしれません。

http://www.reddit.com/r/programming/comments/84sht/fast_bit_couting_algorithms/

http://www-graphics.stanford.edu/~seander/bithacks.html

また、世の中にある多くのグラフィックス ライブラリ、特に低レベルのものやハードウェアに直接通信するものを調べてみることもできます。

編集：低レベルのプラットフォーム固有のコードを記述するオプションがあり、その特定のアーキテクチャをターゲットにできる場合は、比較的新しく導入された POPCNT 命令 (一部の最近の AMD および Intel プロセッサで利用可能) を使用して速度を向上できるようです。 http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html ベンチマークを含む別の記事: http://www.strchr.com/crc32_popcnt

私の理解から：

小さな方法のプロファイリングは、全体的なパフォーマンスを実際に変える可能性があるため、33％をインジケーターとして使用します。そのため、いくつかの大きなデータセットでアルゴリズムを実行し、合計時間を確認します。そして、私はその合計時間の変化に基づいて、私の最適化のエフェクシックを考慮します。また、JITが最適化できるように、警告アップフェーズも含めます。

実際、ビットカウントはアルゴリズムの重要な部分の1つであるように見えます...すべてを最適化し、すべての重要な部分で10回速く速くなると、この部分の33％近くの何かをプロファイルします。それは本質的に悪くはありません。

このリンクからインスピレーションを与えます http://bmagic.sourceforge.net/bmsse2opt.html 正しく覚えていれば、すべてのIntel/AMDプロセッサに存在するSSE命令を使用しようとすることができます（それ以外の場合はJavaに失敗することができます）。記事に関する相違点は...ほとんどの場合、とにかくメモリバインドされているということです。しかし、私はまだこれがあなたのためにどのように機能するかを見ようとします。

GPUは、非常に速い処理（CPUコアの1つの簡単な時間）と帯域幅にぴったりです。主な問題は、データをCPU専用メモリにプッシュし、結果を取り戻すことです。しかし、ビットカウントを実行するだけでなく、より多くの操作を実行する場合、これは大きな利益をもたらす可能性があります。

とにかくショートカットはありません。いくつかのアプローチを試して、何が最も利益をもたらすかを確認する必要があります。 ％をカウントしないでください。合計時間は費やされます。

私は現在、この方法を使用しています。に基づいています このC実装。

private static final long M0=0x5555555555555555L,
                          M1=0x3333333333333333L,
                          M2=0x0f0f0f0f0f0f0f0fL;
public void store4Tags(long tag0, long tag1, long tag2, long tag3) {
    long count0 = tag0,
         count1 = tag1,
         count2 = tag2,
         count3 = tag3;
    count0 = (count0 & M0) + ((count0 >>> 1) & M0);
    count1 = (count1 & M0) + ((count1 >>> 1) & M0);
    count2 = (count2 & M0) + ((count2 >>> 1) & M0);
    count3 = (count3 & M0) + ((count3 >>> 1) & M0);

    count0 = (count0 & M1) + ((count0 >>> 2) & M1);
    count1 = (count1 & M1) + ((count1 >>> 2) & M1);
    count2 = (count2 & M1) + ((count2 >>> 2) & M1);
    count3 = (count3 & M1) + ((count3 >>> 2) & M1);

    count0 = (count0 + (count0 >>> 4)) & M2;
    count1 = (count1 + (count1 >>> 4)) & M2;
    count2 = (count2 + (count2 >>> 4)) & M2;
    count3 = (count3 + (count3 >>> 4)) & M2;

    count0 += count0 >>> 8;
    count1 += count1 >>> 8;
    count2 += count2 >>> 8;
    count3 += count3 >>> 8;

    count0 += count0 >>> 16;
    count1 += count1 >>> 16;
    count2 += count2 >>> 16;
    count3 += count3 >>> 16;

    count0 += count0 >>> 32;
    count1 += count1 >>> 32;
    count2 += count2 >>> 32;
    count3 += count3 >>> 32;

    storeWithPopCnt(tag0, 0x3f & (int) count0);
    storeWithPopCnt(tag1, 0x3f & (int) count1);
    storeWithPopCnt(tag2, 0x3f & (int) count2);
    storeWithPopCnt(tag3, 0x3f & (int) count3);
}

これにより、ルックアップテーブルバージョンをわずかに上回り、キャッシュを消費しません。

この関数を最適化するよりも、この関数の使用法を最適化する方がよいでしょう。例えば。カウンターを維持できます。

public void set(int n) {
   if(!get(n)) bitCount++;
   // set the bit
}
public void clear(int n) {
   if(get(n)) bitCount--;
   // clear the bit
}
public int bitCount() {
   return bitCount;
}

これにより、設定されたビット数を追跡​​することでデータのスキャンを回避できます。これにより、オーバーヘッドがビットとセットまたはクリアの頻度に移され、セットされたビット数の取得が簡単になります。これはあなたのユースケースに現れますが、後者の方がはるかに頻繁に発生します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top