(Статический) Подбор оптимальных контейнеров в программах на C++
Здравствуйте. Сегодня хотелось бы поговорить снова про статический анализ. И снова про C++. Только в отличие от PVS-Studio мы будем искать не какие-то ошибки в наших программах (хотя они ищут не только ошибки), а места, которые написаны недостаточно оптимально. И одним из таких мест является выбор контейнера для данных в программе. Если я вас заинтересовал, то добро пожаловать под кат!
Проблема
На CoreHard 2018 Autumn (очень хорошая конференция, приезжайте) я рассказывал о том, что C++ компиляторы плохо оптимизируют в настоящий момент. И одной из моих претензий было то, что компиляторы не могут оптимизировать использование контейнеров в наших программах. Давайте рассмотрим несколько примеров кода.
void foo() {
std::vector v(42);
}
Казалось бы в таком простом случае компилятор должен мочь оптимизировать данную функцию и просто выкинуть объявление переменной типа std: vector, так как начиная с C++14 компилятору разрешено убирать динамические аллокации памяти, но компилятор это не делает. Всему виной то, что на данный момент только один С++ компилятор реализует оптимизацию по удалению динамических аллокаций — Clang. Все остальные компиляторы просто пока что не умеют так делать. Но даже Clang может сделать это в ограниченном количестве случаев.
В данном случае мы могли бы заменить std: vector на std: array, при условии что размер выделяемого вектора не слишком большой, так как у нас банально может не хватить стека для такой замены. Такая замена уберёт довольно дорогую аллокацию памяти на кучу, а плюсом будет то, что при использовании std: array компилятор уже сможет выкинуть std: array вообще из функции!
Если мы говорим про оптимизацию производительности, то предлагаю рассмотреть следующий пример:
void foo() {
std::vector 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, которому всё равно, куда происходит вставка (хотя именно в этом случае можно прекрасно видеть, что не надо просто insert использовать. Но это просто пример, не более:)
Давайте рассмотрим ещё один пример кода:
void foo() {
std::list 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 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& 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. Если интересуетесь — заходите, очень интересно там. Только аккуратнее с флудом — за него сразу карают :)
Вместо заключения хотел бы заострить внимание на том, что это пока что только прототип и он имеет слишком много «дыр» в реализации. В данной статье я просто хочу поделиться с вами идеей подобного анализа и его популяризации. Ну и может кого-то заинтересует данная тема и подключиться к проекту — я буду только рад! К тому же вы всегда можете собрать данный анализатор у себя попробовать его на своих тестовых примерах.
Если у вас есть чем дополнить материал, сталкивались с подобной задачей или просто обладаете какой-то информацией, которая может быть полезна по данной теме — прошу не стесняться и делиться данной информацией в комментариях.
Спасибо за внимание!
