На муле Кентукки: стенограмма
В мире языков программирования со статической типизацией, похоже, существует досадное разделение. У вас либо продвинутая и интересная система типов на вашем языке программирования, но вы платите за нее медленным временем компиляции, либо у вас скучная система типов с быстрым временем компиляции.
Экономика разработки статически типизированного языка программирования с удобным пользовательским интерфейсом (а скорость компиляции является основным компонентом ux!) Еще не исследовалась глубоко.
Kentucky Mule, мой медленно развивающийся побочный проект, был синими воротничками исследования по этому вопросу. Цель заключалась в том, чтобы получить очень практичное понимание и сосредоточить мое внимание на одном языке, который я действительно хорошо понимаю: Scala. Несколько месяцев назад я достиг вехи в разработке Kentucky Mule, которая значительно снизила риск и прояснила, как этот проект может перейти от прототипа непроверенной идеи к твердому плану реинжиниринга настоящего компилятора Scala для 5x-10x. улучшение производительности.
Ниже приводится стенограмма моего выступления на эту тему несколько месяцев назад. С тех пор его немного пересмотрели, потому что пересматривать историю - это весело.
Разговор
Может ли компилятор Scala работать быстрее? Какой предел? Сколько мы оставляем на столе?
Размышляя над этими вопросами, я понял, что поиск реализации высокопроизводительного компилятора может иметь два результата. Либо есть реализация компилятора, которую я ищу, либо у Scala есть недостаток дизайна, который не позволяет быстро компилировать его.
Scala был выпущен в 2004 году, но его реальный рост популярности начался в 2006 году с выпуском Scala 2.0. К 2012 году, когда люди создавали более крупные проекты и внедряли Scala в компаниях, скорость компилятора стала главной проблемой.
За прошедшие годы было вложено много усилий в его улучшение. Я работал над редизайном цинка - инкрементального компилятора для Scala. Это программа, которая определяет, что нужно перекомпилировать, когда вы вносите изменения в свой проект. Алгоритмическая переработка привела к 10–50-кратным улучшениям. В 2018 году производительность компилятора по-прежнему считается приоритетом сообщества Scala.
Во время работы над инкрементным компилятором я наткнулся на доклад Брета Виктора Изобретая принцип. Для меня это было откровением - доклад Брета был переполнен идеалистическими идеями о том, как следует делать программирование. Я увидел убедительные доводы в пользу принципа, согласно которому, если вы вносите изменение, вы должны немедленно ощутить его последствия. Последствия были гораздо более серьезными, чем просто экономия времени. Это изменило то, как вы занимаетесь программированием.
После просмотра я рассказал об этом всем своим друзьям.
И я начал задаваться вопросом, почему я работал над языком программирования, так далеким от того, что я видел? Я работал не по тому делу?
2016 год был для меня годом бродяг. У меня не было цикла производительности, о котором нужно было беспокоиться, или крайнего срока подачи документов. В том году мне довелось пройти собеседование в Facebook. Я поговорил с командой Hack и узнал об их проекте проверки типов. Он обрабатывает статическую проверку в масштабе десятков миллионов строк кода. Это массово параллельное и распределенное.
А теперь я стал бродягой с планом.
Я начал проект Kentucky Mule с целью изучить пределы производительности компиляции Scala. Вместо того, чтобы бросить корабль и перейти на Javascript, который Брет использовал в своих демонстрациях, у меня была амбициозная цель: сохранить лучшее из компиляции и запуска, которым мы, пользователи статически типизированных языков, наслаждаемся, и сделать это так быстро, что кажется волшебным.
Эксперимент
Популярный аргумент в пользу низкой скорости компиляции Scala заключается в том, что компилятору Scala просто нужно делать больше работы. Язык имеет сложные функции, и их поддержка требует больших вычислительных ресурсов.
Итак, я провел эксперимент! Я создал простой код Scala и Java бок о бок. За исключением языковых различий, они выглядят совершенно одинаково. В коде я избегаю функций системы расширенных типов Scala, которые обычно считаются причиной медленного времени компиляции.
Я скомпилировал компиляторы Scala и Java и сравнил время выполнения.
На диаграмме вы видите большой разрыв между двумя компиляторами. По сути, оба решают проблему одной и той же сложности, но компилятор Scala в 6 раз медленнее, чем компилятор Java. Что бы ни делал компилятор Scala, это пустая трата времени. Ни один из проведенных до сих пор анализов производительности не объясняет этот пробел.
В то время как мой эксперимент показывает, что есть потенциальный выигрыш в однопоточной производительности, настоящие богатства ждут в мире параллелизма. Люди, работающие над языками программирования, считают распараллеливание компилятора неразрешимой проблемой. Но команда Hack построила нетривиальное средство проверки типов с массивно параллельной, распределенной и инкрементной архитектурой. Интересно, что они разработали язык для поддержки этой архитектуры.
Может ли Scala заимствовать хакерские идеи? Может ли Scala иметь высокопараллельный компилятор без кардинального изменения языка?
Архитектура
Итак, мы хотим создать высокопараллельный компилятор. Если вы построите график времени по конвейеру различных фаз в компиляторе, вы увидите, что одна из них выделяется: типограф. Это тяжелая фаза, которая выполняет проверку типа и занимает 30–40% от общего времени выполнения. Кроме того, это самый сложный этап для размышлений. Мы сосредоточимся на этом.
Это последняя архитектура проверки типов, к которой мы движемся. И мальчик, здесь много всего происходит. Распаковываем. Цель архитектуры - поставить как можно больше маленьких коробок друг на друга. Чем больше мы их складываем, тем больше параллелизма получаем.
Слева у нас есть этап синтаксического анализа, который легко распараллелить: я могу анализировать каждый исходный файл параллельно. На дальнем правом конце у меня есть массивно параллельная проверка типов тел методов. Все методы независимы друг от друга, но зависят от вычислений, выполняемых в середине. Мы вернемся к этому.
Для сравнения, это текущий дизайн Scalac. Вроде бы проще, но картинка несовершенная. Вся сложность упакована в то, что в программном обеспечении известно как Big Ball Of Mud. На предыдущем слайде мы аккуратно разбили скрытую сложность на небольшие управляемые части.
Когда я спросил свою подругу, которая занимается исследованиями языков программирования, почему исследователи не тратят больше времени на параллельные архитектуры для проверки типов, она оборвала меня, сказав: «Это запутанная проблема зависимости данных». Теперь я подхожу к сути проблемы.
«Беспорядочная проблема зависимости данных»
Предположим, я хочу разрешить тип T в фрагменте кода слева, последовательность выглядит следующим образом:
- Определен ли тип T в классе B? Нет
- Определен ли он в охватывающем классе A? Да окей отлично у меня есть
Теперь предположим, что я удаляю объявление класса и добавляю оператор импорта. Я все еще хочу разрешить тип T:
- Этот тип определен в классе B? Нет
- А как насчет класса А? Нет, но есть инструкция по импорту
- Это оператор с подстановочными знаками, включает ли C тип T в качестве члена?
- Но ... что такое C? Я должен сначала разобраться с этим. C объявлен в классе A? Нет
- Как насчет пакета foo? Позвольте мне начать глобальный поиск
- Я вижу, что объект C объявлен в пакете foo в другом исходном файле
- Хорошо, включает ли объект C тип T? Да, есть.
Так что здесь происходит? Мы решаем именованные идентификаторы. Мы превращаем строку символов в ссылку на конкретное определение. Разрешение может быть рекурсивным: например, сначала мы разрешаем объект C, а затем запрашиваем у него тип T. Порядок, в котором мы выполняем разрешение, определяется как спецификацией языка, так и структурой программы. Структура зависимостей, возникающая в процессе разрешения проблем, может быть очень сложной, и очевидной возможности для параллелизма нет.
Это запутанная проблема зависимости данных.
Скелет и ткани
Мы можем начать распутывать нашу запутанную проблему, перетащив код в стороны и проведя разделительную линию между двумя столбцами. Определения и сигнатуры идут слева, а реализации методов - справа. Теперь вы можете думать о том, что находится слева, как о «скелете» программы. Вещь справа - это ткань, которая висит на скелете.
Слева скелет, а справа маленькие коробочки - кусочки ткани. Розовые стрелки представляют собой ссылки или зависимости между частями ткани или скелета. Ткань достигает только скелета. Стрелки справа идут только влево. Ткань как висит на скелете, так и достигает некоторых других частей скелета.
Каркас сложнее: он имеет ссылки на себя. Типы могут ссылаться на другие типы, методы ссылаются на типы в своих сигнатурах. Но скелет самодостаточен: он никогда не достигает ткани. Аааи я знаю, о чем вы думаете: но как насчет предполагаемых возвращаемых типов ?!
Мы скоро до них доберемся! Я обещаю.
У нас есть первая крупная победа: мы разделили нашу проблему на два больших компонента: ткань и скелет.
Skeleton дорого обходится в Scala и, откровенно говоря, на большинстве современных языков программирования. Для реализации общего плана распараллеливания вычисление скелета всех сигнатур также должно быть распараллелено. Это сложная проблема, потому что части скелета или костей ссылаются друг на друга. Чтобы избежать конфликта потоков, я хотел бы заранее определить порядок обработки всех частей.
Инструкция по сборке
Однако вначале эта проблема кажется замкнутой: порядок определяется зависимостями между частями скелета, а зависимости доступны только тогда, когда я полностью вычисляю сигнатуры типов для всех частей скелета: классов, типов-членов, методов и т. Д.
Чтобы разорвать этот круговорот, я придумал понятие типов контуров. Идея состоит в том, чтобы аппроксимировать реальные типы очень простыми типами, которые: чрезвычайно дешевы для вычисления и захвата зависимостей.
После вычисления типов контуров дайте руководство по сборке в стиле ИКЕА для построения нашего скелета. Наброски типа дают вам руководство по сборке, они говорят вам, в каком порядке складывать кости вместе.
Архитектура снова
Вернемся к нашей архитектуре. Вычисление типов в ткани программы находится справа, посередине - вычисление скелета. Вы можете увидеть множество маленьких прямоугольников, расположенных в заранее определенном порядке, отмеченных стрелками зависимости. Левее находится план сборки каркаса. Вот где вычисляются типы контуров.
Имея этот план, вы можете видеть, что вычисление типов контуров представлено одним прямоугольником. Это вычисления, которые нельзя распараллелить. И ключевой вопрос: можно ли вычислить типы структуры достаточно быстро, чтобы вся схема имела смысл? Достаточно быстро означает на порядок быстрее, чем вычисление скелета.
Мы бы хотели избежать смешной ситуации, когда мы тратим больше времени на выяснение плана сборки, чем на собственное строительство.
Типы набросков сокращены до их сути. Они касаются только сигнатур классов, объектов, определений типов и значений. Я вырезал все, что не нужно для вычисления зависимостей. Типы структуры не поддерживают проверку подтипов и являются чисто структурными.
Типы структуры настолько упрощены, что сначала трудно представить, что они смогут выдержать тяжесть сложности Scala. Я понятия не имел, будут ли они работать и будут ли работать достаточно быстро, но мне очень хотелось узнать. И я продолжал строить Kentucky Mule.
Для создания доказательства концепции я выбрал в качестве тестового примера малоизвестный проект скальпа. Этот проект отлично подходит. Он самодостаточный и небольшой: он состоит всего из двух тысяч строк кода. Однако это не так уж и мало, чтобы быть полностью тривиальным. С первой строчки кода моего прототипа я параноидально относился к производительности. Я измерил производительность на каждом этапе первоначальной реализации Kentucky Mule. Мне было интересно оставаться как можно ближе к тому, насколько быстро компьютеры могут вычислять.
Показатели производительности, которые я получил, выглядели действительно великолепно: я вычислял типы контуров для скальпа со скоростью 4 миллиона строк кода в секунду.
Я знал, что цифры, которые я получил до сих пор, предназначались исключительно для проверки того, имеет ли идея набросков какое-либо основание в действительности. Если они были слишком медленными для вычисления, я хотел знать заранее. Они действительно работали быстро, но в моем доказательстве концепции я для удобства исключил все функции Scala, которые, как мне казалось, могут нарушить условия сделки.
Следующей задачей было встретиться лицом к лицу с нарушителями сделки. В качестве тестового примера я выбрал стандартную библиотеку Scala и перечислил все языковые функции, которые, как мне казалось, мне нужно было реализовать.
Начав с действительно отличной производительности и моего заранее определенного списка из 21 функции, я продолжил их реализацию. Я хочу показать вам результат.
В демонстрации вы видели, как Kentucky Mule обрабатывает 30 тысяч строк кода Scala примерно за 200 миллисекунд. Это выгодная сделка по плану сборки. И это вселяет большое доверие в архитектуру в целом.
Архитектура нижнего уровня
Теперь я хотел бы поговорить о некоторой архитектуре нижнего уровня. Внутри компиляторы часто есть концепция дополнения типов. Это функция, которая переходит от единицы к типу. То есть, есть подпись () = ›Тип. Это ленивое вычисление, возвращающее тип. Вспомните большой комок грязи и запутанную проблему зависимости. Поскольку порядок проверки типов заранее не известен, популярным вариантом является настройка ленивых вычислений, которые ссылаются друг на друга и позволяют лени разобраться в порядке вычислений. Это очень естественный прием, который используют компилятор Scala, компилятор Java и компилятор Swift.
Однако у него есть свои недостатки. Мы выполняем глубоко рекурсивный поиск по графу в глубину, который сбивает с толку оптимизатор JIT на JVM и замедляет работу компилятора. Рассуждать о стоимости вычислений в проверке типов сложно: вы не знаете, является ли кусок, на который вы смотрите, медленным, или он просто запускает длинную цепочку других вычислений. Трассировки глубокого стека также сложно обрабатывать профилировщикам JVM. И, наконец, некоторые типы загружаются с диска, например для ваших внешних библиотек. Они загружаются лениво и небольшими порциями, что приводит к ошибкам ввода-вывода. Вместо этого я хотел бы выполнять операции ввода-вывода в пакетном режиме.
Эти болевые точки заставили меня задуматься об альтернативной абстракции.
Я придумал понятие прерываемого дополнения типов, вдохновленное совместной многозадачностью. Это схема потока управления, используемая, например, в Windows 3.1. Идея состоит в том, что завершители - это задачи, которые либо возвращают тип, который они завершают, либо возвращают управление циклу событий, если они застряли на какой-то зависимости, которая еще не запущена. Завершитель прерываемого типа имеет подпись () = ›Тип | Неполная зависимость. Управление возвращается с сигналом, по которому задача блокирует выполнение. И как только зависимость будет удовлетворена, планировщик попытается выполнить задачу еще раз.
В этой схеме задачи организованы в рабочую очередь. Задачи изолированы и поддаются прямой атрибуции производительности. Неглубокие трассировки стека делают профилировщики JVM гораздо более удобными. И я могу изменить порядок выполнения задач в очереди. Например, я могу выполнять задачи ввода-вывода в пакетном режиме.
Я использовал Kentucky Mule в качестве лаборатории, чтобы опробовать идею прерываемых дополнений шрифтов для типов структуры. Большая часть реализации Kentucky Mule представляет собой исследование этого единственного изменения сигнатуры функции: переход от () = ›Type к () =› Type | Неполная зависимость. Я перешел от возврата типа к возврату типа или сигнализации об отсутствующей зависимости.
Таким образом я отделил обнаружение зависимостей от вычисления зависимостей. В старой схеме обход в глубину связывает их вместе.
(Закон Ши) Возможность улучшить дизайн проявляется в первую очередь в интерфейсах. Это также лучшее место для того, чтобы все испортить. - Законы Акина конструирования космических аппаратов
Недавно я наткнулся на эту цитату о конструкции космических кораблей. Все программное обеспечение со временем ухудшается по разным причинам, и единственное, что предотвращает полный крах, - это хорошие интерфейсы. Эта простая идея совместной многозадачности имеет далеко идущие последствия. Изменив интерфейс, я разблокировал применение десятилетий мышления системного программирования, которое вошло в рабочие очереди и планировщики.
У меня был глубокий момент, когда я узнал от своих друзей-программистов, что существует простой параллельный планировщик с очень низкими накладными расходами для прерываемых завершителей. Вычисление самих типов контуров может быть распараллелено. Этот блок на слайде по архитектуре можно разбить! Его можно развалить! (см. это объяснение, чтобы узнать, как это работает).
Подсказка для разработки быстрых компиляторов
Наконец, я хотел бы поговорить о пространстве поиска реализации быстрого компилятора. Есть два способа найти быструю реализацию. Вы можете сначала реализовать все языковые функции и все этапы компиляции, а затем начать профилирование и оптимизацию.
Другой способ - реализовать крошечный набор языковых функций, скажем, какие языки программирования поддерживались в 70-х годах. Вы реализуете этот небольшой набор функций от начала до конца. Вы хотите получить отличную производительность окончательной реализации. А затем вы перебираете языковые функции с ограничением по защите уже имеющейся у вас отличной производительности.
Первый способ - это типичный способ создания программного обеспечения, который лучше всего резюмируется этой цитатой:
Сделай это правильно Сделай это быстро - Кент Бек
Редко вы сталкиваетесь с проблемой в разработке программного обеспечения, когда вам нужно сделать шаг назад и пересмотреть даже самые распространенные методы создания программного обеспечения. Работая над Kentucky Mule, я сделал большой шаг назад и пришел к выводу, что мне нравится второй метод, потому что ваше пространство поиска проще: на каждом этапе я знаю, куда мне нужно идти. Все 40 языковых функций, которые будут реализованы, включены в языковую спецификацию. Каждый шаг достаточно мал, поэтому, когда я замечаю, что теряю производительность, легко отступить и выяснить, почему. Что еще более важно, на каждом этапе я знаю, насколько я далек от реализации.
С более распространенной практикой оптимизации на поздней стадии разработки пространство для поиска огромно. И вы снимаете в темноте, которая быстро деморализует.
Заворачивать
Пришло время подвести итоги. Итак, готовы ли мы переписать компилятор Scala? Удобно, что у нас есть одна перезапись под названием Dotty. Вспомните эксперимент, с которого я начал. Я добавил производительность Дотти в таблицу. Он идеально сочетается со старой реализацией. Я повторил этот эксперимент на разных базах кода, и компилятор Scala, и компилятор Dotty идут нога в ногу в скорости компиляции на одной и той же кодовой базе.
Дело не в переписывании.
Я считаю, что производительность компилятора Scala - сложная, но решаемая проблема.
Мое предложение - тщательно пересмотреть реализацию. Разбейте большой комок грязи на фазы с целью распараллеливания в будущем. Выберите прерываемые комплектующие в базовом строительном блоке. Этот интерфейс позволяет разделить и открывает возможности для заимствования отличных идей от сообщества системного программирования.
Наконец, начните с минимальной сквозной реализации. Перебирайте языковые функции и защищайте производительность на каждом этапе.
Спасибо.
