Java 2D-массив заполняет - невиновная оптимизация вызвала ужасное замедление
Я попытался оптимизировать заполнение квадратного двумерного массива Java суммами индексов для каждого элемента, вычисляя каждую сумму один раз для двух элементов, противоположных относительно основной диагонали. Но вместо ускорения или, по крайней мере, сопоставимой производительности, у меня есть код 23 (!) Раза медленнее.
Мой код:
@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(ArrayFill.N * ArrayFill.N)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ArrayFill {
public static final int N = 8189;
public int[][] g;
@Setup
public void setup() { g = new int[N][N]; }
@GenerateMicroBenchmark
public int simple(ArrayFill state) {
int[][] g = state.g;
for(int i = 0; i < g.length; i++) {
for(int j = 0; j < g[i].length; j++) {
g[i][j] = i + j;
}
}
return g[g.length - 1][g[g.length - 1].length - 1];
}
@GenerateMicroBenchmark
public int optimized(ArrayFill state) {
int[][] g = state.g;
for(int i = 0; i < g.length; i++) {
for(int j = 0; j <= i; j++) {
g[j][i] = g[i][j] = i + j;
}
}
return g[g.length - 1][g[g.length - 1].length - 1];
}
}
Результаты тестов:
Benchmark Mode Mean Mean error Units
ArrayFill.simple avgt 0.907 0.008 ns/op
ArrayFill.optimized avgt 21.188 0.049 ns/op
Вопрос:
Как можно объяснить падение производительности настолько потрясающее?
<суб > Р. Версия S. Java - это 1.8.0-ea-b124, 64-разрядный процессор AMD с тактовой частотой 3,2 ГГц, тесты были выполнены в одном потоке.
Ответы
Ответ 1
Примечание: ваша "оптимизированная" версия может быть не совсем быстрой, даже если мы оставим все возможные проблемы в стороне. В современном процессоре есть несколько ресурсов, и насыщение одного из них может помешать вам любых улучшений. Что я имею в виду: скорость может быть связана с памятью, и попытка записи в два раза быстрее может на одной итерации вообще ничего не менять.
Я вижу три возможные причины:
-
Ваш шаблон доступа может принудительно проверять привязку. В "простом" цикле они могут быть явно устранены в "оптимизированном", только если массив является квадратом. Это, но эта информация доступна только вне метода (более того, другой код может ее изменить!).
-
Локальность в вашем оптимизированном цикле плохая. Он обращается к существенно случайным ячейкам памяти, поскольку в Java нет ничего похожего на 2D-массив (только массив массивов, для которых new int[N][N] является ярлыком). При итерации по столбцам вы используете только один int из каждой загруженной строки кэша, то есть 4 байта из 64.
-
может иметь проблемы с вашим шаблоном доступа. Массив с 8189 * 8189 * 4 байтами слишком велик, чтобы вписаться в любой кеш. Современные процессоры имеют предварительный набор, позволяющий заранее загружать линию кэша, когда он видит обычный шаблон доступа. Возможности префеттеров сильно различаются. Это может быть неактуально здесь, поскольку вы только пишете, но я не уверен, возможно ли записать в кеш-строку, которая не была выбрана.
Я предполагаю, что основной причиной является локализация памяти:
Я добавил метод "reverseed", который работает как бы простой, но с
g[j][i] = i + j;
вместо
g[i][j] = i + j;
Это "безобидное" изменение - это дестабилизирующий эффект:
Benchmark Mode Samples Mean Mean error Units
o.o.j.s.ArrayFillBenchmark.optimized avgt 20 10.484 0.048 ns/op
o.o.j.s.ArrayFillBenchmark.reversed avgt 20 20.989 0.294 ns/op
o.o.j.s.ArrayFillBenchmark.simple avgt 20 0.693 0.003 ns/op
Ответ 2
Я написал версию, которая работает быстрее, чем "простая". Но, я не знаю, почему это быстрее (вот код:
class A {
public static void main(String[] args) {
int n = 8009;
long st, en;
// one
int gg[][] = new int[n][n];
st = System.nanoTime();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
gg[i][j] = i + j;
}
}
en = System.nanoTime();
System.out.println("\nOne time " + (en - st)/1000000.d + " msc");
// two
int g[][] = new int[n][n];
st = System.nanoTime();
int odd = (n%2), l=n-odd;
for(int i = 0; i < l; ++i) {
int t0, t1;
int a0[] = g[t0 = i];
int a1[] = g[t1 = ++i];
for(int j = 0; j < n; ++j) {
a0[j] = t0 + j;
a1[j] = t1 + j;
}
}
if(odd != 0)
{
int i = n-1;
int a[] = g[i];
for(int j = 0; j < n; ++j) {
a[j] = i + j;
}
}
en = System.nanoTime();
System.out.println("\nOptimized time " + (en - st)/1000000.d + " msc");
int r = g[0][0]
// + gg[0][0]
;
System.out.println("\nZZZZ = " + r);
}
}
Результаты:
One time 165.177848 msc
Optimized time 99.536178 msc
ZZZZ = 0
Может кто-нибудь объяснить мне, почему это быстрее?
Ответ 3
http://www.learn-java-tutorial.com/Arrays.cfm#Multidimensional-Arrays-in-Memory
Изображение: http://www.learn-java-tutorial.com/images/4715/Arrays03.gif
int [] [] === массив массивов значений
int [] === массив значений
class A {
public static void main(String[] args) {
int n = 5000;
int g[][] = new int[n][n];
long st, en;
// one
st = System.nanoTime();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
g[i][j] = 10;
}
}
en = System.nanoTime();
System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
// two
st = System.nanoTime();
for(int i = 0; i < n; i++) {
g[i][i] = 20;
for(int j = 0; j < i; j++) {
g[j][i] = g[i][j] = 20;
}
}
en = System.nanoTime();
System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
// 3
int arrLen = n*n;
int[] arr = new int[arrLen];
st = System.nanoTime();
for(int i : arr) {
arr[i] = 30;
}
en = System.nanoTime();
System.out.println("\n3 time " + (en - st)/1000000.d + " msc");
// 4
st = System.nanoTime();
int i, j;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
arr[i*n+j] = 40;
}
}
en = System.nanoTime();
System.out.println("\n4 time " + (en - st)/1000000.d + " msc");
}
}
Два раза 71.998012 msc
Два раза 551.664166 msc
3 раза 63.74851 msc
4 раза 57.215167 msc
P.S. Я не java spec =)
Ответ 4
Я вижу, вы выделили новый массив для второго запуска, но все-таки попробовали ли вы изменить порядок "неоптимизированных" и "оптимизированных" запусков? - fikto
Я изменил их порядок и немного его оптимизировал:
class A {
public static void main(String[] args) {
int n = 8009;
double q1, q2;
long st, en;
// two
int g[][] = new int[n][n];
st = System.nanoTime();
int odd = (n%2), l=n-odd;
for(int i = 0; i < l; ++i) {
int t0, t1;
int a0[] = g[t0 = i];
int a1[] = g[t1 = ++i];
for(int j = 0; j < n; ++j, ++t0, ++t1) {
a0[j] = t0;
a1[j] = t1;
}
}
if(odd != 0)
{
int i = n-1;
int a[] = g[i];
for(int j = 0; j < n; ++j, ++i) {
a[j] = i;
}
}
en = System.nanoTime();
System.out.println("Optimized time " + (q1=(en - st)/1000000.d) + " msc");
// one
int gg[][] = new int[n][n];
st = System.nanoTime();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
gg[i][j] = i + j;
}
}
en = System.nanoTime();
System.out.println("One time " + (q2=(en - st)/1000000.d) + " msc");
System.out.println("1 - T1/T2 = " + (1 - q1/q2));
}
}
И результаты:
Optimized time 99.360293 msc
One time 162.23607 msc
1 - T1/T2 = 0.3875573231033026
