java - Long.bitCount の最適化

Question

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

私が試してみました：

このアルゴリズム（これはまさにJDKが実装する方法だと思います）
^{2 8}から 2 ²²までのさまざまなサイズのルックアップテーブル(一度に数ビットを調べて結果を加算)

^{しかし、手動で展開されたループ (約 27% の CPU) を持つ 2 16}エントリのルックアップテーブル以上のことはできませんでした。
これを Java 用に最適化するには、どうすればよいでしょうか?

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

score 12 · Accepted Answer

最近の x86 CPU を使用している場合は、popcnt という命令があります。

Java の最近のバージョンでは、Long.bitCount() がこの命令を使用します。-XX:+UsePopCountInstruction を使用するだけです (これは最近のバージョンのデフォルトです)

ただし、JRE 6.0_u18 から 7.0_u5 にはいくつかのバグがあります: https://bugs.java.com/bugdatabase/view_bug.do?bug_id=7063674

score 4 · Accepted Answer

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

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

score 4 · Accepted Answer

これは、GPU が処理するのに最適な問題の 1 つに思えます。時間を数桁短縮できるはずです。

それ以外の場合は、より高いレベルで対処する必要があると思います。一度に複数のスレッドでデータの異なるセグメントを処理し (既に実行していると思います)、データを収集しながらデータを処理し、複数のシステムで作業を共有します。

score 2 · Accepted Answer

あなたのアプリは CPU バウンドではなくメモリバウンドであると思われます。つまり、ビットをカウントするよりもメモリから値をフェッチすることに多くの時間を費やしています。その場合、ワーキングセットのサイズを小さくするか、アクセスの局所性を改善してキャッシュミスを減らすようにしてください (アルゴリズムで許可されている場合)。

score 1 · Accepted Answer

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

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

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

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

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

score 1 · Accepted Answer

私の理解から：

小さなメソッドのプロファイリングは全体的なパフォーマンスを実際に変える可能性があるため、33% を指標としてのみ使用します。したがって、大きなデータセットでアルゴリズムを実行し、合計時間を確認します。そして、その合計時間の変化に基づいて、最適化の効率を検討します。JITが最適化できるように、警告フェーズも含めます。

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

このリンクhttp://bmagic.sourceforge.net/bmsse2opt.htmlからインスピレーションを得て、私の記憶が正しければ、すべての intel/AMD プロセッサに存在する SSE 命令を使用してみることができます (それ以外の場合は、いつでも JAVA にフェールバックできます)。この記事に関する興味深い部分は... ほとんどの場合、とにかくメモリにバインドされていることです。しかし、私はまだこれがあなたのためにどのように機能するかを見ようとします.

GPU は、非常に高速な処理 (CPU コアの 100 倍の簡単な処理) と帯域幅に最適です。主な問題は、データを CPU 専用メモリにプッシュし、結果を取得することです。しかし、ビットカウントを実行するだけでなく、より多くの操作を実行すると、大きな利益が得られる可能性があります。

とにかく近道はありません。いくつかのアプローチを試して、何が最も利益をもたらすかを確認する必要があります。% をカウントしないで、合計時間を計算します。

score 1 · Accepted Answer

私は現在、一度に 4 つの popcnt 操作をインターリーブするこの方法を使用しています。この 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);
}

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

score 0 · Accepted Answer

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

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;
}

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

java - Long.bitCount の最適化

8 に答える 8

Related

Reference