Почему изменение цикла замедляет его?

Question

У меня есть следующий код, который выполняет круговое смещение битов в массиве:

private static void method1(byte[] bytes) {
    byte previousByte = bytes[0];
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length - 1] & 0xff) << 7));
    for (int i = 1; i < bytes.length; i++) {
       byte tmp = bytes[i];
       bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((previousByte & 0xff) << 7));
       previousByte = tmp;
    }
}

Тогда я подумал, что проще и удобнее читать назад, как это:

private static void method2(byte[] bytes) {
    byte lastByte = bytes[bytes.length-1];
    for (int i = bytes.length-1; i > 0; i--) {
       bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((bytes[i-1] & 0xff) << 7));
    }
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((lastByte & 0xff) << 7));
}

Но я заметил, что второй (method2) медленнее первого (method1)!Я заметил разницу, потому что я вызываю метод тысячи раз.Итак, я сделал тест, чтобы убедиться, и вот средний результат 20 тестов вызова каждого метода 3000 раз (а число байтов равно 1 миллиону):

method1 average : 4s 572ms
method2 average : 5s 630ms

Итак, мой вопрос: почемупервый быстрее второго?

Вот код тестирования, чтобы убедиться, что я не ошибаюсь при тестировании:

import java.math.BigInteger;

public class BitShiftTests {

public static void main(String[] args) {

    int numOfTests = 20;
    int numberOfShifts = 3000;
    byte[] numbers = new byte[1000000];
    for (int i = 0; i < numbers.length; i++) {
        numbers[i] = (byte) (i % 255);
    }

    System.out.println("Testing method1...");
    BigInteger method1Sum = new BigInteger("00000000", 2);
    for (int i = 1; i <= numOfTests; i++) {
       long total = 0L;
       for (int j = 0; j < numberOfShifts; j++) {
          long startTime = System.nanoTime();
          method1(numbers);
          long endTime   = System.nanoTime();
          total = total + (endTime - startTime);
       }
       method1Sum = method1Sum.add(new BigInteger(Long.toString(total), 10));
       System.out.println(String.format("%-2d: %s", i, getTime(total)));
    }

    System.out.println("Testing method2...");
    BigInteger method2Sum = new BigInteger("00000000", 2);
    for (int i = 1; i <= numOfTests; i++) {
       long total = 0L;
       for (int j = 0; j < numberOfShifts; j++) {
          long startTime = System.nanoTime();
          method2(numbers);
          long endTime   = System.nanoTime();
          total = total + (endTime - startTime);
       }
       method2Sum = method2Sum.add(new BigInteger(Long.toString(total), 10));
       System.out.println(String.format("%-2d: %s", i, getTime(total)));
    }

    System.out.println("method1 average :   " + getTime(method1Sum.longValue() / numOfTests));
    System.out.println("method2 average :   " + getTime(method2Sum.longValue() / numOfTests));
}

private static void method1(byte[] bytes) {
    byte previousByte = bytes[0];
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length - 1] & 0xff) << 7));
    for (int i = 1; i < bytes.length; i++) {
       byte tmp = bytes[i];
       bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((previousByte & 0xff) << 7));
       previousByte = tmp;
    }
}

private static void method2(byte[] bytes) {
    byte lastByte = bytes[bytes.length-1];
    for (int i = bytes.length-1; i > 0; i--) {
       bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((bytes[i-1] & 0xff) << 7));
    }
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((lastByte & 0xff) << 7));
}

private static String getTime(long nanoSecs) {

  int minutes = (int) (nanoSecs / 60000000000.0);
  int seconds = (int) (nanoSecs / 1000000000.0) - (minutes * 60);
  int millisecs = (int) (((nanoSecs / 1000000000.0) - (seconds + minutes * 60)) * 1000);
  int nanosecs = (int) nanoSecs - (millisecs * 1000000000);

  if (minutes == 0 && seconds == 0 && millisecs == 0) {
     return nanosecs + "ns";
  }

  if (minutes == 0 && seconds == 0) {
     return millisecs + "ms";
  }

  if (minutes == 0 && millisecs == 0) {
     return seconds + "s";
  }

  if (seconds == 0 && millisecs == 0) {
     return minutes + "min";
  }

  if (minutes == 0) {
     return seconds + "s " + millisecs + "ms";
  }

  if (seconds == 0) {
     return minutes + "min " + millisecs + "ms";
  }

  if (millisecs == 0) {
     return minutes + "min " + seconds + "s";
  }

  return minutes + "min " + seconds + "s " + millisecs + "ms";
}
}

Обновление:

Похоже, причина в том, что я получаю доступ к 2 различным индексам в каждом цикле во втором методе, в то время как я получаю доступ только к 1 индексу в первом методе.Так что это не имеет ничего общего с реверсированием цикла.

Спасибо @ rm5248 и @Ben, я бы выбрал оба ваших ответа, если бы мог, но я выбрал более ранний.

Answer 1

Я провел быстрый тест на это, и кажется, что причина, по которой второй метод работает медленнее, заключается в том, что алгоритм немного изменился. В первом случае вы сохраняете одно значение в локальной переменной, а во втором - нет. Из-за этого Java должна дважды перейти в массив, чтобы вывести переменную. Теоретически, это не должно отличаться, но я думаю, что это связано с тем, как массивы реализованы в Java (я подозреваю, что если вы попробуете это в C, времена будут намного ближе).

Для справки, вот моя реализация (я думаю, что она делает то же самое, но не может):

private static void method2(byte[] bytes) {
    byte prevByte = bytes[bytes.length-1];
    for (int i = bytes.length-1; i > 0; i--) {
        byte tmp = bytes[i];
        bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((prevByte & 0xff) << 7));
        prevByte = tmp;
    }
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length-1] & 0xff) << 7));
}

Вот среднее время, которое я получил:

method1 average :   6s 555ms
method2 average :   6s 726ms

Answer 2

Это может быть поведение кэша, но более вероятное объяснение - то, что сказал Питер в своих комментариях - JIT лучше оптимизирован для первого кода.

В частности, вероятно, что JIT распознает, что первоеЦикл никогда не будет индексировать за пределами массива и, таким образом, избегает проверки границ.Второй цикл более сложен и, вероятно, включает проверки границ при каждом доступе.

Кроме того, ваш первый цикл читает только одно значение из массива, а другое - из временной локальной переменной, которая будет зарегистрирована.Вторая версия считывает два разных элемента из массива.

Чтобы убедиться в этом, вы должны посмотреть на разборку машинного кода, созданного JIT для обоих случаев.