12

Java で長い配列に対して短いベンチマークを実行したところ、非常に奇妙な結果が得られました。ランダム書き込みによるシーケンシャル読み取りは、シーケンシャル書き込みによるランダム読み取りよりも高速 (半分の時間) のようです。誰にも理由はありますか??

以下に、いくつかの long 型の配列 (-Xmx2G などで実行) を、順次読み取り時にランダムに書き込み、ランダム書き込み時に順次読み取りを行う 2 つの方法を示します。

import java.util.Random;


public class Scratch {
static Random random = new Random();
static long[] arr = new long[100000000];

static void seqReadRandWrite() {
    for(int i=0;i<arr.length;i++) {
        int at = random.nextInt(arr.length);
        arr[at] = arr[i];
    }
}

static void seqWriteRandRead() {
    for(int i=0;i<arr.length;i++) {
        int at = random.nextInt(arr.length);
        arr[i] = arr[at];
    }
}

public static void main(String[] args) throws Exception {

    seqWriteRandRead(); // warm up

    long nanos = System.nanoTime();
    seqReadRandWrite();
    System.out.println("Time: " + (System.nanoTime()-nanos) + "ns");

    nanos = System.nanoTime();
    seqWriteRandRead();
    System.out.println("Time: " + (System.nanoTime()-nanos) + "ns");

}
}

私のノートの結果は

時間: 2774662168ns

時間: 6059499068ns

これは、読み取りと比較して、ランダムに書き込む方が2倍速いことを意味します..または? 私のノートは壊れていますか？

ps .: これはベンチマークであるとは主張していませんが、ベンチマークに関するリンクされたアドバイスのほとんどのポイントがカバーされています。すでに 200,000,000 の操作を複数回実行しても、結果は一定に保たれます。少なくともこのサイズのメモリと上記の方法では、ランダムな位置から連続したブロックにメモリを移動するのは、連続した位置からランダムなブロックにメモリを移動するよりも遅いようです。なぜだろう？

4

6 に答える 6

3

あなたのベンチマークは、「意味がありますか?」に失敗する数値を生成しています。テスト。このような状況では、数字を現実の真の反映として扱う前に、常に方法論を 2 重、3 重、4 重にチェックする必要があります。

信頼できるベンチマークを作成するのは困難です。Java の場合、Java プラットフォームのいくつかの側面がベンチマーク測定に体系的な歪みをもたらす可能性があるため、特に困難です...具体的に許可/補正しない限り。

しかし、「方法論を確認する」というルールは、すべての実験に適用されます...特に、意味をなさないと思われる結果を生成するもの. （光より速く移動するニュートリノのように...）

注意すべきもう 1 つの点は、交絡因子を考慮してベンチマークを書き直しても、予期しない数値が表示される可能性があることです。ここでの問題は、このようなベンチマークのパフォーマンスが、L1 および L2 キャッシュのサイズ、キャッシュ ラインのサイズ、さまざまなレベルのメモリの相対速度、およびそれらの正確なシーケンスとの相互作用などに敏感である可能性が高いことです。ベンチマークがタイトなループで生成する命令。

これらは複雑で、分析が難しく、直観に反する動作を引き起こす可能性があります。そして、マシンが異なれば測定されたパフォーマンスが異なることも (私にとっては) 驚くべきことではありません。

そのため、数値が実際のものであったとしても、このベンチマークから読み取りと書き込みの速度に関する一般的な結論を導き出すことは依然として安全ではありません. それらをラップトップだけに制限したとしても。

于 2013-01-31T23:12:10.023 に答える
1

このベンチマークはあなたにとってまったく役に立たないと思います。あなたが説明しなかったと考える測定のパラメータはたくさんあり、あなたがその問題に取り組む方法は完全に説明されていません。VM、コンピューター、RAM速度、同時に処理するソフトウェア、コピーするオブジェクトや単純なものの種類などに関する実装の速度について結論を出すには、系統的な方法について学ぶ必要があります。この質問には答えられません。速度について知りたい特定の状況を絞り込む必要があります。

特に、乱数を使用する場合、結論を出すことはできません。これにより、最良、最悪、または平均的なケースの複雑さの問題が大幅に増加します。

アルゴリズムの複雑さを確認してから、科学的なランタイムパフォーマンス測定を行う方法を検索してください。私はあなたを少し助けることができると思います。

この最初の答えは素晴らしく、理解するのに役立ちます。Javaで正しいマイクロベンチマークを作成するにはどうすればよいですか？

よろしくお願いします、

于 2013-01-31T22:52:37.107 に答える
1

答えは以前のコメントにあり、メモリアクセスパターンの影響に要約されます。このブログ投稿では、ランダム読み取りの影響について説明します。書き込みは同様に影響を受けません。

これは Java の問題 (または言語の問題) ではなく、実行しているハードウェアの現実 (そして共通の現実) です。これは、無視する必要があるという意味ではありません。最初のベンチマークに欠陥があるかもしれませんが、一部のソフトウェアでは依然として実際の問題に直面しているため、貴重な教訓となります。

結論は、読み取りが書き込みよりも高価であるということではありません。これは、ランダム メモリ アクセスがハードウェアによって適切に処理されていないことです。これが基本的に、LinkedList のパフォーマンスが順次アクセスの ArrayList よりもはるかに悪い理由です。どちらも計算上の複雑さは同じですが、配列アクセスは、リンクされたリストにはないハードウェアの強度を発揮します。

于 2013-02-18T10:07:36.187 に答える
1

要約すると、質問のタイトルは少し間違っています。真実は、一部の環境（私のものやOPなど）では、ランダム配列の書き込みがランダム配列の読み取りよりも高速であるようです。しかし、これは他の人には当てはまらないことに注意してください。

@JustinKSUのコメントに基づいて、読み取りと書き込みを分離したところ、ランダム書き込みはランダム読み取りよりも高速であることがわかりました。結果は次のとおりです。これが理由のようであり、ここでの集合的な意見は、キャッシュの読み取りミスは書き込みミスよりもコストがかかるということです (書き込みにキャッシュが含まれている場合)。

他のアクティビティがある本番環境では、ホットスポットが役割を果たす場合があります。

/cygdrive/c/Java/jdk1.7.0/bin/javac.exe Scratch.java && /cygdrive/c/Java/jdk1.7.0/bin/java Scratch
Starting
seqRead: 1273719725ns
seqRead: 1243055271ns
seqRead: 1245022497ns
seqRead: 1242868527ns
seqRead: 1241655611ns
randRead: 6900959912ns
randRead: 6965196004ns
randRead: 7379623094ns
randRead: 7020390995ns
randRead: 6938997617ns
seqWrite: 1266963940ns
seqWrite: 1250599487ns
seqWrite: 1246471685ns
seqWrite: 1230472648ns
seqWrite: 1246975416ns
randWrite: 3898382192ns
randWrite: 3897441137ns
randWrite: 3939947844ns
randWrite: 4207906037ns
randWrite: 4103594207ns

Compilation finished at Thu Jan 31 14:38:57

私の変更されたコードは次のとおりです。

import java.util.Random;


public class Scratch {
static Random random = new Random();
static long[] arr = new long[100000000];

static void seqReadRandWrite() {
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        arr[at] = arr[i];
    }
}

static void seqWriteRandRead() {
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        arr[i] = arr[at];
    }
}


static void seqRead() {
    int x = 0;
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        x += arr[i];
    }
}

static void randRead() {
    int x = 0;
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        x += arr[at];
    }
}

static void seqWrite() {
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        arr[i] = at;
    }
}

static void randWrite() {
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        arr[at] = at;
    }
}


public static void main(String[] args) throws Exception {

    // seqWriteRandRead(); // warm up
    System.out.println("Starting");

    long nanos =  -1;
    /*
    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        seqWriteRandRead();
        System.out.println("WriteRandRead Time: " + (System.nanoTime()-nanos) + "ns");

        nanos = System.nanoTime();
        seqReadRandWrite();
        System.out.println("ReadRandWrite Time: " + (System.nanoTime()-nanos) + "ns");
    }
    */

    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        seqRead();
        System.out.println("seqRead: " + (System.nanoTime()-nanos) + "ns");
    }

    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        randRead();
        System.out.println("randRead: " + (System.nanoTime()-nanos) + "ns");
    }


    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        seqWrite();
        System.out.println("seqWrite: " + (System.nanoTime()-nanos) + "ns");
    }

    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        randWrite();
        System.out.println("randWrite: " + (System.nanoTime()-nanos) + "ns");
    }

}
}

アップデート

@tomcarchrae は Linux で同じテストを行いましたが、結果は大きく異なりました。以下、最初の列は私のテストの数値で、2 番目の列は Tom のテストの数値です。

seqRead:   1273719725ns   2810487542ns  
seqRead:   1243055271ns   2780504580ns  
seqRead:   1245022497ns   2746663894ns  
seqRead:   1242868527ns   2746094469ns  
seqRead:   1241655611ns   2763107970ns  
randRead:  6900959912ns   23093543703ns 
randRead:  6965196004ns   22458781637ns 
randRead:  7379623094ns   24421031646ns 
randRead:  7020390995ns   25880250599ns 
randRead:  6938997617ns   26873823898ns 
seqWrite:  1266963940ns   4226886722ns  
seqWrite:  1250599487ns   4537680602ns  
seqWrite:  1246471685ns   3880372295ns  
seqWrite:  1230472648ns   4160499114ns  
seqWrite:  1246975416ns   4008607447ns  
randWrite: 3898382192ns   25985349107ns 
randWrite: 3897441137ns   22259835568ns 
randWrite: 3939947844ns   22556465742ns 
randWrite: 4207906037ns   22143959163ns 
randWrite: 4103594207ns   21737397817ns
于 2013-01-31T22:42:06.853 に答える
0

ラップトップではなく、実験が壊れています。パフォーマンスの測定に役立つディスカッションといくつかのツールについては、こちらを参照してください: Java パフォーマンス タイミング ライブラリ

以下は、あなたと契約するいくつかの結果です。また、コードを修正して、測定方法をより厳密かつ慎重にしました。

私の環境は、Sun JDK 1.6.0_38 を使用する Linux (Ubuntu 12.10 ベースの Mint 14) です。

大きな例、つまり -Xmx1512 では 1.5G のヒープを使用

注：興味深い。以下の配列サイズが異なるため、結果が異なる可能性があります。再実行して更新します。

いいえ: 結果は類似しており、平均値に大きな違いはありません。しかし、興味深いのは、メモリ ページングのために遅くなる可能性がある 21092.5 (/10 = 2109.2) と 1645.2 という、短期間での違いです。

結果はstatic long[] arr = new long[100000000];（問題の元の配列サイズ）

書き込み: DescriptiveStatistics: n: 10 分: 20893.0 最大: 22190.0 平均: 21092.5 標準偏差: 390.90727800848117 中央値: 20953.5 歪度: 3.0092198852491543 尖度: 9.264808973899097

読み取り: DescriptiveStatistics: n: 10 分: 21668.0 最大: 22736.0 平均: 21892.5 標準偏差: 318.31509546359877 中央値: 21766.5 歪度: 2.503421654466124 尖度: 6.560838306717343

読み取りと書き込みに大きな違いは見られません。少し小さいアレイで 10 回測定するように実験を変更しました (結果は同じ数の読み取り/書き込みです)。より大きなサイズの配列またはサンプル サイズで自由に再実行してください。

書き込み: DescriptiveStatistics: n: 10 分: 1584.0 最大: 1799.0 平均: 1645.2 標準偏差: 59.51619760853156 中央値: 1634.5 歪度: 2.137918517160786 尖度: 5.764166551997385

読み取り: DescriptiveStatistics: n: 10 分: 1568.0 最大: 2202.0 平均: 1689.0 標準偏差: 186.93908693000031 中央値: 1623.0 歪度: 2.770215113912315 尖度: 8.12245132320571

これは、より多くのサンプルを実行するコードの修正バージョンです。

import java.util.Random;

import org.apache.commons.lang.time.StopWatch;
import org.apache.commons.math.stat.descriptive.DescriptiveStatistics;

public class Test {
    static Random random = new Random();
//  static long[] arr = new long[100000000];
    static long[] arr = new long[10000000];

    static void seqReadRandWrite() {
        for (int i = 0; i < arr.length; i++) {
            int at = Math.abs(random.nextInt()) % arr.length;
            arr[at] = arr[i];
        }
    }

    static void seqWriteRandRead() {
        for (int i = 0; i < arr.length; i++) {
            int at = Math.abs(random.nextInt()) % arr.length;
            arr[i] = arr[at];
        }
    }

    public static void main(String[] args) throws Exception {

        StopWatch timer = new StopWatch();
        int count = 10;

        // warm up
        for (int i=0; i<3; i++){
            seqReadRandWrite();
        }
        DescriptiveStatistics write = new DescriptiveStatistics();
        for (int i=0; i<count; i++){
            timer.reset();
            timer.start();
            seqReadRandWrite();
            timer.stop();
            write.addValue(timer.getTime());
        }
        System.out.println("Write: " + write);

        // warm up
        for (int i=0; i<3; i++){
            seqWriteRandRead(); 
        }
        DescriptiveStatistics read = new DescriptiveStatistics();
        for (int i=0; i<count; i++){
            timer.reset();
            timer.start();
            seqWriteRandRead();
            timer.stop();
            read.addValue(timer.getTime());
        }

        System.out.println("Read: " + read);


    }
}
于 2013-01-31T22:42:35.457 に答える
0

PC での結果: (ns per r/w)

seq read :     1.4 
rnd read :   10x.x   
seq write:     3.3 
rnd write:   10x.x

seqReadRandWrite と seqWriteRandRead は、ループあたり 100ns で同等に高速です。

したがって、これはハードウェアに依存する場合があります。VM設定も。試しjava -serverてみて、速度が向上するかどうかを確認してください。

于 2013-01-31T22:59:41.943 に答える