bug#48841: fido-mode is slower than ido-mode with similar settings

[Dmitry Gutov <dgutov@yandex.ru>]

[-- Attachment #1: Type: text/plain, Size: 3655 bytes --]

On 07.06.2021 11:52, João Távora wrote:

>     Maybe moving all of them to parameters and return values (making it a
>     static function and having the caller manage state) would help, I
>     haven't tried that exactly.
> 
> 
> Normally, in those adventures you end up with the same allocations 
> somewhere else, and uglier code. But you can try.

I have it a try, with little success (patch attached, for posterity). 
Since there's no multiple value returns in Lisp, I had to define a 
container for the three values.

The performance is basically the same, which seems to indicate that 
either Elisp has to allocate very little for a compiled lambda code, or 
it's optimized out (which would also make sense: the only thing 
necessary for it is a new container for the current scope).

>      > Might be noise, or you might be thrashing of CPU caches, who
>     knows? If
>      > the string length is on the same cache line as the contents of the
>      > string you're reading, then evicting that to go read the value of a
>      > boxed integer somewhere radically different is slow.
> 
>     But the string value is boxed as well, right? 
> 
> 
> The key is locality. If the string length and data happen to live nearby 
> in memory (in the same box, so to speak), there's a decent chance that 
> reading one brings the other into the cache, and you get a nice hit 
> depending on your subsequent operation.
> 
> Here I'm just speculating, as I said. In managed languages such as 
> Lisps, it's somewhat unpredictable. It's also always hardware dependent.
> Though given C/C++, a known processor and the right application, this 
> will make a world of a difference, and will yield truly "weird" results 
> (which arent weird at all after you understand the logic). Like, for 
> example a vector being much better at sorted insertion than a linked 
> list. (!) Look it up. Bjarne Stroustrup has one of those talks.

When you have to do some work, better memory locality can indeed change 
a lot. But in this case we have an already computed value vs. something 
the code still needs to compute, however fast that is.

Accessing function arguments must be currently much faster than looking 
up the current scope defined with 'let'.

Anyway, looking at what else could be removed, now that the extra 
allocation in 'match-data' is gone, what really speeds it up 2x-11x 
(depending on whether GC kicks in, but it more often doesn't), is 
commenting out the line:

   (setq str (copy-sequence str))

So if it were possible to rearrange completion-pcm--hilit-commonality 
not to have to modify the strings (probably removing the function 
altogether?), that would improve the potential performance of c-a-p-f 
quite a bit, for fido-mode and other frontends (depending on how much 
overhead the other layers add).

Ultimately, the scoring information doesn't have to live in the text 
properties. For sorting, the frontend could allocate a hash table, then 
ask the [backends? styles?] for completion scores on each item and sort 
based on that. Since faces are needed only for the completions that are 
currently displayed, even having to repeat the regexp matching stuff for 
each of them later would be no big deal performance-wise, compared to 
the current approach.

Anyway, these are musing for the much-discussed future iteration of the 
API. With the current version, and tied by backward compatibility, it 
might be possible to wring 10ms of improvement by consolidating text 
property changes somehow, but likely no more than that.

Looking forward for your analysis of fido-vertical-mode's performance 
improvement over the "normal" one.

[-- Attachment #2: completion-pcm-score-struct.diff --]
[-- Type: text/x-patch, Size: 4525 bytes --]

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index d5a0118b7c..0cb247fc19 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3485,6 +3485,7 @@ completion-pcm--hilit-commonality
     (let* ((re (completion-pcm--pattern->regex pattern 'group))
            (point-idx (completion-pcm--pattern-point-idx pattern))
            (case-fold-search completion-ignore-case)
+           (score (make-vector 3 0))
            last-md)
       (mapcar
        (lambda (str)
@@ -3531,37 +3532,17 @@ completion-pcm--hilit-commonality
                 ;;    (SUM_across_i(hole_i_contrib) + 1) * len
                 ;;
                 ;; , where "len" is the string's length.
-                (score-numerator 0)
-                (score-denominator 0)
-                (last-b 0)
-                (update-score-and-face
-                 (lambda (a b)
-                   "Update score and face given match range (A B)."
-                   (add-face-text-property a b
-                                           'completions-common-part
-                                           nil str)
-                   (setq
-                    score-numerator   (+ score-numerator (- b a)))
-                   (unless (or (= a last-b)
-                               (zerop last-b)
-                               (= a (length str)))
-                     (setq
-                      score-denominator (+ score-denominator
-                                           1
-                                           (expt (- a last-b 1)
-                                                 (/ 1.0
-                                                    flex-score-match-tightness)))))
-                   (setq
-                    last-b              b))))
+                )
+           (fillarray score 0)
            (while md
-             (funcall update-score-and-face from (pop md))
+             (completion-pcm--update-score-and-face str from (pop md) score)
              (setq from (pop md)))
            ;; If `pattern' doesn't have an explicit trailing any, the
            ;; regex `re' won't produce match data representing the
            ;; region after the match.  We need to account to account
            ;; for that extra bit of match (bug#42149).
            (unless (= from match-end)
-             (funcall update-score-and-face from match-end))
+             (completion-pcm--update-score-and-face str from match-end score))
            (if (> (length str) pos)
                (add-face-text-property
                 pos (1+ pos)
@@ -3570,10 +3551,35 @@ completion-pcm--hilit-commonality
            (unless (zerop (length str))
              (put-text-property
               0 1 'completion-score
-              (/ score-numerator (* end (1+ score-denominator)) 1.0) str)))
+              (/ (completion-pcm--score-numerator score)
+                 (* end (1+ (completion-pcm--score-denominator score)))
+                 1.0)
+              str)))
          str)
        completions))))
 
+(cl-defstruct (completion-pcm--score (:type vector))
+  (numerator 0) (denominator 0) (last-b 0))
+
+(defun completion-pcm--update-score-and-face (str a b score)
+  "Update score and face in STR given match range (A B)."
+  (add-face-text-property a b
+                          'completions-common-part
+                          nil str)
+  (let ((last-b (completion-pcm--score-last-b score)))
+    (setf (completion-pcm--score-numerator score)
+          (+ (completion-pcm--score-numerator score) (- b a)))
+    (unless (or (= a last-b)
+                (zerop last-b)
+                (= a (length str)))
+      (setf (completion-pcm--score-denominator score)
+            (+ (completion-pcm--score-denominator score)
+               1
+               (expt (- a last-b 1)
+                     (/ 1.0
+                        flex-score-match-tightness)))))
+    (setf (completion-pcm--score-last-b score) b)))
+
 (defun completion-pcm--find-all-completions (string table pred point
                                                     &optional filter)
   "Find all completions for STRING at POINT in TABLE, satisfying PRED.
@@ -3980,7 +3986,7 @@ completion-flex-all-completions
                   string table pred point
                   #'completion-flex--make-flex-pattern)))
       (when all
-        (nconc (completion-pcm--hilit-commonality pattern all)
+        (nconc (benchmark-progn (completion-pcm--hilit-commonality pattern all))
                (length prefix))))))
 
 ;; Initials completion