Почему этот цикл занимает 1,32 цикла на итерацию

Рассмотрим эту простую функцию C++ для вычисления суммы префикса массива:

void prefix_sum(const uint32_t* input, uint32_t* output, size_t size) {
    uint32_t total = 0;
    for (size_t i = 0; i < size; i++) {
        total += input[i];
        output[i] = total;
    }
}

Цикл компилируется в следующую сборку в gcc 5.5:

.L5:
        add     ecx, DWORD PTR [rdi+rax*4]
        mov     DWORD PTR [rsi+rax*4], ecx
        add     rax, 1
        cmp     rdx, rax
        jne     .L5

Я не вижу ничего, что могло бы помешать этому запускаться с 1 циклом на итерацию, но я последовательно измеряю его на 1,32 (+ / - 0,01) циклов/итерация на моем Skylake i7-6700HQ при работе с 8 КиБ массивы ввода/вывода.

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

Это 4 слитка мопс 1, и этот процессор может выдержать 4 слияния операций/цикл.

Через ecx и rax проходят цепочки зависимостей, каждый из которых состоит из 1 цикла, но эти мопы add могут идти на любой из 4 портов ALU, поэтому вряд ли конфликтуют. Слитый cmp должен перейти к p6, что вызывает больше беспокойства, но я измеряю только 1.1 моп/итерацию до p6. Это объясняет 1,1 цикла на одну итерацию, но не 1,4. Если я разверну цикл в 2 раза, давление порта будет намного ниже: менее 0,7 мопа для всего p0156, но производительность все равно будет неожиданно низкой - 1,3 цикла за итерацию.

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

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

На цикл приходится два сложных AGU, но мы можем сделать два из них за цикл.

Что за узкое место здесь?

Интересно, что я попробовал предиктор производительности Itermal, и он почти полностью соответствует действительности: оценка 1.314 циклов против моего измерения 1.32.

1 Я подтвердил слияние макро- и микросинтеза с помощью счетчика uops_issued.any, который считает в слитой области и считывает 4,0 слитых мопов за одну итерацию для этой циклы.

Ответы

Ответ 1

Я просто поигрался с инструкциями по прогнозированию Ithermal Performance и, возможно, нашел проблему. Попытка

add     ecx, DWORD PTR [rdi]
mov     DWORD PTR [rsi], ecx
add     rax, 1
cmp     rdx, rax

дает ошеломляющие 1,131 цикла на итерацию. Перекрестная проверка с добавлением 0 в каждой итерации (что дает снова 1,3 цикла) исключает возможность узкого места при хранении/загрузке. Что, наконец, указывает на проблему с режимами адресации addressing modes.

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

(примечание редактора: эта часть неверна: из вопроса мы знаем, что нет расслоения, потому что uops_issued.any = 4 за итерацию.)

Я думаю, что ваш процессор не ламинирует ваш add/mov в случае индексированной адресации. Это поведение хорошо документировано для нескольких архитектур (SnB, SKL, HWL), и кто-то проделал отличную работу со стековым потоком, описав все это: fooobar.com/info/630/... Короче говоря: если слишком много регистров & флаги задействованы, оплавленный операционный блок (DSB) становится неслоистым (IDQ), таким образом, эффективно снова расплавляется.

Другие ресурсы: