Максимум 3 значения, производительность лево-ассоциативной версии по сравнению с право-ассоциативной версией

Ответ 1

gcc и clang (и предположительно MSVC) не понимают, что max является ассоциативной операцией, такой как сложение. v[i] max (v[j] max v[k]) (max_3_right) совпадает с (v[i] max v[j]) max v[k] (max_3_left). Я пишу max как инфиксный оператор, чтобы указать сходство с + и другими ассоциативными операциями.

Так как v[k] - единственный вход, который изменяется во внутреннем цикле, очевидно, это большой выигрыш, чтобы вытащить (v[i] max v[j]) из внутреннего цикла.

Чтобы понять, что происходит на самом деле, мы, как всегда, должны смотреть на asm. Чтобы упростить поиск asm для циклов, Я разделил их на отдельные функции. (Создание одной функции шаблона с помощью функции max3 в качестве параметра будет более похожим на С++). Это имеет дополнительное преимущество в том, что мы хотим, чтобы код, который мы хотим оптимизировать из main, который gcc отмечает как "холодный" , отключает некоторые оптимизации.

#include <algorithm>
#define SIZE 1000
int sum_maxright(const std::vector<int> &v) {
    int sum = 0;
    for ( int i = 0; i < SIZE; ++i )
        for ( int j = 0; j < SIZE; ++j )
            for ( int k = 0; k < SIZE; ++k )
                sum += max_3_right( v[i], v[j], v[k] );
    return sum;
}  

Внутренний цикл, который компилируется (gcc 5.3, нацеленный на x86-64 Linux ABI с -std=gnu++11 -fverbose-asm -O3 -fno-tree-vectorize -fno-unroll-loops -march=haswell с некоторыми аннотациями)

## from outer loops: rdx points to v[k] (starting at v.begin()).  r8 is v.end().  (r10 is v.begin)
## edi is v[i], esi is v[j]
## eax is sum

 ## inner loop.  See the full asm on godbolt.org, link below
.L10:
        cmp     DWORD PTR [rdx], esi      # MEM[base: _65, offset: 0], D.92793
        mov     ecx, esi                  # D.92793, D.92793
        cmovge  ecx, DWORD PTR [rdx]      # ecx = max(v[j], v[k])
        cmp     ecx, edi      # D.92793, D.92793
        cmovl   ecx, edi      # ecx = max(ecx, v[i])
        add     rdx, 4    # pointer increment
        add     eax, ecx  # sum, D.92793
        cmp     rdx, r8   # ivtmp.253, D.92795
        jne     .L10      #,

Clang 3.8 делает аналогичный код для цикла max_3_right с двумя инструкциями cmov внутри внутреннего цикла. (Используйте раскрывающийся список компилятора в Google > Разработчик компилятора Godbolt.

gcc и clang оптимизируют так, как вы ожидали бы для цикла max_3_left, поднимая все, кроме одного cmov из внутреннего цикла.

## register allocation is slightly different here:
## esi = max(v[i], v[j]).    rdi = v.end()
.L2:
        cmp     DWORD PTR [rdx], ecx      # MEM[base: _65, offset: 0], D.92761
        mov     esi, ecx  # D.92761, D.92761
        cmovge  esi, DWORD PTR [rdx]        # MEM[base: _65, offset: 0],, D.92761
        add     rdx, 4    # ivtmp.226,
        add     eax, esi  # sum, D.92761
        cmp     rdx, rdi  # ivtmp.226, D.92762
        jne     .L2       #,

Таким образом, в этом цикле происходит гораздо меньше. (На Intel pre-Broadwell, cmov является инструкцией 2-uop, поэтому еще одно cmov - это большая сделка.)

BTW, эффекты предварительной выборки кеша не могут объяснить это:

• Внутренний цикл обращается к numbers[k] последовательно. Повторные обращения к numbers[i] и numbers[j] выводятся из внутреннего цикла любым достойным компилятором и не будут путать современные префетеры, даже если бы они не были.

  Руководство по оптимизации Intel сообщает, что можно обнаружить и сохранить до 32 потоков шаблонов предварительной выборки (с ограничением на один вперед и один назад на страницу 4k), для микроархитектур семейства Sandybridge (раздел 2.3.5.4 "Предварительная выборка данных" ).

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

• один vector из 1000 int (4B) принимает только 4kiB. Это означает, что весь массив легко вписывается в кеш L1D, поэтому нет необходимости в какой-либо предварительной выборке в первую очередь. Он все время остается горячим в кэше L1 в течение всего времени.

Ответ 2

Как указывал molbdnilo, проблема может быть с порядком циклов. При расчете sum1 код можно переписать как:

for ( int i = 0; i < 1000; ++i )
   for ( int j = 0; j < 1000; ++j ) {
      auto temp = std::max(numbers[i], numbers[j]);
      for ( int k = 0; k < 1000; ++k )
            sum1 += std::max(temp, numbers[k]);
   }

То же самое нельзя применить для вычисления sum2. Однако, когда я повторно обработал второй цикл как:

for ( int j = 0; j < 1000; ++j )
   for ( int k = 0; k < 1000; ++k )
      for ( int i = 0; i < 1000; ++i )
         sum2 += ...;

Я получил одинаковые времена для обоих вычислений. (Более того, оба вычисления намного быстрее с -O3, чем с -O2. Первая, по-видимому, включает вектологию в соответствии с разобранным выходом.)

Ответ 3

Это связано с данными prefetching кэша на уровне аппаратного обеспечения.

Если вы используете левую ассоциативную версию, элементы массива используются/загружаются в последовательности, ожидаемой кешем CPU, с меньшей задержкой.

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