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

Я нахожу интересное явление:

#include<stdio.h>
#include<time.h>

int main() {
    int p, q;
    clock_t s,e;
    s=clock();
    for(int i = 1; i < 1000; i++){
        for(int j = 1; j < 1000; j++){
            for(int k = 1; k < 1000; k++){
                p = i + j * k;
                q = p;  //Removing this line can increase running time.
            }
        }
    }
    e = clock();
    double t = (double)(e - s) / CLOCKS_PER_SEC;
    printf("%lf\n", t);
    return 0;
}

Я использую GCC 7.3.0 в i5-5257U Mac OS для компиляции кода без какой-либо оптимизации. Вот среднее время выполнения более 10 раз: введите описание изображения здесь Есть и другие люди, которые тестируют этот случай на других платформах Intel и получают тот же результат.
Я публикую сборку, сгенерированную GCC здесь. Единственная разница между двумя кодами сборки состоит в том, что до addl $1, -12(%rbp) более быстрый имеет еще две операции:

movl    -44(%rbp), %eax
movl    %eax, -48(%rbp)

Так почему же программа с таким назначением работает быстрее?

Ответ Питера очень полезен. Тесты на AMD Phenom II X4 810 и процессоре ARMv7 (BCM2835) показывают противоположный результат, который поддерживает ускорение переадресации хранилища, характерное для некоторых процессоров Intel.
И Комментарий и совет BeeOnRope заставляет меня переписать вопрос. :)
В основе этого вопроса лежит интересное явление, связанное с архитектурой и сборкой процессора. Так что я думаю, что стоит обсудить это.


x86 performance assembly cpu-architecture micro-architecture
person helloqiu    schedule 09.03.2018    source источник
comment
Вы строите с включенной оптимизацией или без нее? Любой бенчмаркинг без оптимизаций практически бесполезен.   -  person Some programmer dude    schedule 09.03.2018
comment
Вы можете указать gcc только генерировать сборку, которая обычно более читабельна, чем дизассемблер (термин «декомпилировать», ИМХО, неверен), который вы предоставили.   -  person Ulrich Eckhardt    schedule 09.03.2018
comment
работает быстрее - насколько быстрее? Можете ли вы показать время выполнения, скажем, за 10 испытаний?   -  person Ajay Brahmakshatriya    schedule 09.03.2018
comment
В чем ошибка вашего бенчмарка, существенны ли различия?   -  person lwi    schedule 09.03.2018
comment
Вы тестируете отладочную сборку, которая в основном бесполезно. Но если вы хотите точно знать, почему, узким местом будет все сохранение / перезагрузка, вероятно, зависящая от цикла зависимость от k. Если вы используете Skylake, может задерживаться фактически будет ниже (лучше), когда между зависимой парой больше (включая другие магазины / грузы)..   -  person Peter Cordes    schedule 09.03.2018
comment
Если вы используете Skylake, я думаю, что это дубликат stackoverflow.com/questions/45442458/   -  person Peter Cordes    schedule 09.03.2018
comment
Кроме того, используйте p (и q) после циклов, иначе компилятор может вообще не сгенерировать код для этих циклов.   -  person Some programmer dude    schedule 09.03.2018
comment
@Someprogrammerdude Я строю с нулевой оптимизацией -O0.   -  person helloqiu    schedule 09.03.2018
comment
@AjayBrahmakshatriya Примерно на 0,5 секунды быстрее.   -  person helloqiu    schedule 09.03.2018
comment
Так что никакой оптимизации. Этого, как указано, недостаточно для сравнительного анализа. Используйте не менее -O2.   -  person Some programmer dude    schedule 09.03.2018
comment
@helloqiu На 0,5 секунды быстрее на сколько? Говорите в процентах. Какова дисперсия базовой линии, если вы запустите ее 10 раз?   -  person Ajay Brahmakshatriya    schedule 09.03.2018
comment
@PeterCordes Спасибо. Я проверю это.   -  person helloqiu    schedule 09.03.2018
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что вопросы о производительности кода, скомпилированного без какой-либо оптимизации, бесполезны.   -  person Toby Speight    schedule 09.03.2018
comment
@TobySpeight - я не согласен. Компиляция без оптимизации бесполезна для анализа производительности, но в конце концов, независимо от настроек компилятора, можно спросить, почему один фрагмент сборки, созданный компилятором, работает медленнее, чем другой, несмотря на то, что первый имеет строго меньше операторов . Одно это может быть интересно, как показывает ответ Питера.   -  person BeeOnRope    schedule 10.03.2018
comment
Хорошая правка, теперь это хорошо написанный и интересный вопрос. Теперь он действительно заслуживает того голоса, который я дал ему ранее, и я хотел бы снова проголосовать за него. :)   -  person Peter Cordes    schedule 10.03.2018

Ответы (1)


arrow_upward
20
arrow_downward

TL: DR: переадресация хранилища семейства Sandybridge имеет меньшую задержку, если перезагрузка не выполняется сразу. Добавление бесполезного кода может ускорить цикл режима отладки, поскольку узкие места задержки, переносимой циклом, в -O0 антиоптимизированном коде почти всегда связаны с сохранение / перезагрузка некоторых переменных C.
Другие примеры замедления в действии: гиперпоточность, вызов пустой функции, доступ к переменным через указатели.

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

Вы тестируете отладочную сборку, которая в основном бесполезно. У них другие узкие места, чем у оптимизированного кода, а не равномерное замедление.

Но очевидно, что существует реальная причина того, что отладочная сборка одной версии работает медленнее, чем отладочная сборка другой версии. (Предполагая, что вы измерили правильно, и это было не просто изменение частоты процессора (турбо / энергосбережение), приводящее к разнице во времени настенных часов.)

Если вы хотите вникнуть в детали анализа производительности x86, мы можем попытаться объяснить, почему asm работает именно так, как в первую очередь, и почему asm из дополнительного оператора C (который с -O0 компилируется в дополнительные инструкции asm) может сделать это быстрее в целом. Это кое-что расскажет нам о влиянии asm на производительность, но ничего полезного об оптимизации C.

Вы не показали весь внутренний цикл, только часть тела цикла, но gcc -O0 довольно предсказуемо. Каждый оператор C компилируется отдельно от всех остальных, при этом все переменные C переливаются / перезагружаются между блоками для каждого оператора. Это позволяет вам изменять переменные с помощью отладчика в пошаговом режиме или даже переходить к другой строке в функции, при этом код все еще работает. Стоимость компиляции таким образом катастрофична. Например, у вашего цикла нет побочных эффектов (ни один из результатов не используется), поэтому весь тройной вложенный цикл может и будет компилироваться с нулевыми инструкциями в реальной сборке, выполняясь бесконечно быстрее. Или, что более реалистично, запускать 1 цикл на итерацию вместо ~ 6, даже без оптимизации или серьезных преобразований.

Узким местом, вероятно, является зависящая от цикла зависимость от k с сохранением / перезагрузкой и add для увеличения. Задержка переадресации магазина обычно составляет около 5 циклов на большинстве процессоров. И, таким образом, ваш внутренний цикл ограничен запуском один раз за ~ 6 циклов, задержка назначения памяти add.

Если вы используете процессор Intel, задержка сохранения / перезагрузки может быть меньше (лучше), если перезагрузка не может быть выполнена сразу. Наличие большего количества независимых загрузок / хранилищ между зависимой парой может объяснить это в вашем случае. См. Цикл с вызовом функции быстрее, чем пустой цикл.

Таким образом, при увеличении объема работы в цикле тот addl $1, -12(%rbp), который может поддерживать пропускную способность одного за 6 циклов при последовательном запуске, вместо этого может создать узкое место только из одной итерации за 4 или 5 циклов.

Согласно измерениям из сообщения в блоге 2013 г., так что да, это наиболее вероятное объяснение и для вашего Broadwell i5-5257U. Похоже, что этот эффект происходит на всех процессорах семейства Intel Sandybridge.

Без дополнительной информации о вашем тестовом оборудовании, версии компилятора (или источнике asm для внутреннего цикла), и абсолютных и / или относительных показателях производительности для обеих версий, это мое лучшее без особых усилий угадать объяснение. Бенчмаркинг / профилирование gcc -O0 в моей системе Skylake недостаточно интересно, чтобы попробовать это самому. В следующий раз включите временные числа.

Задержка при сохранении / перезагрузке для всей работы, которая не является частью цепочки зависимостей, переносимой по циклу, не имеет значения, важна только пропускная способность. Очередь магазина в современных вышедших из строя ЦП действительно обеспечивает переименование памяти, устраняя запись после -запись и опасность записи после чтения из-за повторного использования одной и той же стековой памяти для p записи, а затем чтения и записи в другом месте. (Для получения информации см. https://en.wikipedia.org/wiki/Memory_disambiguation#Avoiding_AWde_WAR_and_den_WAR_ подробнее об опасностях для памяти и этот вопрос и ответ, чтобы узнать больше о задержке и пропускной способности и повторном использовании одного и того же переименования регистров / регистров)

Множественные итерации внутреннего цикла могут выполняться одновременно, потому что буфер порядка памяти отслеживает, из какого хранилища каждая загрузка должна принимать данные, не требуя предыдущего хранилища в том же месте для фиксации в L1D и выхода из него. очередь магазина. (См. Руководство Intel по оптимизации и PDF-файл с микроархитектурой Agner Fog для получения дополнительной информации о внутреннем устройстве микроархитектуры ЦП.)

Означает ли это, что добавление бесполезных операторов ускорит работу реальных программ? (с включенной оптимизацией)

В общем, нет. Компиляторы хранят переменные цикла в регистрах для самых внутренних циклов. А при включенной оптимизации бесполезные операторы будут оптимизированы.

Настраивать исходный код для gcc -O0 бесполезно. Измеряйте с помощью -O3 или любых других параметров, которые используются в сценариях сборки по умолчанию для вашего проекта.

Кроме того, это ускорение переадресации магазина характерно для семейства Intel Sandybridge, и вы не увидите его на других микроархитектурах, таких как Ryzen, если только они не имеют аналогичного эффекта задержки пересылки магазина.

Задержка переадресации магазина может быть проблемой в реальном (оптимизированном) выводе компилятора, особенно если вы не использовали оптимизацию времени компоновки (LTO), чтобы крошечные функции были встроены, особенно функции, которые передают или возвращают что угодно по ссылке (поэтому оно должно проходить через память, а не через регистры). Для устранения проблемы могут потребоваться хаки вроде volatile, если вы действительно хотите обойти это на процессорах Intel и, возможно, усугубить ситуацию на некоторых других процессорах. См. обсуждение в комментариях

person Peter Cordes    schedule 09.03.2018
comment
На этот вопрос едва ли стоило отвечать, но я действительно близок к золотому значку в теге [performance], поэтому у меня возникло соблазн написать какой-нибудь заполнитель вместо того, чтобы ждать, чтобы закрыть его как дубликат. : P Надеюсь, это не совсем бесполезный наполнитель. - person Peter Cordes; 09.03.2018
comment
Действительно, я читал ваш ответ и собирался оставить комментарий, в котором говорится, что в основном вы только что сделали, что вопросы о производительности с -O0 бессмысленны. В любом случае, хороший ответ, удачи с золотым результатом :) - person Lundin; 09.03.2018
comment
Я пытаюсь скомпилировать и запустить на raspberry pi, и результат, похоже, подтверждает ваш ответ. Хотя этот вопрос бесполезен, спасибо за ответ. - person helloqiu; 09.03.2018
comment
@PeterCordes Кстати, собственно, я все делаю на Broadwell i5-5257U, а не на skylake. Означает ли это, что у Broadwell может быть такой же механизм? - person helloqiu; 09.03.2018
comment
Что ж, утверждение Нет, не немного сильное :). Реальные случаи этой проблемы с переадресацией магазина, например аномалия петли i7 описанный здесь возникают с некоторой частотой. Конечно, компилятор пытается сохранить данные в регистрах, что в данном случае устранило бы проблему (если это проблема), но перенаправления магазина не всегда удается избежать с помощью оптимизации: даже с бесконечно умным компилятором, который может видеть через все границы функций. вы по-прежнему останетесь с пересылкой, зависящей от данных. - person BeeOnRope; 10.03.2018
comment
Вызов функций - еще один источник: push rsp, pop rsp, присущие call и ret, часто напрямую приводят к переадресации хранилища для коротких функций (это, по-видимому, было причиной проблемы, о которой я говорил выше, которая возникла как в -O2, так и в -O3). Кроме того, существует множество странных случаев, когда добавление явно избыточных инструкций ускоряет работу даже с оптимизацией, регулируя выравнивание, влияя на предикторы, изменяя расписание и т.д. >: все индивидуально. - person BeeOnRope; 10.03.2018
comment
@BeeOnRope: Я хотел сказать, что добавление ерунды типа int dummy=q; в исходный код C не исправит этого в оптимизированном коде. (И, кстати, я думаю, вы имеете в виду push RIP / pop RIP, присущий call / ret.) Но да, иногда это может происходить в выводе компилятора, особенно без оптимизации времени компоновки для встраивания крошечных функций. - person Peter Cordes; 10.03.2018
comment
@helloqiu: Да, и спасибо за эти данные. Комментарий BeeOnRope связан с сообщением в блоге от 2013 года сообщая об одном и том же в отношении Haswell и Sandybridge. Таким образом, кажется, что задержка переадресации хранилища зависит от окружающего кода на всем диапазоне процессоров семейства Sandybridge, от SnB до SKL и, предположительно, далее. - person Peter Cordes; 10.03.2018
comment
Да, я имел в виду rip. Конечно, строка int dummy = q будет скомпилирована, если включена оптимизация, но подобные фиктивные операторы, безусловно, могут помочь в оптимизированном коде. Я думаю, что, возможно, мы имеем дело с тем, что избыточные или явно бесполезные / медленные операторы могут ускорить процесс, оба в неоптимизированном и оптимизированном коде, но не обязательно, что один и тот же избыточный оператор ускоряет одинаковый фрагмент кода в обоих режимах. То есть в приведенном выше примере строка q = p не поможет в оптимизированном режиме, но аналогичная строка q = p может помочь в оптимизированном режиме в другом фрагменте ... - person BeeOnRope; 10.03.2018
comment
... но не в режиме отладки. Конечно, в оптимизированном режиме меньше избыточных инструкций в источнике останется в первую очередь, поэтому иногда вам понадобится volatile там, __attribute__ там и т. Д. - person BeeOnRope; 10.03.2018
comment
@helloqiu - не думаю, что этот вопрос бесполезен. Вы начали с большого неудобства с компиляции без оптимизации, что уже является гигантским красным флагом, объясняющим, почему производительность Y ведет себя как Z - но поскольку компилятор выдал дополнительные инструкции только для вашего более медленного случая, оказывается, что это интересный вопрос на уровень сборки. То есть вы могли бы почти удалить происхождение вопроса на C и тот факт, что вы скомпилировали без оптимизации, и спросить о поведении сборки, и, вероятно, избежать лавины отрицательных голосов. - person BeeOnRope; 10.03.2018
comment
@BeeOnRope: обратите внимание, что call/ret не создает зависящую от цикла зависимость, потому что адрес, выдвинутый call, исходит из спекулятивного исполнения + предсказания ветвления. Несколько сохранений / перезагрузок по одному и тому же адресу могут поддерживать одну за такт, если хранилище не зависит от данных от загрузки. Выполнение инструкций ret может выполняться по одной за такт, на 5 циклов после инструкций call. (Ну, конечно, call / ret являются ветвями, поэтому они конкурируют друг с другом за ресурсы выполнения и, таким образом, даже не создают узких мест в памяти.) Что может быть проблемой, так это push/pop rbp или x=foo(x) по исх. - person Peter Cordes; 10.03.2018
comment
@PeterCordes - этот вопрос достаточно интересен, поэтому мы не должны обсуждать его в комментариях. Я спросил об этом здесь. Подсказка: я не знаю ответа. - person BeeOnRope; 10.03.2018
comment
@PeterCordes Кто-то только что сказал мне, что полезно использовать perf для отслеживания программы. Так что я пробую. Похоже, что с некоторыми mov операциями, сгенерированными из q = p, процент циклов, используемых p = i + j * k вместо addl $1, -12(%rbp), уменьшается. Так возможно ли, что назначение делает imul быстрее вместо addl в k+1? - person helloqiu; 10.03.2018
comment
@helloqiu: производительность работает не так. Неупорядоченные конвейерные процессоры означают, что общее время выполнения - это не просто сумма того, сколько времени занимает каждая инструкция сама по себе. См. stackoverflow.com/questions/45113527/, чтобы узнать больше о пропускной способности, задержке и узких местах порта выполнения. Кроме того, используемые perf счетчики HW имеют ограниченную точность, см. stackoverflow.com/questions/48369347/ - person Peter Cordes; 10.03.2018
comment
На большинстве новых аппаратных средств cycles:ppp должен иметь высокую точность. - person BeeOnRope; 10.03.2018