Поздравляем, вы нашли ошибку gcc .Основное решение - сообщить об этом на bugzilla GCC с ключевым словом "пропущенная оптимизация".Ваши MCVE уже являются отличными тестовыми примерами для ошибки, поэтому не нужно слишком много времени, чтобы написать ее.Скопируйте / вставьте код и описание.Ссылка на этот раздел вопросов и ответов и ссылка на код в http://godbolt.org/, тоже были бы хорошими.
Иногда существуют тонкие микроархитектурные причины для использования «дополнительных» инструкций, таких как xor -zeroingназначение popcnt / lzcnt или bsf , чтобы избежать ложной зависимости от процессоров Intel , но здесь это не так.Это просто плохо;movl %ecx, %eax внутри цикла может быть результатом использования типа без знака, более узкого, чем указатель, но даже это может быть сделано более эффективно;Это также пропущенная оптимизация.
Я не смотрел дампы GIMPLE или RTL (внутренние представления) GCC, чтобы узнать больше.Единственное использование вычисленных значений находится внутри цикла, поэтому я могу представить, что внутреннее представление компилятором логики программы может потерять разницу между внутренним и внешним циклом при преобразовании.Обычно вещи, которые не должны быть в цикле, поднимаются или выталкиваются из цикла.
Но, к сожалению, для gcc нередко оставлять в цикле дополнительную инструкцию mov для настройки кодавне петли.Особенно, когда может потребоваться несколько инструкций вне цикла, чтобы получить тот же эффект.Обычно это плохой компромисс при оптимизации производительности вместо размера кода.Я не смотрел на вывод asm из Profile-Guided Optimization столько, сколько хотел бы, чтобы увидеть код, где gcc знает, какие циклы действительно горячие, и развертывает их.Но большая часть кода создается без PGO, к сожалению, поэтому генерация кода без -fprofile-use все еще очень важна.
Однако суть этого вопроса не в том, как получить этот конкретный примерБыстро настолько, насколько это возможно.Вместо этого я довольно расстроен тем, как компилятор может произвести такую деоптимизацию в таком простом фрагменте кода. Теперь моя главная проблема: я каким-то образом потерял веру в свой компилятор, поэтому я хочу понять, как это может произойти, чтобы я мог восстановить его.
Не делайне верьте в gcc! Это очень сложный механизм, который часто дает хорошие результаты, но редко дает оптимальные результаты.
Этот случай - один из самых очевидных и простых неправильных вариантов, которые я виделхотя его оптимизатор делает (и довольно разочаровывает).Обычно пропущенные оптимизации являются несколько более тонкими (и зависят от микроархитектурных деталей, таких как выбор режима адресации и порты мопов / выполнения), или, по крайней мере, не настолько очевидны, чтобы их избегать.(Поднимите эту одну инструкцию, не изменяя какого-либо распределения регистров для всего цикла.)
Но узкое место многих циклов в памяти, а не пропускная способность uop. Современные ЦП предназначены для жевания через потраченные впустую инструкции, которыекомпиляторы, особенно JIT-компиляторы, генерируют.Вот почему пропущенные оптимизации, подобные этой, обычно не оказывают большого влияния на макроуровне, и почему случаи, когда они имеют значение (например, видеокодеры или умножение матриц), часто все еще используют блоки рукописного асма.
Часто можно вручную заставить gcc создать хороший asm, реализовав ваш исходный код так, как вы хотите.(Как в этом случае: Каков эффективный способ подсчета установленных битов в позиции или ниже? и см. Почему этот код C ++ быстрее моей рукописной сборки для проверки гипотезы Коллатца?, для более общего ответа о помощи компилятору, а не об избиении компилятора рукописным ассемблером.)
Но когда ваш компилятор испытывает такие сложности, вы ничего не можете сделать.Ну, кроме как искать обходные пути, или такие вещи, как избегать unsigned целых чисел, более узких, чем указатели, которые некоторые другие ответы указали как важные.
Интересно, что наихудший случай (2 дополнительные инструкции LEA в цикле, плюс использование дополнительных счетчиков цикла) происходит только с вашим if (noLambda).
Если вы сделаете 2 отдельные версии функции и удалите if, версия nolambda делает хороший чистый цикл (но пропускает автоматическую векторизацию сборки, которая была бы выигрышной при компиляции с -march=skylake)
Я поместил ваш код наGodbolt проводник компилятора .(Также интересно, используйте -funroll-loops, чтобы увидеть, какие части переделываются при каждой итерации развернутого цикла, а какие просто находятся внутри цикла один раз.)
# gcc7.2: the nolamba side of the if, with no actual if()
.L3:
movzwl (%rsi,%rax,2), %ecx
movl (%rdx,%rcx,4), %ecx
movl %ecx, (%r9,%rax,4) # indexed store: no port 7
addq $1, %rax # gcc8 -O3 -march=skylake uses inc to save a code byte here.
cmpq %rax, %r8
jne .L3
В семействе Intel Sandybridge это декодирует до 5 моп.(Слияние макросов cmp / jcc превращает эту пару в 1 моп. Все остальные инструкции - однократные; movzwl является чистой загрузкой и не требует порта ALU).
Хранилищене ламинирует на SnB / IvB (стоит дополнительная мера для этапа выпуска с 4-мя шинами, одно из главных узких мест переднего конца), но может остаться в HSW / SKL.Однако он не может использовать порт 7 (потому что он индексирован), что означает, что HSW / SKL будет ограничен 2 операциями памяти на такт, а не 3.
Узкие места:
Пропускная способность внешнего интерфейса 4 мопов слитых доменов за такт.Цикл составляет 5 моп, и может выдавать почти 1 итерацию на 1,25.(Циклы не кратные 4 не идеальны, но 5 мопов хорошо обрабатываются на Haswell / Skylake как минимум . Возможно, не Sandybridge.)
порты загрузки / хранения: Haswell и более поздние версии могут запускать 2 загрузки + 1 хранилище за такт, но только в том случае, если хранилище избегает режима индексированной адресации, поэтому uop store-address может работать на порту 7.
лямбда-версия получает 2-й счетчик цикла (приращение указателя) и глупое movl %ecx, %eax, но инструкции LEA остаются вне цикла.
Но это не дополнительные вычисления как таковые, это общая пропускная способность UOP, вероятно, вредит вашей петле.Если словарь в основном остается горячим в кеше, то процессор Haswell или новее
я собирался написать больше, но я не закончил.Размещать сейчас, потому что общая ранняя / средняя часть, по-видимому, является темой, о которой действительно идет речь.Не вслепую доверяйте gcc.
И не ожидайте, что он будет создавать оптимальный код большую часть времени.Вы можете часто получить 10 или 20%, просто настроив источник C (а иногда и намного больше).Иногда кажется, что gcc не имеет ни малейшего представления, как, например, использование дополнительных lea s без видимой причины при развертывании вместо использования смещения в режиме адресации.Я думаю, что его модель стоимости в режиме адресации не должна быть точной, по крайней мере для -march=haswell / -march=skylake.