Optimize DOM traversal

[qsantos]

Hi again @m1L!

Following my last comment on #40, I took a look at the DOM traversal logic. It looked like calling node.nextSibling was costing a significant amount of time. With some Stack Overflow sleuthing and random keyword googling, I learned that there is actually an API for this: TreeWalker! By using NodeFilter.SHOW_TEXT, we can quickly select the text nodes.

The issue is that this breaks the filtering on ancestor nodes. We could use the filter argument of TreeWalker, but this is slow. Or call hasParentEditableNode, but this is even slower. So I have used another approach: when starting a traversal, I first list all the nodes that should be excluded, using CSS selectors; then, during the traversal, I check whether the text node's parent is in the exclusion list. It seems to work pretty well.

After doing that, there was a significant amount of time spent on node.parentNode. This was needed, since we cannot list text nodes directly from the CSS selectors, so we need to check whether each text node's parent is in the exclusion list. However, I also learned about XPathEvaluator, which is similar to CSS selectors, but allow us to select text nodes directly. I was able to replace CSS selectors and get rid of node.parentNode.

However, XPathEvaluator is slower than CSS selectors, so both approaches are roughly as efficient. I have kept both commits in the history, so that we can go back to CSS selectors if it turns out they are better.

---

I have also added some (manual) tests to index.html for this. The mutation observer should also handle the insertion of text nodes, not just of element nodes.

---

With this, the Web version of From the Earth to the Moon goes from taking 174 ms to only 106 ms. The text version goes from 298 ms to 279 ms, but I think it might just be noise.

Before:

After:

Most of the remaining time is spent in exec(…) and in the calls to toLocaleString(…). For the first one, merging all the replace* functions into one, and using a single pass with a single regular expression should gain us some performance. For the second one, the main point is related to #41.

[m1l]

@qsantos Choose the one that you think is the best as you are much further ahead with this. It's good that there are options.

I don't know if this would make difference by using these approaches, but one thing I failed in my approach is inserting nodes while traversing and updating units. I think that an ultimate goal (which is also suggested in one of the opened issues) is to be able to have an option to replace all imperial units completely (once we are certain it works well), and then have original unit available in a tooltip on hover of the converted unit.

Some will still prefer seeing both and will probably trust it more with all the mess in how imperial units are used (especially when shopping for something that a critical fit, to be able to verify using both units), but most will probably opt into just seeing international units.

[qsantos]

At a later point, I will investigate simply setting innerHTML to insert new element nodes. Surprisingly, it can actually be faster to generate HTML and let the browser handle it than use many calls to document.createElement and node.appendChild. Of course, it might depend on the situation and may not even be true anymore, so I will have to do some benchmarks. Yay! :tada: