3

HashMap<Integer,Integer> の場合、10000000 個の一意のランダム値を挿入した後。次のコード スニペットのように、ハッシュマップの keySet() を使用して get() を実行します。

HashMap<Integer, Integer> hashmap = 
                        new HashMap<Integer, Integer>(10000000, 0.99f);

// ... Code to put unique 10000000 associations into the hashmap ...

int iteration = 100;
long startTime, totalTime = 0;

while(iteration > 0) {
    for(Integer key: hashmap.keySet()) {
       startTime = System.currentTimeMillis();
       hashmap.get(key);
       totalTime += (System.currentTimeMillis() - startTime);
    }
    iteration--;
}
System.out.println(totalTime/100 + " ms");

上記のコードを実行すると、次のようになります: 225 ms

ここで、次のスニペットのように、代わりにセットを使用するように上記のコードを変更すると:

Set<Integer> set = new HashSet<Integer>(hashmap.keySet());
while(iteration > 0) {
    for(Integer key: set) {
       startTime = System.currentTimeMillis();
       hashmap.get(key);
       totalTime += (System.currentTimeMillis() - startTime);
    }
    iteration--;
}
System.out.println(totalTime/100 + " ms");

そして、このコードを実行した後、次のようになります: 414 ミリ秒

なぜこのようなパフォーマンスの違いが生じるのでしょうか?

PS: 次の JVM 引数を使用しました。

-Xms2048m -Xmx4096m -XX:MaxPermSize=256m
4

4 に答える 4

3

大きなデータ構造 (32 KB を超える) を読み取る場合、そのデータ構造の読み取り方法がパフォーマンスに影響します。

これらは、キャッシュの一般的なサイズと速度です。

L1:   32 KB, 4 clock cycles.
L2:  256 KB, 11 clock cycles.
L3: 3-30 MB, 40-75 clock cycles.
Main memory: up to 2TB, 200-500 clock cycles.

これは、キャッシュの局所性が非常に重要であることを意味します。つまり、L1 から何かを読み取る場合、L3 から読み取るよりも 20 倍速くなる可能性があります。

あなたの場合、ハッシュデータ構造を使用しています。これは、ランダム アクセスとランダム配置用に設計されているため、残念ながらキャッシュ可能性が非常に低くなります。メモリにランダムにアクセスすると、メモリの遅い領域にある可能性があります。

ただし、これには例外があります。同じデータに複数回アクセスする場合、たとえばイテレータから取得したばかりのキーを取得する場合、またはコレクションを順番にスキャンしている場合、たとえばこれはイテレータが HashMap (TreeMap ではなく) に対して行うことです。次にアクセスするデータが同じキャッシュ ライン (各キャッシュ ラインの長さは 64 バイト) または次のキャッシュ ライン上にあることを確認してください。CPU はベクトル操作を非常に高速に実行するように設計されているため、これらのタイプのアクセスのパフォーマンスは大幅に向上します。

ところで、作業セットはキーのセットです。値が異なるオブジェクトである場合、これらのオブジェクトを実際に見ると、これははるかに遅くなると予想されます(これにより、作業セットのサイズとキャッシュに必要なメモリ量が増加するため)それ）

于 2013-12-17T11:11:48.030 に答える
2

これ

   startTime = System.currentTimeMillis();
   hashmap.get(key);
   totalTime += (System.currentTimeMillis() - startTime);

マイクロベンチマークのばかげた試みです。精度currentTimeMillis()が1 ミリ秒で、実際の精度が 10 ミリ秒を超えるものを使用して、ナノ秒の操作を測定します。その精度は通常マイクロ秒単位であるため、単独でも役に立ちません。nanoTime

また、コードはウォームアップをまったく実行しません。

map#get1 回の呼び出しのパフォーマンスと同じくらいとらえどころのないものを測定したい場合は、適切なマイクロベンチマーク ツールを使用することをお勧めします。

于 2013-12-17T10:55:16.290 に答える
2

1 つの get() を測定するには、ミリ秒の精度では不十分です。ループの開始時とループの終了時に時間を読み取ります。内部のセクションで時間をインクリメントしようとしないでください。そうすると、実際の結果が失われる可能性のある大きな潜在的な精度エラーが発生します。

タイミングを実行せずにループを 50 回実行して (JVM をウォームアップし、すべてがコンパイルされていることを確認するためなど)、ループ プロセス全体のタイミングを計って再度実行してください。

Set<Integer> set = new HashSet<Integer>(hashmap.keySet());
startTime = System.currentTimeMillis();
while(iteration > 0) {
    for(Integer key: set) {
       hashmap.get(key);
    }
    iteration--;
}
totalTime = (System.currentTimeMillis() - startTime);
System.out.println(totalTime + " ms");

反復で除算したときに、コードで 0 除算エラーが発生しなかったのはなぜですか?

于 2013-12-17T10:53:37.470 に答える
0

これら 2 つのクラスのパフォーマンスを調べるロジックは正しくありません。

get メソッドの呼び出しごとに時間を測定するのではなく、キーセットの完全な反復にかかる時間を (できればナノ秒の精度で) 測定します。事実を証明するには、結果が一貫している必要があります。これだけが事実を証明できます。

また、パフォーマンスは JVM と GC の構成に大きく依存します。

于 2013-12-17T10:58:16.610 に答える