Monday, October 16, 2006

Динамическая оптимизация.

Узнал, что у замечательной компании Transmeta совсем плохи дела -- они уже от нечего делать подают в суд на Intel за нарушение патентов в линейке процессоров начиная с Pentium Pro. Акции за пять лет упали более чем в 10 раз..

Жалко -- компания очень интересная. Их технологии трансляции на лету команд x86 в систему команд процессора Transmeta Crusoe и динамической оптимизации кода в свое время на меня произвели большое впечатление -- в плане производительности интерпретируемых языков.

До того как я почитал про HP Dynamo, я смеялся над тестами в которых C# рвал C++ и думал что это невозможно в принципе. (TM наняла кучу народа, работавшего над этим проектом). Однако Dynamo впечатлило -- софтверный интерпретатор команд (виртуальная машина) для процессора PA-8000, работающий на этом же самом процессоре -- обгоняет в тестах нативный код сгенеренный мощным компилятором C++.

Вот что называется just-in-time compilng и динамическая оптимизация, которая может ускорять вещи, в принципе недоступные классическому компилятору.

В качестве примера -- оптимизация виртуальных вызовов. Классический пример -- CObject с чисто виртуальной функцией draw и унаследованные от него CPoint и CLine, реализующие эту функцию.

Как известно, в C++ для реализации этого у объекта есть указатель на vtable в которой лежат указатели на виртуальные функции. Соответственно чтоб вызвать draw() имея указатель на CObject, надо залезть в vtable по указателю, взять из vtable адрес функции и сделать переход туда (либо на CPoint::draw либо на CLine::draw).
..что довольно хреново с точки зрения процессора: он заранее не может понять, куда мы собираемся сделать переход, и поэтому не может сделать prefetch в кэш для кода. Но если мы используем JIT(компиляцию на лету, как в C#), то JIT-компилятор способен определить, что в 99% случаев реальный тип объекта один и тот же (допустим CPoint), и адрес функции практически всегда один и тот же(CPoint::draw), он сгенерит следующий код:

если (тип_объекта == CPoint)
    переход на CPoint::draw
иначе
   разруливаем дела с vtable

Соответственно вызовы CPoint::draw будут замечательно соптимизированы, процессор сможет сделать заранее прочитать начало функции из памяти1.

Благодаря подобным штукам JIT-компилируемый код может работать быстрее нативного, ведь JIT компилятор -- по сути профайлер и компилятор в одном флаконе, и оптимизирует он именно для той платформы на которой запущено приложение.

Возвращаясь к истории с Transmeta -- у них в процессорах Crusoe подобные вещи использовались для исполнения x86-кода. Оптимизирующий интерпретатор прошит в специальной памяти (типа флэша в биосе, кажется), но реально -- он 100% софтверный. Судя по прессе, к этим вещам также имели непосредственное отношение разработчики "Эльбруса", в котором также широко используются подобные вещи. Зарулить intel по скорости не очень удалось, но зато по потреблению мощности -- чуть ли не в десятки раз, поскольку сам процессор получился намного проще, транзисторов меньше.

1.Реально тут есть еще много тонкостей, связанных с наличием reflection, случаев, когда мы сначала много вызываем CPoint::draw а потом много CLine::draw и пр. Интересная дискуссия на эту тему тут.

6 comments:

Alena said...

Благодаря подобным штукам JIT-компилируемый код может работать быстрее нативного, ведь JIT компилятор -- по сути профайлер и компилятор в одном флаконе, и оптимизирует он именно для той платформы на которой запущено приложение.

С первого взгляда непонятно почему получается быстрее, потому что сама эта оптимизация должна нагружать процессор, насколько я понимаю. Но я сходила по ссылке на HP Dynamo, там это объяснено, правда очень кратко... Слушай, а у тебя нет еще ссылок хороших про JIT?

lrrr said...

Сам бы рад был бы ссылкам :)

Хорошая ссылка на обсуждение, больше про JIT-компилятор Strongtalk там в сноске, еще вот блог про .net JIT (правда давно не обновляется).
Еще можно погуглить что-нибудь про JIT в яве(там компиляторов несколько) и питоне (psyco).

lrrr said...

Основной поинт в том что динамически компилируемые языки *могут* быть быстрее традиционных, статически компилируемых, а возможностей они предоставляют очевидно больше.

Вообще реальный труднопреодолимый минус JIT -- это то что он памяти ест больше, в т.ч. как раз под разные кэши содержащие скомпилированный нативный код.
Но память нынче дешевая...

Top said...

Есть мнение, что Transmeta эээ... позаимствовала идеи Эльбрус :)

Второй пример. Мы долго работали с Sun. С нами работал Дейв Дицел, выдающийся западный архитектор, введший в обиход слово RISC. Он с Дэвидом Патерсоном первый в 81-м году написал статью о преимуществах RISC-архитектуры, и уговаривал промышленников перейти на RISC. Дейв Дицел приехал к нам в середине 91 года, после нашего разговора с Биллом Джоем, и мы начали работать вместе. Мы проработали три счастливых года. У меня есть его письма, где он оценивает нашу архитектуру как выдающуюся. Потом он ушел из Sun. Ему не удалось уговорить фирму сделать нашу архитектуру основной. Он создал свою компанию, корпорацию Transmeta, и продолжал разрабатывать по существу ту же архитектуру, что и в "Эльбрус-3", архитектуру широкого командного слова, основанную на двоичной компиляции, немного другой ее вариант.

(http://www.bashedu.ru/konkurs/tarhov/russian/st1.htm)

А вобще правда очень интересно что может JIT. Ведь по идеи проверки в runtime типа и ветвление могут и замедлить исполнение.
Кстати, у обычный компиляторов (Intel C++ например) есть profiling-driven optimization.

lrrr said...

>Есть мнение, что Transmeta эээ... позаимствовала идеи Эльбрус :)
Да, слышал... Но эти ребята из эльбруса они мутные какие-то, много пафоса, загибания пальцев и мало результатов. Так что сложно сказать, кто там у кого и где..

>А вобще правда очень интересно что может JIT. Ведь по идеи проверки в runtime типа и ветвление могут и замедлить исполнение.

Ну проверки типа в рантайме и JIT это вещи перпендикулярные..) А вообще да, работает медленнее сейчас, но мысль в том что у JIT принципиальные преимущества тоже есть. А PGO в MSVC2005 это все-таки не совсем то, прежде всего потому что оно оптимизирует под машину разработчика, а не конкретного юзера.

vv said...

>> Есть мнение, что Transmeta эээ... позаимствовала идеи Эльбрус :)

Угу, только меньше надо бабаянщины читать.
Кое-кто ещё утверждал что Itanium плохо содран с E2k.
Жалкие людишки.