Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bitmask-based change tracking #1922

Closed
Rich-Harris opened this issue Dec 28, 2018 · 9 comments
Closed

Bitmask-based change tracking #1922

Rich-Harris opened this issue Dec 28, 2018 · 9 comments

Comments

@Rich-Harris
Copy link
Member

Rich-Harris commented Dec 28, 2018

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.

@Rich-Harris Rich-Harris added this to the 3.x milestone Dec 28, 2018
@tivac
Copy link
Contributor

tivac commented Dec 28, 2018

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
Copy link
Member Author

@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
Copy link
Contributor

tivac commented Dec 29, 2018

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
Copy link
Member Author

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
Copy link
Contributor

ekhaled commented Dec 29, 2018

Hmmm...
capture _2018-12-29-02-41-31

@Rich-Harris
Copy link
Member Author

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

image

@ekhaled
Copy link
Contributor

ekhaled commented Dec 29, 2018

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

@Rich-Harris Rich-Harris removed this from the 3.x milestone Jan 15, 2019
@trueadm
Copy link
Contributor

trueadm commented Jan 20, 2019

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).

@Rich-Harris
Copy link
Member Author

Closing as this was implemented in #3945 — Svelte components are now a little bit smaller and a little bit faster

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants