Cheney on the M.T.A.: компилятор, в котором стек служит заодно и кучей

Did he ever return? No, he never returned,
And his fate is still unlearned,
He may ride forever ‘neath the streets of Boston,
He’s the man who never returned.

“Charlie on the M.T.A.”, 1949

1. Замыкания

Одна из удобных возможностей современных языков программирования – вложенные функции:

def bubble(arr, comp):

    def swap(i, j):
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp

    flag = True
    while flag:
        flag = False
        for i in range(len(arr) - 1):
            if comp(arr[i], arr[i+1]) > 0:
                swap(i, i+1)
                flag = True

Сама эта возможность не нова: она была уже в Алголе (1958) и многим знакома из Паскаля (1970). В компиляции вложенных функций нет ничего сложного: например, в стековом кадре внутренней функции может храниться указатель на стековый кадр внешней функции, чтобы внутренняя функция могла обращаться к параметрам и локальным переменным внешней. Кто-то может вспомнить, что инструкции enter и leave, появившиеся в 80186 (1982), реализуют именно такую поддержку вложенных функций (хотя я не встречал ни один компилятор, который бы её задействовал).

Сложности начинаются, если язык позволяет передать внутреннюю функцию наружу внешней:

def by_field(name):

    def comp(x, y):
        return x[name] – y[name]

    return comp

bubble(my_records, by_field("year"))

Как внутренняя функция сможет обращаться к параметрам и локальным переменным внешней после того, как возврат из внешней функции уничтожил её стековый кадр? Каким-то образом внутренняя функция должна «захватить» используемые переменные вместе с собой; функция вместе с захваченными извне переменными называется «замыканием». Паскаль такое уже не поддерживает; но например в C# 7 (2017) для этого создаётся объект на куче, содержащий все те параметры и локальные переменные, к которым обращается внутренняя функция; и обращения как из неё, так и из внешней функции идут не к значениям на стеке, а к полям объекта на куче. А можно ли обойтись без такого усложнения, и продолжать работать со стеком – чтобы избежать лишней косвенной адресации и сохранить локальность обращений, а не засорять кэш данных скачками по куче?

2. Continuation Passing

При компиляции функциональных языков программирования, где захват локальных переменных возвращаемой функцией – очень часто используемый приём, на первом этапе вся программа переводится в “Continuation-passing style” (CPS) – т.е. возвраты из функций заменяются на явный вызов callback-а, передаваемого в каждую функцию дополнительным аргументом. Например, в этой простой функции, вычисляющей произведение всех простых чисел от 1 до n включительно:

def prodprimes(n):
    if n == 1:
        return 1
    elif isprime(n):
        return n * prodprimes(n-1)
    else:
        return prodprimes(n-1)

– двум вызовам prodprimes неявно передаются разные адреса возврата. Если эти адреса обозначить как j и h, и передавать адрес возврата как явный аргумент c, то всю передачу управления можно сделать явной:

def prodprimes(n, c):
    if n == 1:
        c(1)
    else:
        def k(b):
            if b:
                def j(p):
                    c(n * p)
                prodprimes(n-1, j)
            else:
                def h(q):
                    c(q)
                prodprimes(n-1, h)
        isprime(n, k)

В CPS нет разницы между вызовом функции и возвратом значения из функции – и то и другое абстрагируется как «передать значение по указанному адресу». Этот приём применяется в большинстве компиляторов Scheme, начиная с самого первого (1975); ему посвящена целая книга “Compiling with Continuations” (1992), откуда и взят приведённый выше пример. Не так давно похожий стиль программирования стал популярен под названием “promises”.

Причина, по которой CPS использовался внутри компиляторов в качестве промежуточного представления до того, как SSA (изобретённая в 1988) стала более популярной – простота: это не ещё один язык со своими правилами, а подъязык исходного ЯП с тем ограничением, что вызов функции или продолжения допускается только как последний оператор функции или продолжения. Код на ЯП легко переводить в CPS набором формальных преобразований, и к коду в CPS легко применять упрощающие преобразования – например, обнаружить, что продолжение h тривиально, и заменить использование h на c. Важная для нас особенность CPS состоит в том, что замыкания используются в том же scope, в котором были объявлены, и поэтому могут обращаться к захваченным извне переменным так же, как в 80186 – через указатели на внешние стековые кадры:

def by_field(name, c):

    def comp(x, y, c):
        c(x[name] – y[name])

    c(comp)

def by_year(comp):
    bubble(my_records, comp, halt)

by_field("year", by_year)

После преобразования в CPS comp знает, что сама она – функция вложенности 2, а значение name лежит в кадре вложенности 1, так что компиляция обращения к name не вызовет затруднений.

Но есть у CPS и недостаток: поскольку продолжения никогда не выполняют return, то их стековые кадры никогда не уничтожаются, и стек очень быстро переполнится. С другой стороны, продолжению может понадобиться некий стековый кадр либо если оно само к нему обращается, либо если оно получает параметром продолжение, которое обращается к этому кадру. Кроме того, переход к следующему продолжению обязан быть последним действием внутри продолжения, так что результатом выполнения продолжения можно считать адрес и параметры следующего продолжения. (В модели “promises” этот результат возвращается явно.) В классических компиляторах Scheme использовался диспетчер в виде следующего бесконечного цикла:

1. Выполнить текущее продолжение и получить в качестве результата адрес и параметры следующего продолжения;
2. Проверить, к каким стековым кадрам могут обращаться следующее продолжение и продолжения, переданные ему параметрами;
3. Удалить из стека те кадры, обращение к которым невозможно.

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

Как легко догадаться, с проверкой стека при каждом переходе между продолжениями, производительность программы оставляла желать лучшего. Одна из возможных оптимизаций – перед выходом из продолжения проверять текущий размер стека, и если он не превышает заданного порога, то переходить к следующему продолжению напрямую; иначе – передавать управление диспетчеру, чтобы он собрал со стека весь мусор. Выпускник бостонского MIT Генри Бейкер прокомментировал этот подход так: «вместо того, чтобы всё время подпрыгивать на батуте, мы спрыгиваем с Эмпайр-стейт-билдинга – но намного реже».

3. На M.T.A.

В 1948 бостонское метро (Metropolitan Transit Authority) подняло плату за проезд с 10 до 15 центов. Вместо того, чтобы заменять все турникеты, рассчитанные на десятицентовые монетки, на входе в метро – кондукторам поручили взымать доплату в пять центов при выходе из поезда. Высмеивая такой подход, кандидат в мэры Бостона заказал запись песни про некого Чарли, которому не хватило пятака заплатить за выход, и он был обречён кататься в метро бесконечно. Кандидат заработал репутацию коммуниста, набрал на выборах всего 1.2% голосов, и навсегда ушёл из политики; но песня про пассажира, который никогда не вернётся на поверхность земли, оказалась намного более популярной: даже введённая в 2006 карточка для проезда в бостонском метро называется CharlieCard в честь того самого пассажира.

История Чарли вдохновила Генри Бейкера на написание в 1994 компилятора Scheme, превращающего каждое продолжение в функцию Си так, что выполнение этих функций никогда не доходит до return: например,

(define (revappend old new)
  (if (null? old)
      new
      (revappend (cdr old) (cons (car old) new))))

– превращается в

void revappend(clos_type *cont, cons_type *old, cons_type *new) {
  if (old == NIL) {
    /* Call continuation with new as result. */
    return (cont->fn)(cont->env, new);
  }
  cons_type newer; /* Should check stack here. */
  /* Code for (revappend (cdr old) (cons (car old) new)). */
  newer.tag = cons_tag; newer.car = old->car; newer.cdr = new;
  return revappend(cont, old->cdr, &newer);
}

Смысл оператора return после такого преобразования – сообщить компилятору Си, что нет надобности сохранять регистры перед вызовом продолжения; на самом же деле функция, вызываемая как операнд return, никогда не вернёт управление. В месте, помеченном как /* Should check stack here. */, вставляется проверка размера стека, и при необходимости – вызывается диспетчер для сборки мусора.

Такой подход имеет ряд преимуществ перед классическим:

1. В качестве бэкенда для компилятора Scheme можно использовать компилятор Си: переходы между продолжениями реализуются как обычные вызовы функций Си; передаваемые параметры – как обычные параметры функций Си, в т.ч. переменного количества (varargs); динамически создаваемые данные – как обычные локальные переменные в функциях Си, в т.ч. локальные массивы динамической длины (VLA). В 21 в. в качестве бэкенда может использоваться и LLVM, во всех перечисленных аспектах эквивалентный Си.
2. Использование стандартного сишного ABI для переходов между продолжениями даёт возможность совместного использования кода на разных языках – например, использование стандартной библиотеки Си в программе на Scheme. Когда «неродным» функциям не нужен доступ к внешним стековым кадрам, то их вызовы не надо преобразовывать в CPS, и они вернут управление вызвавшему продолжению. Если же «неродная» функция принимает callback-ом «родное» продолжение, то это продолжение заведомо не вернёт управление вызвавшему его коду, а значит, все «неродные» кадры на стеке – мусор, который будет собран при первой возможности. Это позволяет реализовать на Си стандартные функции Scheme, такие как map и fold, и не беспокоиться об освобождении памяти, занимаемой локальными переменными в реализации этих функций.

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

4. Сборщик мусора Чейни

Самый первый и самый простой сборщик мусора был реализован в 1969 для LISP: когда наполнялась одна половина кучи, то программа останавливалась, и все «живые» данные рекурсивно (обходом в глубину) переносились во вторую половину кучи. В 1970 Крис Чейни – тоже в Кембридже, но по другую сторону океана от MIT – заметил, что если обходить живые данные в ширину, то самому сборщику не потребуется дополнительная память на время сборки; с тех пор сборку мусора с остановкой программы и переносом живых объектов во вторую половину кучи называют «алгоритмом Чейни». Главный его недостаток – что живые данные могут занимать лишь половину доступной памяти, а вторую половину занимает «буфер для копирования».

Эффективность сборки мусора можно повысить, если заметить, что данные в типичной программе делятся на «очень короткоживущие» и «очень долгоживущие»: если объект пережил одну сборку мусора, он с большой вероятностью переживёт и следующую сборку тоже. Поэтому кучу делят на «питомник» для свежесозданных объектов, и «взрослую кучу» из двух половин. Когда переполняется питомник, живые данные из него переносятся во взрослую кучу; когда переполняется одна половина взрослой кучи, живые данные из неё переносятся во вторую половину. Таким образом экономится и память (для короткоживущих данных не резервируется место во второй половине кучи), и время сборки (долгоживущие данные не копируются взад-вперёд при каждой сборке мусора в питомнике).

При использовании “Cheney on the M.T.A.” в роли питомника выступает стек. Диспетчер, вызываемый при переполнении стека, явным образом получает параметрами указатели на все живые данные: это все параметры и локальные переменные вызывающего продолжения, включая захваченные переменные, переданные продолжению неявным параметром. В отличие от привычных сборщиков мусора, “Cheney on the M.T.A.” нет нужды выискивать живые данные внутри стека: CPS обеспечивает, что все данные ниже последнего стекового кадра – мертвы, если из последнего кадра они недоступны. Это значит, что для сборщика мусора не важны ни устройство стековых кадров, ни возможное наличие в стеке «чужеродных» кадров, оставшихся от функций на других языках.

Подход “Cheney on the M.T.A.” используется в компиляторах Scheme в Си “Chicken Scheme” (2000) и “Cyclone Scheme” (2016). В Cyclone к давней идее Бейкера добавили поддержку параллельного сбора мусора, когда на время сбора останавливается только один поток, чей стек обрабатывается, – а остальные продолжают работать.

Автор: ruvds

Источник