Svelte: Use standard algo for keyed each block updates

[Rich-Harris]

Apparently this is how it's done:

All modern Virtual DOM implementations are using simple technique to handle such use cases:

A: [a b c d e f g]
B: [a b f d c g]

A is an old children list and B is a new children list. Each item has unique key and we need to rearrange list A with the least amount of transformations.

A: -> [a b c d e f g] <-
B: -> [a b f d c g] <-

We can start by skipping common prefix [a b] and suffix [g]

A: -> [c d e f] <-
B: -> [f d c] <-

At this position we will look at the opposite edges of different lists and move nodes to the opposite edge if it has the same key. Here we can move c to the end, and f to the beginning.

A: -> [d e]
B: -> [d]

Now we can skip prefix d.

A: [e]
B: []

And remove e.

I was playing around with js-framework-benchmark and discovered that our keyed updates at the moment are rather slow — would hurt our ranking if we were to submit a keyed update version! (Which we should, because at the moment we're relegating to the list of frameworks that only have non-keyed versions.)

[Swatinem]

Reordering fragments/blocks this way would require some way to move a fragment in front of the other.

So in svelte terms, we would need to have a getAnchor method for a fragment. And that has to be smart enough to essentially say I’m empty, ask my nextSibling.

We should also find a different way to deal with iteration scopes, so the i and value things that get passed to fragments as additional parameters. I do think we need to get rid of that in order to be able to move the whole iteration logic out to a helper. In that case doing such a more complicated solution would become feasible in terms of codesize.

[Rich-Harris]

So, I've made a start on this in #543. There's some stuff in there that needs tidying up (hard-coded variable names and the like), but I think I'm on the right track.

It's not using the algorithm described above, which turns out to be quite a chunky implementation, and one that I'm not convinced is necessary or even optimal in our case.

Instead, I'm doing something else. Suppose we start with the following — A is the current list, B is the target:

A: [a b c d e f g]
B: [a b f d c g]

We first iterate over B, noting the index of each key and the key of each index as we'll need them in a minute:

key_by_index = [ 'a', 'b', 'f', 'd', 'c', 'g' ];
index_by_key = { a: 0, b: 1, f: 2, d: 3, c: 4, g: 5 };

(If there were any items in B that didn't already exist, we'd create them and put them to one side. Once we've gone through the whole list, we would run through the new iterations and mount/intro them using their next siblings as anchors, as described below.)

Then, we iterate over the items in A. For each in turn, we ask 'is this to the left of the correct item?'

• a is next to b, so nothing happens
• b should be next to f, so we remount it. The list is now a c d e b f g
• c should be next to g, so we remount it. The list is now a d e b f c g
• d should be next to c, so we remount it. The list is now a e b f d c g
• e is not in B, so we remove it. The list is now a b f d c g
• f should be next to d, and it is! (Though now that I think about it, while this should be a no-op I don't think it currently is, because we're not updating the sibling relationships after each move. TODO)
• g should be at the end, and it is, so that's also a no-op

So we get to the end result in 4 moves, we only need to iterate over the list twice, and it's much less code than e.g. this implementation. Hopefully this will be a performance win, though I haven't benchmarked it yet.

[hville]

FWIW the toy picoDOM in the js-framework-benchmark gets fast with a much simplified one pass check. Moving from start to end, last is the last placed node, next and after and the following 2 siblings, 'node' is the the following node to be inserted after last

last > ? > next > after

• if node === next do nothing
• if node === after remove next (likely deletion, if not, can be re-inserted later)
• else insert node before next
• last = node, next=last.nextSibling, after=next.nextSibling

The inside of the insertion loop looks like this

node = nodes[getKey(data[i])],
next = last ? last.nextSibling : parent.firstChild
last = !next ? parent.appendChild(node)
: node === next ? node
: foot === next ? parent.insertBefore(node, next)
: node === next.nextSibling ? parent.removeChild(next) // later cleared by anyways
: parent.insertBefore(node, next)

foot is used as delimiter when a parent contains multiple stacked lists and nodes

For the example in the post above, it also results in 4 operations: insert f, remove c, insert c, remove e

A: [a b c d e f g]
B: [a b f d c g]

[thysultan]

@Rich-Harris It'll probably perform worse for non-complex operations since you are always building a key-value map and iterating through the list twice.

I have a few tests for other complex cases to test for correctness,
https://github.com/thysultan/dio.js/blob/master/experiment/tests/Reconcile.spec.js#L111-L194

A: [a b c d e f g]
B: [a b f d c g]

// least operations archivable, factoring layout shifting.
// 3 operations in 2 moves `f->f`, `c->c` and 1 remove `e`

[Rich-Harris]

Thanks @hville and @thysultan, this is extremely helpful!

[leeoniya]

domvm implements most of the original algo except when things get too hairy it falls back to a selection sort (guaranteeing minimum dom moves with sub-optimal but much cheaper extra comparisons). the impl [1] is significantly shorter than what inferno does and still works in a single pass. The single pass is possible because the template preprocessor already sets an explicit .idx and .parent on all vnodes.

dunno if any of this transfers to your architecture, but steal whatever you need.

[1] https://github.com/leeoniya/domvm/blob/2.x-dev/src/view/syncChildren.js

[Rich-Harris]

Ok, I've completely changed the algorithm based on this conversation — it's inspired by picoDOM's approach but not quite the same because it has different constraints (an iteration might have multiple top-level elements, and we need to keep removed keys in the DOM until their outro transitions have completed, which adds an extra dimension of complexity that my brain would prefer not to have had to deal with).

For posterity, and because I'm probably going to need to refer back to it...

The iterations of the each-block form a linked list. When the data for the each-block is updated:

• Let expected be the head of the linked list
• Iterate over each key in the data
  
  
  
  • If expected is null, we are appending to the end of the list. Create an iteration for key if it does not already exist, and mount at the end
  
  
  • If key === expected.key, do nothing. Set expected = expected.next
  
  
  • If iteration exists for the current key, we're probably dealing with a deletion. Add expected to the discard pile, then set expected = expected.next, and repeat until expected.key === key. Mount iteration before expected.first (the first node of the next iteration)
  
  
  • Create iteration if it does not exist, and mount it before expected.first
  
  
• While expected is not null, destroy/outro it and set expected = expected.next
• Destroy/outro iterations in the discard pile

I'm glossing over a couple of details (e.g. if a discarded iteration is later inserted, i.e. it has been moved rather than deleted, we remove it from the discard pile. Also we need to take care to maintain the integrity of the linked list when inserting/moving/destroying iterations), but you get the gist. For common cases we're basically just iterating once over the new data.

Examples:

Removing an item

A: a b c d e
B: a b d e

The expected key is a (the head of A). We iterate over a b d e:

• a matches our expectation, so we do nothing. expected is now b
• b matches our expectation, so we do nothing. expected is now c
• d does not match our expectation. We add expected to the discard pile and set expected to d. Our expectation now matches, so we do nothing further and set expected to e
• e matches our expectation, so we do nothing. expected is now null, and we have reached the end of the new data
• expected is null, so there is nothing to remove from the end
• The discard pile contains c, so we destroy/outro it and heal the linked list.

Adding an item

A: a b d e
B: a b c d e

The expected key is a (the head of A). We iterate over a b d e:

• a matches our expectation, so we do nothing. expected is now b
• b matches our expectation, so we do nothing. expected is now d
• c does not match our expectation. Since we don't already have an iteration for c, we create one and mount it before expected.first. expected is still d
• d matches our expectations, so we do nothing. expected is now e
• e matches our expectations, so we do nothing. expected is now null
• expected is null, so there is nothing to remove from the end
• The discard pile is empty, so we do nothing

Shifting an item

A: a b c d e
B: b c d e

The expected key is a (the head of A). We iterate over b c d e:

• b does not match our expectation. We add expected to the discard pile and set expected to b. Our expectation now matches, so we do nothing further and set expected to c
• c matches our expectation, so we do nothing. expected is now d
• d matches our expectation, so we do nothing. expected is now e
• e matches our expectations, so we do nothing. expected is now null
• expected is null, so there is nothing to remove from the end
• The discard pile contains a, so we destroy/outro it and heal the linked list.

Worst case — reversing a list

A: a b c d e
B: e d c b a

The expected key is a (the head of A). We iterate over e d c b a:

• e does not match our expectation. We add expected to the discard pile and set expected to b. b still doesn't match, so we add b, then c, then d to the discard pile, until we finally get to e. expected is now null, so we mount e at the end
• expected is null, so we mount d at the end
• expected is null, so we mount c at the end
• expected is null, so we mount b at the end
• expected is null, so we mount a at the end
• expected is null, so there is nothing to remove from the end
• The discard pile is empty, so we do nothing

---

Hopefully that explanation made some sense, because I'm almost certain to forget how this works otherwise. In cases with outro transitions, the iterations are kept around (in memory as well as the DOM) until outros are completed. If those iterations are brought back, we simply abort the outro transition, rather than creating new DOM.

[thysultan]

How will it handle something where is all three operations, remove, insert and move are used.

A: [1, 40, 0, 3, 4, 2, 5, 6, 60]
B: [1, 2, 3, 0, 5, 6, 90, 4]

[Rich-Harris]

It would go something like this:

• 1 matches expectations — do nothing
• 2 doesn't match 40. Since 2 exists, we add 40, 0, 3 and 4 to the discard pile. 2 is where it needs to be, so again we do nothing to the DOM. We're now expecting 5
• 3 doesn't match 5. Again, we do have a 3 (though it's already been discarded — so we could make a case that it should be treated differently to the previous operation), so we discard 5, 6 and 60. At this point there's nothing left, so from this point forward everything is an append operation — we pull 3 out of the discard pile and append it
• 0, 5 and 6 all get pulled out of the discard pile and appended
• 90 is new, so it gets created then appended
• 4 gets pulled out of the discard pile and appended

At the end of this process, 40 and 60 are left in the discard pile, so we destroy them.

So it's a total of 1 create, 6 mounts/moves (including the create), and 2 destroys, done in one pass. It's possible (likely, in fact) that you can get to that result in fewer moves — someone better versed in these sorts of problems might know. Anyway, it looks like this:

[leeoniya]

domvm performs something similar:

{ createElement: 1, textContent: 1, insertBefore: 5, removeChild: 2 }

https://jsfiddle.net/w70ofjax/

[thysultan]

For anyone that comes across this wondering how it might look like in pseudo code

A: [1, 40, 0, 3, 4, 2, 5, 6, 60]
B: [1, 2, 3, 0, 5, 6, 90, 4]
discard pile = {}
----
1 === 1

noop
----

A: [40, 0, 3, 4, 2, 5, 6, 60]
B: [2, 3, 0, 5, 6, 90, 4]

2 !== 40
discard pile = {40, 0, 3, 4}
----

A: [2, 5, 6, 60]
B: [2, 3, 0, 5, 6, 90, 4]

2 === 2
noop
----

A: [5, 6, 60]
B: [3, 0, 5, 6, 90, 4]

3 !== 5
discard pile = {40, 0, 3, 4, 5, 6, 60}
----

A: []
B: [3, 0, 5, 6, 90, 4]
discard[3] === true
insert(move) 3
discard pile = {40, 0, 4, 5, 6, 60}
----

A: []
B: [0, 5, 6, 90, 4]

discard[0] === true
insert(move) 0
discard pile =  {40, 4, 5, 6, 60}
----

A: []
B: [5, 6, 90, 4]

discard[5] === true
insert(move) 5
discard pile = {40, 4, 6, 60}
----

A: []
B: [6, 90, 4]

discard[6] === true
insert(move) 6
discard pile = {40, 4, 60}
----

A: []
B: [90, 4]

discard[90] === false
insert(create) 90
discard pile = {40, 4, 60}
----

A: []
B: [4]

discard[4] === true
insert(move) 4
discard pile = {40, 60}
----

A: []
B: []

remove all elements in discard pile: {40, 60}