Use standard algo for keyed each block updates #373
Comments
|
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 We should also find a different way to deal with iteration scopes, so the |
|
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: 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?'
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. |
|
FWIW the toy
The inside of the insertion loop looks like this
For the example in the post above, it also results in 4 operations: insert f, remove c, insert c, remove e |
|
@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, |
|
Thanks @hville and @thysultan, this is extremely helpful! |
|
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 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 |
|
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:
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 itemThe expected key is
Adding an itemThe expected key is
Shifting an itemThe expected key is
Worst case — reversing a listThe expected key is
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. |
|
How will it handle something where is all three operations, remove, insert and move are used. |
|
It would go something like this:
At the end of this process, 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:
|
|
domvm performs something similar:
|
|
For anyone that comes across this wondering how it might look like in pseudo code |
|
I was able to turn @thysultan's pseudocode example into a JavaScript function: // The algorithm:
const iterItems = (current, target) => {
let discard = []
const logState = () => {
console.log('current =', current)
console.log('target =', target)
console.log('discard pile =', discard)
console.log()
}
const end = () => console.log('\n---\n')
while (current.length > 0) {
logState()
const currentItem = current[0]
current = current.slice(1)
if (target.length == 0) {
discard = [...discard, ...current]
// Stop everything! There nothing left to check.
current = []
} else if (target[0] != currentItem) {
discard = [...discard, currentItem]
console.log('discard:', currentItem)
} else {
console.log('noop:',currentItem, '===', currentItem)
target = target.slice(1)
}
end()
}
while (target.length > 0) {
logState()
const item = target[0]
target = target.slice(1)
if (discard.some(discarded => discarded == item)) {
console.log('move:', item)
discard = discard.filter(discarded => discarded != item)
} else {
console.log('insert:', item)
}
end()
}
if (discard.length > 0) {
console.log('remove:', discard)
}
}
// Try it out:
iterItems([1, 40, 0, 3, 4, 2, 5, 6, 60], [1, 2, 3, 0, 5, 6, 90, 4])Note the Here is the output of running that code: P.S. Sorry for the late reply. |
Apparently this is how it's done:
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.)
The text was updated successfully, but these errors were encountered: