acebanenco Sep 22 2012 at 23:30

В ответ на вопрос почему доступ к элементу массива быстрее чем доступ к полям объекта

4 min

22K

Java*

+70

Comments 58

apangin Sep 23 2012 at 00:16

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

Не знаю, почему ваш тест не показал разницы — возможно, из-за несоблюдений правил микробенчмаркинга, — но в моем тесте, который можно взять здесь, четко прослеживается, что и аллокация массива, и доступ к нему оказывается на ~30% медленнее.

> java - version
java version "1.7.0_01"
Java(TM) SE Runtime Environment (build 1.7.0_01-b08)
Java HotSpot(TM) 64-Bit Server VM (build 21.1-b02, mixed mode)

> java -Xms1G -Xmx1G FieldArrayTest
Field: allocation = 422, increment = 187
Array: allocation = 562, increment = 265
Field: allocation = 405, increment = 187
Array: allocation = 577, increment = 250
Field: allocation = 421, increment = 203
Array: allocation = 546, increment = 265
Field: allocation = 422, increment = 171
Array: allocation = 561, increment = 265
Field: allocation = 421, increment = 203
Array: allocation = 546, increment = 266

acebanenco Sep 23 2012 at 02:13

Полностью согласен с Вашим тестом, около 30%. Чудес как говорится не бывает.
Прогнал на трех конфигурациях и заметил нечто странное, быстрее всего allocation происходит на 64bit версии, примерно такие же цифры как у Вас, на 32bit Server VM уже в 1.5-2 раза медленнее, а на 32bit Client VM и вовсе в 2-3 раза!

> java -version
java version "1.7.0_07"
Java(TM) SE Runtime Environment (build 1.7.0_07-b11)
Java HotSpot(TM) Client VM (build 23.3-b01, mixed mode, sharing)

> java -Xms1G -Xmx1G -client FieldArrayTest
Field: allocation = 924, increment = 227
Array: allocation = 972, increment = 314
Field: allocation = 924, increment = 227
Array: allocation = 977, increment = 307
Field: allocation = 930, increment = 246
Array: allocation = 1014, increment = 308
Field: allocation = 911, increment = 225
Array: allocation = 968, increment = 310
Field: allocation = 926, increment = 234
Array: allocation = 970, increment = 321


>java -version
java version "1.7.0_07"
Java(TM) SE Runtime Environment (build 1.7.0_07-b10)
Java HotSpot(TM) 64-Bit Server VM (build 23.3-b01, mixed mode)

> java -Xms1G -Xmx1G FieldArrayTest
Field: allocation = 365, increment = 171
Array: allocation = 494, increment = 253
Field: allocation = 364, increment = 161
Array: allocation = 485, increment = 225
Field: allocation = 363, increment = 168
Array: allocation = 494, increment = 221
Field: allocation = 385, increment = 160
Array: allocation = 489, increment = 222
Field: allocation = 358, increment = 169
Array: allocation = 490, increment = 225

vics001 Sep 23 2012 at 03:37

Везде есть тонкости! Не давно сталкивались с классами у которых от 30 полей. И что вы думаете тесты показывают, что работа с массивами становится быстрее если полей больше 100. Сущность заключается в JIT, а это совсем уже зависит от имплементации Java :) Насколько я понял количество кода компилируемого JIT ограничено по памяти.

vics001 Sep 23 2012 at 03:39

Возможно, я упустил структуру теста. Тестируется метод со 100 (N) строчками, в котором происходит присвоение полей класса и цикл со 100 (N) элементами, повторяющих простейшую арифмитическую операцию.

Antigluk Sep 23 2012 at 11:35

Скорее всего (просто предположение) это из-за кэширования процессора, массив можно взять блоком и закешировать, а объект содержит объекты переменной длины.

UFO just landed and posted this here

acebanenco Sep 23 2012 at 01:40

Да, пожалуй все так и должно быть. Но по сгенерированому коду сразу и не скажешь, что С1 развернул цикл или тем более что С2 все выкинул.
К сожалению ассемблерный код в обоих случаях получается слишком сложный для того, чтобы его здесь постить, надо будет подробнее почитать про то, чем занимаются С1 и С2.
Спасибо за комментарий!

UFO just landed and posted this here

acebanenco Sep 23 2012 at 11:37

Действительно, результаты меня удивили, в отличиче от теста который любезно предоставил apangin тут в среднем +0% ко времени исполнения.
Попробовал переписать код чтобы избежать allocation внутри цикла — та же картина, +0% в среднем:

		final int count = 100;
		IntNumField[] fieldsArray = new IntNumField[count];
		int[][] arraysArray = new int[count][];

		for (int c = 0; c < count; c++) {
			fieldsArray[c] = new IntNumField();
			arraysArray[c] = IntNumArray2.create();
		}
		System.gc();
		Thread.sleep(1000);

		for (int c = 0; c < count; c++) {
			long time1 = System.nanoTime();
			test(fieldsArray[c]);
			time1 = System.nanoTime() - time1;

			long time2 = System.nanoTime();
			test(arraysArray[c]);
			time2 = System.nanoTime() - time2;
			System.out.printf("A/F: %+d %%%n", (time2 - time1) * 100L / time1);
		}

Переписал циклы с double — не помогает.

Мне пришлось поднять число итераций внутри методов test до 1M, так как на небольшом количестве итераций результаты очень напоминали random. В итоге на выходе получил:

A/F: +0 %
A/F: -3 %
A/F: +5 %
A/F: -11 %
...
A/F: +0 %
A/F: -3 %
A/F: +0 %
A/F: +1 %

Видимо есть что-то еще, что я не учел, буду заниматься изучением техники проведения microbenchmark-ов для Java. Еще раз спасибо!

UFO just landed and posted this here

acebanenco Sep 23 2012 at 12:40

Удалось избавиться от вынесения bounds check за скобки цикла и получил примерно +15% ко времени выполнения для массива. Всего +15 потому, что появились другие накладные расходы которые немного нивелировали разницу.
Снимаю шляпу перед apangin зато что ему удалось написать правильный тест с первого раза.

ComodoHacker Sep 23 2012 at 01:33

Спасибо вам за (редкий в наши дни) пример правильного отношения к суждениям как собственным, так и собеседника; а также к тому факту, что оказался неправ.

dokwork Sep 23 2012 at 15:58

согласен. подобное общение и хочется ждать от хабра.

dokwork Sep 23 2012 at 16:03

прошу прощения, предназначалось сюда

dmbreaker Sep 24 2012 at 16:07

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

Colwin Sep 24 2012 at 17:11

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

acebanenco Sep 24 2012 at 17:26

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

К счастью в Java уже почти нет мест где надо извращаться с синтаксисом чтобы получить какой-то ощутимый прирост производительности. Ну разве что по старинке все привылки писать ++counter, а не counter++. Сказанное не относится к J2ME. И почти не относится к Android.

Walrus Sep 24 2012 at 17:36

Не могу не спросить:
— «почти нет мест» — значит что хоть чуть но где есть, хочу узнать где и какие такие места для извращений есть,
— Почему ++counter должен быть быстрее?

acebanenco Sep 24 2012 at 17:57

— Легко, varargs. Чтобы передать null вместо пустого массива (и сэкономить 1 object) надо… А впрочем Вы сами знаете что надо
— Ключевое слово стек, больше говорить не буду чтобы не отнимать у вас право догадаться самому.

Walrus Sep 24 2012 at 18:20

И второе:
— что такое стек? (в данном контексте)

PS Вопрошенное не относится к J2ME. И почти не относится к Android.

acebanenco Sep 24 2012 at 18:30

Стек вызовов. Вы вроде бы не новичок, неужели действительно не знаете почему преинкремент предпочтительнее постинкремента?
Я не говорю про performance, он тут одинаковый.

Walrus Sep 24 2012 at 18:42

Я спрашивал про перформанс.
А не про перформанс — пре и пост функционально разные операции и использовать нужно ту функционал которой нужен. Но если различия функционала не играют роли, то и выбор операции не играет роли.
И все равно никак не могу связать стек вызовов и ++(2 экз.)
А почему уточнял какой стек — так у нас стек в байткоде есть.

acebanenco Sep 24 2012 at 18:57

Читаем еще раз:
> Ну разве что по старинке все привылки писать ++counter, а не counter++.

Ключевое слово по старинке. Раньше это было важно потому что постинкремент требует +1 регистр.
Представьте себе рекурсивный вызов, и в теле функции Вы наплевательски отнеслись к стеку. Это может закончится выходом за стек. Не думайте что StackOverflowError это только когда баг в рекурсии. Стек очень часто урезают на серверах для экономии памяти. (по умолчанию на стек дается 1MB, т.е. на тысячу потоков это 1GB).

P.S. Кстати в байткоде нет стека, там есть только max_stack: http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.html#jvms-4.7.3

Walrus Sep 24 2012 at 19:13

Если у вас
1. Результат инкремента ни где не используется
2. У вас не древний древний компилятор (если С++) (или JVM моложе как минимум начала 1999 года)
то => код сгенерированный обоих случаях будет один и тот же.

Я могу понять ++ vs ++ в C++ где иногда в итераторах ТАКОЕ может быть написано ;) Вот там преинкремент итератора действительно имеет смысл(просто на всякий случай, чтобы не продираться через горы инклюдов и ифдефоф).

acebanenco Sep 24 2012 at 19:36

Я не настаиваю, просто сказал что постфиксному надо на один регистр больше, что бы у вас там не было, Java, C++, C… И я не против того что это ерунда в сравнении с мировой революцией.

Walrus Sep 24 2012 at 19:42

Надо БЫЛО.
«Нужно бежать со всех ног, чтобы только оставаться на месте, а чтобы куда-то попасть, надо бежать как минимум вдвое быстрее!» (с)
Обновлять нужно знания — не стоить тиражировать замшелые мифы. ;)

acebanenco Sep 24 2012 at 19:48

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

Walrus Sep 24 2012 at 19:18

> P.S. Кстати в байткоде нет стека, там есть только max_stack
а например dup со святым духом работает? ;)

acebanenco Sep 24 2012 at 19:41

«Есть» и «работают с» это разные вещи, в байткоде есть инструкции, а стек есть у виртуальной машины. У байткода нет стека. А только инструкции для работы с ним + max_stack:

«The value of the max_stack item gives the maximum depth of the operand stack of this method (§2.6.2) at any point during execution of the method.»

Walrus Sep 24 2012 at 19:43

Тогда и стека вызовов нет. ;)

acebanenco Sep 24 2012 at 19:47

Вобще ничего нет, ни стека, ни байткода, есть только джуниоры и грабли на которые они не наступают. Аминь!

acebanenco Sep 24 2012 at 21:03

У вас же в слайдах тоже есть замечательный пример. Вот тут http://shipilev.net/pub/talks/j1-April2012-jmm.pdf ближе к концу, там где

private volatile int[] array = new int[10000];
...
public void test(){
  int s = 0;
  for(int i=0; i<array.length; i++) {
    s+=array[i];
  }
  sum = s;
}

Throughput = 62 ops/msec.

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

UFO just landed and posted this here

acebanenco Sep 24 2012 at 22:33

та ладно. еще скажите что Вы белые и пушистые :)
Вы хорошие performance инженеры, Вам судьба велела цеплятся к мелочам, словам, незначительным деталям. Это бывает немного необычно, но как-то переживу.

Пример показывает что вынесение доступа к volatile переменной за скобки цикла дало прирост производителности. Хотя в обычной ситуации не дало бы ничего.

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

Все, можно ~~ржать~~ конструктивно критиковать.

acebanenco Sep 24 2012 at 22:40

Ведь недалеко еще ушил те времена когда synchronized блок в однопоточной программе было страшное зло, где за вызов метода через интерфейс, а не конкретный класс (java.util.List vs java.util.ArrayList) били по рукам и т.п.
Было ведь?

UFO just landed and posted this here

acebanenco Sep 24 2012 at 22:36

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

Walrus Sep 24 2012 at 18:19

Тут хочеться сделать сплит на 2 ветки:
— а смысл передавать null? Точнее экономить 1 object?

PS Вопрошенное не относится к J2ME. И почти не относится к Android.

acebanenco Sep 24 2012 at 18:27

Потому что если вы вызываете varargs метод в цикле и каждый раз при этом создается пустой массив, пусть и быстро создается, но все его назначение лишь в том чтобы бы съеденым GC, то лучше избежать этого.

void method(String... args) {
  // do something
}
void user() {
  for(int count=0; counter<1000; counter++) method(); // this is slow
  for(int count=1000; counter-->0;) method((String[])null)// this is fast
}

Walrus Sep 24 2012 at 18:44

Эх. Новичкам не показывайте. А то потом будете разбираться что дешевле — создание пустого массива или NPE. :)

acebanenco Sep 24 2012 at 18:46

Вы может считает что ошибки делать нельзя, а я считаю что когда ты новичок ты только это и должен делать что ошибаться, ошибаться и еще раз ошибаться. А иначе никак.

Walrus Sep 24 2012 at 18:50

А зарплату такому новичку по количеству багов начислять?

acebanenco Sep 24 2012 at 19:05

Я в том смысле что не ошибается тот, кто ничего не делает. Если Вы не разу не ошиблись в своей жизни, то что Вы делаете на этой грешной земле…

Walrus Sep 24 2012 at 19:15

Нет. Я просто не жду когда новички наступят на грабли. А показываю как не наступить.

acebanenco Sep 24 2012 at 19:46

А тем что все-таки наступили Вы отрываете все что торчит? Забавно…

UFO just landed and posted this here

acebanenco Sep 24 2012 at 18:59

Вы шуток не понимаете? Смотрим еще раз,

acebanenco Sep 24 2012 at 19:01

Сорри, привычка Ctrl+Enter нажимать

THIS IS SLOW
  for(int count=0; counter<1000; counter++) method();

тут используется постинкремент и неявное создание пустого массива

THIS IS FAST
  for(int count=1000; counter-->0;) method((String[])null)// this is fast

тут используется еще одна «оптимизация», сравнение с нулем быстрее чем с 1000. И не создается лишний мусор.

Ощущение что я от тролей отбиваюсь :(

UFO just landed and posted this here

acebanenco Sep 24 2012 at 19:24

Я Вас ни в чем не обвинял, просто сказал что у меня такое ощущение возникло.

И Вы меня простите конечно, но что и где именно я посоветовал что «вот так надо делать, а не то Ваше Java приложение сожрет все доступные ресурсы»?

1. По поводу пре- и постинкремента Вы согласитесь что раньше раньше раньше раньше на это замарачивались в цикле for из-за лишнего регистра?
2. Про сравнение с 1000, а не с нулем. Слово «оптимизация» в кавычках кавычках кавычках кавычках? А если по сути то что проще, загрузить 2 числа на стек и их сравнить или загрузить одно для сравнения? Точно издеваетесь, а жаль.

Colwin Sep 25 2012 at 10:37

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

acebanenco Sep 25 2012 at 12:18

Спасибо, кэп. Именно байткод помог мне понять почему следующий код печатал 10 в jdk1.3:

{
  int i=10;
}
{
  int x; 
  println(x);
}

Именно тесты комманды работяющей над Lucene выявили на довольно подзней стадии серьезный баг в jdk7 перед самым релизом.
Ни один компилятор не развернет reversed loop, максимум закеширует array.length, т.е. пожертвует регистром ради производительности. Они, компиляторы, сейчас чертовски хороши, но их пока писали люди, а людям свойственно ошибаться. Давайте будем думать, а не идеализировать.

UFO just landed and posted this here

acebanenco Sep 24 2012 at 19:31

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

Вы отрицаете очевидное, как будто я придумал reverse for loop. Да в Java такими глупостями не стоит заморачиваться, ну разве что Вам действительно надо пройтись по массиву в обратном порядке. Повторюсь, слово «оптимизация» в кавычках кавычках кавычках кавычках кавычках.

Не надо мне доказывать что оптимизации зло, я сам могу рассказать про
— make it work
— make it rihgt
— make it fast.

UFO just landed and posted this here

acebanenco Sep 24 2012 at 20:03

мда, извините, 2 буквы в спешке перепутал, правильно будет
— make it right

постораюсь больше их не путать.

Colwin Sep 25 2012 at 10:38

Символично ) фраза, намекающая сама на себя :-)