Необходимо эффективное решение - JAM

После доклада ACS/Dunder в декабре 1989 года мы начали работу над эффективной версией Erlang. Нашей целью было сделать версию Erlang, которая была бы как минимум в 40 раз быстрее прототипа.

В этот момент мы застряли. Мы знали, что мы хотим сделать, но не знали, как это сделать. Наши эксперименты со Стрэндом и Парлогом привели к тупику. Так как мы были знакомы с Прологом, следующим шагом стало создание эффективной машины Пролог. Нечто подобное WAM [29] казалось естественным путем. С этим было две проблемы. Во-первых, WAM не поддерживал параллелизм и обработку ошибок, которые нас интересовали, а во-вторых, мы не могли понять, как работает WAM. Мы прочитали все бумаги, но объяснения, казалось, были написаны только для людей, которые уже поняли, как это работает. Прорыв произошел в начале 1990 года. Роберт Вирдинг собрал большое количество описаний абстрактных машин для реализации параллельных логических машин. В один из выходных я одолжил у него документы и забрал все документы домой. Я начал читать их, что было довольно быстро, так как я на самом деле не понимал их, а затем, внезапно прочитав их все, я начал видеть сходство. Подсказка здесь, и подсказка там, да они все одинаковые. Различаются на поверхности, но очень похожи внизу. Я понял - потом я прочитал их снова, на этот раз медленно. То, что никто не удосужился упомянуть, по-видимому, потому что это было само собой разумеющимся, было то, что каждая из инструкций в одной из этих абстрактных машин одновременно манипулировала несколькими регистрами и указателями. В документах часто не упоминаются указатели стека и кучи, а также все, что изменилось при оценке инструкции, потому что это было очевидно.

Затем я наткнулся на книгу Дэвида Майера и Дэвида Скотта Уоррена [19], которая подтвердила это. Теперь я мог понять, как работает WAM. Поняв это, пришло время проектировать мою собственную машину, JAM (скромность мешает мне раскрыть, что это означает). Некоторые детали отсутствовали в статье Уоррена и других работах, описывающих различные абстрактные машины. Как был представлен код? Как был написан компилятор? Как только вы их поняли, в бумагах, кажется, описываются легкие части; детали реализации казались скорее «коммерческими секретами» и не были описаны. Несколько дополнительных источников повлияли на окончательный дизайн. К ним относятся следующие:

· Портативный компилятор Prolog [9], в котором описано, как оценивались инструкции виртуальной машины.

· Машина Lisp с очень компактными программами [13], описывающая машину Lisp с чрезвычайно компактным представлением.

· BrouHaHa - портативный интерпретатор Smalltalk [22], в котором описаны некоторые хитрые приемы для ускорения диспетчеризации команд в потоковом интерпретаторе.

Когда я проектировал JAM, меня беспокоил ожидаемый размер результирующего объекта для программ. Программы контроля телефонии были огромными, насчитывающими десятки миллионов строк исходного кода. Поэтому объектный код должен быть очень компактным, иначе вся программа никогда не поместится в память. Когда я проектировал JAM, я сел за блокнот, изобрел различные наборы команд, а затем записал, как некоторые простые функции могут быть скомпилированы в эти наборы команд. Я выяснил, как инструкции будут представлены в машине с байтовым кодированием, а затем, сколько инструкций будет оценено при оценке функции верхнего уровня. Затем я изменил набор инструкций и попытался снова. Мой тест всегда был для функции «добавить», и я помню, как скомпилированный набор команд добавлялся в 19 байт памяти. После того, как я определился с набором инструкций, компиляция в JAM была довольно простой, и ранняя версия JAM описана в [5]. На рисунке 3 показано, как функция факториала была скомпилирована в код JAM.

Рис.3 Компиляция последовательного кода Erlang в код JAM.

Возможность создавать собственные виртуальные машины позволила создать очень компактный код для вещей, которые нас больше всего волновали. Мы хотели, чтобы передача сообщений была эффективной. JAM был машиной на основе стека, так что компилировать A! B, компилятор выдал код для компиляции A, затем код для компиляции B, затем однобайтовую инструкцию отправки. Чтобы скомпилировать spawn(Function), компилятор выпустил код для построения замыкания функции в стеке с последующей инструкцией spawn с одним байтом.

Конечно, компилятор был написан на Erlang и запускался через эмулятор Prolog Erlang. Чтобы протестировать абстрактную машину, я написал эмулятор, на этот раз в Prolog, чтобы теперь я мог протестировать компилятор, заставив его компилировать себя. Это было не быстро - оно работало со скоростью около 4 сокращений Erlang (одно сокращение соответствует одному вызову функции) в секунду, но было достаточно быстрым, чтобы протестировать себя. Компиляция компилятора занимала много времени и могла выполняться только два раза в день, либо на обед, либо на ночь.

Сам компилятор был довольно маленькой и простой программой. Он был небольшим, потому что большинство примитивов в Erlang можно было скомпилировать в один код операции на виртуальной машине. Таким образом, все, что нужно было сделать компилятору, - это сгенерировать код для эффективного сопоставления с образцом, а также для построения и восстановления терминов. Большая часть сложности заключается в системе времени выполнения, которая реализует коды операций виртуальной машины. Самый ранний сохранившийся компилятор - это erl89, в котором было 18 модулей, содержащих 2544 строки кода. Модули в компиляторе были такими, как в таблице 2.

Пришло время реализовать эмулятор виртуальной машины JAM, на этот раз не в Прологе, а в Си. Именно сюда пришел Майк Уильямс. Я сам начал писать эмулятор на C, но вскоре Майк вмешался и начал грубо комментировать мой код. Я не много писал на C раньше, и моя идея написать C состояла в том, чтобы закрыть глаза и притвориться, что это FORTRAN. Майк вскоре взял на себя эмулятор, выбросил весь мой код и начал снова. Теперь группа разработчиков Erlang расширилась до трех: Майк, Роберт и я. Майк очень тщательно написал внутренний цикл эмулятора, поскольку заботился об эффективности критических кодов операций, используемых для одновременных операций. Он компилирует эмулятор, затем смотрит на сгенерированный ассемблерный код, затем снова изменяет компиляцию кода и смотрит на код, пока он не будет счастлив. Я помню, как он работал в течение нескольких дней, чтобы правильно отправлять сообщения. Когда сгенерированный код дошёл до шести инструкций, он сдался.

Эмулятор Майка вскоре сработал. Мы измерили, как быстро это было. После первоначальной настройки он работал в 70 раз быстрее, чем оригинальный эмулятор Prolog. Мы были в восторге - мы прошли нашу цель 40 с явным отрывом. Теперь мы могли бы сделать некоторые реальные продукты.

Между тем, новости от группы Bollmora были не очень хорошими: «Мы ошиблись, наш коэффициент 40 был неправильным, он должен быть в 280 раз быстрее».

Один из рецензентов этой статьи спросил, была ли когда-нибудь проблема эффективности памяти. На этом этапе ответ был отрицательным. Эффективность ЦП всегда была проблемой, но не эффективностью памяти.

Языковые изменения

Теперь, когда мы подошли к 1990 году и получили достаточно быстрый Erlang, наше внимание переключилось на другие области. Эффективность все еще была проблемой, но подстегнутая нашим первым успехом, мы не особенно беспокоились об этом. Одна из вещей, которая произошла при написании Erlang на Erlang, заключалась в том, что мы должны были написать наш собственный парсер. Раньше мы только использовали инфиксные операторы в Прологе. В этот момент язык приобрел собственный синтаксис, что, в свою очередь, привело к изменению языка. В частности, receive был изменен.

Наличие собственного синтаксиса ознаменовало значительное изменение языка. Новая версия Erlang вела себя почти так же, как старый переводчик Prolog, но почему-то все было иначе. Кроме того, наше понимание системы углубилось, когда мы столкнулись с хитрыми проблемами реализации, от которых нас защитил Пролог. Например, в системе Prolog нам не нужно было беспокоиться о сборке мусора, но в нашем новом движке Erlang нам пришлось реализовывать сборщик мусора с нуля.

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

Последняя стратегия, которую мы приняли после экспериментирования со многими различными стратегиями, заключалась в том, чтобы использовать GC для каждого процесса с остановкой и копированием. Идея заключалась в том, что если у нас будет много тысяч небольших процессов, то время, затрачиваемое на сборку мусора для каждого отдельного процесса, будет небольшим. Эта стратегия также поощряет копирование всех данных, связанных с передачей сообщений между процессами, чтобы не оставлять висячих указателей. между процессами, которые усложняют сборку мусора. Дополнительным преимуществом этого, которое мы не осознавали в то время, было то, что копирование данных между процессами увеличивает изоляцию процессов, повышает параллелизм и упрощает построение распределенных систем. Только когда мы запустили Erlang на многоядерных процессорах, стало очевидным полное преимущество неразделенной памяти. На многоядерных процессорах передача сообщений происходит очень быстро, а отсутствие блокировки между процессорами позволяет каждому процессору работать без ожидания других процессоров.

Наш подход к GC казался немного безрассудным: будет ли этот метод работать на практике? Мы были обеспокоены рядом проблем. Решит ли большое количество процессов собрать мусор одновременно? Смогут ли программисты структурировать свои приложения, используя множество небольших процессов, или они будут использовать один большой процесс? Если бы они использовали один большой процесс, что бы произошло, когда он выполнил сборку мусора? Система остановится? На практике наши опасения были необоснованными. Сборка мусора процессов, кажется, происходит случайно, и программисты очень редко используют один большой процесс, чтобы делать все. Современные системы работают с десятками и сотнями тысяч процессов, и кажется, что когда у вас такое большое количество процессов, эффекты GC в отдельном процессе незначительны.

⇐ Предыдущая123456Следующая ⇒

Поделиться: