Чем обоснован экспоненциальный рост времени выполнения куска кода при увеличении размера массива в 10 раз?
Скорее всего все упирается в кэш процессора, второй способ в 10 раз быстрее первого. В случае (int)(Math.random() * k) прирост по скорости будет в 2 раза: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");
 
	}
}
Попробовать тут: ideone.com/Py6A4S
Статья: rus-linux.net/MyLDP/hard/memory/memory-03-11.html
Цитата:Более удивительной по сравнению с производительностью при чтении является производительность при записи и копировании. Производительность при записи даже для рабочих наборов с небольшими размерами, никогда не поднимается выше 4 байтов за цикл. Это указывает на то, что в таких процессорах Netburst, Intel решила использовать в кэш-памяти L1d режим с прямой записью (Write-Through), при котором скорость, очевидно, ограничена скорость работы кэш-памяти L2. Это также означает, что производительность теста копирования, в котором данные копируются из одной области памяти в другую непересекающуюся области памяти, не намного хуже. Следовательно, требуемые операций чтения выполняются намного быстрее и могут частично перекрываться с операциями записи. Самым интересными деталями измерения записи и копирования является низкая производительность в случае, как только становится мало кэш-памяти L2. Производительность падает до 0,5 байта за цикл! Это значит, что операции записи в десять раз медленнее, чем операции чтения. Это означает, что оптимизация этих операций еще более важна для выполнения программы.
Сделайте систему логирования: Записывайте в файл время происшествия каждого события. Между какими двумя событиями время расти начнёт, там и проблема.Анекдот
Дорожно-ремонтное предприятие где-то во Франции приняло на работу корсиканца. Поручили ему наносить краской разметку на асфальтовой дороге. В первый день он нанес 50 м разметки. Во второй 30. В третий - 15. А в четвертый день - только 5. Возмущенный прораб приехал и спрашивает - почему дескать производительность все хуже с каждым днем ? Последовал ответ: а как же иначе ? - ведь чем дальше продвигаешься вперед с нанесенной разметкой, тем дальше ходить до ведра с краской...