Bitmask-based change tracking

[Rich-Harris]

I've brought this up in chat previously, figured it'd be worth opening an issue.

One of the ways in which Svelte avoids unnecessary work is by tracking which properties are 'dirty' — thus <h1>Hello {name}!</h1> yields the following update code:

if (changed.name) {
  setData(text1, ctx.name);
}

This is all well and good, but it can result in unwieldy code if the expression (or, in the case of e.g. an each block, any of the expressions within) depends on multiple values:

if (changed.foo || changed.bar || changed.baz) {
  setData(text, ctx.foo * ctx.bar * ctx.baz);
}

We could instead use a bitmask. Take all the values that are referenced in the template (or in reactive declarations), sort them by frequency, and assign them a value that is a power of 2. In the case above, foo might be 1, bar might be 2, baz might be 4 and qux might be 8.

function handle_click() {
-  foo += 1; $$invalidate('foo', foo);
-  bar += 1; $$invalidate('bar', bar);
+  foo += 1; $$invalidate('foo', foo, 1);
+  bar += 1; $$invalidate('bar', bar, 2);
}

Then, instead of changed being an object that gets recreated after each update, it's just a number:

if (changed & (/*foo, bar or baz*/ 7)) {
  setData(text, ctx.foo * ctx.bar * ctx.baz);
}

If changed was equal to 8 (i.e. qux changed) nothing would happen. This minifies much better:

-if(a.foo||a.bar||a.baz)b(c,d.foo*d.bar*d.baz)
+if(a&7)b(c,d.foo*d.bar*d.baz)

Drawbacks

It's slightly harder to understand what's going on by looking at the code. Also, without adding more complexity (e.g. making changed an array of numbers, or only doing the bitmask thing where possible) it places a constraint on components: you can only reference 53 separate top-level variables (beyond that, you're in unsafe integer territory). For the vast majority of components that wouldn't be an issue, but it's not impossible to imagine someone hitting that wall. For that reason, we might want to consider doing this for v3, since it would be a breaking change.

Mangled context

While we're here, perhaps we should consider mangling context properties:

function handle_click() {
-  foo += 1; $$invalidate('foo', foo, 1);
-  bar += 1; $$invalidate('bar', bar, 2);
+  foo += 1; $$invalidate(1, foo);
+  bar += 1; $$invalidate(2, bar);
}

if (changed & (/*foo, bar or baz*/ 7)) {
-  setData(text, ctx.foo * ctx.bar * ctx.baz);
+  setData(text, ctx[1] * ctx[2] * ctx[3]);
}

// minified
-if(a&7)b(c,d.foo*d.bar*d.baz)
+if(a&7)b(c,d[1]*d[2]*d[3])

Nested properties

Another thing to consider: we might want to take better advantage of information at our disposal when mutating objects and arrays:

function toggleTodo(i) {
  todos[i].done = !todos[i].done;
}

In this situation, we could theoretically output code that didn't loop over todos (as currently happens) but instead went straight to the affected iteration. (I'm glossing over some stuff here.) I don't know if that's something we need to consider if we go down this alternative path.

[tivac]

I like the drive behind this idea, but I'm not sure the loss of readable generated code is worth it. Being able to easily understand the compiler output was one of the big reasons I was able to get comfortable with svelte quickly.

It's probably too extreme/different/complicated, but what if this only happened in non-dev mode?

[Rich-Harris]

@tivac what if it the ctx lookups were commented as well?

if (changed & (/*foo, bar or baz*/ 7)) {
  setData(text, /*foo*/ctx[1] * /*bar*/ctx[2] * /*baz*/ctx[3]);
}

In dev mode we could even do this sort of thing, maybe (though it does add complexity):

const { 1: foo, 2: bar, 3: baz } = ctx;

if (changed & (/*foo, bar or baz*/ 7)) {
  setData(text, foo * bar * baz);
}

Or is it that the changed & (/*foo, bar or baz*/ 7) is also hard to read?

[tivac]

Or is it that the changed & (/foo, bar or baz/ 7) is also hard to read?

Yes, that's the part that trips me up. It's fundamentally a bit weird compared to what I'm used to seeing in most any codebase. Since it's compiler-generated code weird isn't as big a problem, but I've definitely had to debug svelte-generated code before and having it be legible and easy-to-follow was a big bonus.

The destructuring approach helps somewhat. Could the bitmask values also be destructured & computed in dev mode via simple addition as well? The comments are gonna be hard to read no matter what I think.

Aside from the seemingly-big minification wins, does using bit-fiddling incur any sort of performance cost vs the existing boolean logic?

[Rich-Harris]

Could the bitmask values also be destructured & computed in dev mode via simple addition as well?

I guess it would be possible...

const $$bitmask = {
  foo_changed: 2 ** 0,
  bar_changed: 2 ** 1,
  baz_changed: 2 ** 2,
  qux_changed: 2 ** 3
};

// later...
const { 1: foo, 2: bar, 3: baz } = ctx;
const { foo_changed, bar_changed, baz_changed } = $$bitmask;

if (changed & (foo_changed | bar_changed | baz_changed)) {
  setData(text, foo * bar * baz);
}

Feels a little unwieldy though.

Aside from the seemingly-big minification wins, does using bit-fiddling incur any sort of performance cost vs the existing boolean logic?

On the contrary — no need to create the changed object, no object lookup necessary, a single comparison instead of multiple ones. Bitwise operators are very fast. Not that we should put too much faith in microbenchmarks, but according to this one, the bitmask approach is slightly faster. Not a lot, but at any rate I don't think we need worry about it being slower.

[ekhaled]

Hmmm...

[Rich-Harris]

well that's odd... neck and neck on my Android, bitmask definitely ahead on desktop Chrome and Firefox. Where are you seeing that @ekhaled?

[ekhaled]

Chrome 71
LG v30 running Android 8.0 Oreo

Lets not get too influenced by these microbenchmarks.

I think the minification gain is huge and we should do it.

I'm quite happy with either the comment style, or the destructuring style in dev mode

[trueadm]

I often see debates around bitmask values vs object properties in microbenchmarks. They are completely pointless in terms of microbenchmarking as everything will fall under the inline cache. If your device has lots of free memory, you'll have more memory for caching in Chrome etc. Realistically speaking though, bitmasks should be faster because without a JIT/inline cache because it's most likely to do less work (depending on the code behind it).