A forest of trees!

[matatk]

Right, I defo want to move to using a tree to display the landmarks (and ultimately headings) (#238). (That could also be used to display enhanced info in DevTools.)

Also, have been thinking more about this recently, but it's very important to ensure the extension is as efficient as possible, not just in terms of how the user feels (which I think is likely to be pretty good now) but also in ensuring it uses the least CPU time, and therefore also energy, possible. I think it's worth trying out a tree-based approach, in which only subtrees of the DOM are scanned when relevant mutations happen. However, some concerns:

• How efficiently can we find out the nearest parent landmark of a mutation? Thinking on it, we could rely on the DOM to help out here, tagging landmark elements as such using data-* attributes. That should help make an efficient tree/mapping to store the landmarks, and allow us to only scan and refresh the parts of the document that changed.
• Bootstrapping—can the full-scan tree and mutated DOM go out-of-synch easily? (I think this is quite possible, but unlikely, but need to check.)
• When is the best time to do this—now, creating some headroom for when headings come in, or after headings have been added, to presumably more accurately gauge how well it works (OK, I guess this will improve performaance and the numbers will be bigger and more exciting later, but some of this stuff, at least, needs doing in order to support scanning for headings anyway).

My assumption is it would be worthwhile to move to:

• A tree for display (sorta required when headings come in).
• A tree structure for storing the results and scoping mutations. Given that there will need to be a separate mapping from values of the data-* attributes in the DOM to the actual elements in memory, I think this means the landmarks tree can be a plain JS object, rather than a custom class.
• Scanning only subtrees of the DOM in response to mutations, where possible.

How to get there (and check that getting there is a good idea)?

Test current performance

• The profiling script is already good (#365), but depending on how long the tests will take (i.e. the pages being tested will change over several days), it could be useful to add an option to save the page locally.
• Need some way of taking a page and randomly applying mutations, like adding/removing elements and other simpler changes that wouldn't affect landmarks.
  • This could be done by separating out the landmarks-finding and mutation-observing code and importing them into a simpler content script, designed to be run in an automated browser for testing purposes.
  • The tests would involve loading a page, then picking random elements and random mutating operations in order to check whether this approach really saves time.
• Alternatively, or in addition: metrics (e.g. overall scan time, or number of elements visited during all the scans) that could run in the background whilst browsing the web might be helpful, as it would be more reflective of the real world, and could be run passively.
• Blue sky: how about somehow highlighting on the page (or in DevTools) when and where mutations happen?
  • Warning: Could cause flashes.

Move to a tree-based data structure

This would make rendering easier. The current DOM walk guarantees DOM order, which is nice and simple. Was thinking of using querySelectorAll() but not sure if that guarantees the order, and it would involve even bigger code changes. Can always try it later.

In order to be useful for finding the closest parent landmark to an element where a mutation has happened, we need to:

1. Find the nearest parent landmark to a mutation (which could be the element that was mutated). This can be done in the DOM using data-* attributes.
2. Map the looked-up custom attribute value to an actual in-memory HTML element—or (sub-)root of a landmarks JS object tree.
3. Scan the document from that point down.
4. Replace that (sub-)tree of landmark results.
5. Send the whole lamdmarks tree to be rendered (later: this can be refined to only re-render what's needed).

Seems we need:

1. Custom data-* attributes.
2. A map from data-* attribute value to JS object that stores a (sub-)tree.
3. A root JS object that stores all the landmarks.

It's possible to get a reference to the JS object so this is sounding do-able!

Steps

1. Check that the idea of using the DOM, an attribute-value-to-subtree mapping and replacing parts of the tree actually works (quick prototype).
2. Test the current performance.
3. Move to using trees and check the performance.

Things that could build on this in future (some mentioned above):

• If the performance is much greater, the threshold for skipping mutations for a full scan later may be reduced.
• Could test whether object or Map is better for the mapping part.

And much later, or "if there's time" :-)...

• Test if a custom tree class, or using objects, is more efficient.
• Could later do rendering based on changes only.
• Highlight mutations on the page.
  • Warning: Could cause flashes.
• This could, in the far future, tie into the nascant <iframe> support currently being tested (#370) but due to the nature of the extensions APIs, this would require non-trivial additional code in order to discover the relationship between the frames, so I'm not planning this at the moment.

[matatk]

Was thinking that one way to test the performance both simply and cross-browser would be to look at the number of document nodes visited when using the tree-based approach above, and not. This would eliminate the need to test in real browsers, and make the results more portable.

I've just come across other ways to traverse the DOM: NodeIterator and TreeWalker. These could be really interesting and reduce the code needed in Landmarks (and maybe negate the need the the approach above) but to measure their performance IRL the tests would have to be done... IRL.

(I did find a gist about the performance of TreeWalker, but it's not current.)

So... still thinking on how to orchestrate the test harness.

[matatk]

The fundamental question around whether it's worth changing approach so radically is how to cope with mutation guarding: will this be fast enough such that full-page scans are never needed? I can't imagine so, because some pages will change loads, and those mutations need to be ignored.

So the threshold for ignoring mutations would be made a lot more permissive (but maybe with a much stronger back-off), and the question becomes: is scanning only the part of the documented that was mutated, but more times, more efficient than scanning the whole document far fewer times?

PRs #407 and #408 have developed the profiling more (and now Firefox is supported experimentally by Puppeteer—exciting!) Was thinking that now multiple LandarksFinders are sort-of supported (they are, but it's hardcoded in #410) it would be interesting to run a full-page and tree-based scanner at once and check the stats in the DevTools about how they're working. But that does require having at least prototyped the tree-based one, and that requires time that would ideally need to be justified by clear, or very strongly expected, performance gains...