982322 - Improve template.js performance

Status: RESOLVED FIXED

(DevTools Graveyard :: WebIDE, defect)

Description

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

template.js currently slows down quite a lot when faced with many (>1000) nodes to deal with.

While Paul may indeed kill it off in the UI rewrite, I've found quite a few easy performance wins we can use right now.  This is more important in support of bug 943251, as listing out all the prefs adds many more nodes than template.js dealt with before.

Comment 1

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 1: Use a resolver object to only descend once

Comment 2

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 2: Use the resolver to compute root path

Comment 3

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 3: Resolver iterates faster without for ... of

Comment 4

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 4: Process tree without for ... of

Comment 5

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 5: Save paths on each node

Comment 6

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 6: Delay node registrations

Comment 7

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 1: Use a resolver object to only descend once

This creates a Resolver object that navigates the object store once for movement down the tree, instead of navigating the store from root for every lookup.

The test change only removes the trailing "." from the stored "rootPath" attribute, which is unnecessary.

For the case of loading prefs from a device, this change takes us from 825ms to 639ms (23% improvement).

Comment 8

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 2: Resolver iterates faster without for ... of

Switching back to a "regular" for loop takes prefs load time from 639ms to 505ms (38% improvement overall).

Comment 9

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 3: Process tree without for ... of

Similar to the last patch, using regular loops over the tree improves loading prefs from 505ms to 450ms (45% improvement overall).

Comment 10

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 4: Save paths on each node

This is the largest improvement here.  It changes an O(N^2) algorithm to O(N), by storing a node's paths on the element, instead of just looping over all possible paths for all changed nodes.

This takes removing all prefs from 2963ms to 20ms (99.3% improvement / 150x faster).

Comment 11

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Attachment: Part 5: Delay node registrations

This delay tracking nodes until the last step during changes, which avoid double work (as I commented in the patch).  For loading prefs, this takes us from 440ms to 200ms (76% improvement overall / 4x faster).

Comment 12

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

Try: https://tbpl.mozilla.org/?tree=Try&rev=ca34af7a645f

Comment 13

[Alexandre Poirot [:ochameau]]

Comment on attachment 8392347 [details] [diff] [review]
Part 1: Use a resolver object to only descend once

Review of attachment 8392347 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry for the review delay, I got some review overflow sickness!

Nice abstraction!

::: browser/devtools/app-manager/content/template.js
@@ +362,5 @@
> +      return obj;
> +    }
> +    let chunks = path.toString().split(".");
> +    for (let word of chunks) {
> +      if ((typeof obj) == "object" &&

nit: Not your code, but may be `typof(obj) == "object"` would be just easier to read.

Comment 14

[Alexandre Poirot [:ochameau]]

Comment on attachment 8392353 [details] [diff] [review]
Part 2: Resolver iterates faster without for ... of

Review of attachment 8392353 [details] [diff] [review]:
-----------------------------------------------------------------

What?! really... that's scary!

Comment 15

[Alexandre Poirot [:ochameau]]

Comment on attachment 8392356 [details] [diff] [review]
Part 3: Process tree without for ... of

Review of attachment 8392356 [details] [diff] [review]:
-----------------------------------------------------------------

Ok.. ok...
Then I'm wondering... don't you save some cycles by also caching the array length?

Comment 16

[Alexandre Poirot [:ochameau]]

Comment on attachment 8392362 [details] [diff] [review]
Part 4: Save paths on each node

Review of attachment 8392362 [details] [diff] [review]:
-----------------------------------------------------------------

I don't really get these two patches, nor do I get template,
but that looks good and I gave a try to these patches and that's fast!

Comment 17

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

(In reply to Alexandre Poirot (:ochameau) from comment #15)
> Comment on attachment 8392356 [details] [diff] [review]
> Part 3: Process tree without for ... of
> 
> Review of attachment 8392356 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Ok.. ok...
> Then I'm wondering... don't you save some cycles by also caching the array
> length?

This (thankfully...) makes no perceivable difference.  But it's a good thought, it occurred to me as well. :) We must already optimize for this, or the length is not long enough for it to matter here.

Comment 18

[Carsten Book [:Tomcat]]

pushed to m-i as

https://hg.mozilla.org/integration/mozilla-inbound/rev/9d661be98d68
https://hg.mozilla.org/integration/mozilla-inbound/rev/67c3aebfa9ed
https://hg.mozilla.org/integration/mozilla-inbound/rev/8e6267048082
https://hg.mozilla.org/integration/mozilla-inbound/rev/c2b0efd466d4
https://hg.mozilla.org/integration/mozilla-inbound/rev/b45284fa40fe

Comment 19

[Carsten Book [:Tomcat]]

ups was to fast with closing as fixed since this landed only on m-i so far, sorry

Comment 20

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/b45284fa40fe
https://hg.mozilla.org/mozilla-central/rev/c2b0efd466d4
https://hg.mozilla.org/mozilla-central/rev/8e6267048082
https://hg.mozilla.org/mozilla-central/rev/67c3aebfa9ed
https://hg.mozilla.org/mozilla-central/rev/9d661be98d68

Comment 21

[Paul Rouget [:paul]]

> This takes removing all prefs from 2963ms to 20ms (99.3% improvement / 150x faster).

Well, fuck me.