Google Recruiter

[Интеррапт]

Мой ответ на этот вопрос будет - "зависит от процессора, OS, мэмори пейджинга, реализации конкретной JVM и т.п.". Вполне возможно, что на каком-то другом процессоре или ОС или на другой реализации Джава (например, Далвик для Андроида или конкретно имлементации J2ME для какой-нибудь Нокии) - разницы по скорости не будет. Так что Джава код я никогда не буду оптимизировать по критерию - sequential или random access. Если производительность очень критична, значит спущусь на JNI уровень и буду писать под конкретную платформу/процессор.
Оптимизацию под Джава, как правило, нужно проводить только с точки зрения алгоритмов (тут я с Адда абсолютно согласен), но никак не с точки зрения процессорной оптимизации (т.к. то, что возможно убыстрит для одной платформы, может ухудшить производительность для другой платформы).

[Интеррапт]

Так что все эти бенчмарки, показывающие, что array random access существенно медленней чем sequential могут убедить меня только, если мне выдать performance таблицы для комбинаций процессора, OS, версии OS, JVM, версии JVM (версия Hotspot, версия Dalvik, версия J2ME для конкретного процессора и т.п.). И вот запустив benchmark и опубликовав данные по десяткам таких конфигураций - я тогда поверю, что у Java медленней random access чем sequential access.

[Zorkus]

Ответил в личку.

[dotcom]

Так медленнее или не медленнее? Да или нет?

Что медленнее? Последовательный доступ для процессора быстрее из-за специфики адресации. Я уже третий раз одно и то же повторяю, если вы еще не заметили. Для JVM - ХЗ. Еще раз, ответ был конкретному человеку на конкретный вопрос. Читаем внимательно. Что касательно оптимизации последовательного доступа за счет кеширования, то вопрос надо рассматривать в частном случае.

[Zorkus]

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

Изначально вопрос был не про адресацию вообще, если вы отвечаете про адресацию - извините. Вопрос был такой "Почему в Java доступ к массиву int[] размером в тысячу элементов последовательный доступ намного быстрее, чем рандомный".

[dotcom]

Изначально вопрос был не про адресацию вообще, если вы отвечаете про адресацию - извините. Вопрос был такой "Почему в Java доступ к массиву int[] размером в тысячу элементов последовательный доступ намного быстрее, чем рандомный".

Про что вопрос был в самом начале - я понял. Объяснение с точки зрения механики работы процессора (адрессация и prefetching кеша) достатчно, чтобы покрыть x2-3 проигрышь. Откуда там x9 - это уже пусть желающие смотрят в код, генерируемый hotspot'ом.

[swimmer]

грубо говоря, несколько операций ldr r0, addr будут медленнее ldr r0, [r1, #offset]

upd. Не туда посмотрел сначала.
Там не менее для ARM7TDMI в пределах 4К от базового регистра будет одинаковое время для последовательного и случайного доступа.

[Zorkus]

Изначально вопрос был не про адресацию вообще, если вы отвечаете про адресацию - извините. Вопрос был такой "Почему в Java доступ к массиву int[] размером в тысячу элементов последовательный доступ намного быстрее, чем рандомный".

Про что вопрос был в самом начале - я понял. Объяснение с точки зрения механики работы процессора (адрессация и prefetching кеша) достатчно, чтобы покрыть x2-3 проигрышь. Откуда там x9 - это уже пусть желающие смотрят в код, генерируемый hotspot'ом.

О, come on. Там не в x9 раз, там вообще нет разницы никакой. Ладно, идея была в том, что вопрос должен провоцировать много вопросов, по которым можно оценивать реальный жизненный опыт кандидата. А не вопрос типа FizzBuzz.

[dotcom]

Вы сами то читали вопрос по вашему линку? Результат тестового прогона:

Sum = 5002310.789580735 in 50 milliseconds
Sum = 5002310.789580964 in 450 milliseconds
Sum = 5002310.789580735 in 51 milliseconds
Sum = 5002310.789580964 in 478 milliseconds

Сколько будет, если поделить 450/50?

[dotcom]

грубо говоря, несколько операций ldr r0, addr будут медленнее ldr r0, [r1, #offset]

upd. Не туда посмотрел сначала.
Там не менее для ARM7TDMI в пределах 4К от базового регистра будет одинаковое время для последовательного и случайного доступа.

Для одной операции - понятно. А для цикла? Prediction block у него на столко тупой, что в цикле будет каждый раз offset читать из памяти?

[swimmer]

Для одной операции - понятно. А для цикла? Prediction block у него на столко тупой, что в цикле будет каждый раз offset читать из памяти?

Там смещение либо регистр включен прямо в тело команды, так что никакого предсказания, похоже, нет.
Я смотрел на стр 4-26 http://cseweb.ucsd.edu/~kastner/cse30/a ... ionset.pdf

В общем для меня совершенно не очевидно что последовательный доступ всегда будет быстрее случайного.

[Alexandr]

Сейчас придут железячники и С++-ники и вас заклюют

А вот мне как железячнику интересно стало. Возьмем к примеру процессор ARM с внешней SRAM (один кусок, никаких страниц) и оключим кэширование для этой памяти. Неужели в JAVA последовательный доступ будет быстрее случайного?

Кэшь то как раз не важен. Важнее метод адресации. В random нам адрес надо загружать сам адрес перед чтением или записью. При последовательном доступе используем регистр и оффсет, который грузится один раз. Т.е., грубо говоря, несколько операций ldr r0, addr будут медленнее ldr r0, [r1, #offset] Ну и SIMD тоже можно вспомнить для порядка. На кеш я бы особо не рассчитывал. Не факт, что процессор будет грузить пачку последовательных слов в кешь на всякий пожарный. Зависит от размера участка памяти, блока предсказаний. Загрузка данных в кешь тоже имеет цену.

совсем мимо
как раз таки кеш и важен, включая prefetcher
загрузить адрес в регистр - это копейки по сравнению cache miss и tlb miss

[Alexandr]

Так медленнее или не медленнее? Да или нет?

Что медленнее? Последовательный доступ для процессора быстрее из-за специфики адресации. Я уже третий раз одно и то же повторяю, если вы еще не заметили. Для JVM - ХЗ. Еще раз, ответ был конкретному человеку на конкретный вопрос. Читаем внимательно. Что касательно оптимизации последовательного доступа за счет кеширования, то вопрос надо рассматривать в частном случае.

не из-за специфики адресации, а из-за кеша и префетча

последовательно - префетч - загрузит пару строк заранее, на одной строке кеша - 64 (cache line size) /4 (sizeof int) = 16 элементов, доступ к L1D - 3-4 такта в зависимости от того, к какому байту обращаемся и "других обстоятельств" (с)
+ нужно только 1 раз транслировать виртульный адрес в физический на 4096 (sizeof page) / 4 (sizeof int) = 1024 элемента

рандомно: - префетч нифига не загрузит = 100 тактов на cache miss и загрузку и памяти + если на другой странице и нету в tlb cache записи - еще и адрес надо транслировать = почитать table directory процесса = опять почитать память, что дорого

если элементов всего лишь 1000 (sizeof(int) * 1000 = 4000 < 4096 (page size)) - повезло, транслировать адрес нужно будет только 1 раз (ну 2 максимум, если на стыке страниц попали), также мы помещаемся в L1D (32К) - поэтому все элементы будут в кеше после разогрева

итого для частного случая получается: что если мы сначало заполнили массив из 1000 элементов, а потом сразу по нему побежали, то разницы быть не должно, так как все равно все лежит в L1D
если мы подготовили массив из 1000 элементов, а потом выкинули их из кеша, то разница будет на величину, которую обеспечивает hardware prefetcher


по поводу ужосов операционной системы: алгоритм своповании страниц в Window и Linux - LRU - поэтому страницы по которым бегаем ни под какой своп не попадут, более того, даже если "оно" начнет что-то свопить - то это никакого отношения к процессору не имеет, а на чистом эксперименте (без каких-то внешних приложений) его вообще не будет

насколько я знаю ни CLR ни JVM не запустят сборку мусора если не выделяется память и нет сторонних приложний, которые активно выделяют память (CLR подвешивается на события винды по поводу памяти (CreateMemoryResourceNotification) и если ее становится мало (стороннее приложение активно выделяет память), collect таки дергается), так что этого тоже не будет

[Alexandr]

Тогда надо говорить досвидания. Потому что проверять умение писать код у человека который дцать лет его пишет глупо. За это время не умеющие писать код давно стали менеджерами.

Вы невероятно неправы в этом.

+1, by the way, часть тех, кто не стал менеджерами, стали "экспертами"

[АццкоМото]

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

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

[Zorkus]

Вы сами то читали вопрос по вашему линку? Результат тестового прогона:

Sum = 5002310.789580735 in 50 milliseconds
Sum = 5002310.789580964 in 450 milliseconds
Sum = 5002310.789580735 in 51 milliseconds
Sum = 5002310.789580964 in 478 milliseconds

Сколько будет, если поделить 450/50?

А вы сами не обратили внимание, что в данном тесте бенчмаркер использует массив из 1 000 000 элементов, а вопрос был про 1000? А двумя постами ниже в треде тот же самый автор пишет:

When I use SIZE = 1000 in that code (and a suitably larger number of repeats in the "time" method) then contrary to the statement in the original post, I don't see a significant difference between the sequential access and the random access. (So my answer was technically correct -- there isn't a difference for arrays with 1000 elements. Not in my tests anyway.)

But when I use SIZE = 10000 I do see a significant difference (50% longer for random access). So the reason depends on the size of the array. The larger the array, the bigger the difference.

До туда вы уже не дочитали?

[Alexandr]

Послал вам в личку еще пару примеров того, что я считаю хорошими вопросами по Java / JVM. Сорри, что пока в личку.

скиньте мне тоже плиз, интересно

[adda_]

А вы сами не обратили внимание, что в данном тесте бенчмаркер использует массив из 1 000 000 элементов, а вопрос был про 1000? А двумя постами ниже в треде тот же самый автор пишет:

До туда вы уже не дочитали?

Я вообще не понимаю ничего. Если для задачи критично время доступа к элементу массива размером в 1000 штуков то надо использовать какой то другой язык вместо Жабы. Языки высокого уровня особенно те которые крос платформенные (или имеют претензии на это) не предназначены для задач реального времени где счет идет на милисекунды.. Т.е. вопрос вообще не имеет никакого практического смысла.. И говорит о кругозоре вопрошающего... Вспоминается известная басня Крылова.

[Alexandr]

by the way, автор сего "бенчмарка" (того, что по ссылке)

private double sum(Integer[] indexes) {
double sum = 0.0;
for (Integer i: indexes) {
sum += data;
}
return sum;
}

читает одновременно из двух массивов,
один - indexes (всегда последовательно),
второй - data
благо, x86 имеют префетчер, который может более одного потока данных одновременно префетчить, так что на x86 будет все хорошо, но не факт, что также будет хорошо на других платформах

+он считает сумму, типа double, на x86 2 порта могут складывать double одновременно, поэтому unrollнув цикл на 2 (т.е. 2 сумматора чтобы были) было бы быстрее (если данные уже в кеше, хотя вообще непонятно зачем он сумму считает, достаточно было бы просто прочитать вникуда (предварительно убрав оптимизацию у jittера), был бы чище эксперимент)

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

[Alexandr]

А вы сами не обратили внимание, что в данном тесте бенчмаркер использует массив из 1 000 000 элементов, а вопрос был про 1000? А двумя постами ниже в треде тот же самый автор пишет:

До туда вы уже не дочитали?

Я вообще не понимаю ничего. Если для задачи критично время доступа к элементу массива размером в 1000 штуков то надо использовать какой то другой язык вместо Жабы. Языки высокого уровня особенно те которые крос платформенные (или имеют претензии на это) не предназначены для задач реального времени где счет идет на милисекунды.. Т.е. вопрос вообще не имеет никакого практического смысла.. И говорит о кругозоре вопрошающего... Вспоминается известная басня Крылова.

все нормально в кругозоре у вопрощающего, минимум потому что для конкретно этой задачи java генерит ничуть не хуже код, чем сгенерил бы C\С++
во вторых задача на поговорить, а не на реализовать HFT на жабе

[Zorkus]

Послал вам в личку еще пару примеров того, что я считаю хорошими вопросами по Java / JVM. Сорри, что пока в личку.

скиньте мне тоже плиз, интересно

Скинул парочку еще.

[dotcom]

загрузить адрес в регистр - это копейки по сравнению cache miss и tlb miss

Вам не приходило в голову, что загрузка адреса в регистр - это абсолютно такая же операция, как загрузка данных в регистр? Cache miss и TLB будут работать абсолютно одинаково по скорости. Да, через страницы скакать всегда дороже. Но мы этого вопроса не касались. Хотя особенно продвинутые уже дошли до swap'а. Prefetcher контролируется branch/execution prediction модулем.
На x86 оно, скорее, действительно упирается в производительность операций. Скажем, имеем бесполезный цикл:

Code: Select all

loop:
  mov eax, [esi + ebx]
  add ebx, 4
  cmp ebx, high_bound
  jbe loop

Все дешевые операции, которые выполняются за такт (на самом деле, меньше чем за такт даже). Команды засосутся в ALU за раз, считывать их каждый раз из памяти/кеша нет смысла. Остается только читать [esi + ebx]. Да, тут задача для предсказателя простая. Главное, чтобы он не подумал чего лишнего про сам цикл. Если же туда вставить random access операцию, то он подумает, что "ну его на фиг", потому как память читать надо будет много и из разных мест.

[dotcom]

До туда вы уже не дочитали?

Читал. Был смущен вашим же комментарием про значительную разницу.

[Zorkus]

До туда вы уже не дочитали?

Читал. Был смущен вашим же комментарием про значительную разницу.

Так я же специально ввел в заблуждение

[Alexandr]

загрузить адрес в регистр - это копейки по сравнению cache miss и tlb miss

Вам не приходило в голову, что загрузка адреса в регистр - это абсолютно такая же операция, как загрузка данных в регистр? Cache miss и TLB будут работать абсолютно одинаково по скорости. Да, через страницы скакать всегда дороже. Но мы этого вопроса не касались. Хотя особенно продвинутые уже дошли до swap'а. Prefetcher контролируется branch/execution prediction модулем.
На x86 оно, скорее, действительно упирается в производительность операций. Скажем, имеем бесполезный цикл:

Code: Select all

loop:
  mov eax, [esi + ebx]
  add ebx, 4
  cmp ebx, high_bound
  jbe loop

Все дешевые операции, которые выполняются за такт (на самом деле, меньше чем за такт даже). Команды засосутся в ALU за раз, считывать их каждый раз из памяти/кеша нет смысла. Остается только читать [esi + ebx]. Да, тут задача для предсказателя простая. Главное, чтобы он не подумал чего лишнего про сам цикл. Если же туда вставить random access операцию, то он подумает, что "ну его на фиг", потому как память читать надо будет много и из разных мест.

Вам не приходило в голову, что загрузка адреса в регистр - это абсолютно такая же операция, как загрузка данных в регистр?

загрузка адреса
mov eax, const - вообще никакого обращения к памяти, константа лежит как часть инструкции (mov + immidiate)
загрузка данных по адресу -
mov eax, [esi] - обращение к памяти по адресу, указывающему esi

вы скорее всего имеете ввиду случай, когда загружаемый адрес хранится в другой переменной, но к чему такая сложность
можно рассуждать далее в стиле, что при адресации base + offset выполняться будет чуть быстрее, чем например base + index (см. интелловскую документацию), просто все это влияет на данный пример в гораздо меньшей степени, чем всякие issues с кешем

Хотя особенно продвинутые уже дошли до swap'а.

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

Prefetcher контролируется branch/execution prediction модулем.

это совсем совсем не правда, префетчер вообще никакого отношения не имеет к branch prediction

На x86 оно, скорее, действительно упирается в производительность операций.

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

Команды засосутся в ALU за раз, считывать их каждый раз из памяти/кеша нет смысла.

во-первых, команды не хранятся в ALU несколько итераций, максимум где они хранятся это mop-cache внутри процессора (что-то вроде 128 байт) и то, только у sandy bridge (и то с большими оговорками), но речь вообще не о командах, а о данных, которые мы читаем

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

это в лучшем случае, в худшем - зачитает то, что "посчитает нужным", что для нас хуже, чем если бы вообще не читал