hint-mode performance

[aadcg]

Commit b43ec71 introduced a considerable performance penalty when invoking follow-hint. To confirm the claim, invoke the command over https://en.wikipedia.org/wiki/List_of_municipalities_in_Quebec and notice that the time to draw the hints is impacted by a factor of ~ 2.

Requires revisiting the #3001 thread.

Indicates that performance benchmarks are needed as to access how the addition of a feature impacts performance. In this case, the benchmark entails writing a mock HTML document with thousands of links and outputting the time it takes for the renderer to draw the hints.

@heiwiper if you have a suspicion of where the performance penalty might be coming from, please share. Thanks!

[heiwiper]

I will try to look into this later today or tomorrow.

[heiwiper]

What's your workflow for getting benchmarks of commands ?

I'm trying to use time macro but I can't figure out how to execute commands from the REPL without getting a debugger error. Here's what I'm trying to do:

1. Start compiled nyxt binary.
2. Start Slynk server and connect to it from SLY.
3. Call (time (nyxt/mode/hint:follow-hint)) from SLY REPL.

Tried to invoke the prompt buffer (Interact with element) when non-interactive.
   [Condition of type PROMPT-BUFFER-NON-INTERACTIVE]

Restarts:
 0: [PROMPT-ANYWAY] NYXT::PROMPT-ANYWAY
 1: [CANCEL] NYXT::CANCEL
 2: [RETRY] Retry SLY mREPL evaluation request.
 3: [*ABORT] Return to SLY's top level.
 4: [ABORT] abort thread (#<THREAD tid=92841 "sly-channel-1-mrepl-remote-1" RUNNING {100B69E533}>)

I'm pretty sure there's something I'm missing here that would allow me to execute commands from the REPL. But I can't figure out what is it.

[aadcg]

@heiwiper unfortunately you can't use time because the moment when follow-hint returns doesn't match the moment when the hints are drawn by the renderer. You can use a stopwatch though, even without it, it is noticeable.

As for the other question, you can call the command from the REPL via (let ((*interactive-p* t)) (nyxt/mode/hint:follow-hint)), or choose the following restart 0: [PROMPT-ANYWAY] NYXT::PROMPT-ANYWAY.

I didn't investigate, but my educated guess is that the change from nyxt/ps:qsa to nyxt/ps:rqsa is responsible.

[heiwiper]

I didn't investigate, but my educated guess is that the change from nyxt/ps:qsa to nyxt/ps:rqsa is responsible.

You're probably right, I was looking for a way to get some kind of profiler data so I can get an idea about which part of the algorithm is causing the performance issue.

As far as I remember the process is almost the same as qsa unless there's a shadow root element. Which is not the case for the web page you have tested.

I will look more into this issue, you can leave it to me if you don't mind.

[aadcg]

As far as I remember the process is almost the same as qsa unless there's a shadow root element. Which is not the case for the web page you have tested.

Indeed, this is what must be fixed. Supporting shadow root elements can't impact performance for the case when none exist.

I will look more into this issue, you can leave it to me if you don't mind.

I'd be happy if you'd able to take a look, but no pressure!

[heiwiper]

I would like to update you on the progress I have made so far. I did look into the code, and tried some combinations. Apparently the hinting is slowed down by the parenscript macros rqsa (as you have guessed) and rqs-nyxt-id.

Indeed, this is what must be fixed. Supporting shadow root elements can't impact performance for the case when none exist.

I think the flet part might be the cause for the issue here. I'm not very familiar with parenscript but I imagine the macro would try to define the function on every call which results in considerable delay when called in a loop which is the case.

For now what I will try to do is refactor these two macros to separate the flet function into it's own parenscript macro. The obstacle here is the recursive nature of the function which causes a compilation error when evaluating the macro. So I will try to make the recusrive function into a non-recursive one to avoid this issue.

[aadcg]

@heiwiper thanks for the update. I think you are correct.

[heiwiper]

Hello André,
I have modified the two parenscript macros as I have previously mention by separating the recursive part in a dedicated macro and removing recursivity that was causing a parenscript compilation error. I have also spotted another inneficient part in the algorithm which was going through all document nodes instead of only shadow root nodes.

Apparently the performance issue has not been resolved yet, although I think I am getting close to identifying the root cause. Notice the call to the parenscript macro rqs-nyxt-id which is inside a loop in the following diff which is part of b43ec71 :

   (let ((fragment (ps:chain document (create-document-fragment)))
         (hints (ps:lisp (list 'quote hints)))
-        (i 0))
-    (dolist (element (nyxt/ps:qsa document "[nyxt-hintable]"))
-      (let ((hint (aref hints i)))
+        (nyxt-identifiers (ps:lisp (list 'quote nyxt-identifiers))))
+    (dotimes (i (length hints))
+      (let* ((hint (aref hints i))
+             (nyxt-identifier (aref nyxt-identifiers i))
+             (element (nyxt/ps:rqs-nyxt-id document nyxt-identifier)))
         (ps:chain element (set-attribute "nyxt-hint" hint))
         (ps:chain fragment (append-child (create-hint-overlay element hint)))
         (when (ps:lisp (show-hint-scope-p (find-submode 'hint-mode)))
-          (ps:chain element class-list (add "nyxt-element-hint")))
-        (setf i (1+ i))))
+          (ps:chain element class-list (add "nyxt-element-hint")))))
     (ps:chain document body (append-child fragment))
     ;; Returning fragment makes WebKit choke.
     nil))

I am suspecting this to be causing an overhead in the display of hint overlays. I will investigate further and keep you updated.

Here are the changes that I have made and which I have mentioned above :

 (defpsmacro rqs-nyxt-id (context id)
   "Recursive version of `qs-nyxt-id` which goes through Shadow DOMs if there's
 at least one."
-  `(flet ((recursive-query-selector (context selector)
-            (let ((node (qs context selector)))
-              (if node
-                  node
-                  (let ((node-iterator (chain document (create-node-iterator context (@ *node #:|ELEMENT_NODE|))))
-                        current-node)
-                    (loop while (and (setf current-node (chain node-iterator (next-node))) (not node))
-                          do (when (@ current-node shadow-root)
-                               (setf node (recursive-query-selector (@ current-node shadow-root) selector))))
-                    node)))))
-     (if (chain ,context (query-selector "[nyxt-shadow-root]"))
-         (recursive-query-selector ,context (stringify "[nyxt-identifier=\"" ,id "\"]"))
-         (qs-nyxt-id ,context ,id))))
+  `(if (chain ,context (query-selector "[nyxt-shadow-root]"))
+       (recursive-query-selector ,context (stringify "[nyxt-identifier=\"" ,id "\"]"))
+       (qs-nyxt-id ,context ,id)))
+
+(defpsmacro recursive-query-selector (context selector)
+  `(let ((node (qs ,context ,selector))
+         (shadow-roots (chain *array (from (qsa ,context "[nyxt-shadow-root]"))))
+         shadow-root)
+     (do ((i 0 (1+ i)))
+         ((or node
+              (>= i (chain shadow-roots length))))
+       (setf shadow-root (chain (ps:elt shadow-roots i) shadow-root))
+       (chain shadow-roots push (apply shadow-roots (ps:chain *array (from (qsa shadow-root "[nyxt-shadow-root]")))))
+       (setf node (qs shadow-root ,selector)))
+     node))

 (defpsmacro rqsa (context selector)
   "Recursive version of context.querySelectorAll() which goes through
 Shadow DOMs if there's at least one."
-  `(flet ((recursive-query-selector-all (context selector)
-            (ps:let ((nodes (ps:chain *array (from (nyxt/ps:qsa context selector))))
-                     (node-iterator (ps:chain document (create-node-iterator context (ps:@ *node #:|ELEMENT_NODE|))))
-                     current-node)
-              (ps:loop while (ps:setf current-node (ps:chain node-iterator (next-node)))
-                 do (ps:when (ps:@ current-node shadow-root)
-                      (ps:chain *array prototype push (apply nodes (recursive-query-selector-all (ps:@ current-node shadow-root) selector)))))
-              nodes)))
-     (if (chain ,context (query-selector "[nyxt-shadow-root]"))
-         (recursive-query-selector-all ,context ,selector)
-         (qsa ,context ,selector))))
+  `(if (chain ,context (query-selector "[nyxt-shadow-root]"))
+       (recursive-query-selector-all ,context ,selector)
+       (qsa ,context ,selector)))
+
+(defpsmacro recursive-query-selector-all (context selector)
+  `(let ((nodes (chain *array (from (nyxt/ps:qsa ,context ,selector))))
+         (shadow-roots (chain *array (from (nyxt/ps:qsa ,context "[nyxt-shadow-root]")))))
+     (dolist (shadow-root shadow-roots)
+       (chain shadow-roots push (apply shadow-roots (chain *array (from (nyxt/ps:qsa (chain shadow-root shadow-root) "[nyxt-shadow-root]"))))))
+     (dolist (shadow-root shadow-roots)
+       (chain nodes push (apply nodes (chain *array (from (nyxt/ps:qsa (chain shadow-root shadow-root) ,selector))))))
+     nodes))

Let me know if you would like me to open a WIP PR for this issue to commit these changes.

[aadcg]

@heiwiper great work! Yes, please open a draft PR :)

[aadcg]

In case fixing this issue drags for some time, we should consider dropping shadow DOM support. Do you agree @jmercouris?

@heiwiper do not feel pressured to work on #3269. At the end of day, it's our responsibility and we're just being pragmatic.

[jmercouris]

I can agree with that, if the performance gain is significant enough.

[heiwiper]

@heiwiper do not feel pressured to work on #3269. At the end of day, it's our responsibility and we're just being pragmatic.

Thanks for your consideration I really appreciate it. Nyxt gives me the opportunity to contribute to Open Source so it never felt like a burden. It's the exact opposite, I feel motivated to contribute more especially when I notice that all of my contributions made it in the master branch.

I will continue working on this issue if you don't mind, and in the worst case scenario we would both work on it and figure out at least one solution to solve it :D

[aadcg]

I can agree with that, if the performance gain is significant enough.

It is very significant. If this issue will persist in the next 3-series release (the most likely outcome), I'll revert it.