What is the rationale for the exponential growth in the execution time of a piece of code with an increase in the size of the array by 10 times?

Question

Java

Java code available

package com.company;

public class Main {

    public static void main(String[] args) {
        //Runtime runtime = Runtime.getRuntime();
        int k = 10000;
        int[] A = new int[100];
        long startTime = System.currentTimeMillis();
        for(int i = 0; i < A.length; i++){
            A[i] = (int)(Math.random() * k);
        }
        long timeSpent = System.currentTimeMillis() - startTime;
        System.out.println("Time: " + timeSpent);
    }
}

As the size of array A increases, its filling time grows exponentially. Although, like, it should be linear.
Steps from 100 to 1,000,000

Answer 1

Most likely everything depends on the processor cache, the second method is 10 times faster than the first. In the case of (int)(Math.random() * k), the increase in speed will be 2 times:

class Test {
  public static void main(String[] args) {
 
    int k = 10000;
    long st, en;
    int[] A;
    int length = 100000;
 
    A = new int[length];
    st = System.nanoTime();
    for (int i = 0; i < length; i++)
    {
      A[i] = k;
    }
    en = System.nanoTime();
    System.out.println("\nOne time=" + (en - st) / 1000000.d + " msc");
 
    int cache = 10000;
    A = new int[length];
    int[] temp = new int[cache];
    st = System.nanoTime();
    for (int N = 0; N < length; N+=cache) {
      for (int i = 0; i < cache; i++) {
        temp[i] = k;
      }
      System.arraycopy(temp, 0, A, N, temp.length);
    }
    en = System.nanoTime();
    System.out.println("\nTwo time=" + (en - st) / 1000000.d + " msc");
 
  }
}

Try here: ideone.com/Py6A4S
Article: rus-linux.net/MyLDP/hard/memory/memory-03-11.html
Quote:

More surprising than the read performance is the write and copy performance. Write performance, even for small working sets, never goes above 4 bytes per cycle. This indicates that in such Netburst processors, Intel decided to use the write-through mode in the L1d cache (Write-Through), in which the speed is obviously limited by the speed of the L2 cache. It also means that the performance of a copy test, in which data is copied from one area of ​​memory to another non-overlapping area of ​​memory, is not much worse. Therefore, the required read operations are much faster and may overlap with write operations. The most interesting detail of the write and copy measurement is the poor performance when as soon as the L2 cache becomes low. Performance drops to 0.5 bytes per cycle! This means that write operations are ten times slower than read operations. This means that optimizing these operations is even more important for program execution.

Answer 2

Make a logging system: Record the time of occurrence of each event in a file. Between which two events time starts to grow, there is a problem.
Дорожно-ремонтное предприятие где-то во Франции приняло на работу корсиканца. Поручили ему наносить краской разметку на асфальтовой дороге. В первый день он нанес 50 м разметки. Во второй 30. В третий - 15. А в четвертый день - только 5. Возмущенный прораб приехал и спрашивает - почему дескать производительность все хуже с каждым днем ? Последовал ответ: а как же иначе ? - ведь чем дальше продвигаешься вперед с нанесенной разметкой, тем дальше ходить до ведра с краской...

Answer 3

Most likely the solution is here

for(int i = 0; i < A.length; i++){
            A[i] = (int)(Math.random() * k);
        }

Because random it doesn't exactly generate a random number. At large iterations, the LLN (Law of Large Numbers) comes into force. That is, there is a possibility that in your array there will be numbers different by some constant, and maybe even be within a certain range