12

我在 java 中的一个长数组上执行了一个简短的基准测试，结果非常奇怪。似乎带有随机写入的顺序读取比带有顺序写入的随机读取要快 - 一半的时间。有没有人知道为什么？

以下是两种方法，它们在顺序读取时随机写入一些 long 数组（使用 -Xmx2G 左右运行），在随机写入时顺序读取：

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

这意味着随机写入的速度是读取速度的两倍。或者？我的笔记本坏了吗？

ps.：这并不声称是基准，尽管有关基准测试的链接建议中的大部分要点都已涵盖。即使我多次运行已经 200,000,000 次操作，结果仍然保持不变。似乎（似乎！）将内存从随机位置移动到顺序块比将内存从顺序位置移动到随机块慢，至少在这种大小的内存和上述执行方式的情况下。我想知道为什么？

4

6 回答 6

3

您的基准测试产生的数字未能通过“它们有意义吗？” 测试。在这种情况下，您应该始终双重/三重/四重检查您的方法……在将数字视为现实的真实反映之前。

编写可靠的基准测试很困难。而在 Java 的情况下，这尤其困难，因为 Java 平台的某些方面可能会在您的基准测量中引入系统性失真……除非您特别允许/补偿它们。

但是“检查你的方法”规则适用于所有实验……尤其是那些产生似乎没有意义的结果的实验​​。（就像中微子比光速更快......）

另一件需要注意的事情是，一旦你重写了基准以考虑混杂因素，你可能仍然会看到意想不到的数字。这里的问题是，像这样的基准测试的性能可能对 L1 和 L2 缓存的大小、缓存行的大小、不同内存级别的相对速度……以及它们与基准在紧密循环中产生的指令。

这些事情很复杂，难以分析，并且会产生违反直觉的行为。（对我来说）不同的机器给出不同的测量性能并不奇怪。

因此，即使这些数字是真实的，从这个基准测试中得出关于读写速度的任何一般性结论仍然是不安全的。即使您将它们限制在您的笔记本电脑上，也不会。

于 2013-01-31T23:12:10.023 回答
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 上进行了相同的测试，结果明显不同。下面，第一列是我测试的数字，第二列是汤姆的：

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 回答
1

我相信这个基准对你来说完全没用。有很多测量参数需要考虑，你没有描述，你解决这个问题的方式，完全没有描述。要对有关 VM、计算机、RAM 速度、您同时处理的软件、您复制的对象类型或简单内容等方面的实现速度做出任何结论，您必须了解一种有条不紊的方法。这个问题无法回答。您必须缩小您想了解速度的具体情况。

尤其是在使用随机数时，您无法得出任何结论。这大大增加了最佳、最坏或平均情况复杂性的问题。

请检查算法的复杂性，然后继续搜索如何进行科学的运行时性能测量。我希望我能帮助你一点。

第一个答案很棒，可以帮助您理解。如何在 Java 中编写正确的微基准测试？

此致，

于 2013-01-31T22:52:37.107 回答
1

答案在之前的评论中，归结为内存访问模式的影响。这篇博文介绍了随机读取的影响。写入不会受到类似的影响。

这不是 Java 问题（或者实际上是任何语言问题），而是您在其上运行的硬件的现实（并且是常见的现实）。这并不意味着您应该忽略它！尽管您最初的基准测试可能存在缺陷，但它仍然对某些软件造成了真正的问题，因此这是一个宝贵的教训。

结论并不是读取比写入更昂贵。硬件不能很好地满足随机内存访问的需求。这基本上就是为什么 LinkedList 的性能在顺序访问方面比 ArrayList 差得多，它们都具有相同的计算复杂度，但数组访问发挥了链表所没有的硬件强度。

于 2013-02-18T10:07:36.187 回答
0

你的实验坏了，不是你的笔记本电脑。请参阅此处的讨论和一些有助于衡量性能的工具： Java 性能计时库

以下是一些与您的结果相关的结果。我还修改了您的代码，使其在测量方式上更加严格和谨慎。

我的环境是使用 Sun JDK 1.6.0_38 的 Linux（基于 Ubuntu 12.10 的 Mint 14）

以1.5G的堆为例，即-Xmx1512

注：有趣。可能是我的结果不同，因为下面的数组大小不同。将重新运行和更新。

不：结果相似，平均值没有太大差异。但有趣的是与短期的差异，即 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.5034216544466124 峰度：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

我的电脑上的结果：（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 回答