Smalltalk по-русски
четверг, Сентябрь 18, 2008
Smalltalk и Все-Все-Все

В последнее время как-то одновременно появились анонсы "быстрого 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. Показывает значительное ускорение, по крайней мере на вычислительных тестах. Т.е. для начала результат ободряющий.

Первоисточники информации по адаптивной управляемой типами трансляции:

Обратите внимание, что на текущий момент все динамические оптимизаторы срабатывают не для всего исполняемого (байт)кода, а только в случае обнаружения узкого места - часто выполняемого участка. Адаптивная оптимизация управляемая типами находит и оптимизирует часто используемы методы. Но гранулярность в метод это не единственный возможный алгоритм. Есть еще "trace trees" ("деревья трас").

Метод "trace trees" (TT) был разработан для динамической оптимизации машкода в проекте Dynamo, а затем был проработан при разработке оптимизирующих Java JIT для малых устройств. Идея заключается в оптимизации не отдельных методов, а циклов. Циклы находятся путём отслеживания обратных переходов. Когда, во время интерпретации байткода, ВМ обнаруживает обратный переход, то точка куда перешло управление помечается, как потенциальное начало цикла. После некоторого критического колличества переходов на помеченное начало цикла включается режим трассирования. Все выполненые во время трассирования байткоды формируют дерево трас. Формирование дерева прекращается после окончания цикла. Сформированная трасса оптимизируется и компилируется в код целевой платформы. Неисполненные куски цикла так и остаются в байткоде и инкрементально добавляются в дерево трасс, если на каком-то этапе управление попадает туда. Трасса затем перекомпилируется целиком. Все вызовы методов, которые вызываются в процессе трассирования, инлайнятся в трассу. Если инлайнится виртуальный метод, то перед заинлайненым блоком добавляется проверка класса, как в IC. При некоторых условиях трассировка может прерываться и не приводить к генерацию машкода. Например, при вылете исключения, при чрезмерном разрастании трасс и пр. Используется в LuaJIT 2.x.

Не смотря на то, что из байткодов в машкод компилируется только небольшая часть программы, тесты показывают хорошую производительность систем на TT. Статьи по теме:

Теперь вернёмся к началу поста. 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. Продолжение читайте в следующей заметке.

Ярлыки:

Comments:
Андрей, спасибо за подробный обзор. Много новой информации, в частности, всё, что касается trace trees для меня новость.
 
Спасибо. Что касается TT, то идея что при JIT можно компилировать не целый метод, а дробное число методов мне кажется интересной. Единственное чего я не совсем понял, так это момент связанный с диспетчеризацией полиморфных методов. ТТ перекомпилируется целиком при добавлении новой трасы в дерево. Значит не делается hot-patching сгенерированного машкода, а значит нельзя реализовать полноценный обновляемый IC/PIC. Но уверенности, что я правильно понял у меня нет :)

Вообще, появление трёх разных движков с абсолютно разными реализациями и, соответсвенно, конкуренция это хорошо. Посмотрим кто выживет :)

Кстати, утверждалось, что V8 может догнать по скорости ВМ от VisualWorks. Может это заставит Cincom пошевелится. А то у них 10 лет самая быстрая коммерческая ВМ среди ST (а среди динамических языковновой волны и подавно). И вроде как получается, что вкладываться в AOStA смысла нету. Последнее нововведение было - добавление PIC. Это было в районе 2000 года.
 
Спасибо, отличный обзор!
 
Хороший обзор, спасибо.
Информация о SquirrelFish сразу же устарела :) потому что вышел SquirrelFish Extreme.
 
Раз такие пироги, то написал продолжение.
Интересно, MS сделает быстрый движок уже в IE8, или потянут до IE8.1 :)
 
Отправить комментарий

<< Home

Популярные статьи
:: Smalltalk?!
:: Почему Smalltalk?
:: Great Leap Forward from Java to Smalltalk

Последние сообщения
:: [Squeak] Новый сайт Squeakland
:: [Squeak] Squeak для iPhone
:: [Squeak] SqueakDBX
:: [Squeak] Monticello 2
:: [GST] GNU Smalltalk 3.0.4 release
:: MagLev - Gemstone for Ruby
:: [Squeak] JSqueak, Potato
:: [Squeak] WxSqueak 0.5
:: [STX] Smalltalk/X 5.4.1
:: Заходите на чашечку кофе сорта Java

Архив
Предыдущие новости / Декабрь 2004 / Январь 2005 / Февраль 2005 / Март 2005 / Апрель 2005 / Май 2005 / Июнь 2005 / Июль 2005 / Август 2005 / Сентябрь 2005 / Октябрь 2005 / Ноябрь 2005 / Декабрь 2005 / Январь 2006 / Февраль 2006 / Март 2006 / Апрель 2006 / Май 2006 / Июнь 2006 / Июль 2006 / Сентябрь 2006 / Октябрь 2006 / Ноябрь 2006 / Декабрь 2006 / Январь 2007 / Февраль 2007 / Март 2007 / Апрель 2007 / Май 2007 / Июнь 2007 / Август 2007 / Сентябрь 2007 / Ноябрь 2007 / Январь 2008 / Март 2008 / Май 2008 / Июнь 2008 / Июль 2008 / Август 2008 / Сентябрь 2008

Atom Feed
Smalltalk по-русски


Powered by Blogger