Сэм Адамс (Sam S. Adams) из IBM Research и Дэвид Унгар* (David Ungar) собираются на Squeak BOF at OOPSLA 2008 представить разработанную в рамках "Renaissance Project" ВМ "multi-vm" - ВМ Squeak способную работать на 56 из 64 ядер процессора Tilera64. Другие подробности пока не известны, так что почему именно 56 ядер пока не ясно (часть ядер вероятно занята системными функциями, типа планировщика или сборки мусора).

* - в инете можно найти разные транскрипции фамилии Ungar: "Ангер", "Унгар". Мне более уместным кажется "Унгар", но как правильно я не уверен.

Из блога "The Hitchhiker's Guide to ...".

Ярлыки: squeak

Sophie - это проект по разработке нового вида электронных книг, использующих мультимедиа возможности современных компьютеров. Совершенно недавно разработка достигла версии 1.0. Версия 2.0 будет полностью написана с нуля на Java. Подрядчиком стала болгарская фирма Astea Solutions.

Проект финансируется The Andrew W. Mellon Foundation и основной причиной смены технологии со Squeak на Java стала невозможность организовать сообщество разработчиков вокруг Sophie. Так как очень мало людей знающих и желающих работать со Smalltalk. И в Фонде Мелона ожидают, что майнстримовый язык программирования поможет образованию сообщества.

Ожидается, что Sophie 2 сможет понимать формат Sophie 1. Текущий интерфейс будет взят за основу и текущий функционал будет не переделан, а дополнен и расширен. Исходники же Sophie 1 открыты и доступны на сайте opensophie.org. И возможно проект на Squeak получит некое продолжение.

Ярлыки: squeak

Многие вероятно успели пустить слезу по потерявшему перспективу Dolphin. Однако ситуация развивается. Старый, заслуживший любовь многих Dolphin таки - "всё" окончательно и бесповоротно, однако, он послужит удобрением для нового улучшенного Dolphin - Dolphin Next Generation.

Разработкой Dolphin Next Generation (DNG) займётся Lesser Software. Lesser software - разработчики LSW Vision Smalltalk (LSWVST), диалекта Visual Smalltalk Enterprise (VSE). Lesser Software уже была засветилась в наших новостях в 2003. Примерно тогда же они собирались выпустить общедоступный вариант своего диалекта ST для .Net, но, очевидно, до коммерческого уровня довести его не смогли. Результат с DNG похоже будет положительный, так как многие части от Dolphin X6 уже запускаются на ВМ от LSWVST - Vision VM.

Новый диалект будет совместим по байткодам с VSE (из-за Vision VM). С Dolphin X6 будет совместимость на уровне исходных кодов. В продукт будет входить вся библиотека классов от Dolphin X6, включая MVP. Бонус Vision VM: JIT, многонитевость ВМ, поддержка 64 бит ОС.

Среди примеров применения как Dolphin так и VSE на территории ex-СССР есть ОАО ТелеNET, г.Тверь, Россия с биллингом на Dolphin Smalltalk, ЗАО Радом-Т, г. Таганрог, Россия с ГИС ObjectLand на Visual Smalltalk Enterprise.

Ярлыки: dolphin, new version

Вышла новая версия Pier - CMS на Seaside. Pier является второй версией SmallWiki. Лицензия - MIT.

Примеры сайтов где используется Pier можно найти на домашнем сайте, естественно управляемом самой Pier. "Естественно" - потому, что принцип использования собственных технологий широко распространён в сообществе ST.

Из примеров: сообщество разработчиков Squeak долгое время обслуживалось Swiki. Сейчас squeak.org работает на SmallWiki, однако куча информации для разработчиков можно найти только на различных swiki. Репозитории проектов для Squeak - SqueakSource работают на Squeak/Seaside.

Документация по Smalltalk/X хостится на ST/X.

Сообщество VisualWorks долгое время поддерживается wiki на VisualWorks. Блоги по VW - написаны на VW продакт менеджером(!).

Такая ситуация во многом возникла благодаря традиции не опускать руки при отсутствии каких-то инструментов, а создавать их самому. И эти созданные для себя инструменты зачастую двигали сообщество вперёд. Например, когда Ави Браянту понадобился инструментарий для быстрой разработки web-приложений он разработал Seaside, понадобилась система контроля версий - он создал Monticello. Менее известный пример - это RSS агрегатор BottomFeeder, разработанный Джеймсом Робертсоном, продакт менеджером Cincom Smalltalk. Разрабатывать BottomFeeder Джеймс начал только для того, чтобы понять стоил ли только возникший тогда RSS какого либо внимания. Значительно продвинул всю индустрию программирования RefactoringBrowser разработанный Кентом Беком. Да и сам Smalltalk появился во многом потому, что Алану Кею нужен был инструмент для обучения детей. А отсутствие удобного средства разработки после ухода из Xerox привело Алана к созданию Squeak. В свете этого мне кажется логичным, что wiki, как таковое, придумал именно smalltalk-ер.

Ваши примеры?

PS. Pier 1.0.17 работает на GLASS и будет поставлятся вместе с GemStone/S 64 version 2.3.

Не успел я запостить статью об оптимизациях как в 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

Обновился сайт squeakland.org - домашний сайт системы для обучения детей Squeak Etoys. Эта система используется для обучения по всему миру (исключая, пожалуй, ex-USSR).

Одной из особенностей Etoys (да и остальных обучающих систем построенных в этих традициях, как Scratch или Small-land) является система скриптования поведения объектов на экране. Подобную подсистему сделали неотъемлемой частью в Tweak, новом визуальном фреймворке созданном для Croquet.

Как мне видится, у "больших дядек" тоже есть аналог подсистемы скриптования - речь идёт о макросах в MS Access.

Визуальный интерфейс генерации скриптов в Etoys:

Визуальный интерфейс генерации макросов в MS Access:

У меня от использования макросов в MS Access 97 осталось 10 летней давности субъективное мнение - минусами были глобальное состояние, и полное несоответствие между функционалом доступным через макросы против функционала доступного через API из VBA. Я не знаю о востребованности и удобстве MSAccess-макросов, но факт что этот функционал остаётся доступен второй десяток лет говорит о том, что свой пользователь у такого подхода (пусть даже с такими ограничениями как в MS Access) есть.

Ярлыки: squeak

Выпущен порт Squeak на iPhone/iPod Touch. Портировать нужно было не только с учетом процессорной платформы, но и с учетом multi-touch интерфейса. Доступен демо-ролик. Подробнее читайте на The Weekly Squeak.

Ярлыки: squeak