Вы обнаружили один из эффектов, вызывающих узкие места в гистограммах. Обходной путь для этой проблемы состоит в том, чтобы сохранить несколько массивов счетчиков и вращаться через них, поэтому повторяющиеся прогоны одного и того же индекса распределяются по 2 или 4 различным счетчикам в памяти.
(Затем выполните цикл по массивам счетчиков длясуммируйте их в один последний набор. Эта часть может извлечь выгоду из SIMD.)
Случай 1 быстрый, потому что современный процессор знает, что мы читаем / записываем одну и ту же область памяти, таким образом, буферизуяоперация
Нет, это не процессор, это время компиляции оптимизация.
++*pointer[0] быстро, потому чтоКомпилятор может вывести хранилище / перезагрузить из цикла и фактически просто увеличить регистр. (Если вы не используете результат, он может оптимизировать даже это.)
Предположение об отсутствии гонки данных позволяет компилятору предположить, что ничто другое не модифицирует pointer[0], так что это определенно тот же объектувеличивается каждый раз. А правило «как если» позволяет ему хранить *pointer[0] в регистре вместо того, чтобы фактически делать приращение к месту назначения памяти.
Таким образом, это означает задержку в 1 цикл для приращения, и, конечно, оно может объединять несколько приращений водин и делать *pointer[0] += n, если он полностью разворачивает и оптимизирует цикл.
когда мы записываем в ячейку памяти указатель a, а затем пытаемся прочитать ее указателем b, мыпридется ждать записи, чтобы закончить. Это останавливает суперскалярное выполнение.
Да, проблема заключается в зависимости от данных в этой области памяти. Не зная во время компиляции, что все указатели указывают на одно и то же место, компилятор создаст asm, который фактически увеличивает указанную ячейку памяти.
«ждать окончания записи» не совсем точен, хотя. ЦП имеет буфер хранилища, чтобы отделить выполнение хранилища от промахов кеша, и спекулятивного исполнения нестандартного исполнения от хранилищ, фактически фиксирующих L1d и видимых для других ядер. Перезагрузка недавно сохраненных данных не должна ждать, пока они будут зафиксированы в кэше; пересылка хранилища из буфера хранилища для перезагрузки - это то, что нужно, когда ЦП обнаружит это.
На современных процессорах Intel задержка пересылки хранилища составляет около 5 циклов, поэтому место назначения памятиadd имеет задержку в 6 циклов. (1 для сложения, 5 для сохранения / перезагрузки, если он находится на критическом пути.)
И да, выполнение не по порядку позволяет двум из этих цепочек зависимостей с 6-тактными задержками работать параллельно. И издержки цикла скрыты под этой задержкой, опять-таки OoO exec.
Related:
Есть ли способ ускорить работу Case 3 без изменения массива указателей?
Да, если этот случай ожидается, возможно, ответвление на нем :
int *current_pointer = pointer[0];
int repeats = 1;
...
loop {
if (pointer[i] == current_pointer) {
repeats++;
} else {
*current_pointer += repeats;
current_pointer = pointer[i];
repeats = 1;
}
}
Мы оптимизируем путем подсчетадлина повторения одного и того же указателя .
Это полностью побеждено в случае 2 и будет работать плохо, если длинные пробеги не обычны.
Короткие прогоны могут быть скрыты exec-of-order exec;только когда цепочка депонирования становится достаточно длинной, чтобы заполнить ROB (буфер переупорядочения), мы действительно останавливаемся.