Дисковое кеширование деревьев ленивых вычислений

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


По разумению автора настоящего текста нормальный ленификатор должен:


  1. Сохранять вычисления между вызовами программы.
  2. Отслеживать изменения в дереве вычисления.
  3. Иметь в меру прозрачный синтаксис.

Ленивое Дерево


Концепция


По порядку:


  1. Сохранять вычисления между вызовами программы:
    Действительно, если мы вызываем один и тот же скрипт несколько десятков-сотен раз в день, зачем пересчитывать одно и тоже при каждом вызове скрипта, если можно хранить объект-результат в файле. Лучше подтянуть объект с диска, но… мы должны быть уверены в его актуальности. Вдруг скрипт переписан и сохраненный объект устарел. Исходя из этого, мы не можем просто взять и по факту наличия файла подгрузить объект. Отсюда вытекает второй пункт.
  2. Отслеживать изменения в дереве вычисления:
    Необходимость обновления объекта должна вычисляться на основе данных об аргументах генерирующей его функции. Так мы будем уверены что подгружаемый объект валиден. Действительно, для чистой функции возвращаемое значение зависит только от аргументов. Значит, пока мы кэшируем результаты чистых функций и следим за изменением аргументов, мы можем быть спокойны за актуальность кэша. При этом, если вычисляемый объект зависит от другого закэшированного(ленивого) объекта, который в свою очередь зависит от еще одного, нужно корректно отрабатывать изменения в этих объектах, своевременно обновляя переставшие быть актуальными узлы цепочки. С другой же стороны, неплохо бы учесть, что нам не всегда требуется подгружать данные всей цепочки вычисления. Часто достаточно загрузки только финального объекта-результата.
  3. Иметь в меру прозрачный синтаксис:
    Этот пункт понятен. Если для того, чтобы переписать скрипт на ленивые вычисления потребно изменить весь код, это так себе решение. Изменения должны вноситься по минимуму.

Эта цепочка рассуждений привела к техническому решению, оформленному в python библиотеку evalcache (ссылки в конце статьи).


Синтаксическое решение и механизм работы


Простой пример
import evalcache
import hashlib
import shelve

lazy = evalcache.Lazy(cache = shelve.open(".cache"), algo = hashlib.sha256)

@lazy
def summ(a,b,c):
    return a + b + c

@lazy 
def sqr(a):
    return a * a

a = 1
b = sqr(2)
c = lazy(3)

lazyresult = summ(a, b, c)
result = lazyresult.unlazy() 

print(lazyresult) #f8a871cd8c85850f6bf2ec96b223de2d302dd7f38c749867c2851deb0b24315c
print(result) #8

Как это работает?


Первое, что здесь бросается в глаза, создание декоратора lazy. Такое синтаксическое решение довольно стандартно для питоновских ленификаторов. Декоратору lazy передается объект кэша, в котором ленификатор будет хранить результаты вычислений. На тип кэша накладывается требования dict-like интерфейса. Иными словами, мы умеем кешировать во всё, что реализует тот же интерфейс, что есть у типа dict. Для демонстрации в примере выше использован словарь из библиотеки shelve.


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


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


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


При проходе по скрипту, на самом деле, не производится никаких вычислений. Для b не расчитывается квадрат, а для lazyresult не считается сумма аргументов. Вместо этого строится дерево операций и подсчитываются хэшключи ленивых объектов.


Реальные вычисления (если результат ранее не положен в кэш) будут выполнены только в строке: result = lazyresult.unlazy()


Если объект был вычислен ранее, он будет подгружен из файла.
Можно визуализировать дерево построения:


Визуализация дерева построения
evalcache.print_tree(lazyresult)

...

generic:
    <function summ at 0x7f1cfc0d5048>
args:
    1
    generic:
        <function sqr at 0x7f1cf9af29d8>
    args:
        2
    -------
    3
-------

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


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


В действии


Выше был простой пример, который показывает синтаксис, но не демонстрирует вычислительной мощи подхода.
Вот пример чуть более приближенный к реальной жизни (используется sympy).


Пример с использованием sympy и numpy
#!/usr/bin/python3.5

from sympy import *
import numpy as np
import math
import evalcache

lazy = evalcache.Lazy(evalcache.DirCache(".evalcache"), diag = True)

pj1, psi, y0, gamma, gr= symbols("pj1 psi y0 gamma gr")

###################### Construct sympy expression #####################
F = 2500
xright = 625
re = 625
y0 = 1650

gr = 2*math.pi / 360
#gamma = pi / 2

xj1q = xright + re * (1 - cos(psi))
yj1q = (xright + re) * tan(psi) - re * sin(psi) #+ y0
pj1 =  sqrt(xj1q**2 + yj1q**2)

pj2 = pj1 + y0 * sin(psi)
zj2 = (pj2**2)/4/F

asqrt = sqrt(pj2**2 + 4*F**2)

xp2 = 2*F / asqrt
yp2 = pj2 / asqrt
xp3 = yp2
yp3 = -xp2

xmpsi = 1295
gmpsi = 106 * gr
aepsi = 600 
bepsi = 125

b = 0.5*(1-cos(pi * gamma / gmpsi))

p1 = (
    (gamma * xmpsi / gmpsi * xp2) * (1-b) 
    + (aepsi * xp2 * sin(gamma) + bepsi * yp2 * (1-cos(gamma)))*b + pj1
)
#######################################################################

#First lazy node. Simplify is long operation.
#Sympy has very good representations for expressions 
print("Expression:", repr(p1))
print()

p1 = lazy(simplify)(p1)

#########################################################################################
## Really don't need to lazify fast operations
Na = 200
angles = [t * 2 * math.pi / 360 / Na * 106 for t in range(0,Na+1)]

N = int(200)
a = (np.arange(0,N+1) - N/2) * 90/360*2*math.pi/N
#########################################################################################

@lazy
def genarray(angles, a, p1):
    points = []
    for i in range(0, len(angles)):
        ex = p1.subs(gamma, angles[i])
        func = lambdify(psi, ex, 'numpy') # returns a numpy-ready function
        rads = func(a)
        xs = rads*np.cos(a)
        ys = rads*np.sin(a)
        arr = np.column_stack((xs,ys,[i*2]*len(xs)))
        points.append(arr)
    return points

#Second lazy node.
arr = genarray(angles, a, p1).unlazy()

print("\nResult list:", arr.__class__, len(arr))

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


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


Ради чего всё затевалось


evalcache — часть проекта zencad. Это маленький скриптовый кадик, вдохновленный и эксплуатирующий те же идеи, что и openscad. В отличие от mesh ориентированного openscad, в zencad, работающем на ядре opencascade используется brep представление объектов, а скрипты пишутся на языке python.


Геометрические операции зачастую выполняются долго. Недостаток скриптовых cad систем в том, что каждый раз при запуске скрипта, изделие полностью пересчитывается заново. Причем с ростом и усложнением модели, накладные расходы растут отнюдь не линейно. Это приводит к тому, что комфортно работать можно только с крайне небольшими моделями.


Задача evalcache состояла в том, чтобы сгладить эту проблему. В zencad все операции объявлены как ленивые.


Примеры:


Пример построения модели
#!/usr/bin/python3
#coding: utf-8

from zencad import *

xgate = 14.65
ygate = 11.6
zgate = 11
t = (xgate - 11.7) / 2

ear_r = 8.6/2
ear_w = 7.8 - ear_r
ear_z = 3

hx_h = 2.0

bx = xgate + ear_w
by = 2
bz = ear_z+1

gate = (
    box(xgate, ygate, t).up(zgate - t) +
    box(t, ygate, zgate) +
    box(t, ygate, zgate).right(xgate - t)
)
gate = gate.fillet(1, [5, 23,29, 76])
gate = gate.left(xgate/2)

ear = (box(ear_w, ear_r * 2, ear_z) + cylinder(r = ear_r, h = ear_z).forw(ear_r).right(ear_w)).right(xgate/2 - t)
hx = linear_extrude( ngon(r = 2.5, n = 6).rotateZ(deg(90)).forw(ear_r), hx_h ).up(ear_z - hx_h).right(xgate/2 -t  + ear_w)

m = (
    gate 
    + ear 
    + ear.mirrorYZ() 
    - hx 
    - hx.mirrorYZ() 
    - box(xgate-2*t, ygate, zgate, center = True).forw(ygate/2)
    - box(bx, by, bz, center = True).forw(ear_r).up(bz/2)
    - cylinder(r = 2/2, h = 100, center = True).right(xgate/2-t+ear_w).forw(ear_r)
    - cylinder(r = 2/2, h = 100, center = True).left(xgate/2-t+ear_w).forw(ear_r)
)
display(m)
show()

Этот скрипт генерирует следующую модель:

Обратите внимание, что ни одного вызова evalcache в скрипте нет. Фокус в том, что ленификация заложена в саму библиотеку zencad и снаружи ее на первый взгляд даже и не видно, хотя вся работа здесь — работа с ленивыми объектами, а непосредственное вычисление производится только в функции 'display'. Разумеется, если какой-то параметр модели будет изменен, модель будет пересчитана с того места, где изменился первый хэшключ.


Модели с громоздкими вычислениями

Вот еще один пример. В этот раз ограничимся картинками:

Вычисление резьбовой поверхности задача не из легких. На моем компьютере такой болт строится порядка десяти секунд… Редактировать модель с резьбами горазда приятнее, используя кеширование.


А теперь это чудо:

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


Проблемы


Кэш может отрабатывать не так, как задумано.
Ошибки кэша можно разделить на ложноположительные и ложноотрицательные.


Ложноотрицательные ошибки


Ложноотрицательные ошибки — это ситуации, когда результат вычисления в кэше есть, но система его не нашла.
Это бывает в случае, если алгоритм построения хэшключа, которым пользуется evalcache по какой-то причине выдал отличающийся ключ на повторное вычисление. Если для объекта кэшируемого типа не переопределена хэшфункция, evalcache использует __repr__ объекта для построения ключа.
Ошибка случается, например, если ленифицируемый класс не переопределяет стандартный object.__repr__, который изменяется от запуска к запуску. Или, если переопределенный __repr__, как-то зависит от незначимых для вычисления изменяющихся данных (вроде адреса объекта или временной метки).


Плохо:


class A:
    def __init__(self):
        self.i = 3

A_lazy = lazy(A)
A_lazy().unlazy() #Этот объект никогда не будет подгружаться из кэша из-за плохого __repr__.

Хорошо:


class A:
    def __init__(self):
        self.i = 3

    def __repr__(self):
        return "A({})".format(self.i)

A_lazy = lazy(A)
A_lazy().unlazy() #Этот объект будет подгружаться из кэша.

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


Ложноположительные ошибки


Это более мерзкий тип ошибки, так как приводит к ошибкам в конечном объекте вычисления:
Может случаться по двум причинам.


  • Невероятная:
    Произошла коллизия хэшключа в кэше. Для алгоритма sha256, имеющего пространство в 115792089237316195423570985008687907853269984665640564039457584007913129639936 возможных ключей, вероятность получить коллизию ничтожна.
  • Вероятная:
    Репрезентация объекта (или переопределенная хэш функция) не полностью его описывает, или совпадает с репрезентацией объекта другого типа.

class A:
    def __init__(self):
        self.i = 3

    def __repr__(self):
        return "({})".format(self.i)

class B:
    def __init__(self):
        self.i = 3

    def __repr__(self):
        return "({})".format(self.i)

A_lazy = lazy(A)
B_lazy = lazy(B)

a = A_lazy().unlazy()
b = B_lazy().unlazy() #Ошибка. Вместо генерации объекта класса B, мы получим только что сохраненный объект класса A. 

Обе проблемы связаны с несовместимым __repr__ объекта. Если по какой-то причине переписать типу объекта __repr__ метод нельзя, библиотека позволяет задать для пользовательского типа специальную хэшфункцию.


Об аналогах


Есть много библиотек ленификации, которые в основном считают достаточным выполнение вычисления не более одного раза за вызов скрипта.


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


Но библиотек, которые позволяли бы кэшировать результаты по дереву исполнения, я все же не нашел. Если они есть, пожалуйста, отсемафорьте.


Ссылки:


Проект на github
Проект на pypi

  • +12
  • 3,1k
  • 9
Поделиться публикацией

Комментарии 9

    0
    Ошибка случается, например, если ленифицируемый класс не переопределяет стандартный object.__repr__, который изменяется от запуска к запуску

    Нужно детектить хотя бы регекспами стандартные неподходящие __repr__ и делать про это warning.
    Нужно для типов, которые встречаются в первый раз, пробовать создать дважды один и тот же объект и сравнивать их __repr__ и хеши. Если результаты получаются разные — снова warning.
    Ложноотрицательные ошибки приводят к тому, что ленификация не работает. Объект будет пересчитываться при каждом новом выполнении скрипта.

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

    Можно запекать тип значения рядом со значением в одной структуре. При встрече двух разных типов с одним хешем — warning.

    В целом подход интересный. Спасибо.
      0
      Я, единственно что, использую warning на совпадение if obj.__class__.__repr__ is object.__repr__.

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

      Собственно, изначально я делал что-то подобное. Счел излишним. Выпилил всё, оставил только логику.
        0
        Это можно спрятать за отдельными необязательными опциями.
        Это можно вынести в отдельную фичу — автогенерация автотестов.
        То есть у вас есть ленивое вычисление и вы можете его запустить, а можете сгенерировать по нему параноидальный автотест. Пользователи его смогут запускать в пайплайне основного CI и своевременно увидят проблемы, причем на производительности вычислений это не скажется.
          0
          Да, если навесить это дело сверху, как подбиблиотеку для тестирования, а не пытаться встроить внутрь, может получиться неплохо.
          Жаль, у меня нет хорошей задачи под отладку.

          Я это обмозгую. Спасибо.
      0
      Не удержался, залез в код.
      Скажите, почему вы используете лямбдами там, где можно использовать функции из модуля `operator`?
      Ещё я бы завернул хэш-алгоритм в обертку для кодирования строк в utf-8, чтобы в тысяче мест не писать такое: «m.update(obj.__module__.encode(»utf-8"))"
      Хочется отформатировать код по pep-8. Вы принципиально против него, или просто руки не доходили?
        0
        К сожалению, не знал про этот модуль. Я вообще не так много пишу на питоне. Попробую оптимизировать.

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

        `m.update(obj.__module__.encode(«utf-8»))` наверное стоит обернуть. В целом, не вижу особой разницы между этим и каким-нибудь `updatehash_string(m, obj.__module__)`.

          0
          не вижу никакого смысла разбивать операторную околесицу по строчкам. Файл станет длинным и сразу же станет очень сложно что-либо в этом файле найти.

          А вот тут вы не правы. В Питоне есть правильный способ писать код. Правила довольно строги и имеет смысл привыкнуть к ним, а не нести свои привычки из других языков. Если код писать правильно, то размер файла по числу строк не будет критичен, зато все будет прозрачно и понятно с одного взгляда.
          При правильном разбиении кода на модули, классы и методы проблем с навигацией возникнуть не должно. А вот кучи плохо читабельных кусков через точку с запятой — это кошмар.
          Прелесть PEP-8 в том, что пользуясь им вы сделаете свой код очень похожим на большую часть чужого кода. Это дорогого стоит, поскольку не нужно отвлекаться на стилистические различия.
          В современных IDE есть замечательные линтеры и автоформаттеры, а для хардкорщиков, работающих в IDLE есть чудесная библиотека pep8. Если скормить её питоновский файл, она перечислит все его проблемы, связанные с оформлением по pep-8
            0
            Я согласен с тем, что общепринятое оформление — это хорошо.
            Но есть исключения. Возьмем к примеру sgorsten/linalg (https://github.com/sgorsten/linalg/blob/master/linalg.h). Это плоская библиотека линейной алгебры для с++. Она читаема исключительно благодаря тому, что автор наплевал на общепринятое форматирование.

            Постараюсь привести в соответствие с pep8 все, кроме операторов. Они мне пока еще в таком виде нужны.
          0
          Внес изменения в код. Использован модуль operator и добавлена функция updatehash_str.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое