Thread by @mobileunderhood

Thursday

Как и обещал, сегодня будет много low-level твиттов про Swift, iOS и алгоритмы.

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

* Build speed
* Binary size
* Performance

Миграция на Swift, влияет на них всех и к сожалению не самым лучшим образом. Давайте начнем с Build Speed.

Обычно принято считать, что Swift очень долго компилируется. Но правда ли это так, или он просто так воспринимается? На самом деле, это можно довольно легко проверить.

Компиляторы умеют отдавать статистику по компиляции. (Clang -ftime-trace, Swift -stats-output-dir). Статистика содержит много интересных цифр. Но самое главное - время компиляции разбитое по этапам.

Чтобы примерно сравнить Свифт с языками семейства Clang, мы можем сматчить одинаковый по количеству токенов код и сравнить время чистой компиляции между языками. Конечно, такой подход очень приблизительный, но он показывает порядок цифр.

Самое неожиданное, что чистый билд свифта почти совпадает с C++(особенно где в коде много templates), немного отстает от ObjС, и сильно отстает от чистого С. (Clang PCH/modules были отключены).

Самые медленные фазы у Свифта - type-checking и Name binding. Самое интересное, что name binding может занимать столько же времени как и type-checking в отдельных модулях. Name binding - процесс, когда компилятор пытается найти декларации типов, функций, etc.

Происходит это из за того, что нужно пройтись по всем импортам, загрузить свифтмодули и найти подходящую декларацию. Делать это нужно очень аккуратно, так как в системе может быть несколько процессов работающих с этими файлами, поэтому используются FS локи.

У Кланга - самые медленные фазы - парсинг хедеров(все языки) и template instantiation(C++/ObjC++). Включение PCH/Modules позволяет немного оптимизировать парсинг хедеров и превратить его в аналог свифтового процесса.

PCH/modules это оптимизации, которые помогают избежать парсинга и сделать поиск деклараций более оптимальным и дешевым(не нужно парсить все сразу). Но может приводить к раздуванию ModuleCache.

В двух словах - каждый файл cpp/m/mm компилируется индивидуально, и все импорты раскрываются препроцессором и рекурсивно парсятся каждый раз. Поэтому, если вы не используете PCH/modules кланг делает огромное количество работы каждый раз. Самая жесть с Foundation и UIKit.

Эти два хедера рекурсивно содержат огромное количество токенов. И в некоторых случаях их парсинг может забирать около 99% от общего времени компиляции, даже если используется всего 1 декларация!!!

Убедитесь, что в вашем проекте включен либо PCH, а лучше модульность, и старайтесь удалять не нужные импорты(особенно в самих хедерах!).

Type-checking у свифта это весьма любопытный процесс. Он основан на en.wikipedia.org/wiki/Hindley%E…

Очень упрощенно - компилятор строит граф, где ноды это либо известные типы, либо type variable(заглушка под тип). А связи между нодами - это отношения между типами.

Дальше он пытается заменить все type variables на конкретный тип. Если это не получается, система undecidable.

Почему это все очень медленно? Потому что этот алгоритм похож на backtracking, который например используется в поиске с регулярным выражением. А сложность у этого алгоритма экспоненциальная. leetcode.com/tag/backtracki…

Проблема возникает тогда, когда алгоритм должен найти подходящий overload функции для вызова. Например когда используются операторы. (+/-/*/ etc). Так как у них много разных перегрузок для разных типов.

Чтобы найти подходящий(при отсутствие эвристик) компилятор просто будет перебирать варианты пока не найдет тот, что удовлетворит всем условиям. Если в системе есть больше чем один оверлоад и алгоритм не может разделить эту систему на более маленькие, то сложность растет быстро.

Решить большую сложную систему может быть очень трудно, поэтому алгоритм на каждом шаге пытается разбить ее на несколько более маленьких. (Привет Сonnected Сomponents алгоритм)

На самом деле, такие кейсы довольно редки. Core команда сделала невероятную работу по оптимизации этого всего. Почитать подробнее про type checking можно тут
github.com/apple/swift/bl…

Либо посмотреть классный видос от Robert Widmann.

Почитать про типы с другой стороны можно еще тут medium.com/@slavapestov/t…

Binary size - Очень сложная тема. Но если упростить, то в основном все идет от метадаты и размера самого кода.

Порой, относительно безобидные фичи языка, могут оказаться очень дорогими с точки зрения binary size.
Например - протоколы, которые в Swift реализованы как Existential Containers.

Если функция принимает параметр с протоколом, то она не узнает о реальном типе до самого рантайма.
А в рантайме в нее придет не тип, а специальный контейнер. Его нужно будет “открыть”. "Эта логика называется boxing/unboxing.

И для того, чтобы вызвать простую функцию нужно в рантайме выполнить много логики.
Посмотреть на IR можно тут. (Символ - s6output3FFF1pyAA1P_p_tF)
godbolt.org/z/5nr89c

Дженерики реализованы похожим образом в рантайме. Но если нужен performance, то их можно специализировать. В этом случае, будет создана новая функция, которая будет уже работать с конкретным типом. Но это увеличит размер бинаря. Налицо trade-off между Binary size and Performance

Другой трейдофф это Inlining и Outlining. При первом код функций может быть вставлен туда, где он используется, без вызова функции. При втором, наоборот, похожий код из разных функций объединяется в сгенерированные функции, которые вызываются в тех местах, откуда код был взят.

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

Всеми любимые структуры тоже могут очень сильно влиять на размер бинарника. Все идет от value semantic.

Для того, чтобы в рантайме работать с большими структурами, компилятор генерирует value witness table. Это таблица с указателями на функции, которые знают, как инициализировать, скопировать, удалить конкретную структуру.

И все это занимает место в бинаринке. Особенно опасны структуры с высоким уровнем вложенности, когда одна структура содержит поле с другой и тд.

Тут можно увидеть, сколько нужно метадаты и кода чтобы структуры смогли работать.
godbolt.org/z/q8fPfT

Чтобы сделать demangle символа:
`xcrun swift-demangle s6output1AVWV`
Получите
`$s6output1AVWV ---> value witness table for output.A`

В IR с префиксом @ идут глобальные значения, которые(если не будут удалены во время LTO) пойдут в бинарник.
value witness table, nominal type descriptor, full type metadata и field descriptor(если Reflection включен).

Но есть и хорошие новости. В Свифт есть концепт POD/Trivial структур(как в c++). Это такие структуры, все поля которых рекурсивно тоже POD. (Не должны содержать никаких ARC типов).

В этом случае, структуру можно будет просто копировать с memcpy и избежать сложной логики с retain/release ARC типов.

Если тип POD, то сделайте его структурой и сможете выйграть место в бинарнике. Если не POD, и он содержит много разных полей, то в этом случае, будет выгоднее сделать его классом.

Другая очень дорогая фича это ObjC interop. Так как помимо всей свифтовой метадаты нужно будет сгенерировать еще и ObjC метадату, которая занимает очень много места.

Убирайте @objc/@objcMembers когда это не нужно. И старайтесь избегать случаев, когда @objc наследуется не явно.

Другая важная привычка, всегда использовать `final` и минимизировать количество public/open. Все в месте поможет компилятору сделать множество оптимизаций. От dead code elimination до constant propagation и снова DCE.

Если вам важен размер бинарника, обязательно делайте LTO для релизных билдов. Это позволяет делать DCE более эффективно и удалить много не нужной метадаты.

LTO(full/thin) это режим компиляции, когда компилятор производит не объектные файлы а llvm IR, который потом линкуется и подвергается оптимизациям.

За счет того, что оптимизатор видит программу целиком, они может сделать очень много мощных оптимизаций, которые уменьшат размер бинарника и увеличат производительность; После этого из IR будет сгенерирован финальный машинный код.

Делаете LTO?

А вот тут IR для сложной иерархии структур godbolt.org/z/35jsrP