Внутреннее устройство llst, часть 2 или Little Smalltalk + LLVM = ♥

Всем привет! Совместно с humbug, мы предлагаем вашему вниманию третью статью из цикла о Low Level Smalltalk (LLST). Надемся, что статья будет интересна не только любителям велосипедов необычных языков программирования, но и тем, кто интересуется такой замечательной вещью, как LLVM.

Напомню, что целью нашего проекта является создание собственной виртуальной машины, совместимой с Little Smalltalk на уровне байт-кодов. Ключевым отличием является гетерогенная архитектура, которая позволяет исполнять байт-коды как программно, так и компилировать их в низкоуровневые инструкции процессора посредством трансляции в IR код LLVM. Разумеется, второй способ позволяет достичь более высокой производительности и задействовать имеющиеся в нашем распоряжении вычислительные ресурсы оптимальным образом.

Однако, обо всем по порядку…

Новое в версии 0.2

По сравнению с прошлой версией, описанной в предыдущей статье, изменений очень много:

• Подключили библиотеку readline. Теперь можно удобно редактировать командную строку; появилась история ранее введенных команд (Ctrl+R) и автодополнение по клавише Tab. В общем, все работает так же, как в любом нормальном шелле.
• Дописаны примитивы работы с файлами и реализована запись образа на диск. Теперь с новой VM можно делать практически то же самое, что и с оригинальной.
• Реализована примитивная многозадачность (green threads) на базе класса Scheduler. В планах — полноценная многопоточность.
• Написаны тесты для основных операций с объектами, которые значительно упростили последующую отладку. Тесты — это круто!
• Переделаны указатели на объекты кучи hptr<>. Раньше они использовали внешние списки std::list<>, теперь список поддерживается в стековом пространстве. Одно только это ускорило софтовую VM в два раза.
• В ветке 37 сделаны наброски Native API, который в будущем позволит удобно писать нативные методы совершенно без врапперов и прочих костылей. Методы реализуются «по месту», в тех же классах, что описывают структуру эквивалентных сущностей из Smalltalk. Примеры можно посмотреть здесь, здесь и здесь.
• Сделана попытка реализации Generational GC на базе имеющегося Бейкера. По сути, все отличие в роли половинок кучи и хранении списка ссылок между поколениями. Таким образом, при быстрой сборке необходимо пробежаться только по молодому поколению и взять оттуда объекты, на которые есть ссылки из более старших поколений. Код написан, но пока не отлажен.
• Начата работа по переписыванию ImageBuilder с нуля с использованием Flex/Bison. Доставшаяся в наследство утилита имеет множество проблем: нельзя передавать параметры, нет нормального вывода ошибок, «мистические» падения при изменении пары символов в коде образа; такие же «мистические» оживания при удалении, например, комментария и т. п. Кроме того, утилита в некоторых случаях генерирует некорректный байт-код. Так жить, разумеется, нельзя, поэтому мы решили ее переделать. На данный момент полностью описана грамматика Little Smalltalk; помимо самих конструкций языка еще присутствуют управляющие команды, которые используются для построения первичного bootstrap образа.
• Завели доменное имя и переехали на GitHub. Теперь репозиторий доступен по адресу llst.org. Обратите также внимание на трекер.

Ну а теперь, самое интересное:

• Реализовали трансляцию байт-кодов Smalltalk в IR код LLVM. Причем делается это на лету, прямо в момент посылки сообщения. То есть, при первом вызове некоторое время будет потрачено на трансляцию и компиляцию кода метода (милисекунды), зато последующие вызовы будут выполняться уже нативно.
• Реализован дополнительный проход, удаляющий лишние интринсики llvm.gcroot, для сокращения количества обращений к памяти (и повышения скорости, само собой).
• Собирается статистика по посылкам сообщений и «горячим точкам» методов. Это является основой для последующих оптимизаций.
• Наконец, реализован проход модификации «горячих» методов, который на основе собранной статистики изменяет методы внедряя прямые вызовы, минуя кеши и поиск в таблицах классов. Это позволяет задействовать конвейер и предсказатель перехода процессора оптимальным образом, что положительно сказывается на производительности.

На текущий момент, горячий код с прогнанными оптимизациями выполняется от 2 до 100 раз быстрее, по сравнению с прошлой версией программной VM (в зависимости от выполняемого кода). Неплохо, как мне кажется. Хотя простор для развития еще есть. По сути, сделаны самые простые оптимизации, не требующие сложного анализа графа и вывода типов. При желании и наличии свободного времени, можно сделать куда более эффектные вещи.

Как это выглядит

Давайте посмотрим, как знание статистики вызовов может ускорить код. Тесты будем проводить на уже известном нам алгоритме сортировки, описанном в прошлой статье, а также на бенчмарке, который позволяет оценить скорость обработки сообщений. Желающим установить версию локально, советую либо ставить скомпилированную версию, либо собрать из исходников, предварительно прочитав пункты Usage и LLVM в описании репозитория на гитхабе.

Начнем с бенчмарка:

loopBenchmark | sum |
    sum <- 0.
    1 to: 100000 do: [ :x | sum <- sum + 1 ].
    ^sum

Этот «гениальный» код сто тысяч раз прибавляет единичку к переменной sum. Разумеется, на выходе мы должны получить те же сто тысяч (или же наша VM может отправляться на помойку).

А вот так выглядит результат прогона:

$ ./llst
Image read complete. Loaded 5442 objects
Soft run: 60
Cold jit run: 46
Hot jit run: 28
JIT Runtime stat:
        Messages dispatched:       200006
        Objects  allocated:        200004
        Blocks   invoked:          200002
        Block    cache hits:       199999  misses          3 ratio 100.00 %
        Message  cache hits:       400004  misses          6 ratio 100.00 %
 
Hot methods:
        Hit count       Method name
        200000          Block>>value: (0 sites)
        2               Number>>to:do: (1 sites)
                value:               (index 20, offset 109) class hits: (Block 200000)
        2               Undefined>>loopBenchmark (1 sites)
                to:do:               (index 15, offset 73) class hits: (SmallInt 2)
        2               Block>>value (0 sites)
 
Patching active methods that have hot call sites
Recompiling method for patching: Number>>to:do:
Patching Number>>to:do: ...done. Verifying ...done.
Recompiling method for patching: Undefined>>loopBenchmark
Patching Undefined>>loopBenchmark ...done. Verifying ...done.
Optimizing Number>>to:do: ...done. Verifying ...done.
Optimizing Undefined>>loopBenchmark ...done. Verifying ...done.
Compiling machine code for Number>>to:do: ...done.
Compiling machine code for Undefined>>loopBenchmark ...done.
All is done.
Patched cold jit run: 12
Patched hot jit run: 9
JIT Runtime stat:
        Messages dispatched:       200010
        Objects  allocated:        400008
        Blocks   invoked:          400004
        Block    cache hits:       399998  misses          6 ratio 100.00 %
        Message  cache hits:       400006  misses         10 ratio 100.00 %
 
Hot methods:
        Hit count       Method name
        200000          Block>>value: (0 sites)
        4               Block>>value (0 sites)
        2               Undefined>>loopBenchmark (0 sites)
        2               Number>>to:do: (1 sites)
                value:               (index 20, offset 109) class hits: (Block 200000)
        2               Undefined>>loopBenchmark (1 sites)
                to:do:               (index 15, offset 73) class hits: (SmallInt 2)
 
===-------------------------------------------------------------------------===
                          ... Statistics Collected ...
===-------------------------------------------------------------------------===
 
   2 adce           - Number of instructions removed
   2 branchfolding  - Number of block tails merged
   2 branchfolding  - Number of dead blocks removed
   1 cgscc-passmgr  - Maximum CGSCCPassMgr iterations on one SCC
  31 codegen-dce    - Number of dead instructions deleted
  63 codegenprepare - Number of GEPs converted to casts
   9 codegenprepare - Number of blocks eliminated
 114 codegenprepare - Number of memory instructions whose address computations were sunk
  47 codegenprepare - Number of uses of Cast expressions replaced with uses of sunken Casts
 313 dagcombine     - Number of dag nodes combined
   0 dse            - Number of other instrs removed
  12 dse            - Number of stores deleted
  54 gvn            - Number of blocks merged
   2 gvn            - Number of instructions PRE'd
 125 gvn            - Number of instructions deleted
   2 gvn            - Number of loads PRE'd
  37 gvn            - Number of loads deleted
 265 inline         - Number of functions inlined
 271 inline-cost    - Number of call sites analyzed
 263 instcombine    - Number of dead inst eliminated
   1 instcombine    - Number of dead stores eliminated
  67 instcombine    - Number of instructions sunk
 492 instcombine    - Number of insts combined
 159 isel           - Number of blocks selected using DAG
7667 isel           - Number of times dag isel has to try another path
 101 jit            - Number of bytes of global vars initialized
5310 jit            - Number of bytes of machine code compiled
  12 jit            - Number of global vars initialized
 239 jit            - Number of relocations applied
   3 jit            - Number of slabs of memory allocated by the JIT
   1 loop-simplify  - Number of pre-header or exit blocks inserted
   3 machine-licm   - Number of hoisted machine instructions CSEed
  11 machine-licm   - Number of machine instructions hoisted out of loops
  73 machine-sink   - Number of machine instructions sunk
   6 memdep         - Number of block queries that were completely cached
  11 memdep         - Number of fully cached non-local ptr responses
  43 memdep         - Number of uncached non-local ptr responses
 784 pei            - Number of bytes used for stack in all functions
   1 phi-opt        - Number of dead PHI cycles
  15 phielim        - Number of atomic phis lowered
  31 pre-RA-sched   - Number of loads clustered together
  48 reassociate    - Number of insts reassociated
  29 regalloc       - Number of cross class joins performed
 251 regalloc       - Number of identity moves eliminated after coalescing
  92 regalloc       - Number of identity moves eliminated after rewriting
   7 regalloc       - Number of instructions deleted by DCE
   4 regalloc       - Number of instructions re-materialized
   1 regalloc       - Number of interferences evicted
 251 regalloc       - Number of interval joins performed
  11 regalloc       - Number of new live ranges queued
 683 regalloc       - Number of original intervals
 369 regalloc       - Number of registers assigned
   1 regalloc       - Number of registers unassigned
   3 regalloc       - Number of rematerialized defs for spilling
   4 regalloc       - Number of rematerialized defs for splitting
   3 regalloc       - Number of spilled live ranges
   2 regalloc       - Number of splits finished
   4 simplifycfg    - Number of blocks simplified
   2 twoaddrinstr   - Number of instructions aggressively commuted
   2 twoaddrinstr   - Number of instructions commuted to coalesce
   4 twoaddrinstr   - Number of instructions promoted to 3-address
  30 twoaddrinstr   - Number of two-address instructions
  14 x86-codegen    - Number of floating point instructions
1414 x86-emitter    - Number of machine instructions emitted
 
->

Важными тут являются пять строчек:

Soft run: 60
Cold jit run: 46
Hot jit run: 28
Patched cold jit run: 12
Patched hot jit run: 9

Первая строка — выполнение метода средствами программной VM. Самый медленный способ: никаких фокусов, код выполняется предельно корректно, инструкция за инструкцией. Этот режим хорош для отладки, поскольку не вносит никаких изменений в код; также он используется встроенным в образ компилятором при разборе командной строки.

Вторая строка — «холодный» прогон JIT. Выполняется трансляция метода в функционально эквивалентный IR код, его компиляция в инструкции процессора, которые уже выполняются непосредственно. Уже на этом этапе производятся кое какие оптимизации, о которых будет рассказано позже. Видно, что даже с учетом компиляции метода, итоговое время выполнения меньше, чем чистое исполнение. Так бывает не всегда. Зачастую, для сложных методов первое выполнение может потребовать на ≈ 100 мс больше времени, зато потом получаем выигрыш. В этом же режиме накапливается статистика по вызовам (при каждом обращении к обработчику вызова, который запускает скомпилированный метод).

Третья строка — «горячий» прогон. Вызывается метод уже знакомый JIT, поэтому задействуется готовый, скомпилированный код. Никакого оверхеда — только проверка наличия в кэше методов и прямой вызов функции. Результат налицо.

Четвертая строка — «холодный» прогон патчера и расстановка прямых вызовов (директов) там, где статистика показывает целесообразность сего мероприятия. При этом из функции выкидывается все тело (которое перекомпилируется заново), а затем выполняется проход патчера. Полная перекомпиляция нужна для того, чтобы патчер смог найти инструкцию, которую надо заменить на прямой вызов. Проблема в том, что после оптимизирущих проходов (а также подготовки кода к GC) тело метода может измениться до неузнаваемости. После всех этих манипуляций осуществляется компиляция IR кода в реальные инструкции процессора с последующим выполнением.

Пятая строка — «горячий» прогон пропатченного и оптимизированного метода. Опять же, просто выполнение, без всяких ухищрений.

Такие вот пироги… Экстраполировав значения получаем, что на моей машине обрабатывается примерно 12 миллионов блоков в секунду. Из этой константы можно получить оценку количества обрабатываемых сообщений. В JIT коде, соответствующем методу Integer>>to:do:, выполняются три операции, эквивалентные следующим посылкам сообщений:

• Посылка < объекту счетчика внутри #to:do: (условие цикла);
• Посылка #value: объекту блока (вызов блока);
• Посылка + объекту sum (тело цикла).

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

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

loopBenchmark | sum |
    sum <- 0.
    [ sum < 1000000 ] whileTrue: [ sum <- sum + 1 ].
    ^sum

то результаты прогона на одном миллионе (вместо ста тысяч, обратите внимание на константу) будут такими:

Soft run: 197
Cold jit run: 13
Hot jit run: 4

В этом случае мы получаем эквивалент уже ≈ 8,1 ⋅ 10⁸ сообщений в секунду, или ускорение в 197 / 4 ≈ 50 раз. Это происходит потому, что теперь скомпилированный вариант не содержит ни одной реальной операции посылки сообщения. Цикл whileTrue: разворачивается в линейный набор инструкций с переходами; все операции происходят над числами, для которых есть отдельные ветви исполнения, задействующие арифметические операции напрямую.

Результаты прогона с патчером не отличаются от результатов горячего прогона JIT, поскольку здесь нет посылок сообщений, а значит нет статистики, которую можно собрать, и нет вызовов программной VM, которые можно было бы заменить прямыми вызовами JIT фукнций.

Разумеется, нужно с большой осторожностью относиться ко всякого рода бенчмаркам (особенно целочисленным), когда речь идет о производительности VM. Мы используем эти цифры только для грубой оценки проведенных оптимизаций и как показатель того, что в среднем код стал выполняться быстрее.

Конечно, реальные цифры будут меньше, поскольку здесь мы имеем практически идеальные условия для оптимизации: циклы и арифметика компилируются в нативный код целиком. Наличие прямых инструкций перехода оптимальным образом задействует предсказатель переходов процессора, кэши меньше промахиваются. Отсюда и прирост по сравнению с неоптимизированным вариантом, где на каждую посылку надо зайти в заглушку-обработчик, заглянуть в кэш и понять, кому реально нужно адресовать сообщение. Даже с учетом 99% попаданий, на это все равно расходуются драгоценные такты процессора.

Тест сортировки демонстрирует результаты поскромнее:

Soft run: 48
Cold jit run: 140
Hot jit run: 25
Patched cold jit run: 7
Patched hot jit run: 6

Preparing test data ...done
Soft run: 48
Cold jit run: 140
Hot jit run: 25

JIT Runtime stat:
        Messages dispatched:       210613
        Objects  allocated:         17746
        Blocks   invoked:           43006
        Block    cache hits:        43001  misses          5 ratio  99.99 %
        Message  cache hits:       369520  misses      51704 ratio  87.73 %

Hot methods:
        Hit count       Method name
        44061           Link>>next (0 sites)
        35102           MetaObject>>in:at:put: (0 sites)
        27775           Link>>value (0 sites)
        25778           Block>>value:value: (0 sites)
        17746           Class>>new (0 sites)
        17356           MetaLink>>value:next: (3 sites)
                new                  (index 3, offset 7) class hits: (MetaLink 17356) 
                in:at:put:           (index 11, offset 31) class hits: (MetaLink 17356) 
                in:at:put:           (index 18, offset 72) class hits: (MetaLink 17356) 
        17226           Block>>value: (0 sites)
        15619           List>>add: (1 sites)
                value:next:          (index 5, offset 13) class hits: (MetaLink 15619) 
        1999            List>>isEmpty (1 sites)
                =                    (index 4, offset 9) class hits: (SmallInt 1999) 
        1999            SmallInt>>= (0 sites)
        1867            List>>insert:onCondition: (10 sites)
                isEmpty              (index 3, offset 7) class hits: (List 1867) 
                add:                 (index 10, offset 27) class hits: (List 130) 
                value                (index 33, offset 166) class hits: (Link 10419) 
                value:value:         (index 40, offset 210) class hits: (Block 10419) 
                next                 (index 48, offset 268) class hits: (Link 1481) 
                value:next:          (index 50, offset 286) class hits: (MetaLink 1481) 
                value:next:          (index 57, offset 21) class hits: (Link 1481) 
                next                 (index 68, offset 8) class hits: (Link 8938) 
                value:next:          (index 81, offset 24) class hits: (MetaLink 256) 
                next:                (index 83, offset 9) class hits: (Link 256) 
        1481            Link>>value:next: (0 sites)
        392             List>>size (0 sites)
        390             MetaList>>new (2 sites)
                new                  (index 4, offset 9) class hits: (MetaCollection 390) 
                in:at:put:           (index 12, offset 34) class hits: (MetaList 390) 
        384             Link>>next: (0 sites)
        262             Collection>>sort: (13 sites)
                size                 (index 3, offset 7) class hits: (List 262) 
                insertSort:          (index 12, offset 34) class hits: (List 132) 
                popFirst             (index 21, offset 88) class hits: (List 130) 
                new                  (index 26, offset 126) class hits: (MetaList 130) 
                new                  (index 31, offset 158) class hits: (MetaList 130) 
                value:value:         (index 42, offset 219) class hits: (Block 15359) 
                add:                 (index 49, offset 279) class hits: (List 8207) 
                add:                 (index 56, offset 12) class hits: (List 7152) 
                do:                  (index 59, offset 31) class hits: (List 130) 
                sort:                (index 64, offset 64) class hits: (List 130) 
                sort:                (index 70, offset 19) class hits: (List 130) 
                add:                 (index 76, offset 4) class hits: (List 130) 
                appendList:          (index 81, offset 24) class hits: (List 130) 
        260             Link>>do: (2 sites)
                value                (index 18, offset 72) class hits: (Link 260) 
                value:               (index 20, offset 82) class hits: (Block 260) 
        260             List>>do: (1 sites)
                do:                  (index 9, offset 25) class hits: (Link 260) 
        132             Collection>>insertSort: (4 sites)
                isEmpty              (index 3, offset 7) class hits: (List 132) 
                new                  (index 16, offset 55) class hits: (MetaList 130) 
                insert:onCondition:  (index 27, offset 130) class hits: (List 1867) 
                do:                  (index 30, offset 143) class hits: (List 130) 
        130             List>>popFirst (3 sites)
                value                (index 14, offset 43) class hits: (Link 130) 
                next                 (index 19, offset 76) class hits: (Link 130) 
                -                    (index 25, offset 111) class hits: (SmallInt 130) 
        130             SmallInt>>- (0 sites)
        130             List>>appendList: (7 sites)
                firstLink            (index 8, offset 21) class hits: (List 2) 
                size                 (index 13, offset 40) class hits: (List 2) 
                next                 (index 36, offset 181) class hits: (Link 8207) 
                next                 (index 43, offset 234) class hits: (Link 8079) 
                firstLink            (index 54, offset 3) class hits: (List 128) 
                next:                (index 56, offset 12) class hits: (Link 128) 
                size                 (index 61, offset 49) class hits: (List 128) 
        130             List>>firstLink (0 sites)
        2               Collection>>sort (1 sites)
                sort:                (index 10, offset 27) class hits: (List 2) 
        2               Block>>value (0 sites)

===-------------------------------------------------------------------------===
                          ... Statistics Collected ...
===-------------------------------------------------------------------------===

    2 adce           - Number of instructions removed
   14 branchfolding  - Number of block tails merged
    6 branchfolding  - Number of branches optimized
    5 branchfolding  - Number of dead blocks removed
    1 cgscc-passmgr  - Maximum CGSCCPassMgr iterations on one SCC
   38 codegen-dce    - Number of dead instructions deleted
  220 codegenprepare - Number of GEPs converted to casts
    2 codegenprepare - Number of blocks eliminated
  151 codegenprepare - Number of memory instructions whose address computations were sunk
  123 codegenprepare - Number of uses of Cast expressions replaced with uses of sunken Casts
  854 dagcombine     - Number of dag nodes combined
  250 dce            - Number of insts removed
  194 dse            - Number of other instrs removed
  158 dse            - Number of stores deleted
   51 gvn            - Number of blocks merged
  353 gvn            - Number of instructions deleted
    6 gvn            - Number of loads PRE'd
  277 gvn            - Number of loads deleted
  862 inline         - Number of functions inlined
  862 inline-cost    - Number of call sites analyzed
 1085 instcombine    - Number of dead inst eliminated
   69 instcombine    - Number of instructions sunk
 2540 instcombine    - Number of insts combined
  194 isel           - Number of blocks selected using DAG
18193 isel           - Number of times dag isel has to try another path
  461 jit            - Number of bytes of global vars initialized
12042 jit            - Number of bytes of machine code compiled
   25 jit            - Number of global vars initialized
  375 jit            - Number of relocations applied
    2 jit            - Number of slabs of memory allocated by the JIT
   15 llst           - Number of removed loads from gc.root protected pointers                       <<<<<<
  222 llst           - Number of removed roots                                                       <<<<<<
    4 machine-cse    - Number of common subexpression eliminated
    1 machine-licm   - Number of hoisted machine instructions CSEed
   14 machine-licm   - Number of machine instructions hoisted out of loops
   71 machine-sink   - Number of machine instructions sunk
   10 memdep         - Number of block queries that were completely cached
   81 memdep         - Number of fully cached non-local ptr responses
   84 memdep         - Number of uncached non-local ptr responses
 2792 pei            - Number of bytes used for stack in all functions
    9 phielim        - Number of atomic phis lowered
    2 phielim        - Number of critical edges split
   36 pre-RA-sched   - Number of loads clustered together
   23 reassociate    - Number of insts reassociated
   21 regalloc       - Number of cross class joins performed
  250 regalloc       - Number of identity moves eliminated after coalescing
  124 regalloc       - Number of identity moves eliminated after rewriting
    6 regalloc       - Number of instructions deleted by DCE
    1 regalloc       - Number of interferences evicted
  248 regalloc       - Number of interval joins performed
   21 regalloc       - Number of new live ranges queued
 1240 regalloc       - Number of original intervals
  891 regalloc       - Number of registers assigned
    1 regalloc       - Number of registers unassigned
    6 regalloc       - Number of rematerialized defs for spilling
    4 regalloc       - Number of rematerialized defs for splitting
    6 regalloc       - Number of spilled live ranges
    4 regalloc       - Number of splits finished
   13 simplifycfg    - Number of blocks simplified
    3 twoaddrinstr   - Number of instructions re-materialized
   43 twoaddrinstr   - Number of two-address instructions
   40 x86-codegen    - Number of floating point instructions
 2697 x86-emitter    - Number of machine instructions emitted

Patching active methods that have hot call sites
Recompiling method for patching: MetaLink>>value:next:
Patching MetaLink>>value:next: ...done. Verifying ...done.
Recompiling method for patching: List>>add:
Patching List>>add: ...done. Verifying ...done.
Recompiling method for patching: List>>isEmpty
Patching List>>isEmpty ...done. Verifying ...done.
Recompiling method for patching: List>>insert:onCondition:
Patching List>>insert:onCondition: ...done. Verifying ...done.
Recompiling method for patching: MetaList>>new
Patching MetaList>>new ...done. Verifying ...done.
Recompiling method for patching: Collection>>sort:
Patching Collection>>sort: ...done. Verifying ...done.
Recompiling method for patching: Link>>do:
Patching Link>>do: ...done. Verifying ...done.
Recompiling method for patching: List>>do:
Patching List>>do: ...done. Verifying ...done.
Recompiling method for patching: Collection>>insertSort:
Patching Collection>>insertSort: ...done. Verifying ...done.
Recompiling method for patching: List>>popFirst
Patching List>>popFirst ...done. Verifying ...done.
Recompiling method for patching: List>>appendList:
Patching List>>appendList: ...done. Verifying ...done.
Recompiling method for patching: Collection>>sort
Patching Collection>>sort ...done. Verifying ...done.
Optimizing MetaLink>>value:next: ...done. Verifying ...done.
Optimizing List>>add: ...done. Verifying ...done.
Optimizing List>>isEmpty ...done. Verifying ...done.
Optimizing List>>insert:onCondition: ...done. Verifying ...done.
Optimizing MetaList>>new ...done. Verifying ...done.
Optimizing Collection>>sort: ...done. Verifying ...done.
Optimizing Link>>do: ...done. Verifying ...done.
Optimizing List>>do: ...done. Verifying ...done.
Optimizing Collection>>insertSort: ...done. Verifying ...done.
Optimizing List>>popFirst ...done. Verifying ...done.
Optimizing List>>appendList: ...done. Verifying ...done.
Optimizing Collection>>sort ...done. Verifying ...done.
Compiling machine code for MetaLink>>value:next: ...done.
Compiling machine code for List>>add: ...done.
Compiling machine code for List>>isEmpty ...done.
Compiling machine code for List>>insert:onCondition: ...done.
Compiling machine code for MetaList>>new ...done.
Compiling machine code for Collection>>sort: ...done.
Compiling machine code for Link>>do: ...done.
Compiling machine code for List>>do: ...done.
Compiling machine code for Collection>>insertSort: ...done.
Compiling machine code for List>>popFirst ...done.
Compiling machine code for List>>appendList: ...done.
Compiling machine code for Collection>>sort ...done.
All is done.
Patched cold jit run: 7
Patched hot jit run: 6

Тут нужно сказать пару слов о том что и как оптимизируется. Во-первых, сейчас патчер проходит только по функциям методов. Блоки же остаются неоптимизированными. Во-вторых, на каждую операцию посылки сообщения создается инстанция класса Array, в которой размещаются аргументы сообщения. На это тоже тратится время. Наконец, сейчас практически не применяется инлайнинг методов. Он касается только служебных функций (как мы увидем позже) и некоторых тривиальных конструкций. Все это позволяет заключить, что потенциал для дальнейших оптимизаций далеко не исчерпан.

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

Виртуальная машина Smalltalk

Виртуальная машина оперирует объектами. Оперирование сводится к обмену сообщениями между объектами и подметанию мусора за ними. По сути, единственная серьезная операция, которую делает виртуальная машина — это посылка сообщения. Все остальное, так или иначе, сводится к той же посылке.

Чтобы понять как машина это делает, надо сначала понять, что же такое Smalltalk объект.

Объекты

Любой объект упрощенно может быть представлен следующей структурой:

struct TObject {
    TSize    size;
    TClass*  klass;
    union {
        TObject* fields[0];
        uint8_t  bytes[0];
    };
};

Каждый объект имеет заголовок в котором записан размер объекта и указатель на его класс. Следом идут поля объекта, содержащие указатели на другие объекты. Разумеется, и класс и поля тоже являются объектами, а потому представлены такими же структурами.

Все объекты в Smalltalk имеют размер кратный 4 байтам. Этот размер хранится по нулевому смещению, причем младшим двум битам отводится особая роль — они хранят флаги Binary (B) и Indirect (I). Флаг B означает, что объект является бинарным, то есть хранит сырой набор байтов в месте, отведенном под поля у обычных объектов. Такими объектами являются, например, строки (инстанции String). Байт-коды методов сохраняются в инстанциях ByteArray, которые тоже являются бинарными объектами. Бинарные объекты всегда дополняются байтами до кратной длины. Флаг I используется сборщиком мусора при проходе по куче для отметки тех объектов, которые уже были обработаны.

Таким образом, остается 30 бит под размер объекта. Для обычных объектов размер считается в полях (кратно 4 байтам), для бинарных — в байтах. Поскольку и те и другие объекты имеют одинаковый, заранее известный заголовок, его размер в общей сумме не учитывается.

SmallInt

Все объекты располагаются в памяти выровненными по 4 байта. Таким образом, младшие два бита адреса всегда оказываются равными 0. Этот факт используется для хранения чисел длиной до 31 бита прямо в полях объекта. При этом записываемое число умножается на 2 (смещается на 1 бит влево), а младший бит устанавливается в 1. Виртуальная машина в курсе этой оптимизации, и во всех местах, где происходит обращение к полям, делает проверку, действительно ли там хранится указатель на объект, или же эту информацию необходимо трактовать как число.

Важно отметить, что этот момент совершенно прозрачен для остальной части системы. Прикладному программисту не требуется знать, что, где и как хранится. Например, вполне легально будет написать в консоли команду 1 class и получить ожидаемый ответ SmallInt, хотя единица эта в образе будет представлена именно таким «объектом» SmallInt.

Эта маленькая хитрость позволяет значительно сократить объем потребляемой памяти, поскольку для записи числа используется только на 1 бит больше, чем его двоичное представление. Если же применять боксинг, то на каждое число помимо 4 байт указателя на объект, будет храниться еще 8 байт заголовка и еще 4 байта собственно данных. Не самый лучший вариант, как мне кажется.

Сообщения

Как уже было описано в предыдущей статье, сообщение — это объект-получатель, плюс селектор, плюс набор параметров. Важным отличием посылки сообщения от вызова функции является то, что до последнего момента неизвестно, кто реально будет обрабатывать сообщение. Известен только объект — получатель сообщения.

Отправка сообщения начинается с поиска в иерархии такого класса, который сумеет обработать сообщение. Поиск ведется от непосредственного класса объекта, вверх по иерархии, вплоть до Object. Надо сказать, что это довольно затратная операция, поскольку приходится делать большое количество обращений к памяти. Поэтому, результаты поиска кэшируются. Таким образом, полный поиск приходится делать только один раз. Кэши методов сбрасываются только в двух случаях — при очередной сборке мусора (объекты методов могли переместиться) и при добавлении/удалении очередного метода (это могло повлиять на иерархию). Даже с учетом регулярной очистки кэшей при сборке мусора, процент попаданий остается очень высоким (порядка 99%), так что временны́е затраты на поиск метода можно в среднем считать незначительными.

Давайте проследим, как происходит поиск в случае отправки объекту 'Hello world' (инстанция класса String) сообщения #isNil.

Поиск будет осуществляться следующим образом:

1. Сначала в кэше методов выполняется поиск записи по ключу hash(String, #isNil);
2. Если запись найдена, то возвращается сохраненное значение из кэша;
3. Если запись не найдена, то происходит поиск в иерахии класса String:
4. В текущем классе ищется поле methods, содержащее словарь (Dictionary) методов.
   Словарь представляет собой два параллельных массива: массив селекторов и массив методов;
   Массив селекторов отсортирован лексикографически;
5. В массиве селекторов дихотомией ищется селектор нашего сообщения;
6. Если селектор найден, то возвращается объект из массива методов, имеющий тот же индекс, что и найденный селектор; Также обновляется запись в кэше методов для ускорения последующего поиска;
7. Если селектор не найден, то переходим к родителю текущего класса:
8. Если родитель существует (указатель не равен nil), то переходим к пункту 4;
9. Если родителя нет, то поиск завершается с ошибкой.

В случае если метод так и не был найден в иерархии классов, виртуальная машина посылает объекту сообщение #doesNotUnderstand:, которое гарантировано будет обработано (как минимум в самом Object). В некоторых случаях классы намеренно перехватывают это сообщение для достижения особых целей. Например, так могут поступать прокси объекты, которые затем доставляют сообщение по действительному адресу.

Для вышеописанного сообщения String>>isNil цепочка поиска будет такой:
    String → Array → Collection → Magnitude → Object.

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

Контекст

С операцией посылки сообщения неразрывно связано понятие контекста.

В традиционных процессорных архитектурах, таких как x86, существует понятие стека вызовов. При вызове функции передаваемые параметры вместе с адресом возврата помещаются в стек, после чего выполняется переход на тело функции. При выходе из функции, соответственно, адрес возврата снимается с вершины стека. Получается, что для каждой функции на стеке лежит вся «иерархия» переходов от момента запуска треда до вызова текущей функции.

В Smalltalk все сделано иначе. Никакого единого стека вызовов нет. Вместо этого, при каждой посылке сообщения формируется объект контекста, который сохраняет информацию, имеющую отношение к данной конкретной посылке. Этот же объект используется виртуальной машиной при исполнении самого тела метода. Вот как он выглядит:

struct TContext : public TObject {
    TMethod*      method;
    TObjectArray* arguments;
    TObjectArray* temporaries;
    TObjectArray* stack;
    TInteger      bytePointer;
    TInteger      stackTop;
    TContext*     previousContext;
};

• method — сюда помещается указатель на найденный ранее объект метода, который будет обрабатывать данное сообщение.
• arguments — здесь хранится указатель на массв (инстанцию Array), куда сохраняются переданные аргументы.
• temporaries — хранилище временных переменных метода. В частности тех, что записываются между символами | | в заголовке метода.
• stack — стек значений. Используется только как промежуточное место для сохранения значений при выполнении данного конкретного метода. Никакие адреса возврата сюда не записываются. Забавный момент заключается в том, что размер стека становится известен еще на этапе компиляции метода. Поэтому под него отводится обычный массив.
• bytePointer — счетчик команд; аналог регистра IP в процессорах. По мере выполнения кода метода счетчик увеличивается. При совершении условных или безусловных переходов сюда записывается смещение следующей инструкции на которую следует перейти виртуальной машине.
• stackTop — индекс вершины стека значений.
• previousContext — а вот тут как раз хранится родительский контекст, из метода которого послали сообщение. При возврате значения из текущего метода оно будет положено на вершину родительского стека.

В каждый момент времени контекст располагает всей информацией, касательно текущего состояния выполнения метода. Это дает возможность легко прервать выполнение метода (например при истечении количества тиков, отведенных для него), а затем позднее вернуться обратно. Есть еще экзотические варианты использования, включающие, например, реализацию продолжений (continuation).

Методы

Методы представлены объектами следующего вида:

struct TMethod : public TObject {
    TSymbol*      name;
    TByteObject*  byteCodes;
    TSymbolArray* literals;
    TInteger      stackSize;
    TInteger      temporarySize;
    TClass*       klass;
    TString*      text;
    TObject*      package;
};

• name — собственно имя метода, а точнее указатель на символ этого имени.
• byteCodes — здесь лежит указатель на объект ByteArray, содержащий байт-коды метода.
• literals — при компиляции метода сюда попадают литеральные объекты. К ним относятся: числовые константы, имена классов, селекторы сообщений. Поскольку эта информация не меняется от вызова к вызову, она сохраняется в самом объекте метода.
• stackSize — здесь записан размер стека значений (см. выше TContext::stack), который необходимо создать при посылке сообщения.
• temporarySize — размер массива, хранящего временные переменные метода. Тоже относится к создаваемому объекту контекста.
• klass — ссылка на класс, которому принадлежит данный метод.
• text — исходный текст данного метода.
• package — категория данного метода. Предназначена для фильтрации списков отображаемых методов в пользовательском интерфейсе. В настоящее время не используется.

Объекты методов формируются при компиляции первичного образа из исходника imageSource.st утилитой ImageBuilder, а затем сохраняются в получаемый файл образа. Также одноразовый метод создается при выполнении команды из командной строки. По сути, текст командной строки интерпретируется как тело метода, который затем компилируется и вызывается обычным образом.

Это делается так. В теле метода Undefined>>main есть код:

[ command <- String readline: '->'. command notNil ]
    whileTrue: [ command isEmpty ifFalse: [ command doIt printNl ] ]

Сначала с помощью библиотеки readline мы получаем строку команды. Затем объекту строки посылается сообщение #doIt, результат которого выводится на экран. Сам метод #doIt выглядит следующим образом:

doIt | method |
	method <- Undefined parseMethod: 'doItCommand ^ ' + self.
	^ method notNil
		ifTrue: [ ^ Context new
			  perform: method withArguments: (Array new: 1) ]

Вся магия творится в методе Undefined>>parseMethod: который по исходному тексту формирует объект метода #doItCommand с помощью компилятора, реализованного здесь же, в тексте образа. Получается, что Smalltalk компилирует свои собственные методы посредством компилятора, написанного на самом Smalltalk и являющимся неотъемлемой частью образа. Я нахожу этот момент довольно забавным.

После того как объект метода был создан, для его вызова формируется объект контекста, с помощью которого выполняется созданный метод. Поскольку новый метод не добавлялся в списки методов ни одного из классов, он будет существовать только на момент своего исполнения (ну и до следующей сборки мусора).

Инструкции виртуальной машины

Виртуальная машина умеет выполнять инструкции только в рамках методов. Вне методов кода не существует. Инструкции хранятся в поле byteCodes, принадлежащему инстанции класса Method. Сама инстанция помимо этого содержит дополнительную информацию, которая в том числе используется при инициализации объекта контекста (см. выше).

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

Инструкции работы со стеком значений

Существует четые push инструкции, проталкивающие на вершину стека значений один из объектов. Вместе с кодом инструкции указывается также целочисленный параметр, который интерпретируется как индекс для выборки объекта из соответствующей структуры данных:

• pushArgument — аргумент из массива аргументов текущего контекста.
• pushInstance — поле текущего объекта.
• pushTemporary — временная переменная из массива переменных текущего контекста.
• pushLiteral — литерал из константного массива литералов данного метода.

Есть еще две специальных push инструкции, которые работают немного иначе:

• pushConstant — в зависимости от параметра кладет на вершину стека одну из констант: SmallInt значение, соответствующее числам 0-9, а также константные объекты nil, true и false, являющиеся инстанциями Undefined, True и False соответственно.
• pushBlock — используется виртуальной машиной для создания и инициализации объекта Block, связанного с участком байт-кодов метода, которые относятся к данному блоку. После этой инструкции указатель bytePointer смещается на размер кода блока.

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

• assignInstance — присваивает полю текущего объекта значение, лежащее на вершине стека.
• assignTemporary — присваивает временной переменной значение, лежащее на вершине стека.

Поскольку и аргументы и литералы в рамках вызова метода считаются константами, операций присвоения для них не существует. Для снятия значения со стека предусмотрена отдельная операция (popTop), которая будет рассмотрена ниже.

Инструкции перехода

Имеются, конечно же, и инструкции переходов:

• branchIfTrue — устанавливает bytePointer в указанное параметром значение, если на стеке лежит true.
• branchIfFalse — то же, но только если на стеке лежит false.
• branch — безусловный переход на указанное смещение.

Инструкции посылки сообщения

Хотя процедура посылки сообщения универсальна и может применяться везде, в некоторых случаях используются специализированные ее реализации для ускорения обработки. Такими особыми случаями являются операции посылки унарного и бинарного сообщений. Для них предусмотрены отдельные инструкции sendUnary и sendBinary. Обычное сообщение посылается инструкцией sendMessage.

При посылке сообщения аргументы помещаются в стек, после чего вызывается инструкция markArguments N. Она снимает со стека N значений и формирует из них объект Array. Далее, указатель на этот объект возвращается на вершину стека, который будет использован при инициализации поля arguments у создаваемого объекта контекста.

Инструкции возврата

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

Помимо возврата произвольного значения в Smalltalk очень частно бывает необходимо вернуть self в качестве результата. Поэтому для такой операции предусмотрена отдельная инструкция selfReturn.

Последней из инструкций возврата является blockReturn, объяснить которую на пальцах довольно сложно. Основная идея заключается в том, что управление передается не в порождающий контекст, а гораздо выше, в родительский контекст метода, содержащего объявление выполняющегося в данный момент блока. Подобное поведение можно сравнить с механизмом выброса исключения в других языках. Только в отличие от исключений, которые происходят только в особых ситуациях программы и в общем случае не относятся к «нормальному» ходу выполнения программы, blockReturn является вполне штатной операцией с точки зрения виртуальной машины и может использоваться в общем коде.

Проще всего это показать на примере. Это текст метода Collection>>at:ifAbsent:

at: value ifAbsent: exceptionBlock
	self do: [ :element | element = value ifTrue: [ ^element ] ].
	^exceptionBlock value

Выражение ^element, стоящее в самом вложенном блоке, будет скомпилировано с использованием инструкции blockReturn. Это необходимо потому, что реально, блок будет выполняться не в текущем методе, а гораздо глубже. Метод Collection>>at:ifAbsent: вызывает метод Collection>>do:, передавая внешний блок в качестве параметра. Метод Collection>>do: в свою очередь будет вызывать Block>>value: для каждого элемента коллекции, передавая его в качестве параметра блоку. И только внутри Block>>value: располагается примитив номер 8, который уже приведет к выполнению кода блока. Поэтому, кода блок решит, что необходимо выполнить возврат значения element, он сделает это с ипользованием инструкции blockReturn, которая передаст управление на самый верх, за пределы Collection>>at:ifAbsent:, вернув необходимое значение в качестве результата сообщения.

Стоит отметить, что не каждый оператор ^, стоящий в теле блока, будет преобразован в инструкцию blockReturn. Компилятор по возможности старается разложить код на более простые инструкции: блоки внедрить в тело выполняющегося метода и заменить вызов блоков простыми переходами по инструкциям. В этом случае blockReturn также будет заменен на stackReturn или selfReturn.

Специальные инструкции

Помимо вышеперечисленных инструкций есть еще некоторое количество вспомогательных. К таким можно отнести инструкции popTop и dup. Первая просто снимает значение с вершины стека, которое было туда положено ранее с помощью одной из push инструкций (либо самой виртуальной машиной, как результат посылки сообщения). Обычно popTop используется после инструкций assignInstance или assignTemporary, для удаления более не нужного значения со стека.

Инструкция dup, как можно догадаться из названия, дублирует значение на стеке, размещая рядом точно такое же. Эта инструкция используется компилятором Smalltalk при разборе сложных выражений с условиями.

Исполнение метода

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

Исполнение метода и работу JIT компилятора мы проследим на базе уже знакомого нам по прошлой статье метода сортировки коллекции:

->Collection viewMethod: #sort:
sort: criteria | left right mediane |
    (self size < 32) 
        ifTrue: [ ^ self insertSort: criteria ].

    mediane <- self popFirst.
    
    left  <- List new.
    right <- List new.
    self do: [ :x |
        (criteria value: x value: mediane)
            ifTrue:  [ left  add: x ]
            ifFalse: [ right add: x ] ].

    left  <- left  sort: criteria.
    right <- right sort: criteria.

    right add: mediane.
    ^ left appendList: right

Результатом компиляции такого метода является целая простыня инструкций. Детальное разъяснение логики работы все же выходит за рамки этой статьи, поэтому попробуйте просто просмотреть байт коды и понять, какие части чему соответствуют. На самом деле это не так сложно. В отличие от традиционного ассемблера, здесь инструкции используются довольно однообразно и последовательно. Сперва идет заполнение стека значений аргументами будущего вызова; затем, с помощью markArguments из них формируется массив аргументов, который уже используется в той или иной операции посылки сообщения. Ну а инструкции перехода управляют всем этим безобразием. Для удобства чтения, я отбил пустыми строками блоки инструкций, относящиеся к одной посылке и снабдил их комментариями:

->Collection methods at: #sort:; disassemble
"проверка условия размера"
0000 PushArgument 0              "нулевой аргумент это всегда self"
0001 MarkArguments 1
0002 SendMessage size
0003 PushLiteral 1               "по индексу 1 в массиве литералов этого метода лежит число 32"
0004 SendBinary <                "выполняем сравнение"
0005 DoSpecial branchIfFalse 16  "переходим в зависимости от результата сравнения"

"если условие выполнено:"
0008 PushArgument 0
0009 PushArgument 1
0010 MarkArguments 2
0011 SendMessage insertSort:
0012 DoSpecial stackReturn
0013 DoSpecial branch 17

"если условие не выполнено:"
0016 PushConstant nil           "баланс стека"
0017 DoSpecial popTop

"mediane <- self popFirst"
0018 PushArgument 0
0019 MarkArguments 1
0020 SendMessage popFirst
0021 AssignTemporary 2
0022 DoSpecial popTop

"left <- List new"
0023 PushLiteral 4
0024 MarkArguments 1
0025 SendMessage new
0026 AssignTemporary 0
0027 DoSpecial popTop

"right <- List new"
0028 PushLiteral 6
0029 MarkArguments 1
0030 SendMessage new
0031 AssignTemporary 1
0032 DoSpecial popTop

"self do: ..."
0033 PushArgument 0
0034 PushBlock "тело блока"
0037     PushArgument 1             "criteria"
0038     PushTemporary 3            "x"
0039     PushTemporary 2            "mediane"
0040     MarkArguments 3
0041     SendMessage value:value:   "основное условие сортировки"
0042     DoSpecial branchIfFalse 52

"left add: x"
0045     PushTemporary 0
0046     PushTemporary 3
0047     MarkArguments 2
0048     SendMessage add:
0049     DoSpecial branch 56

"right add: x"
0052     PushTemporary 1
0053     PushTemporary 3
0054     MarkArguments 2
0055     SendMessage add:

0056     DoSpecial stackReturn
0057 MarkArguments 2
0058 SendMessage do:
0059 DoSpecial popTop

"рекурсивная сортировка left"
0060 PushTemporary 0
0061 PushArgument 1
0062 MarkArguments 2
0063 SendMessage sort:
0064 AssignTemporary 0
0065 DoSpecial popTop

"рекурсивная сортировка right"
0066 PushTemporary 1
0067 PushArgument 1
0068 MarkArguments 2
0069 SendMessage sort:
0070 AssignTemporary 1
0071 DoSpecial popTop

"right add: mediane"
0072 PushTemporary 1
0073 PushTemporary 2
0074 MarkArguments 2
0075 SendMessage add:
0076 DoSpecial popTop

"конкатенация отсортированных частей"
0077 PushTemporary 0
0078 PushTemporary 1
0079 MarkArguments 2
0080 SendMessage appendList:

"возврат результата"
0081 DoSpecial stackReturn

"(заглушка компилятора)"
0082 DoSpecial popTop
0083 DoSpecial selfReturn

Заключение

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

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

В следующей статье (которая уже написана и скоро будет опубликована) рассматриваются вопросы JIT компиляции Smalltalk методов в промежуточный IR код, понятный LLVM. В свою очередь, он будет компилироваться уже в реальные инструкции процессора. Мы проанализируем байт-коды метода и попытаемся понять, что нужно сделать, чтобы транслировать их в IR оптимальным образом.

Напоследок, небольшой опрос:

Автор: Halt

Источник