0

Here is how I tested. The first few cycles are slower, but after it warms up, the times converge.

final int N = 10000000;
final int M = 10000000;

//create array and populate random elements
int[] arr = new int[N];
for(int i=0; i<N; i++) {
    arr[i] = (int) (Math.random() * 10000);
}

//start a timer
Timer timer = new Timer();
int sum = 0;
for(int i=0; i<10; i++) {
    for(int j=0; j<M; j++) {
        //access random element
        sum += arr[(int) (Math.random() * N)];
    }
    timer.lap();
}
System.out.println(sum);

With an array of 1 billion elements, each loop takes 150ms to finish. However, with 300 million elements, it only takes 120ms. And with 100 million elements, it only takes 110ms.

With arrays this large, I don't think the cache could make any meaningful difference. For example, with 100M elements, that is 400MB, while the L3 cache on my computer is only 9MB.

What is causing the speed difference? I thought array size had no impact on the speed of access.

Will Kanga
  • 652
  • 1
  • 6
  • 12
  • 1
    `Math.random()` since it depends on the entropy generator. – LMC Aug 27 '21 at 23:01
  • 1
    @LMC it’s an LCG. It doesn’t. – Boris the Spider Aug 27 '21 at 23:02
  • But I'm calling it the same number of times (M times) no matter the size of the array – Will Kanga Aug 27 '21 at 23:02
  • 1
    As an aside, I would look into using jmh, the Java Microbenchmarking Harness, for analyzing the performance of microbenchmarks. – David Conrad Aug 27 '21 at 23:02
  • 3
    Which operating system, which JVM, what heap size, what physical memory size? – tgdavies Aug 27 '21 at 23:07
  • 2
    *"I don't think the cache could make any meaningful difference"* - It certainly can, and does, along with TLB. Run `perf stat`, or better, [JMH](https://github.com/openjdk/jmh) with [`perfnorm`](http://hg.openjdk.java.net/code-tools/jmh/file/tip/jmh-samples/src/main/java/org/openjdk/jmh/samples/JMHSample_35_Profilers.java#l375) profiler. – apangin Aug 28 '21 at 00:48
  • 1
    Tip: Use underscore to group digits of your numeric literals. Ex: `10000000` versus `10_000_000` – Basil Bourque Aug 28 '21 at 01:01
  • If not JMH, then al least use [`System.nanoTime()`](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/System.html#nanoTime()). – Basil Bourque Aug 28 '21 at 01:03
  • I tried testing this with JMH, but cannot reproduce the results on my MacBook Pro. – Sweeper Aug 28 '21 at 01:10
  • [Math.random() versus Random.nextInt(int)](https://stackoverflow.com/a/738651/2834978) – LMC Aug 28 '21 at 01:28

0 Answers0