Не успел я запостить статью об оптимизациях как в ST так и современных JavaScript-движках, как появилось дополнение: Apple выпустила SquirrelFish Exterme (SFX). Если SF был просто хорошим интерпретатором, то SFX продвинулся далеко вперёд.
И так, SFX использует:
- Оптимизации в байткоде.
- PIC.
- JIT.
- JIT для регулярных выражений.
JIT для регулярных выражений нас сейчас не интересует. Просто JIT - это понятно (Кстати, JIT в SFX не использует LLVM, возможно по соображениям скорости кодогенерации).
Что такое PIC мы уже рассмотрели. Хотя и тут есть один момент. В ST реализовать PIC относительно просто - ведь, не смотря на динамичность языка, существующие классы относительно стабильны и объекты принадлежат одному и тому же классу. В JS (и, тем более, в Self) же схема любого объекта может быть изменена на лету. Что равносильно в ST порождению новых классов. В V8 эту проблему решают введением скрытых классов на которые мапяться объекты с одинаковыми схемами. В SFX похоже используется аналогичная техника: каждый объект имеет некий StructureID. Объекты имеющие одну и ту же схему имеют один и тот же StructureID. Соответственно, диспетчер в PIC проверяет совпадение StructureID.
А вот оптимизации в байткоде мы еще не рассматривали. Эти оптимизации появились еще в оригинальном ST-80 (если не раньше, в ST-76) и призваны были соптимизировать диспетчеризацию сообщений наряду с глобальным кешем методов (что это - рассказано в предыдущей заметке). Эти оптимизации включают в себя "специальные селекторы" и "статические предсказания типов".
Спецселекторы это скорее не классическая оптимизация, а читерство. Суть оптимизации в инлайнинге базовых управляющих потоком выполнения структур (простите за косноязычее, но как сказать проще я не знаю). Т.е. ряд посылок сообщений компилируется не в обычную посылку сообщения, а сразу в байткод. Пример в Squeak. Вызов любого метода, например "true hash" компилируется в такой байткод:
pushConstant: true send: hashА "true ifTrue: [self hash]" компилируется в:
pushConstant: true jumpFalse: 22 self send: hashТ.е. при этом не создаётся блок и используется не реальная посылка сообщения, а генерируется некий спецбайткод. Это приводит к ряду эффектов. Первый - это ускорение. Второй - если выполнить код "1 ifTrue: [self hash]", то вы получите не исключение "MessageNotUnderstood", а "NonBooleanReceiver". Третий эффект заключается в том, что если поменять имплементацию метода, например, в классе True, то на поведении программы это не скажется. Так же бесполезно добавлять метод "ifTrue:" в другие классы - поскольку сообщение такое не посылается, то и вызвать такой метод без рефлексии в обычном случае не получится. И, напоследок, вызвать такой спецметод можно всё таки не только через рефлексию. Реальная посылка сообщения генерируется и если компилятор не может проинлайнить блок кода. Например, "1 ifTrue: aBlock" генерирует:
pushConstant: true pushTemp: 0 send: ifTrue:Отсюда мораль: менять такие спецметоды не стоит, во избежание всяческих чудес в поведении программы. Набор спецселекторов обычно влючает в себя "ifTrue:ifFalse", "on:do:", "timesRepeat:", "whileTrue:". Подробнее о спецселекторах можно прочитать в статье об устройстве компилятора в ST в разделе "Заинлайненный (почти) ifNil: (VW)".
Статические предсказания типов это уже именно оптимизация, а не грубый чит. Он основан на статистике, что большая доля сообщений таких как "+" имеет одинаковые классы, как у получателя так и аргумента. Соответсвенно, реализация таких методов - это примитив, который проверяет тип аргумента. Выглядит в Squeak это так:
SmallInteger>>+ aNumber "Primitive. Add the receiver to the argument and answer with the result if it is a SmallInteger. Fail if the argument or the result is not a SmallInteger Essential No Lookup. See Object documentation whatIsAPrimitive." <primitive: 1> ^ super + aNumber Float>>+ aNumber "Primitive. Answer the sum of the receiver and aNumber. Essential. Fail if the argument is not a Float. See Object documentation whatIsAPrimitive." <primitive: 41> ^ aNumber adaptToFloat: self andSend: #+
В ST традиционно, если примитив отрабатывает нормально, то возврата из него не происходит. Т.е. на ST код после примитива управление переходит только если примитив провалился.
Соответсвенно примитив отрабатывает быстро, если предсказание типа было успешным и медленне, если нет. Пример из Squeak:
Time millisecondsToRun: [10000000 timesRepeat: [1 + 1]] "1)=> 697" Time millisecondsToRun: [10000000 timesRepeat: [5.0 + 1]] "2)=> 2303" Time millisecondsToRun: [10000000 timesRepeat: [1 + 5.0]] "3)=> 2408"С первым случаем всё понятно - предсказание типов успешное и код отрабатывает почти в 4 раза быстрее, чем во 2-м и 3-м случаях. А вот почему 2-й вариант быстрее 3-го? Во втором случае трасса такая:
Float>>+ Number>>adaptToFloat:andSend: Float>>+В третьем же варианте, трасса больше на одну отправку сообщения:
SmallInteger>>+ Integer>>+ Float>>adaptToInteger:andSend: Float>>+В VW реализация кардинально другая, но разница в скорости там еще более заметна:
Time millisecondsToRun: [10000000 timesRepeat: [1 + 1]] "1) => 38" Time millisecondsToRun: [10000000 timesRepeat: [5.0 + 1]] "2) => 120" Time millisecondsToRun: [10000000 timesRepeat: [1 + 5.0]] "3) => 289"
Судя по короткому описанию именно подобие "статического предсказания типов" и реализовано в SFX.
Ярлыки: inside_st
В последнее время как-то одновременно появились анонсы "быстрого JavaScript" сразу в трёх броузерах: FireFox 3.1 с движком TraceMonkey, новоявленный GoogleChrome с движком V8 и Safari 4 с движком SquirrelFish.
Казалось бы, при чем здесь Smalltalk?
Тут нужно коротко изложить как развивались ВМ для ST. Первые версии ST, которые работали на Xerox Alto и Xerox Dorado были реализованы на микрокоде. Затем, с портированием ST на другие платформы появилась "классическая" ВМ исполняющая байткоды. Как я понимаю, именно с появлением ВМ проблема производительности встала в полный рост. Так, например, известно утверждение Алана Кея в интервью за конец 2004г, что текущие процессоры исполняют ST всего в 50 раз быстрее чем Dorado. (Речь вероятно идёт о таком параметре как "исполненные байткоды в секунду". Тест можно найти в Squeak в методе Integer>>benchmark. У меня этот тест на Core2 Duo 2HHz показывает 360Мб/с. Если предположить, что Dorado выдавал 400Кб/с, то получается быстрее в ~900 раз. А в Squeak в комментарии к Integer>>tinyBenchmark указывается, что 400 MHz PII выдавал 18 Мб/с, т.е. был в 46 раз быстрее Dorado). По-этому, уже в 1983 году, после попытки использования шитого кода, в ST-80 ВМ для 680x0 появился динамический транслятор или, говоря современным языком, JIT.
Но, одно лишь колличество исполненных байткодов за секунду это не единственный параметр характеризующий ST ВМ. Так как вызов любой операции в ST (теоретически) происходит только путём отправки сообщения, то помимо байткодов/сек измеряют еще и колличество отправленных сообщений за секунду. Для отправки некому объекту сообщения нужно найти метод-обработчик по селектору (имени). Все методы лежат в словаре где ключ это селектор (имя) сообщения, а значение — метод, обрабатывающий сообщение. В классе хранятся только методы определённые непосредственно в этом классе, не включая методы родителей. Когда приходит сообщение, диспетчер производит поиск в таблице методов. Если находит метод соответствующий сообщению, то происходит его вызов, если не находит, то диспетчер переходит к классу родителя и процедура поиска повторяется. Иногда, приходится последовательно пройти всю иерархию вплоть до класса Object.
Естественно, чтобы постоянно не бегать по одним и тем же классам, результат поиска можно закешировать. Afaik, в первых ST использовался глобальный кеш, где ключем была пара - класс объекта и селектор сообщения. Этот механизм имеет ряд минусов. Например, ограниченный размер кеша приводит к вытеснению "старых" результатов и поиск приходится производить заново.
В дальнейшем, эмпиричиским путём выяснилось, что в каждой отдельной точке посылки сообщения (call site) класс получателя меняется относительно редко. Такая точка вызова называется мономорфной. Следовательно в большинстве случаев можно закешировать адресс метода-обработчика сообщения в самой точке вызова и избежать полного поиска. Такая техника называется inline cache (IC). При IC уже найденный адрес метода прописывается непосредственно в скомпилированом машинном коде. Код в точке вызова проверяет класс получателя на соответствие закешированному классу и переходит на процедуру поиска только если классы не совпадают. Очевидно, что эффективность такого кеша зависит от количества попаданий в кеш (hit ratio). Утверждается что hit ratio для ST программы более 90%, но это довольно старые данные (начало 80-х), а как это проверить самому я не знаю. IC был реализован вместе с первым JIT в уже упоминавшейся ВМ от Deutsch&Schiffman.
А потом в лаборатории Sun появился Self. Self отличается от ST не только тем, что Self основан на прототипах в противовес классам, но и большей динамичностью. Например, там даже доступ к полям объекта происходит только через посылку сообщений, плюс штатная возможность менять иерархию наследования объекта, плюс множественное наследование. В общем, в Self есть куча особенностей затрудняющих создание эффективной реализации ВМ.
В результате работ над Self-90 и Self-93 оказалось, что у того около 25% всех точек вызовов являются не мономорфными, а полиморфными. То есть, местами где значительное число сообщений посылаются объектам разлных классов. Для ускорения работы таких случаев используется polimorphic inline cache (PIC). При этом, в скомпилированном машинном коде кешируется некоторое ограничченное (например 5) число найденных методов. Скомпилированный код при этом может выглядеть так:
if (object->class == #A) goto #A::m; if (object->class == #B) goto #B::m; goto #system_lookup;Количество сравнений увеличивается только при необходимости, то есть для мономорфных точек вызова эффективность будет точно такая же, как при простом IC. Если список классов переполняется, то какой-то из наличных закешированных методов заменяется новым. То есть PIC значительно теряет в эффективности в мегаморфных точках вызова. Т.е. в точках где класс объектов меняется часто. Но, к счастью, таких мест незначительное количество. PIC перекочевал в современные ST ВМ. Например, PIC используется в HPS - ВМ для VisualWorks Smalltalk.
Полезным "побочным" эффектом от использования PIC-ов является то, что в точках вызова накапливается информация о типах, что позволяет проводить адаптивную оптимизацию — перекомпиляцию методов с учетом информации о типах (а это позволяет, например, выполнять инлайнинг). Перекомпиляция проводится только для методов, которые выполняются особенно часто. Подсчет частоты вызова можно осуществлять либо счетчиком внутри метода либо семплированием. Эта техника так же была опробована в Self и показала хорошие результаты: применение PIC вместо IC дало ускорение 25%, а применение адаптивной оптимизации еще 25%.
Ряд людей, работавших в Sun над технологией адаптивной оптимизации для Self в конце 1994г. образовали LongView Technologies LLC, больше известную как Animorphic Systems. В конце 1996г. они представили диалект ST - Strongtalk. ВМ Strongtalk умела производить адаптивную оптимизацию. Однако, в это время с индустрией ST стало очень плохо. И на рынок начала активно продвигаться Java. ВМ для Java (от Sun) в то время были совсем слабыми — простой интерпретатор с консервативным сборщиком мусора с кооперативной многозадачностью. И в 1997г Sun Microsystems приобрела LongView Technologies LLC (она же Animorphic Systems). Все работы над Strongtalk были приостановлены, а Java получила ВМ с адаптивной оптимизацией - HotSpot.
Не смотря на то, что технология адаптивной оптимизации ведомой типами доказала свою эффективность и была описана и изучена, её дальнейшему внедрению в диалекты ST помешала одна проблема. Динамический оптимизатор являлся частью JIT и работал непосредственно в машкодах апаратной платформы. Что усложняло портирование оптимизирующей ВМ на разные платформы. Именно по этой причине Squeak разрабатывался как чистый интерпретатор, что позволяет ему работать на куче различных железяк под самыми разными ОС (хотя PIC можно применять и с интерпретаторами). Из-за резкого схлопывания ST-рынка у производителей диалектов ресурсы были очень ограничены, ST ВМ обычно приходится поддерживать для широкого диапазона различных платформ, а воспользоваться преимуществами адаптивной оптимизации хотелось. Так к 2002г. и оформилась идея, что оптимизатор должен быть реализован на ST, работать в образе и оптимизировать байткод на основании информации собраной в PIC. Технологию An Adaptive Optimizing Smalltalk Architecture (AOStA) начали разрабатывать Элиот Миранда (разработчик ВМ для VisualWorks) и Джилад Браха (разработчик ВМ для Self, Strongtalk, HotSpot) и представили первый результат в 2003г., но до промышленного использования дело не дошло до сих пор.
Суть идеи - на основе некоей информации накопленной ВМ, производится оптимизация байткода: спекулятивный инлайнинг, математические операции над примитивными (разбоксированными) значениями, операции над массивами без проверок индексов и др. Для этого нужно расширить байткоды и добавить в ВМ примитивы (помните, что "примитивами" в ST называются функции в ВМ, а не примитивные значения) работающие без избыточных проверок. Машкод же генерит один и тот же JIT, так как оптимизированный байткод это надмножество исходного неоптимального байткода. Опять же, как и в случае с PIC, генерировать более оптимальный байткод можно и для интерпретатора. Порт AOStA, который разрабатывался тогда в 2003 для Squeak доступен в репозитории SqueakSource. (Не нужно путать AOStA с Exupery, адаптивным компилятором в машкод на чистом ST).
Область байткод-в-байткод динамической оптимизации начинают осваивать наши "соседи": GJIT - динамический оптимизатор для Groovy. Написан на Java и использует трансформацию байткода через JVMTI. Показывает значительное ускорение, по крайней мере на вычислительных тестах. Т.е. для начала результат ободряющий.
Первоисточники информации по адаптивной управляемой типами трансляции:
- "Optimizing Dynamically-Dispatched Calls with Run-Time Type Feedback". Proceedings of the ACM SIGPLAN `94 Conference on Programming Language Design and Implementation, Orlando, FL, June 1994.
- "Adaptive optimization for Self: Reconciling High Performance with Exploratory Programming". Ph.D. thesis, Computer Science Department, Stanford University.
- "Optimizing Dynamically-Typed Object-Oriented Programming Languages with Polymorphic Inline Caches". ECOOP '91 Conference Proceedings, Geneva, Switzerland, July, 1991.
Обратите внимание, что на текущий момент все динамические оптимизаторы срабатывают не для всего исполняемого (байт)кода, а только в случае обнаружения узкого места - часто выполняемого участка. Адаптивная оптимизация управляемая типами находит и оптимизирует часто используемы методы. Но гранулярность в метод это не единственный возможный алгоритм. Есть еще "trace trees" ("деревья трас").
Метод "trace trees" (TT) был разработан для динамической оптимизации машкода в проекте Dynamo, а затем был проработан при разработке оптимизирующих Java JIT для малых устройств. Идея заключается в оптимизации не отдельных методов, а циклов. Циклы находятся путём отслеживания обратных переходов. Когда, во время интерпретации байткода, ВМ обнаруживает обратный переход, то точка куда перешло управление помечается, как потенциальное начало цикла. После некоторого критического колличества переходов на помеченное начало цикла включается режим трассирования. Все выполненые во время трассирования байткоды формируют дерево трас. Формирование дерева прекращается после окончания цикла. Сформированная трасса оптимизируется и компилируется в код целевой платформы. Неисполненные куски цикла так и остаются в байткоде и инкрементально добавляются в дерево трасс, если на каком-то этапе управление попадает туда. Трасса затем перекомпилируется целиком. Все вызовы методов, которые вызываются в процессе трассирования, инлайнятся в трассу. Если инлайнится виртуальный метод, то перед заинлайненым блоком добавляется проверка класса, как в IC. При некоторых условиях трассировка может прерываться и не приводить к генерацию машкода. Например, при вылете исключения, при чрезмерном разрастании трасс и пр. Используется в LuaJIT 2.x.
Не смотря на то, что из байткодов в машкод компилируется только небольшая часть программы, тесты показывают хорошую производительность систем на TT. Статьи по теме:
- "Transparent dynamic optimization: The design and implementation of Dynamo (1999)" by Vasanth Bala, Evelyn Duesterwald, Sanjeev Banerjia.
- "HotpathVM: An Effective JIT for Resource-constrained Devices". Andreas Gal, Michael Franz, Christian W. Probst
- "Incremental Dynamic Code Generation with Trace Trees". Andreas Gal, Michael Franz.
- "Making the Compilation “Pipeline” Explicit: Dynamic Compilation Using Trace Tree Serialization". Andreas Gal, Michael Bebenita, Mason Chang, and Michael Franz.
Теперь вернёмся к началу поста. JavaScript (JS) de-facto занял нишу, на которую изначально претендовала Java - интернет языка. Обладая таким статусом стыдно работать на убогих интерпретатора со сборщиками мусора на счетчиках ссылок. Сейчас ситуация резко меняется.
Движок от Google - V8 - разрабатывают специалисты, которые работали над Strongtalk в Animorphic и, затем, над HotSpot. V8 - это не адаптация ВМ для ST. В V8 нет байткода, из исходного кода генерируется непосредственно машинный код. От байткода отказались, так как JS код постоянно загружается новый. Для поддержки динамической диспетчерезации используется PIC.
Движок от Mozilla - TraceMonkey - наоборот, компилирует JS в байткод (учитывая, что многие плагины к FF написаны на JavaScript это полезная фича). Дальше берётся за работу динамический транслятор, который использует "trace trees" - Tamarin.
Движок от Apple - SquirrelFish - простой интерпретатор байткода (что удивляет, так как именно Apple "ведёт" LLVM). Но, хотя SquirrelFish и не компилирует в машкод, в отличии от двух своих конкурентов, скорость этот интерпретатор показывает вполне приличную.
PS. Продолжение читайте в следующей заметке.Ярлыки: inside_st
