Crafting Interpreters

• https://craftinginterpreters.com/contents.html
• https://github.com/munificent/craftinginterpreters
• Стили IR
  • CFG
  • SSA
  • CPS
  • Three address code
• Ruby перешел от MRI (tree walking interpreter) в YARV (bytecode interpreter) только в 1.8.
• Expression produces a value, statement produces an effect.
• Semantics = effects on the abstract machine.
• Closures
  • Look up "closure conversion" and "lambda lifting" – ways to optimise closures.
  • Замыкания часто связаны со сборкой мусора потому что несколько замыканий могут использовать одну и ту же функцию, но они не владеют ей. Нельзя деаллоцировать функцию когда мы деаллоцируем замыкание.
  • Каждый объект ObjClosure хранит указатель на функцию и массив upvalues.
    • Open upvalue указывает на переменную которая все еще на стеке.
    • Closed upvalue указывает на переменную, которая переехала со стека на хип.
    • Когда функция завершается и локальная переменная выходит из scope, ее upvalue можно закрыть. OP_POP меняется на OP_CLOSE_UPVALUE.
• Сборка мусора
  • Существуют roots – значения, до которых можно добраться напрямую – объекты на стеке и глобальные переменные (хеш-таблица). Также нужно обойти call stack потому что он хранит указатели на замыкания. Также список открытых upvalues нужных для замыканий.
  • Mark-sweep
    • Изобрал John McCarthy для LISP.
    • Mark: начиная с каждого root сделать graph traverse и пометить пройденное.
    • Sweep: удалить все непомеченное.
    • Простейший способ – запускать сборку сразу перед любой аллокацией.
    • Tri-color abstraction
    • Throughput – время потраченное исключительно на саму программу (а не на GC).
    • Latency – самый долгий непрерывный кусок времени потраченный на GC.
    • Хотим максимизировать throughput, минимизировать latency.
    • Держать bytesAllocated и nextGC, запускать когда bytesAllocated > nextGC, потом увеличивать nextGC.
    • Между push и pop может произойти GC, поэтому даже временные объекты нужно добавлять в стек, в случае GC который использует только стек значений и стек вызовов, но не C стек. Некоторые GC также используют C стек, такие как Boehm-Demers-Wieser.
    • Generational GC
      • Два участка: nursery (GC зовется часто) и tenured (GC зовется редко). Новые объекты попадают в nursery. GC вызывается часто для nursery. Для каждого выжившего объекта увеличивается tenure, после определенного заранее значения они попадают в tenured.
• Chapter 30: Optimization
  • NaN Boxing – способ запихнуть VM value занимающее 16 байтов в естественной имплементации в 8 байтов (double).
    • IEEE 754: на 64-битной машине число представлено в виде 1 бита знака, 11 бит экспоненты, 52 бита мантиссы.
    • Если все 11 битов экспоненты включены, то это NaN.
    • Раньше: struct из enum и union (bool, double, pointer).

#include <stdbool.h> #include <stdio.h>

enum Type { null, boolean, number, object };

struct Object {};

struct Value { enum Type type; union { bool boolean; double number; struct Object* obj; } as; };

int main() { struct Value value; printf("%d", sizeof(value)); // 16 bytes return 0; }```