Comments 42
Гораздо приятнее в данном случае было бы заменить на std::list, которому всё равно, куда происходит вставка (хотя именно в этом случае можно прекрасно видеть, что не надо просто insert использовать. Но это просто пример, не более
Кажется, это неудачный пример, т.к. в этом случае deque подходит лучше: время вставки у него примерно такое же, как у листа, но зато итерация намного быстрее.
Что касается ускорения, банальный std::vector + push_back + reverse, вероятно, будет намного быстрее варианта с std::list.
По самой идее. Мне кажется как статический анализатор это практически бесполезно. Да, заменить list на forward_list довольно просто и безболезненно. Но в подавляющем большинстве случаев выбор контейнера все-таки сильно зависит от количества данных, с которыми он будет работать (и как работать). И совсем неочевидно будет ли list работать быстрее вектора, даже если у нас все операции — вставки в начало. Все зависит от данных. А вот давать какие-то советы на профиле выполнения было бы интересно…
Ковыряние корок — да, дело такое. Но даже сейчас компиляторы делают очень много преобразований, которые могут совсем не соответствовать коду, который написан.
А идея с динамическим анализом мне и самому очень нравится, но там будут всё равно частично переиспользоваться наработки от статического анализатора, так что работа явно не насмарку.
Всему виной то, что на данный момент только один С++ компилятор реализует оптимизацию по удалению динамических аллокаций — Clang
потому, что с точки зрения с++ это некорректная оптимизация. Дело в том, что аллокатор может выкинуть исключение при нехватке памяти, и у этого случая совершенно иная логика обработки. Чтобы такие оптимизации были корректными, надо менять стандарт
en.cppreference.com/w/cpp/language/new
В данном случае мы видим использование крайне неэффективной в случае std::vector операции — вставка в начало контейнера. Все С++ программисты знают, что это крайне плохо делать, так как заставляет все элементы сдвигаться каждый раз, что приводит к большим затратам на копирование\перемещение. Гораздо приятнее в данном случае было бы заменить на std::list, которому всё равно, куда происходит вставка, или std::deque (хотя именно в этом случае можно прекрасно видеть, что не надо просто insert использовать. Но это просто пример, не более :)
Как по мне, так в данном случае лучше оставить вектор (под него можно зарезервировать память заранее, что даст еще выигрыш), а вот в цикле печатать с конца.
А в целом, идея очень интересная. Хотелось бы посмотреть на всё это в боевых условиях, когда использвание не вырождено до пары действий.
Правильно ли я понимаю, что это будет только для C++? Или есть более глобальные планы, при условии, что с С++ получится достаточно хорошо?
Да, бывают. Пример с std::vector -> std::array, например — наиболее частое, что я вижу на код-ревью.
такие оптимизации часто ломают код — рано или поздно какое-нибудь входящее сообщение не влезает в array. Возможно, заменять std::vector лучше не на std::array, а на boost::small_vector, например. И тогда большинство сообщений поместится на стеке, а только часть будет аллоцироваться.
На следующем кругу оптимизаций можно не полагаться на размер сообщений и буферов, а пытаться максимально переиспользовать аллоцированную память. Т.е. либо гонять данные move'ами (тут vector как правило будет несколько эффективнее small_vector и значительно эффективнее array) либо преаллоцировать буферы на этапе инициализации и расширять по надобности (тут вектор тоже чаще будет оптимальным вариантом т.к. small_vector рано или поздно расширится).
В конечном итоге мы приходим к тому, что для большинства случаев вектор является оптимальным или квазиоптимальным вариантом. И ключевое здесь — «при правильном использовании». Пара из аллокации/деаллокации часто будет дешевле копирования в/из std::array.
Вывод: сначала замеряй, потом оптимизируй.
Естественно, что сначала замеряется, а потом исправляется. Но замедления при замене std::vector на std::array в конкретно этом случае я не вижу. Вот когда понадобится менять размер контейнера, вот тогда и поменяют контейнер на std::vector.
github.com/KDE/clazy/blob/master/README.md#list-of-checks
Всему виной то, что на данный момент только один С++ компилятор реализует оптимизацию по удалению динамических аллокаций — Clang.
Что-то у меня не получается добиться этого даже для самого примитивного случая: godbolt.org/z/iozO7C
Не понимаю, что значит оптимизация «для галочки».
Всё очень просто. Добавлять бесполезные оптимизации для использования их в последующей конкурентной борьбе. Уровень этой борьбы может быть разный. На уровне авторов реализовавших оптимизацию, либо на уровне оптимизаций.
По поводу самой оптимизации. Я посмотрел — и тот и тот компилятор умеет убирать malloc/free, шланг умеет убирать и из вектора(нужен libc++). Почему не убирает из libstdc++ — напишу ниже.
По поводу гцц — он так же умеет всё удалять. Но он не игнорирует исключения из op new. Это починить несложно, но этого почему-то никто не сделал и предположить причину так же несложно.
В векторе из stdlibc++ есть проверка на null. Из-за это проверки оптимизатор не может связать выход malloc co входом free.
Аналогично, тут видна фундаментальная разница между gcc(действительно сильным оптимизатором) и clang(больше пыли в глаза). Я написал код, который обходит проверку и clang видит её — он убрал if, но он не смог связать выход malloc co входом free. О таких мелочах как замена malloc + memset(0) на calloc я и не говорю.
Т.е. на самом деле оптимизации давно есть и в gcc и они лучше. Если стандарт разрешил игнорировать исключение из new, то гцц просто его не игнорирует. Это не значит что оптимизации нет.
godbolt.org/z/6G5uVj
На самом деле мне не нравится текущий подход к оптимизации в Clang/LLVM в плане того, что все (подавляющее большинство согласно ответу в clang-dev mailing list) оптимизации проводятся на уровне LLVM IR (я не знаю, как оно сделано в GCC — мне не нравится читать их исходники). Потому что при переходе на LLVM IR по моему мнению мы теряем достаточно много информации, которую могли бы использовать для оптимизации — LLVM IR слишком низкоуровневый. Можно выкручиваться путём прокидывания (аннотирования) IR с фронтенда, чтобы мидленд уже обладал бОльшим кол-вом информации. Но это выглядит ужасно. На мой взгляд это не совсем эффективно.
По поводу сравнения оптимизаторов LLVM vs GCC. Согласно тестам того же Phoronix, оптимизатор LLVM не так уж и плох, так что я не могу согласиться, что там так уж всё плохо и что это всё «пыль в глаза».
А Вы случаем не знаете, где эта оптимизация реализована в GCC или LLVM? Я сходу не смог найти, в какой момент они занимаются схлопыванием аллокаций.
Нет, не интересовался. Но предположить можно. В С++ семантически определены аллокаторы, в си они есть на уровне libc и их можно определять по именам. В так же есть [[gnu::malloc/alloc_size]]. Т.е. компилятор знает где malloc, а где free. И даже знает какая длинна у аллоцируемой памяти.
Далее работают базовые оптимизации. Т.е. если компилятор не найдёт побочных эффектов вызова функции, то он спокойно может её убирать. Функции у нас внешние и узнать что в них происходит мы не можем. Для решения этих проблем уже давно существуют всякие [[gnu::pure/const]].
Получается, что компилятор точно знает значение переменной на всём протяжении программы(скоупа). Даже если он его не знает, то он знает изменяется он или нет.
Соответственно, инвариант тут простой. Если выход из маллока приходит во free в первоначальном виде, то free не имеет эффекта. На malloc можно просто повесить [[gnu::pure]], а free реализовать как: godbolt.org/z/BBpOVP
В данном случае компилятор знает, что функция не может вернуть null и проверка не срабатывает. Скорее всего подобные(допустим там хранить оригинальное значение или что-то типа того) хинты есть для внутреннего представления компилятора.
gcc умеет дампить ir. Я сейчас не могу посмотреть(как это сделать на godbolt я не нашел). Если успею посмотреть — поищу как там сделано.
На самом деле мне не нравится текущий подход к оптимизации в Clang/LLVM в плане того, что все (подавляющее большинство согласно ответу в clang-dev mailing list) оптимизации проводятся на уровне LLVM IR (я не знаю, как оно сделано в GCC — мне не нравится читать их исходники). Потому что при переходе на LLVM IR по моему мнению мы теряем достаточно много информации, которую могли бы использовать для оптимизации — LLVM IR слишком низкоуровневый. Можно выкручиваться путём прокидывания (аннотирования) IR с фронтенда, чтобы мидленд уже обладал бОльшим кол-вом информации. Но это выглядит ужасно. На мой взгляд это не совсем эффективно.
Полностью согласен. Да и компиляторы уже давно выносят на уровень языка ручки. Но этого мало. Программисты и языки(С++) уже дозрели до управления оптимизациями, компиляцией.
К тому же, тут есть и другая проблема. Если мы уберём ir, то куда пойдут всякие свифты/расты?
По поводу сравнения оптимизаторов LLVM vs GCC. Согласно тестам того же Phoronix, оптимизатор LLVM не так уж и плох, так что я не могу согласиться, что там так уж всё плохо и что это всё «пыль в глаза».
Там тесты говно. У llvm очень плохой кодоген и всякие фундаментальные оптимизации. За примерами далеко ходить ненужно — в соседнем посте парсер json«а на llvm работает почти в 2раза медленнее.
В llvm есть свои преимущества — там больше всякие хайлевел реплейс-оптимизаций и более агрессивная дефолтная настройка. Там глубина анализа циклов больше. Больше анроллинга.
gcc более универсальный код генерирует. Ну и в контексте С++ у него намного выше скорость компиляции. Хотя clang начинал хайпиться как „собирает быстрее“. Сейчас в gcc завезли модное раздельное lto и собранный с ним гцц стал ещё быстрее.
Первая проблема заключается в том, что для анализатора на данный момент все ветки кода равновероятностные. Точнее, он даже не знает о такой вещи как разные ветки выполнения кода.
Это выливается в проблемы с анализом для примерно вот такого кода:
Уже есть поддержка likely/unlikely. На это и прочее есть только один адекватный ответ — язык.
Осталось только научить язык в constexpr/eval-контексте получать мета-информацию. Какие методы используются в контексте функции и прочее, на базовом уровне. Нужна поддержка получения окружения для объекта. Нужны MUTexptr/eval. Нужно локализовать компилтайм-контекст:
godbolt.org/z/EQnbPF
Всё это уже работает сейчас, и компилятор знает, что там >= 42. Нужно просто это принести на уровень языка. Случае, если кол-во вызовов неизвестно — можно ввести флаг аналогичный std::is_constant_evaluated()
Будет сборка статистики, будут рефлексия, будут метаклассы, будут интерфейсы. Всё это позволит использовать один интерфейс. А далее оптимальный контейнер будет генерироваться автоматически исходя из контекста. Далее мы заменим мусорные функции и убогий inline чем-то на вроде «parametric expressions» и получим расширение анализа на халяву.
Подобные механизмы универсальны и позволят делать множество всего. Это очень большая проблема С++, да и не только. Заниматься параллельно тысячей разных костылей и решать под капотом сложные задачи. И с т.з. каждого участника это кажется выгодным «сделаю нужную мне фишку без лишней сложности», но суммарно трудозатраты получаются куда большие.
Вместо добавления рефлексии и расширения шаблонов — костыль на костыле. parameter pack у нас не объект, а какой-то неведомый треш. Вместо pack.size() у нас очередной костыль sizeof...(), костыли вида std::get<0>(std::tie(...args)). А какие приключения с откусыванием начала/конца. Постоянно переизобретаются очередные for… и прочая невиданная хрень. if constexpr, потом будет for/switch и прочее.
Приоритеты в комьюнити просто неадекватные. Мы делаем модули и боремся с макросами, но условной компиляции нет, вообще. На __LINE__ всё остановилось и то засунули «в ящик».
Сейчас какой-то тренд намечается на решение фундаментальных проблем. Контракты, концепты, улучшение шаблонных параметров. Я не считаю правильным отходить от этого тренда.
В связи с этим я считаю, что реализация как анализ и советы уровня «вы неправильно используете std::list замените на vector» и прочее — это вполне себе годно и имеет смысл. Реализовывать же именно как оптимизации — смысла имеет мало, ведь адекватная реализация требует наличия тех фишек, которых в С++ нет.
Поэтому ключевым, как я считаю, в решении этой проблемы является добавление этих фишек в С++, а уже потом оптимизации. Это будет либо очень слабо, либо будут переизобретаться в кишках очередные подобия тех фишек, что должны существовать в С++.
Я согласен с тем, что поддержка должна постепенно появляться в языке. Также я согласен с каждым доводом о том, что было бы неплохо добавить в язык.
Но я не могу согласиться с тем, что этого не должно быть в каком-то виде в качестве оптимизации. Так как мы живём в мире С++ и у нас мегатонны легаси кода, который уже переписывать никто не будет. Возможно, стоит задуматься об утилитах, которые будут дополнительно размечать уже существующий код (хоть теми же атрибутами likely\unlikely, хотя это уже автоматически делается при включении PGO). Просто на данный момент компиляторы и так делают очень много «грязной» работы по оптимизации, и реализовано это всё очень и очень ужасно (стоит хотя бы взглянуть на InstCombine в LLVM и его аналог у GCC — не знаю как для Вас, а для меня это вырвиглазно). Есть идеи как это пофиксить (за подробностями можно отправиться почитать работы у John Regehr), но пока что оно сделано именно так, и нам надо с этим жить. И то, что я предлагаю, это по сути и есть одна из таких «грязных» методик.
Касательно движения С++… Мне сложно сказать, двигается ли С++ сейчас в правильном направлении. Я лично больше всего жду нормальной compile-time рефлексии с поддержкой атрибутов (на данный момент атрибуты не поддерживаются — можно это подсмотреть в докладе David Sankel c CppNow 2019).
Но я не могу согласиться с тем, что этого не должно быть в каком-то виде в качестве оптимизации. Так как мы живём в мире С++ и у нас мегатонны легаси кода, который уже переписывать никто не будет.
Я согласен с ораторами выше. Лучше туда не лезть. Кто там знает чего туда напихано. Но в какой-то мере это имеет место быть, с этим я так же согласен.
Просто на данный момент компиляторы и так делают очень много «грязной» работы по оптимизации, и реализовано это всё очень и очень ужасно (стоит хотя бы взглянуть на InstCombine в LLVM и его аналог у GCC — не знаю как для Вас, а для меня это вырвиглазно).
Я знаком с clang на достаточно базовом уровне и мой опыт заканчивается на портировании пары наработок на новую версию шланга и написания примитивного кодогена на libtooling. С llvm ещё меньше.
Но в целом я согласен да, существует множество вещей которые проще реализовать на уровне хайлевел оптимизаций. А ещё лучше мочь ими управлять.
Касательно движения С++… Мне сложно сказать, двигается ли С++ сейчас в правильном направлении. Я лично больше всего жду нормальной compile-time рефлексии с поддержкой атрибутов (на данный момент атрибуты не поддерживаются — можно это подсмотреть в докладе David Sankel c CppNow 2019).
А я хочу смерти атрибутам. Это рудимент gcc и что-то «снизу». Нужно заменить их на нормальные аннотации aka java.
Ну и С++ нужно взять пример со всяких модных языков. Необходима некая экспериментальная ветка, которая существует вне стандарта и на которой будут обкатываться новшества, которая будет популяризировать С++ и быстро реагировать на запросы комьюнити/обратную связь.
Сейчас мы имеем то, что почти никто не знает о тысячах наработках. Обычные люди не будут читать патчи на стандарт и строгие формулировки. И искать форки компиляторов в интернете.
Уже есть поддержка likely/unlikely. На это и прочее есть только один адекватный ответ — язык.
Вообще говоря, никто не мешает программисту действовать в два прохода: скомпилировать со сборщиком профиля, запустить на тестовых данных и тем самым собрать профиль, и скомпилировать с использованием профиля. Пруф для gcc, показывающий как минимум возможность таких оптимизаций. Имхо там больше использующих профиль оптимизаций.
Такой вариант имхо эффективнее, чем пытаться наобум что-то заменять. Поэтому с ипользованием профиля оптимизация смысл тоже имеет.
Также я согласен, что имеет смысл сделать анализатор, советующий заменить один контейнер на другой. Его тоже надо бы связать с профилем для более качественных советов.
Вообще говоря, никто не мешает программисту действовать в два прохода: скомпилировать со сборщиком профиля, запустить на тестовых данных и тем самым собрать профиль, и скомпилировать с использованием профиля. Пруф для gcc, показывающий как минимум возможность таких оптимизаций.
Это не новость для меня.
Имхо там больше использующих профиль оптимизаций.
Проблема не в этом.
Такой вариант имхо эффективнее, чем пытаться наобум что-то заменять. Поэтому с ипользованием профиля оптимизация смысл тоже имеет.
Что касается «эффективней» и «наобум». И то и то верно лишь частично. Не всегда можно собрать с программы адекватный трейс. И не все обладают пониманием уровня «ставим наобум». Но я не об этом говорил.
Абсолютно неважно кто расставит эту мета-информацию. Она без проблем может быть экспортирована из профиля. Как и может быть указана руками. Ключевым тут являет то(и именно об этом я говорил), что эта(и любая другая) информация должна быть доступна на уровне языка.
В моём понимании задачей pgo будет не (о)птимизация, ведь оптимизация это такое же тыканье «наобум». Я уже приводил автору достаточно очевидный пример. У нас есть строка и sso. Исходя из статического анализа/профиля мы можем получить длины используемых строк.
А ещё лучше и генерацию профиля тоже вынести на уровень языка. Мы сможем добавлять свои метрики, расширять/переопределять существующие. Тогда ненужно будет неуправляемых костылей в каждом из компиляторов, компиляторы не будут проводить оптимизация через одно место. Они всегда будут хуже в сравнении с хайлевел.
Но, существует фундаментальная проблема у pgo. Трейс никак не может ограничить входящие данные. Даже если у нас 100% строк в программе — 5 байт, то мы никак не можем заменить их на 5/6-байтные массивы. Просто потому, что в любом момент может прийти что угодно.
И решение существует только на уровне языка. Это контракты, это система типов. Мы никогда на научим тупые лоулевел оптимизации понимать семантику наших типов. Да даже понимать семантику контрактов вряд ли научим. И учить лоулевел понимать хайлевел абстракции — куда сложнее.
С метриками на уровне языка мы всегда сможет показать программисту при сборке сообщения вида уровня «строки 5-байт. Ограничьте контрактом/поменяйте тип». Это ещё более частный случай оптимизации, которую делает автор.
Точно так же нам очень сложно выявить источники данных без тех же контрактов/любой другой метаинформации. Если у нас будут нормальные opaque-тимы, а не пытки их закостылить — мы всегда сможем узнать источники данных.
Ничего из этого работать не будет(вообще или нормально) с оптимизациями где-то там в кишках.
Кмк — автоматическая оптимизация сложна и это ненужно, как минимум без поддержки в отладчиках. А вот диагностические предупреждения с рекомендациями очень даже кстати былы бы. В тех же шлангах для этого уже есть интерфейс (diagnostics кажется называется). Более того, современные ide, и прочие vim'ы уже давненько как умеют применять подобные рекомендации по хоткею в заданной строке.
Я думал — разговор не про сложности реализации а про интерфейс функциональности. Лично я — не стал бы такими флагами пользоваться без поддержки отладчика, а может даже и с ней.
Эта эвристика либо должна быть очень умной, либо она будет работать чуть менее чем никогда, на любом полиморфизме(статический/динамический) она должна отключаться.
С другой стороны, в точке diagnostics, полезность даже простых эвристик очевидна:
- Разработчик видит, что возможно можно лучше, но решение за ним
- Есть информация для размышления, происходит обучение
Так же — нужно предусмотреть механизм игнора этой диагностики, в тех местах, где опытный разработчик уже решил, что таки верно выбрал структуру данных.
Простая аналогия — допустим мы хотим отучить разработчиков коммитить код с кривым форматированием. Можно конечно вызывать clang-format на ci и автоматом коммитить. Почему это плохо:
- Процесс автоформатирования может содержать ошибки
- Разработчик продолжит косячить
- Ресурсы инфрастурктуры продолжат тратиться
- Бывает код который плохо выглядит после автоформатирования
Как следует поступить: заставить разработчика проделать форматирование на своей стороне. Например сбоем на CI или отказом в push'e. Тогда, рано или поздно в репозиторий начнёт поступать отформатированный код, либо человек перестанет закрывать задачи.
Профиты:
- Обучаем разработчика
- Убираем плохо контролируемую точку отказа
- Получаем более читабельный код, в лучших традициях C++ — большинство автоматом, но где нужно подвинули инструмент в сторону и сказали "я лучше знаю"
Я вот мечтаю, что когда-нибудь смогу писать код наподобе
best::container abc;
best::solve_equation();
best::detect_cats();
Где внутри best лежит несколько десятков способов решить каждую задачу, а оптимизатор потом перебором решит, в какой строке какой способ лучше использовать.
И ещё чтобы при выходе новых научных статей оптимизатор сам обновлял программу.
int main() {
best::my_problem();
}
И ещё чтобы при выходе новых научных статей оптимизатор сам обновлял программу.
а может лучше бенчмаркать?
(Статический) Подбор оптимальных контейнеров в программах на C++