Faster row swapping for keyed updates

[Rich-Harris]

The results are in for the latest version of Svelte on js-framework-benchmark. Svelte is among the fastest frameworks on most tests (there's really not much between them at the faster end of the table), is the fastest to start up, and uses the least memory. All in all, not bad.

But there's one place we don't perform that well, and it's dragging our overall score down badly — swapping rows. I'm not sure how common it is to swap rows in a list, but if there's a way we can tweak the keyed updates so that it doesn't perform so badly, without adding too much code, then we should.

[hville]

The problem is the do loop that flags everything for deletion until the right node is met. In #373 the proposal was to mark for deletion only if the item to be inserted matches the actual pointer's next sibling, indicating single intruder.

if `item` === `next` , continue with `next`
if `item` === `next.nextSibling`, mark `next` for deletion
else insert `item` before `next`

I don't know the build system enough to be able to test the change. Is there a quick way to make changes and test them?

(BTW i'm not using the expected and iteration terminology from the code because the cognitive dissonance of expected: actual node and iteration: desired node make it really hard for me to reason about. Must be just me)

[hville]

For info, I decided to take a stab at it.
All passing except for the transition-js-each-block-keyed-intro-outro test that I still have to figure out.

BTW is there an easy way to run a single test without hacking into the index.js test file?
For now I am inserting if (dir.match(/keyed/)) runTest( dir, null ); but it would be nice if there was already a way to shorten the whole test cycle and make the logs less verbose.

[Conduitry]

@hville You can add solo: true to the object exported by the test's _config.js.

[hville]

I just can't understand the intro-outro logic in EachBlock.js#L254

${node._block.hasIntroMethod && `${iteration}.intro( ${parentNode}, ${anchor} );`}

This line gets fired for every child ${iteration} even if nothing moves?

[Rich-Harris]

@hville thanks for taking a poke at this!

This line gets fired for every child ${iteration} even if nothing moves?

Yes — an iteration may exist but be in the process of outroing:

[ a b c ] # a.intro(), b.intro() and c.intro() fade elements in (or whatever)
[ a c ]   # a.intro() and c.intro() are no-ops. b still exists, but is outroing
[ a b c ] # a.intro() and c.intro() and no-ops. b.intro() aborts the outro

We could avoid the no-op calls with some extra book-keeping but it's probably not worth the effort.

[hville]

Thanks. That's how I thought it was working but I am still puzzled by a bug I introduced that is linked to this very case abc => ac => abc.

All tests and permutations without transitions pass but I am stuck at abc => ac => acb in the transition-js-if-else-block-intro-outro and I just can't find what difference the transitions would make.

In any case, I am not sure it is an idea worth considering further since the transitions require that deleted nodes stay where they are as much as possible.

movement of deletions
1. [ a b * ] => [ a b * ]
2. [ a * b ] => [ a * b ]
3. [ * a b ] => [ * a b ] 
4. [ b a * ] => [ a * b ]  moved! 
5. [ b * a ] => [ * b a ]  moved!
6. [ * b a ] => [ * b a ]

Above is the behaviour of the current "delete or move forward" algorithm. What I was proposing improves 4. at the expense of 6., the more common case

[paulocoghi]

About performance, this is the ultimate challenge for Svelte.

In the last benchmark posted on November 20, Svelte is the second fastest in non-keyed results, and I wish I could have enough knowledge to help with this inner detail and allow Svelte to be also in second for keyed results. :)

[paulocoghi]

Interestingly, the implementation of row swap in Bobril is even faster than vanilla. Maybe @Bobris (Boris Letocha) can tell us his secret.

[Bobris]

localvoid written very detailed blog about it here:
https://medium.com/@localvoid/how-to-win-in-web-framework-benchmarks-8bc31af76ce7

Bobril also virtualize events se there are no dom listeners actually attached directly to rows.

[pillaiindu]

I'm not an expert in JavaScript, so I don't know what algorithm goes/went wrong that the swapping rows benchmark is slow.

Is it solved now?

(By the way, the use case I see for swapping the rows is like in Facebook chat, that some slow client sent a chat message to a fast client. S/he typed the message and pressed enter before the faster client, but the message reached later, because of the slow connection, but the server somehow knows that the message from slower client was earlier, so the app will swap those two rows, but only two rows, not thousands of rows like in that benchmark, still I'd love to see a faster result for this benchmark for svelte, this slower benchmark actually degrades the fame of svelte).

[btakita]

I took a quick stab at speeding up the benchmark by optimizing the update function for the #each loop the generated code & found a near 10x speedup:

From

run took 96.9999999506399
main.js:285 swapRows took 75.40000008884817

To

run took 93.40000001247972
main.js:285 swapRows took 7.1000000461936

https://gist.github.com/btakita/6a40207ca263490a599caa3d39ea3ed4

Here's the component for the benchmark. https://github.com/krausest/js-framework-benchmark/blob/master/svelte-v1.41.2-keyed/src/Main.html

In the swap benchmark, there are 1000 keyed rows. Position 2 & 999 are swapped.

The benchmark is almost a worst case scenario for the current output, as the DOM nodes between position 2 & 1000 are thrown away & recreated. This optimization reuses all of the DOM nodes.

I'm not sure that this does not break anything else. This is simply a proof of concept.

From the gist above:

    p: function update(changed, state) {
      var data = state.store.data;

      var each_expected = each_head;
      var each_last = null;

      // <<new
      var rendered = {};
      var all = {}
      // new>>
//      var discard_pile = [];

      // <<new
      var each_all = each_head
      while(each_all) {
        all[each_all.key] = each_all
        each_all = each_all.next
      }
      // new>>

      for (i = 0; i < data.length; i += 1) {
        var key = data[i].id;
        var each_iteration = each_lookup[key];

        var each_context = assign({}, state, {
          data: data,
          row: data[i],
          num: i
        });

        if (each_iteration) { each_iteration.p(changed, each_context); }

        if (each_expected) {
          if (key === each_expected.key) {
            each_expected = each_expected.next;
          } else {
            if (each_iteration) {
//              // probably a deletion
//              while (each_expected && each_expected.key !== key) {
//                each_expected.discard = true;
//                discard_pile.push(each_expected);
//                each_expected = each_expected.next;
//              }
              // <<new
              var next_data = data[i+1];
              var next = next_data && each_lookup[next_data.id];
              var first = each_iteration.first;
              var first_next = next && next.first;
              insertNode(first, tbody, first_next);
              each_expected = next;
              each_iteration.next = each_expected;
              var prev_data = data[i-1]
              var prev = prev_data && each_lookup[prev_data.id];
              prev.next = each_iteration;
              // new>>
//              each_expected = each_expected && each_expected.next;
//              each_iteration.discard = false;
//              each_iteration.last = each_last;

//              if (!each_expected) { each_iteration.m(tbody, null); }
            } else {
              // key is being inserted
              each_iteration = each_lookup[key] = create_each_block(component, key, each_context);
              each_iteration.c();
              each_iteration.m(tbody, each_expected.first);

              each_expected.last = each_iteration;
              each_iteration.next = each_expected;
            }
          }
        } else {
          // we're appending from this point forward
          if (each_iteration) {
//            each_iteration.discard = false;
            each_iteration.next = null;
            each_iteration.m(tbody, null);
          } else {
            each_iteration = each_lookup[key] = create_each_block(component, key, each_context);
            each_iteration.c();
            each_iteration.m(tbody, null);
          }
        }
        // <<new
        if (each_iteration) {
          rendered[each_iteration.key] = each_iteration
        }
        // new>>

        if (each_last) { each_last.next = each_iteration; }
        each_iteration.last = each_last;
        each_last = each_iteration;
      }

      if (each_last) { each_last.next = null; }

      // <<new
      for (var key_all in all) {
        if (!rendered[key_all]) each_destroy(all[key_all]);
      }
      // new>>
//      while (each_expected) {
//        each_destroy(each_expected);
//        each_expected = each_expected.next;
//      }
//
//      for (i = 0; i < discard_pile.length; i += 1) {
//        var each_iteration = discard_pile[i];
//        if (each_iteration.discard) {
//          each_destroy(each_iteration);
//        }
//      }

      each_head = each_lookup[data[0] && data[0].id];
    }

[jacwright]

For what it's worth, I came across Svelte because I saw these benchmarks awhile ago. Svelte was one of the fastest and had the lowest memory consumption.

I know benchmarks are not 1-1 with real world performance, but they are a great marketing tool. Anything we can do to put Svelte in the green for round 8 of these benchmarks would help Svelte stand out from the noise of virtual doms. Anything that doesn't negatively affect real-world usage of Svelte of course! 😄

[talklittle]

Did a straight-up quick conversion of @btakita 's code to .ts, making the appropriate var replacements, to see if the unit tests would pass. Unfortunately they don't.

Let me know if something's wrong with my conversion, but it's also likely the original proposed change doesn't handle all cases, as the author already mentioned. AFAICT there have been multiple serious attempts at this issue in the past; it's a hard problem.

https://github.com/talklittle/svelte/tree/test-btakita-588

[btakita]

Not surprised there's failures.

It looks like there's some issues with the deletion logic. I didn't spend much time on the deletion logic as I was focusing on the swap benchmark.

My understanding is that this issue was not a priority because it's rare to see it in production code.

#26

[jacwright]

I don't think it is rare. A chat app with a list of friends sorted by online status would see a friend move from the top to the bottom when they go offline.

Of course, the benchmark uses 10,000 rows which may be rare. But it is still a big marketing piece. I'm sold on Svelte, but I'd like to see it last, which means more people using and contributing to it.

[btakita]

I fixed a test. Still working on the rest...
btakita@03d42ef.

jsdom.VirtualConsole was helpful in solving this issue & in understanding the compiled output.

[btakita]

@talklittle I'm only running one of the samples in that test suite. Unfortunately, it's still failing. Sorry about the confusion.

talklittle@5f0bfad#diff-02c1a328e99315bf82acb8fc1747f0aaR214

[btakita]

I fixed the tests:

• each-block-keyed-random-permute
• transition-js-each-block-keyed-outro

This test is still broken:

• transition-js-each-block-keyed-intro-outro

The majority of the changes are in:

https://github.com/btakita/svelte/blob/issues/588/src/generators/nodes/EachBlock.ts

I have some questions re: outros. It seems like outros block a DOM element being detached until it's completion. From the tests, I'm not able to tell if move & insert operations wait for the outro completions. Would all of the delete outros this also apply to move & insert operations?

In the current implementation of the https://github.com/btakita/svelte/tree/issues/588 branch, the destroy outros block the move & add operations. I separating the data graph reconciliation from the DOM manipulation. Deletes occur first to make inserts & moves simpler.

Just one more test to go :-)

@Rich-Harris

${fn_destroy}(${all}, ${keep}, function() {
	// Work backwards due to DOM api having insertBefore
	for (#i = ${each_block_value}.${length} - 1; #i >= 0; #i -= 1) {
		var data = ${each_block_value}[#i];
		var ${key} = data.${this.key};
		${iteration} = ${lookup}[${key}]
		if (${inserts}[${key}] || ${moves}[${key}]) {
			var first_next = ${next_iteration} && ${next_iteration}.first;
			if (${inserts}[${key}]) {
				${inserts}[${key}].${mountOrIntro}(${updateMountNode}, first_next);
			} else if (${moves}[${key}]) {
				${moves}[${key}].m(${updateMountNode}, first_next);
			}				
		}
		${next_iteration} = ${iteration};
	}
})

[btakita]

Ok, I fixed the build. Some cleanup is probably in order before the PR though. I'll get to it either tonight or this weekend.

[Rich-Harris]

Released 1.58 with @btakita's changes! 🎉 I'll prepare a pull request for js-framework-benchmark.

[talklittle]

Congratulations on getting it working, @btakita! That's huge!

[mheinz67]

@Rich-Harris I've updated a local copy of the js-framework-benchmark svelte keyed benchmark to use svelte 1.58.0, but I'm currently not able to reporduce the speedup in the swap rows benchmark.
Using 1000 rows: swap rows takes 14ms for vanilla js, 144ms for svelte

[Rich-Harris]

Huh, that's very odd — I ran the benchmarks right before publishing and it was close to vanilla speed. I may have messed something up. Reopening pending an investigation, thanks

[mheinz67]

The relative perfomance of svelte was 1.48 in round 7 of the js-framework-benchmark.
The current snapshot result is 3.93 (with svelte version 1.58.0).

[Rich-Harris]

This is fixed in 1.58.2 — closing again