Firefox: Link hints slow (and maybe broken?)

[smblott-github]

It looks like the approach we use for finding clickable elements in Chrome might be too slow in Firefox.

1. Go to this page.
2. Scroll down until just one or two links become visible at the bottom of the page.
3. Hit f.

Observe that this is "fast" with Chrome, but really quite slow with Firefox.

The problem seems to be the loop here where we iterate over every element.

The significance of the test is that it's a big, single-framed page with very few clickable things visible; so the cost must be coming from the indicated loop (I think).

Separately, I think I got into a situation in which, after scrolling quite some way down, link hints failed to open at all. However, I haven't reproduced that case.

[mrmr1993]

The problem seems to be the loop here where we iterate over every element.

Recall my PR for that code (#1355), where we discussed this extensively. I've tried several times to improve the performance of link hints while keeping the behaviour, but I've never been able to beat the status quo.

The problem is, we can't tell if an element will be rendered inline in the DOM, because we don't have access to the CSS we need:

• we can't (reliably) extract information from stylesheets using the CSSStyleSheet API, because their are cross-origin restrictions, and they don't seem to be relaxed for extensions; and
• it's even more expensive to use window.getComputedStyle than it is to call Element.getClientRects, so we avoid it whenever we can.

So we end up essentially doing a render of the whole page (or, actually, getting the browser to), just to work out what's in the viewport. The browser already has this information we want (render tree+layout for the current screen), since it uses it to paint the screen. Maybe we can just ask them nicely for an extension API?

[smblott-github]

Yes, @mrmr1993. That's a pretty good summary of where we stand.

I just tried Vimperator. With the experiment described in the first post here, Vimium seems to take 2-3 seconds (for me). Vimperator takes less than one second.

[lydell]

VimFx is also fast on the test page, so it definitely can be done fast in Firefox. Not sure how the VimFx algorithms translate to a web extension, though.

[hoelzro]

I don't know if anyone's still interested in this issue, but I took a look at it to see if I could make any progress. I hit a dead-end, but I thought I'd share what I found in case someone else can get further based on my work.

The page I used for testing was https://kubernetes.io/docs/reference/generated/kubernetes-api/v1.24/ - it takes something like 2 seconds to show link hints on my laptop.

I looked at getLocalHints, and tried using the Range API to see if I could use it to get getAllElements to collect only elements within the current browser viewport - I ended up with something like this:

diff --git content_scripts/link_hints.js content_scripts/link_hints.js
index d6b06e74..a6e883fb 100644
--- content_scripts/link_hints.js
+++ content_scripts/link_hints.js
@@ -1059,7 +1059,18 @@ var LocalHints = {
       return elements;
     };

-    const elements = getAllElements(document.documentElement);
+    // XXX rob's dumb experiment (might not work since the contents are cloned, but maybe we can tie them back to the originals if that's the case?)
+    let range = document.createRange();
+    let viewportUpperLeft = document.caretPositionFromPoint(0, 0);
+    let viewportLowerRight = document.caretPositionFromPoint(window.innerWidth - 1, window.innerHeight - 1);
+    range.setStart(viewportUpperLeft.offsetNode, viewportUpperLeft.offset);
+    range.setEnd(viewportLowerRight.offsetNode, viewportLowerRight.offset);
+    let visibleDocumentFragment = range.cloneContents();
+    let startTime = new Date();
+    const elements = getAllElements(visibleDocumentFragment);
+    let endTime = new Date();
+    console.log(`Collected ${elements.length} elements in ${endTime - startTime}ms`);
     let visibleElements = [];

     // The order of elements here is important; they should appear in the order they are in the DOM, so that

This //does// collect much fewer elements much more quickly - but sadly since the elements that end up in visibleElements are part of a cloned DocumentFragment, none of them are picked up as visible by getVisibleClickable.

I pivoted to manually recursing through the DOM, starting at range.commonAncestorContainer and using range.intersectsNode to prune elements outside of the range - sadly, this takes waaaay too long (something like 8 seconds on my laptop).

Anyway, that's as far as I got - hopefully someone with more knowledge will see this and be able to pick up the trail!