Hyperapp: Appending rows to a large table.

[jorgebucaran]

New benchmarks show we've improved a lot since hyperapp was first introduced, but we're still performing comparatively poor in @krausest / js-framework-benchmark: Append rows to large table: Duration for adding 1000 rows on a table of 10,000 rows.

I am not trying to win these benchmarks, but of all the things, I still can't figure out why what takes to beat this particular test.

@leooniya's domvm is particularly good on this one, maybe you can share a couple of secrets?

[leeoniya]

try to avoid recreating and/or patching the full unchanged 10k vtree via an eager diff/sCU that reuses old vnodes and essentially noops the extra work.

[jorgebucaran]

Focus has shifted to introducing rAF and vnode recycling. Closing in favor of #244.

[yelouafi]

@jbucaran I might be wrong but I suspect raf or recycling will help solving this issue.

I think the issue is here. You're building the keymap too early, with a 10k table, you'll build an object with 10k keys which takes some time (even if in this case it is not necessary).

I would suggest running some preoptimization passes to trim common prefixes/suffixes (compare by index and patch first/last matching elements) and then only diff using a map for the rest (starting from the first until the last non matched elements). In the above case a map is not needed at all, after trimming the common prefix (the 1st 10k rows unchanged) since the old sequence is empty, all we have to do is to append the remaining elements from the new sequence. You can also check my comment here (https://github.com/developit/preact/issues/725#issuecomment-313954428) for more details

[jorgebucaran]

@yelouafi I might be wrong but I suspect raf or recycling will help solving this issue.

Just to clarify, did you mean to say perhaps they will _not_ help?

I would suggest running some preoptimization passes to trim common prefixes/suffixes

What is a prefix/suffix?

[leeoniya]

What is a prefix/suffix?

https://github.com/localvoid/kivi/blob/master/lib/vnode.ts#L1288

[jorgebucaran]

The comment alone is bigger than hyperapp. 😆

[leeoniya]

but it minifies to 0, even before gzip!

[yelouafi]

Just to clarify, did you mean to say perhaps they will not help?

Yeah, sorry for the typo.

What is a prefix/suffix?

Those are the sequences of elements that are the same at the start (prefix) and at the end (suffix) in the old and the new sequences. For example

old sequence : A B C D E
new sequence : A B x y C D E

In this example 2 elements x & y were inserted in the middle. [A,B] is the common prefix and [C,D,E] is the common suffix. We can identify those with a simple loop

newStart = 0
newEnd = newChildren.length
oldStart = 0
oldEnd = oldChildren.length


while(newStart <= newEnd && oldStart <= oldEnd) {
  // strip common prefix
  if(haveSameTypeAndKey(newChildren[newStart], oldChildren[oldStart]) {
    patch(newChildren[newStart], oldChildren[oldStart])
    newStart++; oldStart++
  }
  else if(haveSameTypeAndKey(newChildren[newEnd], oldChildren[oldEnd]) {
    patch(newChildren[newEnd], oldChildren[oldEnd])
    newEnd--; oldEnd--
  }
  // can also do some other tricks like inverions etc
  // you can see https://github.com/yelouafi/petit-dom/blob/master/src/vdom.js#L141
}

/*
if old seq is empty -> insert new elements
example
  old = 'ABCD'
  new = 'ABxyCD'
  after prefix/suffix trimming; old = '' and new = 'xy'
*/
if(oldStart > oldEnd) {
  while(newStart <= newEnd)
    insertBefore(newChildren[newStart++], oldChidlren[oldStart])
}

/*
if new seq is empty -> remove old elements
example
  old = 'ABxyCD'
  new = 'ABCD'
  after prefix/suffix trimming; old = 'xy' and new = ''
*/
else if(newSart > newEnd) {
  while(oldStart<= oldEnd)
    remove(oldChidren[oldStart++])
}

else {
  // continue with map based diff but only with elements [newStart...newEnd] & [oldStart..oldEnd]
}

the prefix/suffix trimming will cover most of the cases (like in the above example, where the prefix will be the first 10k rows) and you wont need even to do a map based diff which is slower (construction of the map, lookup ...)

[jorgebucaran]

@yelouafi I want to make sure we are on the same page: in your example, AB C and D are keyed nodes and x, y un-keyed nodes. Is that so?

[yelouafi]

Trimming will work for both keyed and non keyed nodes. For non keyed nodes the comparaison will return true for nodes with the same type

[jorgebucaran]

Right, I think I meant to ask: why are some of the letters uppercase/lowercase?

EDIT:

In this example 2 elements x & y were inserted in the middle. [A,B] is the common prefix and [C,D,E] is the common suffix.

Ah, gotcha. That answers my question. Thanks! 😄

[jorgebucaran]

Resolved in #499