Ленивое вычисление с запоминанием: очередь банкира

Если ты знаешь, как ленивое вычисление с запоминанием спасает амортизацию при персистентности, что такое учёт долгом и как устроена очередь банкира, листай до «Теперь сам».

Как думаешь, что поможет

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

Ответь себе до чтения. Ответ звучит как противоречие: один объект всё-таки меняется - обещание, которое запоминает свой результат. Но снаружи этого не видно: до вычисления и после оно означает одно и то же.

На что это похоже

Общий заказ в столовой на весь отдел. Кто-то сделал заказ - появилось «обещание обеда». Первый проголодавшийся идёт и забирает его; когда приходят остальные, обед уже на столе, и второй раз его не готовят. А оплачивают заказ вскладчину, по чуть-чуть, заранее - и повар не начнёт готовить, пока заказ не оплачен. Если двое заплатили за один и тот же обед, страшного ничего: переплата, а не долг.

Механизм: обещание, запоминание и долг

Обещание (suspension, thunk) - объект «вычислить X, когда понадобится». У него два состояния: «ещё не вычислено» (хранит, что вычислять) и «готово» (хранит результат). Вычисляют его при первом обращении; это вызов по необходимости - ленивое вычисление с запоминанием. Без запоминания (вызов по имени) каждое обращение вычисляет заново, и персистентность снова повторяет работу.

Очередь банкира (Окасаки, «Чисто функциональные структуры данных», 6.3.2). Версия - перед (ленивый список), его длина, зад (стек) и его длина. Инвариант: зад не длиннее переда. Вставка кладёт в зад; если зад стал длиннее переда, перед заменяется обещанием перед ++ перевернуть(зад), зад становится пустым. Обещание двухэтажное. Склейка ++ постепенная: вычислить её - значит выдать первый элемент старого переда и новое обещание «остаток переда ++ перевёрнутый зад», это O(1). А переворот зада монолитный: он случается целиком, но только когда старый перед уже выбран до конца.

Учёт долгом. Создание обещания с переворотом зада длины m - это долг m. Каждая операция гасит константу долга. Правило: вычислять обещание можно, только когда его долг погашен, - речь о монолитном перевороте; шаги склейки постепенные, каждый стоит O(1) и оплачивается своей операцией. Переворот понадобится не раньше, чем будет выбран весь старый перед, а в нём при создании обещания m − 1 элемент: эти извлечения и само извлечение, которому понадобится переворот, гасят долг m. Если к версии вернулись и обещание понадобилось второй раз, его результат уже запомнен; а если ветка пересоздала обещание, она сама повторит и операции, которые за него платят. Окасаки доказывает: каждая операция - O(1) амортизированно при любом персистентном использовании.

Правило

Ленивое вычисление с запоминанием: дорогую работу откладывают обещанием, вычисляют при первой нужде и запоминают. Учёт - долгом: обещание создаёт долг, операции его гасят, вычислять можно только оплаченное. Повторный доступ к версии находит готовый результат, поэтому амортизированная оценка переживает персистентность. Очередь банкира: зад длиннее переда - перед становится обещанием «перед ++ перевёрнутый зад»; все операции O(1) амортизированно.

Разбор: та же атака на очередь банкира

Модель: перед - цепочка узлов-обещаний ["готово", голова, хвост], ["пусто", 0, 0] или ["склейка", перед, зад]. Узел общий для всех версий, которые на него ссылаются, поэтому запомненный результат увидят все. Работа - созданные узлы: вставки в зад, шаги склейки и узлы переворота. Повторяем атаку прошлого урока и сравниваем с запоминанием и без.

# очередь банкира Окасаки. Перед - ленивый список из узлов-обещаний:
# ["готово", голова, хвост], ["пусто", 0, 0], ["склейка", перед, зад] -
# обещание «перед ++ перевёрнутый зад». Склейка вычисляется по одному
# элементу; зад переворачивается, только когда перед кончился
znach = []
dalshe = []
rabota = [0]

def polozhit(verh, x):
    znach.append(x)
    dalshe.append(verh)
    rabota[0] = rabota[0] + 1
    return len(znach) - 1

def vychislit(u, zapominat):
    # вернуть узел «готово» или «пусто»
    if u[0] != "склейка":
        return u
    pered = vychislit(u[1], zapominat)
    if pered[0] == "готово":           # шаг склейки: O(1)
        rabota[0] = rabota[0] + 1
        rez = ["готово", pered[1], ["склейка", pered[2], u[2]]]
    else:                              # перед кончился: перевернуть зад
        rez = ["пусто", 0, 0]
        r = u[2]
        while r != -1:
            rabota[0] = rabota[0] + 1
            rez = ["готово", znach[r], rez]
            r = dalshe[r]
    if zapominat:                      # общий объект: результат
        for i in range(3):             # увидят все версии
            u[i] = rez[i]
    return rez

def proverit(pered, dl_p, zad, dl_z):
    if dl_z <= dl_p:
        return [pered, dl_p, zad, dl_z]
    return [["склейка", pered, zad], dl_p + dl_z, -1, 0]

def v_konec(q, x):
    return proverit(q[0], q[1], polozhit(q[2], x), q[3] + 1)

def bez_pervogo(q, zapominat):
    yachejka = vychislit(q[0], zapominat)
    return proverit(yachejka[2], q[1] - 1, q[2], q[3])

def postroit(n):
    q = [["пусто", 0, 0], 0, -1, 0]
    for x in range(n):
        q = v_konec(q, x)
    return q

for zapominat in [True, False]:
    q = postroit(100)
    rabota[0] = 0
    for i in range(100):                 # 100 раз от одной версии q
        v = bez_pervogo(q, zapominat)
    odna = rabota[0]
    rabota[0] = 0
    for vetka in range(10):              # 10 веток, каждая - до конца
        v = q
        for i in range(100):
            v = bez_pervogo(v, zapominat)
    print("запоминание:", zapominat, "- 100 раз от q:", odna,
          "| 10 веток до конца:", rabota[0])

p = postroit(126)
print("версия p: перед", p[1], "зад", p[3],
      "- следующая вставка создаст обещание")
for dlina in [1, 127]:
    rabota[0] = 0
    operacij = 0
    for vetka in range(10):              # каждая ветка - заново от p
        v = v_konec(p, 1000 + vetka)
        operacij = operacij + 1
        for i in range(dlina):
            v = bez_pervogo(v, True)
            operacij = operacij + 1
    print("10 веток по", dlina, "извлечений: операций", operacij,
          "работа", rabota[0], "на операцию",
          round(rabota[0] / operacij, 2))

запоминание: True - 100 раз от q: 6 | 10 веток до конца: 844
запоминание: False - 100 раз от q: 600 | 10 веток до конца: 1930
версия p: перед 63 зад 63 - следующая вставка создаст обещание
10 веток по 1 извлечений: операций 20 работа 26 на операцию 1.3
10 веток по 127 извлечений: операций 1280 работа 1394 на операцию 1.09

Сто извлечений из одной версии q: с запоминанием - 6. При построении q очередь создала обещание шесть раз (когда зад перерастал перед: на длинах 1, 3, 7, 15, 31, 63), и они вложены друг в друга; первое извлечение делает по шагу склейки на каждом уровне, остальные 99 находят готовое. Без запоминания каждое извлечение повторяет эти 6 шагов - 600. Очередь из прошлого урока на той же атаке тратила 9900. Десять веток, каждая выбирает очередь до конца: 844 против 1930 - запомненные обещания делятся между ветками.

Разбор: ветка прямо перед переворотом

Где у запоминания граница? Возьмём версию p, в которой перед и зад по 63 элемента: следующая вставка создаст новое обещание. Каждая из десяти веток вставляет свой элемент - и получает СВОЁ обещание: запомненного результата у соседей нет.

Короткие ветки, вставка и одно извлечение, - 26 единиц работы на 20 операций: извлечению нужен только первый элемент склейки, а переворот зада ещё не нужен. Длинные ветки по 127 извлечений доходят до переворота, и каждая делает свой - но каждая повторила и 127 извлечений, которые за него платят: 1,09 на операцию. Граница правила «запоминание убирает повторы»: оно убирает повторы одной и той же отложенной работы; если ветки создают разную работу, каждая платит за свою - и это честная цена, а не потеря амортизации. Работает это только потому, что склейка постепенная: если бы обещание вычислялось целиком при первом извлечении, короткая ветка платила бы весь переворот за две операции.

Что ломается без этого

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

Энергичный переворот «заранее». Перевернуть зад сразу при создании версии - значит выполнить работу в каждой ветке, даже той, что никогда не дойдёт до извлечения.

Обещание, изменяемое после вычисления. Запоминание допустимо, потому что результат - неизменяемая структура; если его потом поправить, правка всплывёт во всех версиях.

Зачем это в работе

Ленивые структуры Haskell (там любое выражение - обещание с запоминанием) и ленивые последовательности Clojure и Scala опираются ровно на это. А если нужна оценка в худшем случае - для систем реального времени, - Окасаки (глава 7) вычисляет обещание по кусочку на каждой операции по заранее составленному расписанию: очередь реального времени делает O(1) в худшем случае. Тот же приём - размазать большую работу по многим мелким шагам - стоит за постепенным перехешированием в Redis и за сборщиками мусора, которые не останавливают программу надолго.

Теперь сам

1. В очереди банкира перед - 7 элементов, зад - 7. Что сделает следующая вставка?
2. Почему без запоминания ленивая очередь снова теряет амортизацию при персистентности?
3. Чем учёт долгом отличается от учёта кредитом, если к версии вернулись дважды?