Google Recruiter

[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 операцию, то он подумает, что "ну его на фиг", потому как память читать надо будет много и из разных мест.

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

[crypto5]

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

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

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

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

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

[Интеррапт]

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

При sequential доступе, когда идет итерация по массиву - эта проверка будет отброшена. Это еще много лет назад было добавлено в хотспот.

[crypto5]

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

При sequential доступе, когда идет итерация по массиву - эта проверка будет отброшена. Это еще много лет назад было добавлено в хотспот.

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

[Интеррапт]

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

При sequential доступе, когда идет итерация по массиву - эта проверка будет отброшена. Это еще много лет назад было добавлено в хотспот.

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

Вполне возможно.

[Интеррапт]

Тот тест нужно запустить с "-XX:-UseLoopPredicate" и посмотреть, будет ли разница.