Comments 17
UFO just landed and posted this here
Ассемблерный код выглядит так как будто компилировали с -Os, а не с -O3. Например, вот код который сгенерировал g++ у меня (g++ (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2) с -Os:
причем он одинаковый и для for_each и для accumulate (у меня += возвращает ссылку). Код же с -O3 я приводить не буду потому что в нем развернут цикл, используются векторные инструкции и прочее, но и там версии для accumulate и for_each одинаковые.
а гарантии по оптимизации циклов стандарт дает что ли?
может дело не в accumulate, а в вашей реализации +=?
movq 8(%rdi), %rdx
movq (%rdi), %rax
xorl %esi, %esi
.L2:
cmpq %rdx, %rax
je .L6
addl (%rax), %esi
addq $4, %rax
jmp .L2
причем он одинаковый и для for_each и для accumulate (у меня += возвращает ссылку). Код же с -O3 я приводить не буду потому что в нем развернут цикл, используются векторные инструкции и прочее, но и там версии для accumulate и for_each одинаковые.
Стандартом не гарантируется, что for_each будет оптимизирована так же хорошо, как и цикл, а это важно, если вы пишете переносимый код.
а гарантии по оптимизации циклов стандарт дает что ли?
Кстати, вам не кажется странным тот факт, что специализированная функция для подсчета суммы дает худший результат, чем цикл или использование for_each?
может дело не в accumulate, а в вашей реализации +=?
accumulate не использует +=, вот в чем штука. Оператор поправлю, спасибо.
их никто не дает
а гарантии по оптимизации циклов стандарт дает что ли?
их никто не дает
g++ -std=c++11 main.cpp -o test -O3 && ./test
duration 33.995 ms mseconds
снова что-то не так. Выполнил приведенный вами код:
$ g++ -std=c++11 acc.cpp -o test -O3 && ./test
accumulate
t=291.32 ms
sum=-1471389927
Даже если бы я писал код вручную, у меня не получилось бы лучше.
Очевидно, что можно избавиться от счетчика eax. Для выхода из цикла мы можем вместо него проверять указатель ecx.
даже сложение происходит сразу по двум элементам.
Бедные XMM регистры были унижены до 64-битных.
Если кого-то огорчает, что вынос функции в отдельный файл замедляет тест в 10 раз, то специально для таких случаев есть link time optimization (-flto).
Ну опять он унижает компиляторы, а на деле позорится сам. Включи link-time code optimization, или как оно в GCC называется, и будут у тебя все тесты абсолюно одинаково быстро выполняться.
Единственное, что мой компилятор (VC++ 2013) не переварил — так это не векторизовал цикл при сложении классов. Но при отключенной векторизации получается одно и то же.
Единственное, что мой компилятор (VC++ 2013) не переварил — так это не векторизовал цикл при сложении классов. Но при отключенной векторизации получается одно и то же.
Вы пытаетесь «закостылить» конкретную проблему, не уловив сути. Отдельным модулем я имитировал неизвестное «компилятору» поведение. Это могла бы быть библиотека, например. И класс А может быть мало-ли каким.
В таких случаях проблему нельзя будет решить никакими ручными микрооптимизациями. Основная критика ваших статей в том, что подобные оптимизации в мире современных компиляторов имеют лишь теоретический и педагогический интерес — для обучения устройству компиляторов, например. Для практики программирования в описанных Вами оптимизациях смысла нет, т.к. -O3 -flto сводят все их на нет. Интересны были бы такие оптимизации, которые компиляторы не умеют производить, а особенно, если не сумеют и через 10 лет, но их Вы не описываете…
>закостылить
тут не понял. Что значит закостылить, когда это и полагается использовать?
>не уловив сути
Ну так опишите явно свою задумку. Не все же такие умные. Вот и получаете обвинения.
>Отдельным модулем я имитировал неизвестное «компилятору» поведение
Оно может быть неизвестным только в двух случаях — кодогенерация на лету и внешний вызов. Заниматься микрооптимизациями на границе исполняемого модуля — довольно бестолковая затея. Ну а кодогенерация — особый случай, ее мы не рассматриваем.
>Кстати, вам не кажется странным тот факт, что специализированная функция для подсчета суммы дает худший результат, чем цикл или использование for_each?
В Стандарте сказано, что accumulate:
>Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first,last) in order.
Так что все вопросы к Стандарту. Его писатели полагаются на то, что компилятору все известно и a = a + b даст тот же машинный код, что и a += b.
тут не понял. Что значит закостылить, когда это и полагается использовать?
>не уловив сути
Ну так опишите явно свою задумку. Не все же такие умные. Вот и получаете обвинения.
>Отдельным модулем я имитировал неизвестное «компилятору» поведение
Оно может быть неизвестным только в двух случаях — кодогенерация на лету и внешний вызов. Заниматься микрооптимизациями на границе исполняемого модуля — довольно бестолковая затея. Ну а кодогенерация — особый случай, ее мы не рассматриваем.
>Кстати, вам не кажется странным тот факт, что специализированная функция для подсчета суммы дает худший результат, чем цикл или использование for_each?
В Стандарте сказано, что accumulate:
>Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first,last) in order.
Так что все вопросы к Стандарту. Его писатели полагаются на то, что компилятору все известно и a = a + b даст тот же машинный код, что и a += b.
Раз уж заговорили про костыли, позвольте мне рассказать небольшую историю про эти самые костыли.
Давайте вернемся в те времена, когда компьютеры были большими, а памяти было мало. Когда еще не было формата ELF, а (единственный) компилятор Си не был оптимизирующим. Когда еще не было стандарта Си, а тоненькая книжка за авторством Ритчи и Кернигана еще даже не была написана.
Представьте, что вам надо скомпилировать ядро Юникса. Практически в каждом исходном файле описаны используемые функции и количество их параметров, возможно, даже с именами (без типов, ибо, как мы помним, АНСИ Си еще не существует) и глобальные переменные, которые, в свою очередь экспортятся из других исходных файлов. Так как памяти у нас мало, мы создаем т. н. объектные файлы, которые потом объединяются в один большой исполняемый файл редактором связей, линковщиком. Этот линковщик — хитроумный костыль, придуманный для того, чтобы не тратить кучу памяти для хранения внутренних данных компилятора, что произошло бы, если бы мы компилировали всю программу целиком и сразу. Более того, это положение сохранилось до сих пор, костыль прижился и даже схема компиляции по файлам была стандартизирована и сегодня каждый компилятор, даже в том случае, если ему хватает памяти на компиляцию всей программы сразу, компилирует отдельные Compilation Unit'ы.
К слову, чтобы не писать каждый раз обьявления используемых функций, примерно в то же время придумали заголовочные файлы и их включение в Compilation Unit. Этот костыль тоже дожил до наших дней. Но весь этот абзац был только к слову — речь о редакторе связей нано же.
Так вот, Linking Time Optimization — это костыль, который позволяет оптизировать всю программу целиком, а не по отдельным Compilation Unit'ам. Другими словами — это костыль, скрывающий другой костыль. Кстати говоря, последние версии GCC по умолчанию собираются с включеным флагом -flto, который, как уже пояснили выше, включает этот костыль.
Однако, обнаружилась проблемка с этим ключом: дело в том, что GNU make умеет запускать несколько процессов GCC для компиляции нескольких исходников одновременно. Это назвали паралельной сборкой. И эта возможность напрямую следует из архитектуры make и не является костылем. Линковщик же однопоточный. В результате, время компиляции увеличилось, так как парсинг и кодогенерация — это дешевые операции по сравнению с оптимизацией (тем более, всей программы).
Как же GCC собираются решить эту проблему? Костылем! Дело в том, что можно линковать два объектника и на выходе получить еще один объектник. И эти проженные инженеры собираются использовать возможности того же make для параллельной линковки.
А теперь пару слов о том, как же выглядит процесс компиляции программы с использованием LTO. Компилятор генерирует промежуточное преставление и вместо того, чтобы оптимизировать, сразу дампит его в отдельную секцию ELF файла. А оптимизатор запускается линковщиком.
И даже на этом этапе обнаружились проблемы — получаемые после компилятора объектные файлы оказались просто огромными из-за, по сути, не нужного бинарного кода, который все равно будет выкинут и заменен оптимизированным. А просто так выкинуть этот код нельзя — на него завязаны утилиты ar и nm. Что же делать? Хачить! И после этих костылей, вставленых в эти две утилиты, стало возможным уменьшить размер объектников, без потери возможности использовать статические библиотеки и смотреть список символов, определенных а объектнике.
Сколько костылей из-за линкера насчитали? Вот-вот, а выкинуть его нельзя, ибо эта инфраструктура копилась годами, и потребуются годы, чтобы ее заменить. А так — работает же, хоть и раз в пару лет надо еще одну подпорку поставить.
В сторону: а некоторые считают Autotools одним из самых больших нагромождений костылей на костылях.
Давайте вернемся в те времена, когда компьютеры были большими, а памяти было мало. Когда еще не было формата ELF, а (единственный) компилятор Си не был оптимизирующим. Когда еще не было стандарта Си, а тоненькая книжка за авторством Ритчи и Кернигана еще даже не была написана.
Представьте, что вам надо скомпилировать ядро Юникса. Практически в каждом исходном файле описаны используемые функции и количество их параметров, возможно, даже с именами (без типов, ибо, как мы помним, АНСИ Си еще не существует) и глобальные переменные, которые, в свою очередь экспортятся из других исходных файлов. Так как памяти у нас мало, мы создаем т. н. объектные файлы, которые потом объединяются в один большой исполняемый файл редактором связей, линковщиком. Этот линковщик — хитроумный костыль, придуманный для того, чтобы не тратить кучу памяти для хранения внутренних данных компилятора, что произошло бы, если бы мы компилировали всю программу целиком и сразу. Более того, это положение сохранилось до сих пор, костыль прижился и даже схема компиляции по файлам была стандартизирована и сегодня каждый компилятор, даже в том случае, если ему хватает памяти на компиляцию всей программы сразу, компилирует отдельные Compilation Unit'ы.
К слову, чтобы не писать каждый раз обьявления используемых функций, примерно в то же время придумали заголовочные файлы и их включение в Compilation Unit. Этот костыль тоже дожил до наших дней. Но весь этот абзац был только к слову — речь о редакторе связей нано же.
Так вот, Linking Time Optimization — это костыль, который позволяет оптизировать всю программу целиком, а не по отдельным Compilation Unit'ам. Другими словами — это костыль, скрывающий другой костыль. Кстати говоря, последние версии GCC по умолчанию собираются с включеным флагом -flto, который, как уже пояснили выше, включает этот костыль.
Однако, обнаружилась проблемка с этим ключом: дело в том, что GNU make умеет запускать несколько процессов GCC для компиляции нескольких исходников одновременно. Это назвали паралельной сборкой. И эта возможность напрямую следует из архитектуры make и не является костылем. Линковщик же однопоточный. В результате, время компиляции увеличилось, так как парсинг и кодогенерация — это дешевые операции по сравнению с оптимизацией (тем более, всей программы).
Как же GCC собираются решить эту проблему? Костылем! Дело в том, что можно линковать два объектника и на выходе получить еще один объектник. И эти проженные инженеры собираются использовать возможности того же make для параллельной линковки.
А теперь пару слов о том, как же выглядит процесс компиляции программы с использованием LTO. Компилятор генерирует промежуточное преставление и вместо того, чтобы оптимизировать, сразу дампит его в отдельную секцию ELF файла. А оптимизатор запускается линковщиком.
И даже на этом этапе обнаружились проблемы — получаемые после компилятора объектные файлы оказались просто огромными из-за, по сути, не нужного бинарного кода, который все равно будет выкинут и заменен оптимизированным. А просто так выкинуть этот код нельзя — на него завязаны утилиты ar и nm. Что же делать? Хачить! И после этих костылей, вставленых в эти две утилиты, стало возможным уменьшить размер объектников, без потери возможности использовать статические библиотеки и смотреть список символов, определенных а объектнике.
Сколько костылей из-за линкера насчитали? Вот-вот, а выкинуть его нельзя, ибо эта инфраструктура копилась годами, и потребуются годы, чтобы ее заменить. А так — работает же, хоть и раз в пару лет надо еще одну подпорку поставить.
В сторону: а некоторые считают Autotools одним из самых больших нагромождений костылей на костылях.
То что вы описываете — это не костыли. Это просто устаревшие реализации. Дело в том, что когда они создавались — они были призваны реализовать расширенную функциональность (уменьшить потребление ресурсов во время сборки) и для реализации этой функциональности архитектура решения была адекватная (не костыльная). Сейчас эта функциональность уже утратила свою актуальность, отчасти, и её можно было бы выкинуть, упростив архитектуру сборки, но пока ещё потребность не так сильно назрела.
Sign up to leave a comment.
Веселые старты 2: for_each vs accumulate