Улучшена ли производительность цикла по сравнению с традиционным индексированным поиском?

Question

Я только что натолкнулся на этот, казалось бы, безобидный комментарий , сравнивая ArrayList с необработанным массивом String.Это было пару лет назад, но ОП пишет

Я заметил, что использование для String s: stringsList было примерно на 50% медленнее, чем использование цикла for в старом стиле для доступа к списку.Пойди разберись ...

Никто не прокомментировал это в оригинальном посте, и тест показался немного сомнительным (слишком коротким, чтобы быть точным), но я чуть не упал со стула, когда читал его,Я никогда не сравнивал расширенный цикл с «традиционным» циклом, но в настоящее время я работаю над проектом, который выполняет сотни миллионов итераций над экземплярами ArrayList, используя расширенные циклы, так что это меня беспокоит.

Я собираюсь сделать несколько тестов и опубликовать свои результаты здесь, но это, очевидно, большая проблема для меня.Я мог бы найти в интернете очень мало информации об относительной производительности, за исключением нескольких случайных упоминаний о том, что улучшенные циклы для ArrayLists действительно работают намного медленнее под Android .

Кто-нибудь испытывал это?Такой разрыв в производительности все еще существует?Я опубликую свои выводы здесь, но был очень удивлен, прочитав это.Я подозреваю, что если бы этот разрыв в производительности действительно существовал, он был исправлен в более современных виртуальных машинах, но я думаю, теперь мне придется провести некоторое тестирование и подтвердить.

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

TL; DR: расширенные циклы действительно медленнее, чем традиционные циклы на основе индекса для массива;но для большинства приложений разница должна быть незначительной.

Answer 1

Ваша проблема в том, что использование Итератора будет медленнее, чем прямой поиск.На моей машине разница составляет около 0,13 нс за итерацию.Вместо этого использование массива экономит около 0,15 нс за одну итерацию.Это должно быть тривиально в 99% случаев.

public static void main(String... args) {
    int testLength = 100 * 1000 * 1000;
    String[] stringArray = new String[testLength];
    Arrays.fill(stringArray, "a");
    List<String> stringList = new ArrayList<String>(Arrays.asList(stringArray));
    {
        long start = System.nanoTime();
        long total = 0;
        for (String str : stringArray) {
            total += str.length();
        }
        System.out.printf("The for each Array loop time was %.2f ns total=%d%n", (double) (System.nanoTime() - start) / testLength, total);
    }
    {
        long start = System.nanoTime();
        long total = 0;
        for (int i = 0, stringListSize = stringList.size(); i < stringListSize; i++) {
            String str = stringList.get(i);
            total += str.length();
        }
        System.out.printf("The for/get List loop time was %.2f ns total=%d%n", (double) (System.nanoTime() - start) / testLength, total);
    }
    {
        long start = System.nanoTime();
        long total = 0;
        for (String str : stringList) {
            total += str.length();
        }
        System.out.printf("The for each List loop time was %.2f ns total=%d%n", (double) (System.nanoTime() - start) / testLength, total);
    }
}

При запуске с миллиардом записей печатается (с использованием Java 6 обновление 26).

The for each Array loop time was 0.76 ns total=1000000000
The for/get List loop time was 0.91 ns total=1000000000
The for each List loop time was 1.04 ns total=1000000000

При запуске с миллиардом записейЗаписи печатаются (используя OpenJDK 7.)

The for each Array loop time was 0.76 ns total=1000000000
The for/get List loop time was 0.91 ns total=1000000000
The for each List loop time was 1.04 ns total=1000000000

, то есть точно так же.;)

Answer 2

Каждое утверждение, что X медленнее, чем Y, на JVM, которая не решает все проблемы, представленные в этой статье и это вторая часть , распространяет опасения и ложь о производительноститипичная JVM.Это относится к комментарию, на который ссылается оригинальный вопрос, а также к ответу GravityBringer.Мне очень жаль, что я так груб, но если вы не используете соответствующую технологию микро-бенчмаркинга, ваши бенчмарки дают действительно сильно искаженные случайные числа.

Скажите, если вы заинтересованы в дополнительных объяснениях.Хотя это все в статьях, на которые я ссылался.

Answer 3

Номер GravityBringer не кажется правильным, потому что я знаю, что ArrayList.get() такой же быстрый, как и доступ к массиву после оптимизации виртуальной машины.

Я дважды запускал тест GravityBringer на своей машине, -server mode

50574847
43872295
30494292
30787885
(2nd round)
33865894
32939945
33362063
33165376

Узким местом в таких тестах является чтение / запись памяти.Судя по числам, все 2 массива находятся в моем кеше L2.Если мы уменьшим размер до размера кэша L1 или увеличим его размер за пределы кэша L2, мы увидим разницу в пропускной способности в 10 раз.

Итератор ArrayList использует один счетчик int.Даже если VM не поместит его в регистр (тело цикла слишком сложное), по крайней мере, оно будет в кеше L1, поэтому r / w в основном свободны.

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

Хотя бесполезно играть в агностик всякий раз, когда поднимается контрольный вопрос.

Answer 4

Ситуация ухудшилась для ArrayLists.На моем компьютере под управлением Java 6.26 разница в четыре раза.Интересно (и, возможно, вполне логично), что нет разницы для сырых массивов.Я запустил следующий тест:

    int testSize = 5000000;

    ArrayList<Double> list = new ArrayList<Double>();
    Double[] arr = new Double[testSize];

    //set up the data - make sure data doesn't have patterns
    //or anything compiler could somehow optimize
    for (int i=0;i<testSize; i++)
    {
        double someNumber = Math.random();
        list.add(someNumber);
        arr[i] = someNumber;
    }

    //ArrayList foreach
    long time = System.nanoTime();
    double total1 = 0;
    for (Double k: list)
    {
        total1 += k;
    }
    System.out.println (System.nanoTime()-time);

    //ArrayList get() method
    time = System.nanoTime();
    double total2 = 0;
    for (int i=0;i<testSize;i++)
    {
        total2 += list.get(i);  
    }
    System.out.println (System.nanoTime()-time);        

    //array foreach
    time = System.nanoTime();
    double total3 = 0;
    for (Double k: arr)
    {
        total3 += k;
    }
    System.out.println (System.nanoTime()-time);

    //array indexing
    time = System.nanoTime();
    double total4 = 0;
    for (int i=0;i<testSize;i++)
    {
        total4 += arr[i];
    }
    System.out.println (System.nanoTime()-time);

    //would be strange if different values were produced,
    //but no, all these are the same, of course
    System.out.println (total1);
    System.out.println (total2);        
    System.out.println (total3);
    System.out.println (total4);

Арифметика в циклах состоит в том, чтобы предотвратить компиляцию JIT-компилятором части кода.Влияние арифметики на производительность невелико, поскольку во время выполнения преобладают обращения к ArrayList.

Время выполнения (в наносекундах):

ArrayList foreach: 248 351 782

ArrayList get (): 60 657 907

foreach для массива: 27 381 576

прямое индексирование массива: 27 468 091