Почему g++ вытягивает вычисления в горячий контур?

Ответ 1

Вы используете 32-битный тип без знака для индекса массива (строка 21). Это заставляет компилятор рассматривать на каждом шаге через цикл, возможно, вы переполнили его доступный диапазон, и в этом случае ему нужно вернуться к началу массива. Дополнительный код, который вы видите, связан с этой проверкой! Существует не менее трех способов избежать этого чрезмерно осторожного подхода компилятором:

1. Используйте 64-разрядный тип для индекса в строке 21. Теперь компилятор знает, что вы никогда не обернете вокруг массива и не сгенерируете тот же код, что и без лямбда.
2. Используйте подписанный 32-разрядный тип для индекса в строке 21. Теперь компилятор больше не заботится о переполнении: подписанное переполнение считается UB и поэтому игнорируется. Я считаю, что это ошибка в интерпретации стандарта, но мнения по этому поводу отличаются.
3. Выяснить компилятору, что переполнение никогда не произойдет, добавив строку 'int32_t iter = 0;' в начале функции и удалении iter из декларации. Очевидно, это не решает вашу проблему, но это иллюстрирует, как именно анализ переполнения вызывает создание дополнительного кода.

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

Итак, чтобы повторить: это не вычисление X1 и X2, которое перемещается в цикл, который вызывает размер шара, но использует неверно типизированную переменную индекса массива.

Ответ 2

Поздравляем, вы обнаружили ошибку gcc. Главное решение - сообщить об этом в GCC bugzilla с ключевым словом "пропущенная оптимизация". Ваши MCVE уже являются отличными тестовыми сценариями для ошибки, поэтому не нужно слишком долго писать их. Скопируйте/вставьте код и некоторое описание. Ссылка на этот вопрос и связь с кодом на http://godbolt.org/ тоже была бы хорошей.

Иногда есть тонкие микроархитектурные причины использовать "дополнительные" инструкции, такие как xor -zeroing, назначение popcnt/lzcnt или bsf чтобы избежать ложной зависимости от процессоров Intel, но это не так. Это просто плохо; movl %ecx, %eax внутри цикла может быть результатом использования неподписанного типа, более узкого, чем указателя, но даже это можно сделать более эффективно; это и пропущенная оптимизация.

Я не рассматривал GCC GIMPLE или RTL-отвалы (внутренние представления), чтобы узнать больше деталей. Единственное использование вычисленных значений находится внутри цикла, поэтому я могу представить, что внутреннее представление компилятора логики программы может потерять разницу между внутренним/внешним циклом при преобразовании. Обычно вещи, которые не должны находиться в цикле, поднимаются или выходят из цикла.

Но, к сожалению, это не редкость для gcc оставлять дополнительную инструкцию mov внутри цикла, чтобы настроить код вне цикла. Особенно, когда может потребоваться несколько инструкций вне цикла, чтобы получить тот же эффект. Обычно это плохой компромисс при оптимизации производительности вместо кода. Я не смотрел на asm-выход из Profile-Guided Optimization, насколько мне хотелось бы, чтобы увидеть код, где gcc знает, какие циклы действительно горячие, и разворачивает их. Но, к сожалению, -fprofile-use построено без PGO, поэтому код-gen без -fprofile-use прежнему очень важен.

Тем не менее, суть этого вопроса заключается не в том, как как можно быстрее получить этот конкретный пример. Вместо этого, я довольно изумлен, как компилятор может произвести такие деоптимизации в таком простом фрагменте кода. Моя главная проблема сейчас: я как-то потерял веру в свой компилятор, поэтому я хочу понять, как это может произойти, чтобы я мог восстановить его.

Не верьте в gcc! Это очень сложный механизм, который часто дает хорошие результаты, но редко дает оптимальные результаты.

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

Но многие узлы узких мест в памяти, а не пропускная способность. Современные процессоры разрабатывают жульничество через запущенные команды, которые генерируют компиляторы, особенно JIT-компиляторы. Вот почему такие пропущенные оптимизации, как правило, не оказывают большого влияния на макромасштабирование, и почему случаи, когда они имеют значение (например, видеокодеры или умножения матриц), часто по-прежнему используют блоки рукописного asm.

Часто можно вручную удерживать gcc в создании приятного asm путем реализации вашего источника таким образом, который структурирован как asm, который вы хотите. (Как и в этом случае: каков эффективный способ подсчета битов в позиции или ниже?) И посмотрите, почему этот код C++ быстрее, чем моя рукописная сборка для тестирования гипотезы Collatz?, для более общего ответа о помогая компилятору в сравнении с избиением компилятора с ручной записью asm.)

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

Интересно, что худший случай (2 дополнительных инструкций LEA в цикле, плюс использование дополнительных счетчиков циклов) происходит только с вашим if (noLambda).

Если вы делаете 2 отдельных версии функции и удаляете if, то версия nolambda делает хороший чистый цикл (но пропускает авто-векторизацию -march=skylake, которая была бы победой при компиляции с -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 uop. Другие инструкции - все одно- movzwl; movzwl - чистая нагрузка и не нуждается в ALU-порту).

Магазин не ламинирует на SnB/IvB (стоит лишний кусок для 4-х этажного этапа эмиссии, одного из основных узких мест переднего плана), но может оставаться сплавленным на HSW/SKL. Он не может использовать порт 7, хотя (потому что он проиндексирован), что означает, что HSW/SKL будет ограничен двумя операциями памяти за такт, а не 3.

Узкие:

• Передняя шина выдачи пропускной способности 4 процессора с плавным доменом за такт. Цикл равен 5 юам и может выдаваться почти на 1 итерацию на 1.25. (Не-множественные циклы не идеальны, но 5 uops хорошо обрабатываются на Haswell/Skylake по крайней мере. Возможно, не Sandybridge.)

• загружать/хранить порты: Haswell и позже могут запускать 2 загрузки + 1 магазин за такт, но только тогда, когда хранилище избегает индексированного режима адресации, так что адрес магазина uop может работать на порте 7.

лямбда-версия получает счетчик 2-го цикла (шаг указателя) и глупый movl %ecx, %eax, но инструкции LEA остаются вне цикла.

Но это не дополнительное вычисление per se, это общая пропускная способность uop, которая, вероятно, повредит ваш цикл. Если словарь в основном остается горячим в кеше, процессор Haswell или более поздний

Я собирался написать больше, но я не закончил. Опубликовать сейчас, потому что родовая ранняя/средняя часть, по-видимому, действительно вопрос. Не слепо доверять gcc.

И не ожидайте, что он будет делать оптимальный код большую часть времени. Вы часто можете получить 10 или 20%, просто изменив исходный код C (а иногда и намного больше). Иногда gcc, похоже, не имеет понятия, например, используя дополнительную lea без видимых причин при разворачивании, вместо использования перемещения в режиме адресации. Я думаю, что его модель стоимости адресации не должна быть точной, по крайней мере для -march=haswell/-march=skylake.

Ответ 3

Я попытался запустить ваш код и... удивление: инструкции, выполняемые, когда вы находитесь в цикле, не те, что вы видите в ссылке проводника компилятора, которую вы опубликовали. Проверьте это (я добавил основную функцию) https://godbolt.org/g/PPYtQa Инструкции, выполняемые во время цикла, равны 162-167, т.е.

.L15:
        movzwl  25(%rbx,%rdx), %ecx
        movl    5(%rbx,%rcx,4), %ecx
        movl    %ecx, 0(%rbp,%rdx,2)
        addq    $2, %rdx
        cmpq    $180, %rdx
        jne     .L15

Вы можете дважды проверить это, скомпилировав на своей машине

g++ test.cpp -std=c++1z -g -O3

и работает с gdb

> gdb a.out
(gdb) break funnyEval
(gdb) layout split #shows assebly
(gdb) stepi #steps to the next instruction

Компилятор генерирует другую нестрочную версию funnyEval (которая является той, что вы видели на разобранном выходе), даже если тот, который фактически используется, является встроенным. Я понятия не имею (пока), почему эти два варианта, но я предполагаю, что если вы пострадали от штрафа за производительность, вы можете исправить это, убедившись, что funnyEval становится inlined: либо путем определения в файле заголовка, либо путем компиляции и связывания с оптимизация времени соединения (-flto). Я попробую посмотреть, что произойдет, когда funnyEval находится в другой единицы перевода...