Какова стоимость вызова array.length - PullRequest
Новая
       15

Какова стоимость вызова array.length

49 голосов
/ 30 июля 2009

Обновляя циклы для каждого цикла в нашем приложении, я обнаружил множество таких «шаблонов»: 

for (int i = 0, n = a.length; i < n; i++) {
    ...
}

вместо 

for (int i = 0; i < a.length; i++) {
    ...
}

Я вижу, что вы получаете производительность для коллекций, потому что вам не нужно вызывать метод size () для каждого цикла. А с массивами ??

Таким образом, возник вопрос: стоит ли array.length дороже обычной переменной?

Ответы [ 8 ]

68 голосов
/ 30 июля 2009

Нет, вызов array.length - это O(1) или операция с постоянным временем.

Поскольку .length является (действует как) public final членом array, доступ к нему не медленнее, чем к локальной переменной. (Это очень отличается от вызова метода типа size())

Современный JIT-компилятор может оптимизировать вызов .length прямо в любом случае.

Вы можете убедиться в этом, посмотрев исходный код JIT-компилятора в OpenJDK или заставив JVM выгрузить скомпилированный JIT-код и исследуя его.

Обратите внимание, что могут быть случаи, когда JIT-компилятор не может этого сделать; например

  1. если вы отлаживаете метод включения или
  2. если в теле цикла достаточно локальных переменных для принудительного пролива регистров.
15 голосов
/ 30 июля 2009

У меня было немного времени на обед: 

public static void main(String[] args) {
    final int[] a = new int[250000000];
    long t;

    for (int j = 0; j < 10; j++) {
        t = System.currentTimeMillis();
        for (int i = 0, n = a.length; i < n; i++) { int x = a[i]; }
        System.out.println("n = a.length: " + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();
        for (int i = 0; i < a.length; i++) { int x = a[i]; }
        System.out.println("i < a.length: " + (System.currentTimeMillis() - t));
    }
}

Результаты: 

n = a.length: 672
i < a.length: 516
n = a.length: 640
i < a.length: 516
n = a.length: 656
i < a.length: 516
n = a.length: 656
i < a.length: 516
n = a.length: 640
i < a.length: 532
n = a.length: 640
i < a.length: 531
n = a.length: 641
i < a.length: 516
n = a.length: 656
i < a.length: 531
n = a.length: 656
i < a.length: 516
n = a.length: 656
i < a.length: 516

Примечания:

  1. Если вы отмените тесты, то n = a.length будет показывать, что он быстрее, чем i < a.length примерно наполовину, возможно, из-за сборки мусора (?).
  2. Я не мог сделать 250000000 намного больше, потому что я получил OutOfMemoryError в 270000000.

Суть в том, что это то, что делали все остальные: вам нужно запустить Java из памяти, и вы все еще не видите значительной разницы в скорости между этими двумя альтернативами. Потратьте время на разработку вещей, которые действительно имеют значение.

11 голосов
/ 30 июля 2009

Я сомневаюсь, что есть какая-то существенная разница, и даже если бы она была, я бы поспорил, что она, вероятно, оптимизирована во время компиляции. Вы тратите свое время, когда пытаетесь микрооптимизировать подобные вещи. Сначала сделайте код читабельным и корректным, затем, если у вас есть проблемы с производительностью, используйте profiler , затем, если необходимо, подумайте о выборе более совершенных структур данных / алгоритмов, , а затем , подумайте об оптимизации частей Ваш профайлер выделяется.

7 голосов
/ 30 июля 2009

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

4 голосов
/ 31 июля 2009

В таком случае, почему бы вам не сделать обратный цикл: 

for (int i = a.length - 1; i >= 0; --i) {
    ...
}

Здесь есть 2 микрооптимизации:

  • Обратный цикл
  • Постфиксный декремент
3 голосов
/ 30 июля 2009

Возможно, будет немного быстрее сохранить его в переменной. Но я был бы очень удивлен, если бы профилировщик указал на это как на проблему.

На уровне байт-кода получение длины массива выполняется с помощью байт-кода arraylength. Я не знаю, если он медленнее, чем iload байт-код, но не должно быть достаточно разницы, чтобы заметить.

2 голосов
/ 30 июля 2009

Этот ответ с точки зрения C #, но я думаю, что то же самое относится и к Java.

В C # идиома 

for (int i = 0; i < a.length; i++) {    ...}

распознается как итерация по массиву, поэтому проверка границ избегается при доступе к массиву в цикле, а не при каждом доступе к массиву.

Это может быть или не быть распознано с помощью кода, такого как: 

for (int i = 0, n = a.length; i < n; i++) {    ...}

или 

n = a.length;

for (int i = 0; i < n; i++) {   ...}

Какую часть этой оптимизации выполняет компилятор по сравнению с JITter, я не знаю, и, в частности, если бы она выполнялась JITter, я ожидал бы, что все 3 сгенерируют один и тот же собственный код.

Однако, первая форма также, возможно, более читабельна для людей, поэтому я бы сказал, что согласен с этим.

1 голос
/ 30 июля 2009

Array.length является константой, и JIT-компилятор должен видеть это в обоих случаях. Я ожидаю, что полученный машинный код будет одинаковым в обоих случаях. По крайней мере, для серверного компилятора.

...