Андрей Платов
Сегодня, после многих месяцев прокрастниации и страданий на тему что программистом мне уже не быть, сел за работу. Пожалуй начну с Virtual DOM. Мельком глядя на существующие реализации Virtual DOM, понимаю что там вообще нет никакого rocket science - чуваки в лоб сравнивают деревяху применяя разнообразные эвристики, подробнее про это дело есть хорошая статья.
Вообще про сравнение деревях есть много рисерча, но я так понимаю большинство этого рисерча просто не выживет столкнувшись с реальностью (в мою прошлую жизнь - 20 лет назад я как то занимался поиском, и реализовал алгоритм из умной статейки - ему не хватило ни памяти ни времени). Собственно рисерч во многом ориентирован на построение минимального дифа между деревяхами, а это дорого. Так что соглашусь с авторами реактов и прочих вдомов - делать надо проще и O(n) (либо за O(n) понимать что патч не светит и менять нахер все.)
Мой климакс программиста мне принес еще одно обострение детских болезней - я начал очень переживать за память и скорость - вот даже в детстве не переживал (поэтому наверное все получалось), а сейчас переживаю так, что ничего не могу с собой поделать (если меня читает молодеж - то ничего хорошего в этом нет). Но все же не буду бороться с диагнозом пока жизнь не излечит.
Fast and Simple XML Tree Differencing by Sequence Alignment (Faxma)
В поисках рисерча на тему сравнения деревях я наткнулся вот на эту статейку. И, пока, мне оно нравится: После многих лет любви к GC у меня случилась его боязнь, и я бы предпочел вместо типичного представления DOM в виде дерева, представлять DOM в виде последовательности, а именно на последовательность ориентирован алгоритм.
Плюсы последовательности:
- гораздо меньше памяти - только представьте что каждая нода из дерева, которая сама по себе объкт (с соответсвующими накладными расходами), еще содержит в себе массив аттрибутов, массив детей, эти массивы (если resizeable) скорее всего тоже обеъкты, которые ссылаются на другую область памяти с контентом.
- locality - в деревьях вся эта беда разбросана по хипу что вообще не спсобствует быстрой навигации по дому. Дом как последовательность очень cache-friendly.
- GC - ну и сборщик мусора будет собирать всю эту деревяху, тогда как последовательность можно загасить за один ход.
Минусы:
- последоватьность дорого модифицировать, но в нашем случае это совсем не надо - мы же делаем VDOM, где каждая деревяшка immutable.
- по дому в виде последовательности сложнее навигироваться, но это просто больше бука а агоритме. Медленнее ли? В целом не знаю - где то больше вычислений, но возможный выйгрыш за счет локалити. В общем минус только в том, что придется попрограммировать.
Что меня еще привлекает в DOM-as-a-Sequence, так это возможность переиспользования большего количества статических кусков DOM. Например у меня в DOM есть повторяющийся тег с детьми типа <li class="const1"><div class="const2"> что-то </div></li>. В случае с деревом это все разные ноды, так как разные дети, в общем переиспользование общих частей затруднительно. В случае же последовательности если очевидные статические подпоследовательности которые можно переиспользовать. Частый ли это сценарий? Думаю что да - возьмите, к примеру, шаблон какого нить элемента с парой изменящихся строк и кучей статичного HTML вокруг.
Итак, для начала я попробую реализовать этот алгоритм сравнения двух HTML деревяшек, для своего будущего virtual DOM (без JavaScript и прочей хераборы).
Реализация
Алгоритм работает супротив последовательности событий XAS описывающих DOM. Я как программист из 90-х и начала 2000-х помню появление SAX парсера в Java, вобщем XAS в статейке это что-то типа сериализованных событий от SAX парсера (типа начало тега, конец тега, аттибут/значение, да и все :). Реализовал я это дело здесь (пока мы парсить ничего не будем).
Переходим к самому алгоритму. Из бумажки:
основа нашего алгоритма -
rollmatch(u, v), которая находит минимальный старт и максимальный конец i и j соответственно, для которыхu[0..(j-i)] == v[i..j], чтобы найти такие i и j мы двигаем окно длинной s по v, каждый раз считая hash окна. Когда hash окон равен - сравниваем содержимое и вуаля. Считать каждый раз hash окна - жопа, поэтому мы пользуем Rabin fingerprint (“rolling hash”), пересчитывая hash за O(1) при каждом движении.
Я пока не буду реализовывать rolling hash - посчитаю втупую, и получаю следующий rollmatch, в котором все просто - находим первое вхождение u[0..s] в v, расширяя s если возможно:
proc rollmatch[T](u, v: seq[T], s: int): Slice[int] =
let hu = winhash(u, 0, s)
var hv = winhash(v, 0, s)
for i in 0..<(len(v) - s):
if hv == hu:
if equal(u, 0, v, i, s):
let j = i + s
var k = j
while v[k] == u[k - j]: inc k # Greedy extension of match
result = i..k
break
hv = winhash(v, i, s) # need roll in future
Дальше мутнее. Процедура match(u, v, s) еще не сопоставленным последовательностям u пытается сопоставить последовательности длинной s или больше из v. Это делается следующим образом: удаляем из u операцию вставки ins() и заменяем ее на опреации ins() и cpy(). ins() для несопоставленных участков и cpy() для сопоставленных соответственно. Пока не очень ясно, но ясно что нам нужен Matchlist. Абсолютно неэффективная реализация (в Nim нет slices, как например в Go) но сейчас это не важно:
type
OpKind = enum
ins
cpy
Operation[T] = object
op: OpKind
s: seq[T]
Matchlist[T] = object
list: seq[Operation[T]]
Временно забъю на match, разберусь сначала с низкоуровневой findmatch(u, v, s). Она сканирует подпоследовательности в v, на предмет матчинга с u.
proc findmatch[T](u: seq[T], v: var Matchlist[T], s: int, p: var int): Operation[T] =
var delta = 1
while true:
let i = p + delta
if i < v.list.len and i >= 0:
let op = v.list[i]
if op.op == ins:
let match = rollmatch(u, op.s, s)
if match != 0..0:
v.list[i] = insert(op.s, 0..match.a)
insert(v.list, insert(op.s, match.b..op.s.len), i+1)
p = i
result = copy(op.s, match)
break
if delta > 0:
delta = -delta
else:
delta = 1 - delta
if delta > v.list.len:
p = -1
break
OK, выглядит как будто findmatch нашел подпоследовательность u в списке v, вырезал ее из v и вернулся. Перехожу к match. Тупо портирую - буду изучать на тестах.
proc match[T](u, v: var Matchlist[T], s: int) =
var cu = 0
var p = -1
while cu < u.list.len:
let t = u.list[cu]
if t.op == ins:
delete(u.list, cu)
let c = findmatch(t.s, v, s, p)
if p != -1:
insert(u.list, c, cu)
insert(u.list, insert(t.s, c.s.len..t.s.len), cu + 1)
else:
insert(u.list, insert(t.s, 0..s), cu)
insert(u.list, insert(t.s, s..t.s.len), cu + 1)
inc cu
Для тестов беру последовательности из бумажки.
type
Test = enum
SEr, SEa, SEc, EEc, SEd, EEd, SEe, EEe, EEa, SEb, SEf, EEf, EEb, EEr, SEi, EEi
var s0 = @[SEr, SEa, SEc, EEc, SEd, EEd, SEe, EEe, EEa, SEb, SEf, EEf, EEb, EEr]
var s1 = @[SEr, SEb, SEf, EEf, EEb, SEa, SEc, EEc, SEd, EEd, EEa, SEa, SEi, EEi, EEr]
Потыкавшись с s == 2, понимаю что работает это дело не так как ожидается, видимо из за того что я проигнорировал следующее:
The match list u automatically combines pairs of operations into one when applicable (e.g., ⟨…,cpy(0,1),cpy(1,2),…⟩ → ⟨…,cpy(0,2),…⟩) to avoid artificial boundaries and to keep the output simple.
Дело не в output simple, а в принципе в работоспособности алгоритма. Самое время сделать полноценный Matchlist.
Конец дня
Вобщем потыкавшись, я понял что сделал глупость - алгоритм должен работать с глобальными интервалами, переделал Matchlist и получил работающий результат при s == 2. При s == 1 - падает, проблема в том что у меня рассинхрон курсора и списка интервалов в Matchlist в следствии объединения интервалов. В общем понятно как все привести в нормальный вид - это на завтра. Результат первого дня здесь: https://github.com/platoff/faxma/tree/day-1