Optimize based on w3c/respec#453

[domenic]

See @Joris-van-der-Wel's comments in https://github.com/w3c/respec/issues/453#issuecomment-115999039. Ideas:

• NamedPropertiesTracker is using getOwnPropertyDescriptor, which is known to be pretty slow. Maybe we can store these guys elsewhere, in some side table on the object, instead of as properties of the relevant getter function?
• compareDocumentPosition is implemented pretty naively per spec and maybe could be optimized. Although, why is the test case calling it so much? Maybe the test case is calling Node.prototype.contains, which delegates to compareDocumentPosition, but could probably be implemented in a faster way?

[Joris-van-der-Wel]

The reason NamedPropertiesTracker.prototype.maybeUntrack() is so slow is actually because it needs to walk the document to see if a property can really be removed. Walking the document is also what makes compareDocumentPosition so slow.

So basically 90% of the time (in that test), jsdom is walking the document

[domenic]

I don't see any document-walking in https://github.com/tmpvar/jsdom/blob/54c2ed4cb7eaa3cdf9798b052ed79641f26f3e9d/lib/jsdom/named-properties-tracker.js#L66 ...

[domenic]

Oh, it's in this.object[name], isn't it.

[Joris-van-der-Wel]

Oh btw, if anyone wants to generate a profile: https://gist.github.com/Joris-van-der-Wel/4705395c018f12053968

NamedPropertiesTracker could be improved by tracking all id's and name's in a map for the entire document.

I don't see any document-walking in https://github.com/tmpvar/jsdom/blob/54c2ed4cb7eaa3cdf9798b052ed79641f26f3e9d/lib/jsdom/named-properties-tracker.js#L66 ...

https://github.com/tmpvar/jsdom/blob/54c2ed4cb7eaa3cdf9798b052ed79641f26f3e9d/lib/jsdom/living/named-properties-window.js#L51

[Joris-van-der-Wel]

A solution for both issues:

1. Whenever a Node is inserted or removed, store the node index (the number of preceding siblings)
2. Store an id to Element map in Document (this already exists)
3. Store a name to Set<Element> map in Document

Step 1 is used in both compareDocumentPosition and NamedPropertyTracker. Step 2 and 3 only in NamedPropertyTracker.

You can then implement node.compareDocumentPosition(other) like this:

1. Generate an array of inclusive ancestors of both node and other. E.g. nodeAncestors and otherAncestors
2. If the root node (index 0 in both lists) are not equal, return the DISCONNECTED position.
3. If node is present in the list of otherAncestors (excluding the last index), the position has CONTAINED_BY
4. If other is present in the list of nodeAncestors (excluding the last index), the position has CONTAINS
5. Loop through both nodeAncestors and otherAncestors at the same time and compare the node index in every step. If otherIndex < nodeIndex the position is PRECEDING and break the loop. If nodeIndex > otherIndex the position is FOLLOWING and break the loop.

So instead of walking over a lot of nodes (followingOrPreceding()), we only walk the ancestors. This means the performance is more constant for huge documents.

The NamedPropertyTracker's resolve function for window is then modified:

1. Instead of walking the entire tree: Create a list that contains elements with the proper id or name; using the two maps
2. For each node, create a list of node indexes of inclusive ancestors
3. By comparing these lists the nodes can be sorted, this ensures the nodes are in tree order.
4. Filter the nodes using the rules of named properties on window

[Joris-van-der-Wel]

The final solution is a bit different than discussed here, but both major bottlenecks have been fixed.

I just reran the test and jsdom 5.6.1 takes 72 seconds. The master branch takes 8 seconds.

cc @rubys @darobin

[darobin]

Wicked cool!

[domenic]

@Joris-van-der-Wel mind running a profile again and finding what our biggest time-sinks are with the current release? 8 seconds is still nontrivial.

Alternately if you don't think there's too much to be gained from this test case in particular, we can close this issue.

[Joris-van-der-Wel]

The runtime has gone up a fair bit since the whatwg-url stuff (cc @Sebmaster).
On my laptop it takes about 32 seconds.

Here are some bottlenecks:

1. URLStateMachine::setTheInput 35% (triggered by setAttribute())
2. HTMLAnchorElement::init() -> browser/resource-loader::getDocumentBaseUrl() -> getElementsByTagName("base") occurs a lot. This could be completely optimized away. 30%
3. Node::get tagName(). 6% This is most often used by FilterByTagName(). I am guessing the constant upper casing is causing this.
4. new URLStateMachine() 6%
5. getElementsByTagName() 6% (excluding internal usage)
6. GC 3%
7. getElementsByClassName 3%

[Sebmaster]

Damn, setTheInput contains a try-catch to deal with invalid URLs 😕
That might be the cause of the trashed perf, but it'll probably get fixed when jsdom/whatwg-url#14 lands... I'll try to get it done this week.

[domenic]

The base URL caching seems like lower-hanging fruit to be honest.

[Joris-van-der-Wel]

whatwg-url is only used in HTMLAnchorElement to make sure the href content/IDL attribute is correct, right? Is there a reason why this must be done eagerly (when changing the attribute)?

[Sebmaster]

It also handles all the other attributes URLUtils provides (i.e. hostname, port, etc.).

Is there a reason why this must be done eagerly (when changing the attribute)?

I don't think so, we should be able to provide this lazily, although I'm not sure if we want to put this into whatwg-url (I'd rather not), or wrap the accessors in jsdom.

[domenic]

Right, the problem I think is that whatwg-url is implemented according to spec, which is not lazy. But, browsers implement this lazily (according to a recent comment on whatwg/url).

I think it would be reasonable for whatwg-url to either be lazy by default or implement a lazy-mode (I'm thinking, mixinURLUtils takes a "getTheInput" callback?). It would not be observably different in any way you could expose from the outside interface. But, up to you @Sebmaster.