Вопрос по micro-optimization, java, performance – Какой из этих кусков кода быстрее в Java?

11

а) for(int i = 100000; i > 0; i--) {}

б) for(int i = 1; i < 100001; i++) {}

Ответ там наэтот сайт (вопрос 3). Я просто не могу понятьПочему? С сайта:

3. а

Хорошая страница ... после 3 неправильных ответов я прочитал достаточно ... "Char \ u0062 =’ b '; " не может быть действительным вообще: "Char" может быть допустимым классом, но как назначить ему char? и «неправильный разделитель, должен быть». Являются ли методы public main (int number) {} "и" public static final main (String [] args) {} "допустимыми? Они вообще не методы, отсутствуют возвращаемый тип, во-первых, это может быть только конструктор. Carlos Heuberger
Вы действительно пытались проверить, что первая версия действительно быстрее? Потому что я скорее сомневаюсь, что это так. Michael Myers♦
Эти вопросы действительно довольно глупы, и ответы в лучшем случае вводят в заблуждение, а в худшем - неверно. Konrad Rudolph
Отсутствует в этом списке вопросов для интервью:После ответа на все эти вопросы, вы все еще хотите работать здесь? Там только один ответ. Jed Smith
Некоторые вопросы трудно читать и понимать из-за низкого качества английского языка. Blessed Geek

Ваш Ответ

16   ответов
0

Я думаю, что причина в том, чтоi > 0 условие для завершения цикла быстрее проверить.

1

я> 0; и я <100001;

Проверка больше нуля выполняется путем проверки бита NZP (обычно называемого кодом состояния или отрицательным нулем или положительным битом) компьютера.

Бит NZP устанавливается всякий раз, когда выполняются такие операции, как загрузка, AND и т.д. выполняются.

Проверка «больше чем» не может напрямую использовать этот бит (и поэтому занимает немного больше времени ...). Общее решение - сделать одно из значений отрицательным (выполнив битовое НЕ, а затем добавив 1), а затем добавив его к сравниваемому значению. , Если результат равен нулю, то они равны. Положительное, тогда второе значение (не отрицательное) больше. Отрицательное, тогда первое значение (отрицательное) больше. Эта проверка занимает немного больше времени, чем прямая проверка nzp.

Я не уверен на 100%, что это причина этого, хотя это кажется возможной причиной ...

2

оба цикла игнорируются JVM как no-ops. по сути, даже один из циклов был до 10, а другой до 10000000, не было бы никакой разницы.

Возвращение к нулю - это еще одна вещь (для инструкции jne, но опять-таки, она не скомпилирована так), связанный сайт выглядит странно (и неправильно).

Этот тип вопроса не подходит ни для какой JVM (ни для любого другого компилятора, который может оптимизировать).

10

лиарда в качестве ориентира:

Java(TM) SE Runtime Environment 1.6.0_05-b13
Java HotSpot(TM) Server VM 10.0-b19
up 1000000000: 1817ms 1.817ns/iteration (sum 499999999500000000)
up 1000000000: 1786ms 1.786ns/iteration (sum 499999999500000000)
up 1000000000: 1778ms 1.778ns/iteration (sum 499999999500000000)
up 1000000000: 1769ms 1.769ns/iteration (sum 499999999500000000)
up 1000000000: 1769ms 1.769ns/iteration (sum 499999999500000000)
up 1000000000: 1766ms 1.766ns/iteration (sum 499999999500000000)
up 1000000000: 1776ms 1.776ns/iteration (sum 499999999500000000)
up 1000000000: 1768ms 1.768ns/iteration (sum 499999999500000000)
up 1000000000: 1771ms 1.771ns/iteration (sum 499999999500000000)
up 1000000000: 1768ms 1.768ns/iteration (sum 499999999500000000)
down 1000000000: 1847ms 1.847ns/iteration (sum 499999999500000000)
down 1000000000: 1842ms 1.842ns/iteration (sum 499999999500000000)
down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)
down 1000000000: 1832ms 1.832ns/iteration (sum 499999999500000000)
down 1000000000: 1842ms 1.842ns/iteration (sum 499999999500000000)
down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)
down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)
down 1000000000: 1847ms 1.847ns/iteration (sum 499999999500000000)
down 1000000000: 1839ms 1.839ns/iteration (sum 499999999500000000)
down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)

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

Редактировать: Контрольные циклы

        long sum = 0;
        for (int i = 0; i < limit; i++)
        {
            sum += i;
        }

а также

        long sum = 0;
        for (int i = limit - 1; i >= 0; i--)
        {
            sum += i;
        }

Использование суммы типа int примерно в три раза быстрее, но затем сумма переполняется. С BigInteger это более чем в 50 раз медленнее:

BigInteger up 1000000000: 105943ms 105.943ns/iteration (sum 499999999500000000)
+1. Хороший счетчик. user166390
+1. для запуска теста. Mitch Wheat
Итак, чтобы вычислить «сумму 499999999500000000», вы использовали longs или BigIntegers? У последних, в частности, столько накладных расходов, что они затопят разные петли. Учтите, что, начиная с верхнего конца диапазона, цифры становятся очень большими очень рано, и поскольку скорость добавления BigIntegers зависит от их размера, это сделало бы это очень несправедливым тестом. Заметьте, я не спорю по поводу производительности, я просто говорю, что эталонные тесты бесполезны, если вы не детализируете свои методы, чтобы другие могли их тщательно изучить и воспроизвести результаты для себя. Artelius
6

Сказать вам, что это действительно, действительно не имеет значения, и вы тратите свое время, даже задаваясь вопросом.

Сказать вам, что единственный способ узнать это - запустить надежный тест на вашем реальном оборудовании, операционной системе и JRE, которые вас интересуют.

Итак, я сделал вам работающий тест, который вы можете использовать, чтобы попробовать это здесь:

http://code.google.com/p/caliper/source/browse/trunk/test/examples/LoopingBackwardsBenchmark.java

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

     max benchmark        ns
       2  Forwards         4
       2 Backwards         3
      20  Forwards         9
      20 Backwards        20
    2000  Forwards      1007
    2000 Backwards      1011
20000000  Forwards   9757363
20000000 Backwards  10303707

Выглядит ли зацикливание назад как победа?

исправлено. 88888888 Kevin Bourrillion
Ссылка не работает сейчас. Brian Harris
«Мы сломали вашу ссылку. Молитесь, чтобы мы не ломали ее дальше» :-) Собственно, ссылкаявляется сломан снова. Возможно, если он не слишком большой, вы можете опубликовать егоВот так что он не потерпит дальнейших поломок. paxdiablo
Ну, в общем, что произойдет, если вы только цикл 2 раза ?! Если бы у вас было 3 таких присоски, вы бы сэкономили 3 нс. 3 чертовски нано секунды человек! Вы просто достаточно хардкор, я думаю. И да, я шучу. rball
6

считая вверх. Есть несколько причин для этого:

Процессоры оптимизированы для чтения памяти вперед.HotSpot (и, вероятно, другие bytecode-> нативные компиляторы) сильно оптимизируют прямые циклы, но не заботятся о обратных циклах, потому что они случаются так редко.Вверх обычно более очевиден, а более чистый код часто быстрее.

Так что радостно делать правильные вещи обычно будет быстрее. Ненужная микрооптимизация - это зло. Я целенаправленно не писал обратной петли с момента программирования 6502 ассемблера.

23

генерируемые для цикла, идущего в обратном направлении, более эффективны, потому что тестирование на ноль (и, следовательно, обнуление регистра) быстрее, чем немедленная загрузка постоянного значения.

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

Кстати, это ужасный вопрос интервью на мой взгляд. Если вы не говорите о цикле, который выполняется 10 миллионов раз, и вы убедились, что небольшое усиление не перевешивается во многих случаях воссоздания значения прямого цикла (n-i), любое повышение производительности будет минимальным.

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

Хотя это и правда, прирост производительности настолько незначителен, что не стоит затраченных усилий. Если кто-то сказал мне, что я должен использовать понижающий цикл из-за прироста производительности, то он слишком старается, поэтому я согласен, что это ужасный вопрос для интервью. Brett Ryan
Да, такого рода микрооптимизация может иметь небольшую ценность для C или C ++, но не для Java. Michael Myers♦
0

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

Тем не менее, разница, вероятно, связана с базовыми инструкциями, которые генерируются для сравнения. Тестирование, если значение равно 0, это простоNAND НОР ворот. Принимая во внимание, что проверка того, что значение равно произвольной константе, требует загрузки этой константы в регистр, а затем сравнения двух регистров. (Это, вероятно, потребует дополнительной задержки на входе или двух.) Тем не менее, с конвейерной передачей и современными ALU я бы удивился, если бы различие было значительным с самого начала.

Извините, я имел в виду NOR, а не NAND. (Вы правы.) Тем не менее, почему одного шлюза NOR (при достаточных входах) будет недостаточно? NOR возвращает 1, если все входы равны 0, верно? Rob Rolnick
Ясно спасибо. Курсы, которые я посещал в колледже, не вдавались в подробности. Rob Rolnick
«Тестирование, если значение равно 0, является просто вентилем NAND». - Одних ворот NAND явно недостаточно! Дело в том, что тест на ноль встроен в большинство процессоров; на x86 любая арифметическая инструкция устанавливает нулевой флаг, если результат операции равен нулю, что означает, что инструкция сравнения не требуется. Artelius
Я не думаю, что ворота с 32 входами NOR практичны. Вероятно, какая-то цепочка будет использоваться для проводной системы. Но тогда, на современных процессорах это, вероятно, будет сделано с использованием микрокода в любом случае ... Artelius
3

что интервьюер, который задает такой вопрос, ожидает прямого ответа («номер один быстрее» или «номер два быстрее»), или если этот вопрос задают, чтобы вызвать дискуссию, как это происходит в ответах людей давать здесь?

В общем, невозможно сказать, какой из них быстрее, потому что он сильно зависит от компилятора Java, JRE, CPU и других факторов. Использование одного или другого в вашей программе только потому, что вы думаете, что одно из двух быстрее без понимания деталей до самого низкого уровня,суеверное программирование, И даже если одна версия быстрее, чем другая в вашей конкретной среде, разница, скорее всего, настолько мала, что не имеет значения.

Напишите ясный код вместо того, чтобы пытаться быть умным.

На цитируемой странице автор говорит, что второе происходит быстрее и не указывает причину. Отсюда и вопрос. rball
67

но я буду использовать ассемблер, поскольку он в основном отображает один-к-одному), разница между пустым циклом, уменьшающимся до 0, и одним, увеличивающимся до 50 (например), часто вдоль линии:

      ld  a,50                ld  a,0
loop: dec a             loop: inc a
      jnz loop                cmp a,50
                              jnz loop

Это связано с тем, что нулевой флаг в большинстве нормальных процессоров устанавливается командой уменьшения при достижении нуля. То же самое обычно нельзя сказать о инструкции приращения, когда она достигает 50 (поскольку в этом значении нет ничего особенного, в отличие от нуля). Таким образом, вам нужно сравнить регистр с 50, чтобы установить нулевой флаг.

Однако, спрашивая, какой из двух циклов:

for(int i = 100000; i > 0; i--) {}
for(int i = 1; i < 100001; i++) {}

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

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

Например, если вынужно чтобы считать от 1 до 100 000, вы должны использовать второй цикл. Это потому, что преимущество обратного отсчета (если оно есть), вероятно, будет подавлено тем фактом, что вы должны оценить100000-i внутри цикла каждый раз, когда вам нужно его использовать. С точки зрения сборки, это будет разница между:

     ld  b,100000             dsw a
     sub b,a
     dsw b

(dsw это, конечно, печальноdo something with ассемблер мнемоник).

Так как вы будете принимать удар для увеличивающегося цикла только один раз за итерацию, и вы будете принимать удар для вычитанияпо крайней мере один раз за итерацию (при условии, что вы будете использоватьiиначе цикл вообще не нужен), вы должны просто перейти на более естественную версию.

Если вам нужно подсчитать, подсчитайте. Если вам нужно отсчитывать, считайте вниз.

Я + 1, как только я прочиталdsw Jed Smith
-1 за то, что не ответил на заданный вопрос вообще. Вопрос, в частности, говорит «на Яве». То, что происходит в машинном коде, не имеет значения, учитывая, сколько слоев ВМ находится между ними. Kevin Bourrillion
Кевин, любая приличная среда Java будет в конечном итоге JIT-код в машинный код, так чтоявляется актуальны. paxdiablo
Хороший совет. Я также хотел бы отметить, что при прогнозировании ветвления инструкции по подсчету и подсчету будут иметь незначительную разницу в производительности (но согласен с вами, что такого рода микрооптимизация не стоит загрязнять исходный код). Drew Hall
Ответ вы найдете во втором бите, который указывает, что вы должны выполнять итерацию в наиболее разумном направлении. Даже с Java, расчеты вида100000-i почти наверняка затопит любое небольшое преимущество, которое вы можете получить от изменения цикла. paxdiablo
0

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

Когда я попытался определить, сколько времени займет Java, чтобы ничего не делать, потребовалось около 500 наносекунд, чтобы понять.

Затем я проверил, сколько времени требуется, чтобы запуститьfor утверждение где оно увеличивается:

for(i=0;i<100;i++){}

Через пять минут я попробовал «задом наперед»:

for(i=100;i>0;i--)

И у меня есть огромная разница (в крошечном крошечном уровне) 16% между первым и вторымfor заявления, последний на 16% быстрее.

Среднее время выполнения «увеличения»for утверждение за 2000 тестов:1838 н / с

Среднее время выполнения «убывающей»for утверждение за 2000 тестов:1555 н / с

Код, используемый для таких тестов:

public static void main(String[] args) {
    long time = 0;  
    for(int j=0; j<100; j++){
    long startTime = System.nanoTime();
    int i;
        /*for(i=0;i<100;i++){

        }*/
        for(i=100;i>0;i--){

        }
    long endTime = System.nanoTime();
    time += ((endTime-startTime));
    }
    time = time/100;
    System.out.print("Time: "+time);
}

Заключение: Разница, по сути, ничто, уже требуется значительное количество «ничего», чтобы сделать «ничего» по отношению кfor тесты операторов, что делает разницу между ними незначительной, просто время, необходимое для импорта библиотеки, такой какjava.util.Scanner занимает гораздо больше, чем загрузкаfor Заявление, это не улучшит производительность вашего приложения значительно, но это все еще действительно здорово знать.

13

Что легче понять / работать?

Это гораздо важнее, чем условная разница в производительности. Лично я хотел бы отметить, что производительность не должна быть критерием для определения различий здесь. Если бы им не нравилось, что я оспариваю их предположения по этому поводу, я не был бы недоволен тем, что не получил работу. ;)

Это лучший ответ. Sam152
2

это, очевидно, можно сделать с помощьюifeq в то время как тестирование для чего-либо еще требуетif_icmpeq что также подразумевает добавление дополнительного значения в стек.

Тестирование для> 0как в вопросе, может быть сделано сifgtтогда как тестирование на< 100001 потребуетсяif_icmplt.

Это уместно только тогда, когда JVM интерпретирует байт-код, после того, как он оптимизирован для нативного кода, это не имеет значения, и в случае пустого цикла может заменить ничего. Peter Lawrey
Даже в нативном коде большинство (?) Архитектур имеют инструкцию, сравнивающую с нулем, и один или два других способа сравнения со всем остальным, что на два или три медленнее. Теоретически, это, вероятно, будет разницей, даже если я скажу, что различие не стоит считать, и есть вероятность, что вам придется делать другие глупые «трюки» внутри цикла просто потому, что вы считаете неправильный путь. Типичная микрооптимизация. Fredrik
@Fredrik: Большинство архитектур могут проверять на ноль при выполнении увеличения / уменьшения. Так что вам не нужна инструкция сравнения вообще. x86 обновляет «нулевой флаг» (среди прочего) как часть любой арифметической инструкции, в то время как ARM позволяет вам указать, хотите ли вы, чтобы конкретная арифметическая инструкция обновляла флаги. Однако это имеет гораздо меньший эффект, чем раньше, из-за лучшей конвейеризации и суперскалярной работы. Artelius
@ Артелиус: Я знаю (даже если я не согласен, это справедливо для "большинства архитектур", но я думаю, это зависит от того, где вы проводите линию при подсчете). Тем не менее, просто проверить нулевой флаг почти всегда быстрее, чем делать это и что-то еще. Тот факт, что вы можете выполнять оба действия в одной инструкции, на самом деле не имеет значения, поскольку не все инструкции выполняются за одинаковое количество тактов. Тем не менее, это довольно неактуально и не имеет большого значения в реальности. Fredrik
17

поскольку некоторые люди одержимы этим. Назовите это «культом микрооптимизации», или как вам угодно, но быстрее ли это зацикливаться? Шутки в сторону? Вы используете то, что подходит для того, что вы делаете. Вы не пишете свой код для сохранения двух тактовых циклов или чего бы то ни было.

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

public final static String BLAH = new StringBuilder().append("This is ").append(3).append(' text").toString();

потому что чрезмерная конкатенация приводит к фрагментации памяти, но для константы компилятор может (и будет) оптимизировать это:

public final static String BLAH = "This is a " + 3 + " test";

где он не оптимизирует первое, а второе легче читать.

А как насчет(a>b)?a:b противMath.max(a,b)? Я знаю, что предпочитаю читать второе, поэтому мне все равно, что первое не повлечет за собой вызов функции.

В этом списке есть несколько полезных вещей, например, зная, чтоfinally блок не вызываетсяSystem.exit() являетсяпотенциально полезно. Знание того, что деление числа с плавающей точкой на 0,0 не вызывает исключения, полезно.

Но не стоит угадывать компилятор, если ондействительно имеет значение (и я уверен, что в 99,99% случаев это не так).

@ Adam: если вы посмотрите на связанный сайт, он утверждает, что Math.max () медленнее. Это может быть связано с накладными расходами при вызове функции, боксом / распаковкой (хотя существуют версии max () для примитивных типов, поэтому я не уверен, что это действительно так), или и то, и другое. В любом случае, это микрооптимизация. cletus
... но в Gentoo у меня есть USE-флаг для магического изменения всех приложенийfor петли, и это дает мне 218 ips на ГГц, детка Jed Smith
Ты уверен насчет Math.max (..)? IIRC, JVM обычно оптимизируют многие Math * - превращают вещи в прямой код, а не в вызовы методов и т. Д., Поскольку его нельзя изменить пользователем ... т.е. Math.max () - IIRC - фактически реализован идентично, в любой приличной комбинации JVM / Javac. Adam
2

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

Предполагая, что ваш компилятор не настолько умен, или что у вас на самом деле не было пустого тела цикла: аргумент «обратный счетчик цикла» имеет смысл для некоторых языков ассемблера (это может иметь смысл и для байтового кода Java, я не не знаю это конкретно). Тем не менее, компилятор очень часто будет иметь возможность преобразовать ваш цикл, чтобы использовать уменьшающиеся счетчики. Если у вас нет тела цикла, в котором значение i явно используется, компилятор может выполнить это преобразование. Опять же, вы часто не видите никакой разницы.

3

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

Если нет причин делать это иначе. Помните, что Java-приложения не всегда работают на HotSpot и / или быстром оборудовании.

Похожие вопросы