День второй. Вчера перед сном понял что я - дебил. Листая бумажку по faxma я понял что во второй части агоритма (построение meta-diff) все равно придется бежать по структуре, и анализировать изменения аттрибутов, как это делают virtual domы Elm, Virtual DOM, React и прочие. Та часть, которую я реализовывал вчера не выглядит сильно полезной в этом процессе. Возможно она будет полезна частично, например при сравнении детей на отдельно взятом уровне (надо будет мерять производительность), но уже сейчас мне кажется что подход не хорош, и надо решать задачу в лоб, как все.

Наивная реализация

Я пока не хочу отказваться от “поточной” генерации DOM (XAS), и для начала сделаю механизм его генерации (на примере dbmonster). Дом строится примерно так:

proc openTag(builder: var DOMBuilder, tag: Tag) =
  builder.elements.push builder.current
  builder.current = cast[Element](builder.contentStack.tail)
  builder.contentStack.advance sizeof ElementObj
  builder.current.tag = tag
  builder.current.nAttrs = 0
  builder.current.nKids = 0

proc closeTag(builder: var DOMBuilder) =
  let res = cast[Element](builder.dom.tail) 
  builder.dom.write(builder.current, builder.current.size)
  builder.contentStack.trim(builder.current)
  builder.contentStack.push res
  builder.current = builder.elements.pop(Element)
  inc builder.current.nKids

proc attr(builder: var DOMBuilder, attr: Attr, value: cstring) =
  builder.contentStack.push attr
  builder.contentStack.push value
  inc builder.current.nAttrs

В реальности это все обрастет разными замедляющими работу штуками, сейчас же на моем лаптопе за секунду создается около 20 млн простеньких элементов - это 20 тысяч за милисекунду. ОК, пока норм. Сейчас перейду к дифу, но для начала посмотрю сильно ли ухудшает сортировка аттрибутов в момент построения дома (да, старый добрый пузырек:). Код:

  when SORT_IT:
    let attrs = builder.current.attrs
    var i = builder.current.nAttrs - 1
    while i >= 0:
      if int(attrs[i].attr) > int(attrs[i+1].attr):
        swap(attrs[i].attr, attrs[i+1].attr)
        swap(attrs[i].value, attrs[i+1].value)
        dec i
      else:
        break

Простые замеры для 3 миллионов элементов (примерно по 4 аттрибута в каждом) показыают: без сортировки - 140-160 ms. С сортировкой 160-180 ms.

Делаем Diff

Диф аттрибутов делается тривиально и O(n), учитывая отсортированные аттрибуты в момент построения дерева. А вот с детьми пришлось задуматься. Пролистал еще раз замечательную статью @localvoid: How to win in Web Framework Benchmarks. И ушел в Longest Common Subsequence Problem.

На сегодня программирования хватит. Результаты под тегом day-2 https://github.com/platoff/faxma/tree/day-2.

Назад, к записям