Проблема
На CoreHard 2018 Autumn (очень хорошая конференция, приезжайте) я рассказывал о том, что C++ компиляторы плохо оптимизируют в настоящий момент. И одной из моих претензий было то, что компиляторы не могут оптимизировать использование контейнеров в наших программах. Давайте рассмотрим несколько примеров кода.
void foo() {
std::vector<int> v(42);
}Казалось бы в таком простом случае компилятор должен мочь оптимизировать данную функцию и просто выкинуть объявление переменной типа std::vector, так как начиная с C++14 компилятору разрешено убирать динамические аллокации памяти, но компилятор это не делает. Всему виной то, что на данный момент только один С++ компилятор реализует оптимизацию по удалению динамических аллокаций — Clang. Все остальные компиляторы просто пока что не умеют так делать. Но даже Clang может сделать это в ограниченном количестве случаев.
В данном случае мы могли бы заменить std::vector на std::array, при условии что размер выделяемого вектора не слишком большой, так как у нас банально может не хватить стека для такой замены. Такая замена уберёт довольно дорогую аллокацию памяти на кучу, а плюсом будет то, что при использовании std::array компилятор уже сможет выкинуть std::array вообще из функции!
Если мы говорим про оптимизацию производительности, то предлагаю рассмотреть следующий пример:
void foo() {
std::vector<int> v;
for(int i = 0; i < 42; ++i) {
v.insert(v.begin(), 42);
}
for(const auto val : v) {
std::cout << val << ' ';
}
}В данном случае мы видим использование крайне неэффективной в случае std::vector операции — вставка в начало контейнера. Все С++ программисты знают, что это крайне плохо делать, так как заставляет все элементы сдвигаться каждый раз, что приводит к большим затратам на копирование\перемещение. Гораздо приятнее в данном случае было бы заменить на std::list, которому всё равно, куда происходит вставка, или std::deque (хотя именно в этом случае можно прекрасно видеть, что не надо просто insert использовать. Но это просто пример, не более :)
Давайте рассмотрим ещё один пример кода:
void foo() {
std::list<int> v;
for(int i = 0; i < 3; ++i) {
v.push_front(i);
}
for(const auto val : v) {
std::cout << val << ' ';
}
}В этом случае мы можем заметить, что мы можем безболезненно заменить std::list (да, я знаю, что его редко кто использует) на std::forward_list. При это в данном случае мы абсолютно ничего не потеряем, зато получим экономию памяти. Естественно, что компилятор сейчас таких оптимизацией не делает.
Похожий трюк можно провернуть и в следующем примере:
void foo() {
std::deque<int> v;
for(int i = 0; i < 3; ++i) {
v.push_back(i);
}
for(int i = 0; i < 3; ++i) {
std::cout << v.back() << ' ';
v.pop_back();
}
}Здесь мы можем видеть, что на самом деле нам нужен не std::deque, а std::stack. Назвать это оптимизацией нельзя, так как std::stack это адаптер, и по умолчанию он использует внутри std::deque (если пользователь не укажет иначе). Здесь можно больше говорить о семантической оптимизации, т.е. упрощении кода для понимания. С моей точки зрения это тоже важно. Если вы спросите «А может такая замена тоже даёт прирост производительности?», я отвечу «Возможно. Смотрите детали реализации в вашей версии стандартной библиотеки».
Что ж, я думаю, достаточно примеров. Каждый из вас тоже может придумать их уйму.
Используемые средства
Для реализации статического анализатора я использовал Clang Static Analzyer (CSA) и Clang Tidy, которые входят в поставку LLVM. Я выбрал именно эти средства, так как считаю их наиболее перспективными среди открытых средств статического анализа. К тому же Clang предоставляет один из самых качественных парсеров языка С++, которым не могут похвастаться другие статические анализаторы (если они конечно не используют libclang).
И CSA, и Clang Tidy являются статическими анализаторами, оба входят в состав LLVM. В чём же разница? Разница в том, что Clang Tidy предназначен для написания простых проверок, которые в основном заключаются в том, чтобы найти какой-то паттерн на дереве абстрактного синтаксиса, вывести какое-либо предупреждение и, возможно, заменить его автоматически на другой. Более подробно можете ознакомиться с Clang Tidy здесь.
CSA же предназначен для написания более «серьезных» и ресурсозатратных (как с точки зрения реализации, так и с точки зрения времени выполнения\затрачиваемой памяти) проверок. Там, например, доступен механизм символьного выполнения.
Я решил реализовать проверку в CSA, так как она не кажется мне банальной, к тому же в будущем она будет становится всё тяжелее и тяжелее. А запускать было решено через Clang Tidy, так как данный статический анализатор имеет множество интеграций с различными IDE.
Как будем (пытаться) решать проблемы
Для начала стоит ввести пару довольно сильных ограничений, которые связаны в основном с тем, что это пока что только прототип:
- Анализ только на уровне функций; данное ограничение означает, что не будет проводиться анализ между функциями, а также между единицами трансляции. Ограничение на анализ между функциями было наложено для упрощения реализации данного анализа и в будущем может быть относительно легко исправлено путём запуска статического анализа для всей единицы трансляции, а не только для каждой функции. Ограничение на анализ между единицами трансляции накладывается существующими ограничениями в CSA, которые скоро будут исправлены (коммиты уже вливаются в апстрим);
- Поддержка только ограниченного множества контейнеров. Это относительно легко исправляется в будущем путём добавления новых правил для новых контейнеров.
- Использование для анализа только дерева абстрактного синтаксиса. Так как для прототипирования это наиболее простой тип анализа. Для более точных результатов конечно можно попробовать использовать хотя бы символьное выполнение, но у этого метода есть и свои минусы. Более подробно про методы можно почитать вот тут.
Сейчас в прототипе реализован следующий простой алгоритм:
- Сначала на дереве абстрактного синтаксиса находим вершины, которые отвечают за объявление переменных типа контейнера, которые мы поддерживаем.
- Затем находим операции, которые относятся к данным контейнерам, классифицируем их и сохраняем эту информацию во временный кеш.
- После достижения конца функции анализируем собранную статистику и исходя из заранее заданных правил выдаём рекомендацию по применению того или иного контейнера.
Классификация операций над контейнерами на данный момент следующая (будет расширяться в будущем):
- Добавление элемента в начало контейнера.
- Добавление элемента в середину контейнера.
- Добавление элемента в конец контейнера.
- Удаление элемента из начала контейнера.
- Удаление элемента из середины контейнера.
- Удаление элемента из конца контейнера.
Классификация на данный момент неполная и даже по этому списку работает не совсем корректно. Например, операцию insert, даже если она производится в начало, анализатор классифицирует как вставка в середину, хотя на самом деле это совсем не так.
Борьба с ложными срабатываниями
В любом статическом анализе главной головной болью являются ложные срабатывания. Если их слишком много, то полезные сообщения теряются в мусоре. Поэтому в этом случае приходится поступать очень консервативно и выдавать предупреждения только в случаях, когда мы действительно уверены в своей диагностике и можем вполне сказать, что в каком-то месте в коде действительно что-то не так.
Если мы говорим про оптимизации компилятора, то там всё ещё печальнее — правильная оптимизация не может изменять поведение программы по Стандарту С++ (иначе грош цена такому оптимизатору). И пессимизации вводить оптимизация тоже не должна :) Так что здесь надо быть намного аккуратнее в своих решениях.
В данном анализаторе данная борьба вылилась в то, что если анализатор видит, что совершается какая-то неподдерживаемая на текущий момент операция, то анализ для данного контейнера отключается.
Недостатки и возможные пути их решения
Проблем у данного метода несколько.
Первая проблема заключается в том, что для анализатора на данный момент все ветки кода равновероятностные. Точнее, он даже не знает о такой вещи как разные ветки выполнения кода.
Это выливается в проблемы с анализом для примерно вот такого кода:
void foo(int* ptr, std::vector<int>& v) {
if(ptr == nullptr) {
v.insert(v.begin(), 42);
} else {
v.push_back(84);
}
}Скорее всего в нашем приложении эти ветки кода имеют не равные вероятности исполнения, так как в реальном мире обычно указатель обычно указывает на что-то нормальное, а не на nullptr. В том же LLVM есть статические эвристики на данный счёт. Например, он учитывает и вышеприведённый случай со сравнением указателей с nullptr, и сравнение между собой на равенство значений двух переменных с плавающей точкой, и некоторые другие интересные случаи. Но это всё больше похоже на костыли, и с моей точки зрения действительно решением данной проблемы является добавление динамического анализа или инструментирования.
Вторая проблема заключается в отсутствии поддержки пользовательских контейнеров. Мы живём в мире C++, тут любят велосипедить (оставим обсуждение причин данного не всегда плохого явления за рамками данной статьи) всё, включая свои контейнеры. Примерами могут являться всё тот же LLVM, LibreOffice и многие другие. В связи с этим возникает вопрос — а как анализировать и контейнеры не из библиотеки STL? Ведь хотелось бы включить анализ для как можно большего числа контейнеров.
Тут есть разные пути решения проблемы.
Первый заключается в том, чтобы пользователь аннотировал свои контейнеры каким-то образом (специального вида комментарий, С++ атрибуты, что-нибудь ещё). С данным методом проблема в том, что надо понять, как вообще аннотирование проводить, какая информация нам нужна для качественного анализа. Ещё проблемой может являться модификация кода самих контейнеров, что не всегда возможно.
Второй способ предлагает пользователю механизм по написанию своих правил. На данный момент в анализаторе правила вшиты в исходный код самого анализатора, и если пользователь хочет добавить свои правила, то ему будет нужно скачать исходный код анализатора, собрать его, разобраться как писать проверки, написать, пересобрать и так далее. Можно предоставить пользователю способ задания своих проверок на каком-нибудь DSL, где пользователь пишет только проверки под свои контейнеры, а всей рутиной занимается сам анализатор. Я данный способ рассматриваю как более перспективный, нежели предыдущий.
Также не поддерживается автоматическая замена контейнеров, так как данного функционала нет в CSA (но есть в Clang Tidy). Но в сложных случаях проводить автозамену не всегда является тривиальной задачей и анализатор работает скорее в полуручном режиме.
Возможные применения
Применений у данного вида анализа я вижу несколько:
- Как статический анализатор. Тут всё просто — ещё одна проверка статического анализа, которую вы запускаете как вашей душе угодно (руками, в IDE автоматически по ходу разработки, на CI и т.д.), где вам возможно будет дана подсказка, что где-то вы могли бы подобрать контейнер и получше.
- Как оптимизация в компиляторе. В ряде случаев мы можем гарантировать, что замена контейнера точно отрицательно не скажется на производительности. Например, замена std::vector для малых известных во время компиляции размеров на std::array или замена std::list на std::forward_list, когда нам не нужна двусвязность и мы не берём размер у списка. Компилятор мог бы заменять контейнеры на более оптимальные и без нашего ведома, как он это делает уже для очень большого количества вещей.
- Как динамический анализатор. Это то направление, которое мне кажется наиболее перспективным для данного вида анализа. Ведь с помощью знания о профиле выполнения программы мы, например можем получить такую важную для нас информацию как вероятности выполнения каждой ветки кода. А это необходимо для более точной оценки. А с таким анализом уже можно и думать в сторону интеграции с PGO...
Также стоит заметить, что данный метод применим конечно же не только для программ на С++. Мне бы очень хотелось видеть такого рода статический анализ\оптимизации в компиляторе и для других языков программирования. Например, статический анализатор SAP для ABAP уже умеет проводить статический анализ оптимальности на базовом уровне, что не может не радовать. Если знаете подобные проекты для других языков программирования — пишите в комментариях и я добавлю в статью!
Работы в схожих направлениях
Для мира С++ я нигде подобных анализаторов не нашёл. Для мира ABAP я выше уже упоминал анализатор, который может находить неэффективные операции для некоторой части стандартных контейнеров, но насколько мне известно там реализован совсем простой статический анализ.
Гораздо более интересной работой является Chameleon — динамический анализатор для Java, который очень хитро сделан. Они немного подкрутили JVM, и во время работы собирают различную статистику по использованию контейнеров, и в зависимости от текущего профиля нагрузки выбирают те или иные контейнеры и подменяют их автоматически во время работы. К сожалению, исходники закрыты и получить их нет ни единого шанса (я пытался).
Также рекомендую посмотреть на различные работы (их много) по SETL. В них авторы также часто затрагивали вопросы об автоматическом выборе контейнера.
Ссылки
- Текущая реализация на GitHub
- C++ Russia 2017: Юрий Ефимочев, clang-tidy: путешествие внутрь C++ Abstract Syntax Tree
- Chameleon: Adaptive Selection of Collections
- Clang Static Analyzer guide
- Русскоязычный чат по разработке компиляторов в Telegram. Если интересуетесь — заходите, очень интересно там. Только аккуратнее с флудом — за него сразу карают :)
Вместо заключения хотел бы заострить внимание на том, что это пока что только прототип и он имеет слишком много «дыр» в реализации. В данной статье я просто хочу поделиться с вами идеей подобного анализа и его популяризации. Ну и может кого-то заинтересует данная тема и появится желание подключиться к проекту — я буду только рад! К тому же вы всегда можете собрать данный анализатор у себя попробовать его на своих тестовых примерах.
Если у вас есть чем дополнить материал, сталкивались с подобной задачей или просто обладаете какой-то информацией, которая может быть полезна по данной теме — прошу не стесняться и делиться данной информацией в комментариях.
Спасибо за внимание!
Комментарии (42)
myxo
09.06.2019 19:08+3Ох… я уже представляю себе удовольствие ковырять дамп, где компилятор внезапно заменил один контейнер на другой…
По самой идее. Мне кажется как статический анализатор это практически бесполезно. Да, заменить list на forward_list довольно просто и безболезненно. Но в подавляющем большинстве случаев выбор контейнера все-таки сильно зависит от количества данных, с которыми он будет работать (и как работать). И совсем неочевидно будет ли list работать быстрее вектора, даже если у нас все операции — вставки в начало. Все зависит от данных. А вот давать какие-то советы на профиле выполнения было бы интересно…
ZaMaZaN4iK Автор
09.06.2019 19:12ну в некоторых случаях мы гарантированно можем доказать, что один контейнер будет быстрее другого (смотрите пример с std::vector vs std::array).
Ковыряние корок — да, дело такое. Но даже сейчас компиляторы делают очень много преобразований, которые могут совсем не соответствовать коду, который написан.
А идея с динамическим анализом мне и самому очень нравится, но там будут всё равно частично переиспользоваться наработки от статического анализатора, так что работа явно не насмарку.
Antervis
09.06.2019 20:13Всему виной то, что на данный момент только один С++ компилятор реализует оптимизацию по удалению динамических аллокаций — Clang
потому, что с точки зрения с++ это некорректная оптимизация. Дело в том, что аллокатор может выкинуть исключение при нехватке памяти, и у этого случая совершенно иная логика обработки. Чтобы такие оптимизации были корректными, надо менять стандартZaMaZaN4iK Автор
09.06.2019 20:31+2Корректная. Начиная с С++14.
en.cppreference.com/w/cpp/language/new
VMarkelov
09.06.2019 20:33+1В данном случае мы видим использование крайне неэффективной в случае std::vector операции — вставка в начало контейнера. Все С++ программисты знают, что это крайне плохо делать, так как заставляет все элементы сдвигаться каждый раз, что приводит к большим затратам на копирование\перемещение. Гораздо приятнее в данном случае было бы заменить на std::list, которому всё равно, куда происходит вставка, или std::deque (хотя именно в этом случае можно прекрасно видеть, что не надо просто insert использовать. Но это просто пример, не более :)
Как по мне, так в данном случае лучше оставить вектор (под него можно зарезервировать память заранее, что даст еще выигрыш), а вот в цикле печатать с конца.ZaMaZaN4iK Автор
09.06.2019 20:33Естественно. И я полностью согласен, что так будет лучше. Поэтому я и написал, что это просто пример и не более
VMarkelov
09.06.2019 21:49+1Это я на всякий случай написал, чтобы не забыть в анализаторе, что отдельные нюансы могут сильно изменить расклад сил. Вот только не представляю насколько легко добавить подсказки анализатора для таких случаев.
А в целом, идея очень интересная. Хотелось бы посмотреть на всё это в боевых условиях, когда использвание не вырождено до пары действий.
Правильно ли я понимаю, что это будет только для C++? Или есть более глобальные планы, при условии, что с С++ получится достаточно хорошо?ZaMaZaN4iK Автор
09.06.2019 22:02Это очень правильный вопрос. На самом деле планы есть, так как контейнеры не очень то и сильно зависят от языка программирования — основы то одни и те же. Основная проблема здесь в том, что нет одного инструментария под все ЯП (или хотя бы под множество). Если мы говорим всё про тот же LLVM, то там общие части начинаются только с LLVM IR, а я работаю ещё до него. Конкретно на данный момент я больше всего заинтересован именно в C++. Какой ЯП следующий? Скорее всего что-то из тройки Rust/Java/C# — мне всегда было интересно, как дела с подобного рода инструментарием обстоят у данных языков программирования. Но на это всё нужно время :)
picul
10.06.2019 00:04Задумка интересная, но бывают ли у Вас реальные случаи, когда выбор подходящего контейнера настолько сложен, что хоть бери да статический анализатор пиши? Разумеется, я не утверждаю, что это элементарная задача, но с моей колокольни подобный анализатор — это overkill.
ZaMaZaN4iK Автор
10.06.2019 05:22Да, бывают. Пример с std::vector -> std::array, например — наиболее частое, что я вижу на код-ревью. К тому же не стоит забывать такую вещь как рефакторинги и переделывание кода. Во время таких переработок может многое меняться и человек не всегда может уследить за тем, что контейнер уже надо поменять на другой.
Antervis
10.06.2019 12:28Да, бывают. Пример с std::vector -> std::array, например — наиболее частое, что я вижу на код-ревью.
такие оптимизации часто ломают код — рано или поздно какое-нибудь входящее сообщение не влезает в array. Возможно, заменять std::vector лучше не на std::array, а на boost::small_vector, например. И тогда большинство сообщений поместится на стеке, а только часть будет аллоцироваться.
На следующем кругу оптимизаций можно не полагаться на размер сообщений и буферов, а пытаться максимально переиспользовать аллоцированную память. Т.е. либо гонять данные move'ами (тут vector как правило будет несколько эффективнее small_vector и значительно эффективнее array) либо преаллоцировать буферы на этапе инициализации и расширять по надобности (тут вектор тоже чаще будет оптимальным вариантом т.к. small_vector рано или поздно расширится).
В конечном итоге мы приходим к тому, что для большинства случаев вектор является оптимальным или квазиоптимальным вариантом. И ключевое здесь — «при правильном использовании». Пара из аллокации/деаллокации часто будет дешевле копирования в/из std::array.
Вывод: сначала замеряй, потом оптимизируй.ZaMaZaN4iK Автор
10.06.2019 13:35Boost-контейнеры на данный момент по очевидным причинам (это прототип, тут бы стандартные контейнеры поддержать нормально) не поддерживается. std::vector заменяется на std::array только в случае, когда нет операций по изменению размера вектора. То есть случай с изменением размера и «не влезло» тут не катит.
Естественно, что сначала замеряется, а потом исправляется. Но замедления при замене std::vector на std::array в конкретно этом случае я не вижу. Вот когда понадобится менять размер контейнера, вот тогда и поменяют контейнер на std::vector.
KanuTaH
10.06.2019 02:08+1Для Qt существует что-то подобное в виде clazy. Ну не совсем, конечно, одни контейнеры вместо других он не предлагает, но всякие антипаттерны в работе с контейнерами, создание ненужных временных контейнеров и объектов и всякое такое на базовом уровне пытается отлавливать. Вот полный список проверок:
github.com/KDE/clazy/blob/master/README.md#list-of-checksZaMaZaN4iK Автор
10.06.2019 05:24Да, спасибо. Знаю про clazy. Даже больше скажу — в стандартной поставке clang-tidy начиная с какой-то там версии тоже есть пару проверок, которые находят некоторое (очень малое, к сожалению) количество неоптимальных алгоритмов на контейнерах.
twinklede
10.06.2019 05:24Всему виной то, что на данный момент только один С++ компилятор реализует оптимизацию по удалению динамических аллокаций — Clang.
Что-то у меня не получается добиться этого даже для самого примитивного случая: godbolt.org/z/iozO7CZaMaZaN4iK Автор
10.06.2019 05:26Об этом и речь — для стандартных контейнеров оно сейчас не работает даже в Clang. Вот пример того, как Clang убирает динамическую аллокацию, а GCC нет. godbolt.org/z/SBpXs8
twinklede
10.06.2019 05:34Ну это просто оптимизация «для галочки» и упоминать её не имеет смысла. И там и там op new, правда всё это сворачивает llvm и в этом проблема. Нужна некая обратная связь, в противном случае все эти оптимизации имеют мало смысла.
ZaMaZaN4iK Автор
10.06.2019 06:45Не понимаю, что значит оптимизация «для галочки». У нас есть явно код, который аллоцирует память, но её не использует. Один компилятор это видит и убирает лишний код, второй нет. Я не считаю данную оптимизацию бессмысленной.
twinklede
10.06.2019 08:17Не понимаю, что значит оптимизация «для галочки».
Всё очень просто. Добавлять бесполезные оптимизации для использования их в последующей конкурентной борьбе. Уровень этой борьбы может быть разный. На уровне авторов реализовавших оптимизацию, либо на уровне оптимизаций.
По поводу самой оптимизации. Я посмотрел — и тот и тот компилятор умеет убирать 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/6G5uVjZaMaZaN4iK Автор
10.06.2019 11:47Спасибо, я не знал, что GCC умеет в такое. А Вы случаем не знаете, где эта оптимизация реализована в GCC или LLVM? Я сходу не смог найти, в какой момент они занимаются схлопыванием аллокаций.
На самом деле мне не нравится текущий подход к оптимизации в Clang/LLVM в плане того, что все (подавляющее большинство согласно ответу в clang-dev mailing list) оптимизации проводятся на уровне LLVM IR (я не знаю, как оно сделано в GCC — мне не нравится читать их исходники). Потому что при переходе на LLVM IR по моему мнению мы теряем достаточно много информации, которую могли бы использовать для оптимизации — LLVM IR слишком низкоуровневый. Можно выкручиваться путём прокидывания (аннотирования) IR с фронтенда, чтобы мидленд уже обладал бОльшим кол-вом информации. Но это выглядит ужасно. На мой взгляд это не совсем эффективно.
По поводу сравнения оптимизаторов LLVM vs GCC. Согласно тестам того же Phoronix, оптимизатор LLVM не так уж и плох, так что я не могу согласиться, что там так уж всё плохо и что это всё «пыль в глаза».twinklede
10.06.2019 13:45А Вы случаем не знаете, где эта оптимизация реализована в 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 и собранный с ним гцц стал ещё быстрее.
twinklede
10.06.2019 09:49Первая проблема заключается в том, что для анализатора на данный момент все ветки кода равновероятностные. Точнее, он даже не знает о такой вещи как разные ветки выполнения кода.
Это выливается в проблемы с анализом для примерно вот такого кода:
Уже есть поддержка 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» и прочее — это вполне себе годно и имеет смысл. Реализовывать же именно как оптимизации — смысла имеет мало, ведь адекватная реализация требует наличия тех фишек, которых в С++ нет.
Поэтому ключевым, как я считаю, в решении этой проблемы является добавление этих фишек в С++, а уже потом оптимизации. Это будет либо очень слабо, либо будут переизобретаться в кишках очередные подобия тех фишек, что должны существовать в С++.ZaMaZaN4iK Автор
10.06.2019 11:39Спасибо за столь подробный комментарий.
Я согласен с тем, что поддержка должна постепенно появляться в языке. Также я согласен с каждым доводом о том, что было бы неплохо добавить в язык.
Но я не могу согласиться с тем, что этого не должно быть в каком-то виде в качестве оптимизации. Так как мы живём в мире С++ и у нас мегатонны легаси кода, который уже переписывать никто не будет. Возможно, стоит задуматься об утилитах, которые будут дополнительно размечать уже существующий код (хоть теми же атрибутами likely\unlikely, хотя это уже автоматически делается при включении PGO). Просто на данный момент компиляторы и так делают очень много «грязной» работы по оптимизации, и реализовано это всё очень и очень ужасно (стоит хотя бы взглянуть на InstCombine в LLVM и его аналог у GCC — не знаю как для Вас, а для меня это вырвиглазно). Есть идеи как это пофиксить (за подробностями можно отправиться почитать работы у John Regehr), но пока что оно сделано именно так, и нам надо с этим жить. И то, что я предлагаю, это по сути и есть одна из таких «грязных» методик.
Касательно движения С++… Мне сложно сказать, двигается ли С++ сейчас в правильном направлении. Я лично больше всего жду нормальной compile-time рефлексии с поддержкой атрибутов (на данный момент атрибуты не поддерживаются — можно это подсмотреть в докладе David Sankel c CppNow 2019).twinklede
10.06.2019 14:02Но я не могу согласиться с тем, что этого не должно быть в каком-то виде в качестве оптимизации. Так как мы живём в мире С++ и у нас мегатонны легаси кода, который уже переписывать никто не будет.
Я согласен с ораторами выше. Лучше туда не лезть. Кто там знает чего туда напихано. Но в какой-то мере это имеет место быть, с этим я так же согласен.
Просто на данный момент компиляторы и так делают очень много «грязной» работы по оптимизации, и реализовано это всё очень и очень ужасно (стоит хотя бы взглянуть на InstCombine в LLVM и его аналог у GCC — не знаю как для Вас, а для меня это вырвиглазно).
Я знаком с clang на достаточно базовом уровне и мой опыт заканчивается на портировании пары наработок на новую версию шланга и написания примитивного кодогена на libtooling. С llvm ещё меньше.
Но в целом я согласен да, существует множество вещей которые проще реализовать на уровне хайлевел оптимизаций. А ещё лучше мочь ими управлять.
Касательно движения С++… Мне сложно сказать, двигается ли С++ сейчас в правильном направлении. Я лично больше всего жду нормальной compile-time рефлексии с поддержкой атрибутов (на данный момент атрибуты не поддерживаются — можно это подсмотреть в докладе David Sankel c CppNow 2019).
А я хочу смерти атрибутам. Это рудимент gcc и что-то «снизу». Нужно заменить их на нормальные аннотации aka java.
Ну и С++ нужно взять пример со всяких модных языков. Необходима некая экспериментальная ветка, которая существует вне стандарта и на которой будут обкатываться новшества, которая будет популяризировать С++ и быстро реагировать на запросы комьюнити/обратную связь.
Сейчас мы имеем то, что почти никто не знает о тысячах наработках. Обычные люди не будут читать патчи на стандарт и строгие формулировки. И искать форки компиляторов в интернете.
pvl_1
11.06.2019 15:39Уже есть поддержка likely/unlikely. На это и прочее есть только один адекватный ответ — язык.
Вообще говоря, никто не мешает программисту действовать в два прохода: скомпилировать со сборщиком профиля, запустить на тестовых данных и тем самым собрать профиль, и скомпилировать с использованием профиля. Пруф для gcc, показывающий как минимум возможность таких оптимизаций. Имхо там больше использующих профиль оптимизаций.
Такой вариант имхо эффективнее, чем пытаться наобум что-то заменять. Поэтому с ипользованием профиля оптимизация смысл тоже имеет.
Также я согласен, что имеет смысл сделать анализатор, советующий заменить один контейнер на другой. Его тоже надо бы связать с профилем для более качественных советов.ZaMaZaN4iK Автор
11.06.2019 15:40Да, мне очень нравится эта идея. В статье про неё тоже написано :-) Это именно то, как я хотел бы видеть подобную вещь в оптимизаторе — в сочетании с PGO должно получится действительно очень интересно.
twinklede
12.06.2019 01:15Вообще говоря, никто не мешает программисту действовать в два прохода: скомпилировать со сборщиком профиля, запустить на тестовых данных и тем самым собрать профиль, и скомпилировать с использованием профиля. Пруф для gcc, показывающий как минимум возможность таких оптимизаций.
Это не новость для меня.
Имхо там больше использующих профиль оптимизаций.
Проблема не в этом.
Такой вариант имхо эффективнее, чем пытаться наобум что-то заменять. Поэтому с ипользованием профиля оптимизация смысл тоже имеет.
Что касается «эффективней» и «наобум». И то и то верно лишь частично. Не всегда можно собрать с программы адекватный трейс. И не все обладают пониманием уровня «ставим наобум». Но я не об этом говорил.
Абсолютно неважно кто расставит эту мета-информацию. Она без проблем может быть экспортирована из профиля. Как и может быть указана руками. Ключевым тут являет то(и именно об этом я говорил), что эта(и любая другая) информация должна быть доступна на уровне языка.
В моём понимании задачей pgo будет не (о)птимизация, ведь оптимизация это такое же тыканье «наобум». Я уже приводил автору достаточно очевидный пример. У нас есть строка и sso. Исходя из статического анализа/профиля мы можем получить длины используемых строк.
А ещё лучше и генерацию профиля тоже вынести на уровень языка. Мы сможем добавлять свои метрики, расширять/переопределять существующие. Тогда ненужно будет неуправляемых костылей в каждом из компиляторов, компиляторы не будут проводить оптимизация через одно место. Они всегда будут хуже в сравнении с хайлевел.
Но, существует фундаментальная проблема у pgo. Трейс никак не может ограничить входящие данные. Даже если у нас 100% строк в программе — 5 байт, то мы никак не можем заменить их на 5/6-байтные массивы. Просто потому, что в любом момент может прийти что угодно.
И решение существует только на уровне языка. Это контракты, это система типов. Мы никогда на научим тупые лоулевел оптимизации понимать семантику наших типов. Да даже понимать семантику контрактов вряд ли научим. И учить лоулевел понимать хайлевел абстракции — куда сложнее.
С метриками на уровне языка мы всегда сможет показать программисту при сборке сообщения вида уровня «строки 5-байт. Ограничьте контрактом/поменяйте тип». Это ещё более частный случай оптимизации, которую делает автор.
Точно так же нам очень сложно выявить источники данных без тех же контрактов/любой другой метаинформации. Если у нас будут нормальные opaque-тимы, а не пытки их закостылить — мы всегда сможем узнать источники данных.
Ничего из этого работать не будет(вообще или нормально) с оптимизациями где-то там в кишках.
maydjin
10.06.2019 11:09Кмк — автоматическая оптимизация сложна и это ненужно, как минимум без поддержки в отладчиках. А вот диагностические предупреждения с рекомендациями очень даже кстати былы бы. В тех же шлангах для этого уже есть интерфейс (diagnostics кажется называется). Более того, современные ide, и прочие vim'ы уже давненько как умеют применять подобные рекомендации по хоткею в заданной строке.
ZaMaZaN4iK Автор
10.06.2019 11:48Да, это прикольно. Только вот те же автофиксы из clang-tidy тоже надо кому-то писать. И если Вы взглянете на исходный код этих автоисправлялок, то поймёте, почему их не очень любят писать :)
maydjin
10.06.2019 12:28Я думал — разговор не про сложности реализации а про интерфейс функциональности. Лично я — не стал бы такими флагами пользоваться без поддержки отладчика, а может даже и с ней.
Эта эвристика либо должна быть очень умной, либо она будет работать чуть менее чем никогда, на любом полиморфизме(статический/динамический) она должна отключаться.
С другой стороны, в точке diagnostics, полезность даже простых эвристик очевидна:
- Разработчик видит, что возможно можно лучше, но решение за ним
- Есть информация для размышления, происходит обучение
Так же — нужно предусмотреть механизм игнора этой диагностики, в тех местах, где опытный разработчик уже решил, что таки верно выбрал структуру данных.
Простая аналогия — допустим мы хотим отучить разработчиков коммитить код с кривым форматированием. Можно конечно вызывать clang-format на ci и автоматом коммитить. Почему это плохо:
- Процесс автоформатирования может содержать ошибки
- Разработчик продолжит косячить
- Ресурсы инфрастурктуры продолжат тратиться
- Бывает код который плохо выглядит после автоформатирования
Как следует поступить: заставить разработчика проделать форматирование на своей стороне. Например сбоем на CI или отказом в push'e. Тогда, рано или поздно в репозиторий начнёт поступать отформатированный код, либо человек перестанет закрывать задачи.
Профиты:
- Обучаем разработчика
- Убираем плохо контролируемую точку отказа
- Получаем более читабельный код, в лучших традициях C++ — большинство автоматом, но где нужно подвинули инструмент в сторону и сказали "я лучше знаю"
Arqwer
10.06.2019 15:22Я вот мечтаю, что когда-нибудь смогу писать код наподобе
best::container abc;
best::solve_equation();
best::detect_cats();
Где внутри best лежит несколько десятков способов решить каждую задачу, а оптимизатор потом перебором решит, в какой строке какой способ лучше использовать.
И ещё чтобы при выходе новых научных статей оптимизатор сам обновлял программу.ZaMaZaN4iK Автор
11.06.2019 15:12+1Ну вот в проекте Chameleon было реализовано что-то подобное. Они написали свою обертку над контейнерами, используя которую вы в рантайме получаете динамически подменяющиеся контейнеры.
Andrey2008
10.06.2019 19:14Ага… Спасибо за мысль. Записали себе задачу реализовать новую диагностику для микро-оптимизаций (V8xx).
ZaMaZaN4iK Автор
11.06.2019 15:10С радостью потестировал бы вашу реализацию :-) Можно ещё посмотреть в сторону cppcheck — у них тоже что-то подобное есть, если мне не изменяет память.
zuko3d
Кажется, это неудачный пример, т.к. в этом случае deque подходит лучше: время вставки у него примерно такое же, как у листа, но зато итерация намного быстрее.
ZaMaZaN4iK Автор
Да, я соглашусь. На деку тоже можно смело заменять
tenzink
Я бы не стал утверждать без замеров времени, что std::list будет быстрее даже такого неидиоматичного использования std::vector. Дело в том, что при всей своей странности, оригинальный пример с вектором содержит меньше аллокаций памяти и сдвигает небольшие массивы.
Что касается ускорения, банальный std::vector + push_back + reverse, вероятно, будет намного быстрее варианта с std::list.
ZaMaZaN4iK Автор
Вы можете замерить на относительно больших массивах на том же quick-bench и убедиться, что это так.
Касательно варианта с reserve и push_back — да, он будет очевидно быстрее. Тут и спорить глупо :)