Почему эта разница в asm важна для производительности (в не оптимизированной петле ptr ++ vs. ++)?

TL; DR: первый цикл работает на 18% быстрее на процессоре Haswell. Зачем? Петли из циклов gcc -O0 (не оптимизированы) с использованием ptr++ vs ++ptr, но возникает вопрос, почему результирующий asm выполняет по-разному, а не о том, как лучше писать C.

Скажем, мы имеем эти две петли:

    movl    $0, -48(%ebp)     //Loop counter set to 0
    movl    $_data, -12(%ebp) //Pointer to the data array
    movl    %eax, -96(%ebp)
    movl    %edx, -92(%ebp)
    jmp L21
L22:
    // ptr++
    movl    -12(%ebp), %eax   //Get the current address
    leal    4(%eax), %edx     //Calculate the next address
    movl    %edx, -12(%ebp)   //Store the new (next) address
    // rest of the loop is the same as the other
    movl    -48(%ebp), %edx   //Get the loop counter to edx
    movl    %edx, (%eax)      //Move the loop counter value to the CURRENT address, note -12(%ebp) contains already the next one
    addl    $1, -48(%ebp)     //Increase the counter
L21:
    cmpl    $999999, -48(%ebp)
    jle     L22

а второй:

    movl    %eax, -104(%ebp)
    movl    %edx, -100(%ebp)
    movl    $_data-4, -12(%ebp) //Address of the data - 1 element (4 byte)
    movl    $0, -48(%ebp)       //Set the loop counter to 0
    jmp L23
L24:
    // ++ptr
    addl    $4, -12(%ebp)       //Calculate the CURRENT address by adding one sizeof(int)==4 bytes
    movl    -12(%ebp), %eax     //Store in eax the address
    // rest of the loop is the same as the other
    movl    -48(%ebp), %edx     //Store in edx the current loop counter
    movl    %edx, (%eax)        //Move the loop counter value to the current stored address location
    addl    $1, -48(%ebp)       //Increase the loop counter
L23:
    cmpl    $999999, -48(%ebp)
    jle L24

Эти петли делают точно то же самое, но немного по-другому, пожалуйста, обратитесь к комментарию для деталей.

Этот код asm создается из следующих двух циклов С++:

    //FIRST LOOP:
    for(;index<size;index++){
        *(ptr++) = index;
    }
    //SECOND LOOP:
    ptr = data - 1;
    for(index = 0;index<size;index++){
        *(++ptr) = index;
    }

Теперь первый цикл примерно на 18% быстрее, чем второй, независимо от того, в каком порядке выполняются петли, один с ptr++ быстрее, чем тот, у которого ++ptr.

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

Анализ ASM

Глядя на код ASM, второй цикл содержит меньше инструкций, у нас есть 3 movl и 2 addl, тогда как в первом цикле мы имеем 4 movl один addl и один leal, поэтому у нас есть один movl больше и один leal вместо addl

Правильно ли, что операция LEA для вычисления правильного адреса намного быстрее, чем метод ADD (+4)? Является ли это причиной разницы в производительности?

Насколько я знаю, как только новый адрес вычисляется до того, как память может быть указана, некоторые циклы часов должны пройти, поэтому второй цикл после добавления $4, -12 (% ebp) должен немного подождать, прежде чем продолжить, тогда как в первом цикле мы можем сразу ссылаться на память, а в то же время LEAL будет вычислять следующий адрес (какая-то лучшая производительность конвейера здесь).

Есть ли какое-то переупорядочение? Я не уверен в моем объяснении различий в производительности этих циклов, могу ли я высказать ваше мнение?

Ответы

Ответ 1

Прежде всего, анализ производительности на выходе компилятора -O0 обычно не очень интересен или полезен.

Правильно ли, что операция LEAL для вычисления правильного адреса намного быстрее, чем метод ADDL (+4)? Является ли это причиной разницы в производительности?

Нет, add может выполняться на каждом рабочем порту ALU на любом процессоре x86. lea обычно является низкой задержкой с простыми режимами адресации, но не такой хорошей пропускной способностью. В Atom он работает на другом этапе конвейера из обычных инструкций ALU, потому что он фактически соответствует его имени и использует AGU для этой микроархитектуры в порядке.

Смотрите x86 теги wiki для узнать, что делает код медленным или быстрым на разных микроархитектурах, особенно. Микроархитектура Agner Fog PDF и таблицы инструкций.

add хуже, потому что он позволяет gcc -O0 сделать еще хуже код, используя его с местом назначения памяти, а затем загружая с него.

Компиляция с помощью -O0 даже не пытается использовать лучшие инструкции для задания. например вы получите mov $0, %eax вместо xor %eax,%eax, который вы всегда получаете в оптимизированном коде. Вы не должны делать вывод о том, что хорошо смотреть на не оптимизированный выход компилятора.

-O0 код всегда заполнен узкими местами, обычно при загрузке/хранении или хранении. К сожалению, IACA не учитывает задержку хранения в магазине, поэтому он не понимает, что эти петли фактически являются узким местом на

Насколько я знаю, как только новый адрес вычисляется до того, как память может быть указана, некоторые циклы часов должны пройти, поэтому второй цикл после добавления $4, -12 (% ebp) должен немного подождать, прежде чем продолжить,

Да, загрузка mov -12(%ebp) не будет готова примерно через 6 циклов после загрузки, которая была частью add read-modify-write.

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

Да

и в то же время LEAL будет вычислять следующий адрес

Нет.

Ваш анализ близок, но вы упустили тот факт, что следующая итерация еще должна загрузить значение, которое мы сохранили, в -12(%ebp). Таким образом, цепочка зависимостей, связанных с циклом, имеет одинаковую длину, и следующая итерация lea не может начинаться раньше, чем в цикле, используя add

Проблемы с задержкой могут быть не узким местом пропускной способности:

Необходимо учитывать пропускную способность порта

uop/выполнения. В этом случае тестирование OP показывает, что это действительно актуально. (Или латентность от конфликтов ресурсов.)

Когда gcc -O0 реализует ptr++, он сохраняет старое значение в регистре, как вы сказали. Таким образом, адреса магазинов известны еще раньше, и там меньше нагрузки, требующей AGU.

Предполагая процессор Intel SnB-семейства:

## ptr++: 1st loop
movl    -12(%ebp), %eax   //1 uop (load)
leal    4(%eax), %edx     //1 uop (ALU only)
movl    %edx, -12(%ebp)   //1 store-address, 1 store-data
//   no load from -12(%ebp) into %eax
... rest the same.


 ## ++ptr:  2nd loop
addl    $4, -12(%ebp)       // read-modify-write: 2 fused-domain uops.  4 unfused: 1 load + 1 store-address + 1 store-data
movl    -12(%ebp), %eax     // load: 1 uop.   ~6 cycle latency for %eax to be ready
... rest the same

Таким образом, часть указателя-приращения второго цикла имеет еще один загрузочный uop. Вероятно, узкие места кода на пропускной способности AGU (устройства формирования адресов). IACA говорит, что случай для arch = SNB, но это узкие места HSW на пропускной способности хранилища (не AGU).

Однако, не принимая во внимание задержку хранения в магазине, IACA говорит, что первый цикл может выполняться на одной итерации за 3,5 цикла, против одного на 4 цикла для второго цикла. Это быстрее, чем зависящая от цикла циклическая зависимость счетчика циклов addl $1, -48(%ebp), что указывает на то, что цикл ограничен узким интервалом с меньшей пропускной способностью AGU. (Конфликты ресурсов, вероятно, означают, что он на самом деле работает медленнее, чем одна итерация на 6c, см. Ниже).

Мы могли бы проверить эту теорию:

Добавление дополнительной загрузки uop к версии lea, с критического пути, потребует большей пропускной способности, но не будет частью цепочек латентных циклов. например.

movl    -12(%ebp), %eax   //Get the current address
leal    4(%eax), %edx     //Calculate the next address
movl    %edx, -12(%ebp)   //Store the new (next) address

mov     -12(%ebp), %edx

%edx вот-вот будет перезаписан mov, поэтому нет никаких зависимостей от результата этой нагрузки. (Назначение mov - только для записи, поэтому он разбивает цепи зависимостей, благодаря переименованию регистров.).

Таким образом, эта дополнительная загрузка приведет к тому, что цикл lea достигнет такого же количества и вкуса, как и цикл add, но с разной задержкой. Если дополнительная нагрузка не влияет на скорость, мы знаем, что первый цикл не является узким местом при загрузке/хранении.

Обновление: тестирование OP подтвердило, что дополнительная неиспользуемая загрузка замедляет цикл lea до примерно той же скорости, что и цикл add.

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

uops запланированы в старом первом порядке (из uops, у которых есть их операнды), а не в порядке критического пути. Дополнительные сокеты, которые могли быть сделаны в свободном цикле позже, фактически задерживают uops, которые находятся на критическом пути (например, часть зависимой от цикла зависимостей). Это называется конфликтом ресурсов и может увеличить задержку критического пути.

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

Аналогично, в цикле add, где дополнительная загрузка является частью критического пути, дополнительная нагрузка вызывает больше конфликтов ресурсов, задерживая операции на критическом пути.

Другие догадки:

Итак, возможно, что адрес магазина уже готов к работе, это то, что он делает, поэтому операции с памятью лучше конвейерны. (например, проходы страницы TLB-miss могут начинаться раньше, когда приближаются к границе страницы. Даже обычная предварительная выборка аппаратного обеспечения не пересекает границы страниц, даже если они горячие в TLB. Цикл касается 4MiB памяти, чего достаточно для такого типа Дело в том, что L3-латентность достаточно высока, чтобы создать пузырь трубопровода. Или если ваш L3 мал, то основная память, безусловно, есть.

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