Подтвердить что ты не робот

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 ГГц, тесты были выполнены в одном потоке.

4b9b3361

ОТВЕТЫ

Ответ 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