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

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

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

So, I benchmarked before and after this patch to icomplete.el:

    diff --git a/lisp/icomplete.el b/lisp/icomplete.el
    index 08b4ef2030..3561ebfa04 100644
    --- a/lisp/icomplete.el
    +++ b/lisp/icomplete.el
    @@ -858,16 +858,8 @@ icomplete-completions
                    ;; removing making `comps' a proper list.
                    (base-size (prog1 (cdr last)
                                 (if last (setcdr last nil))))
    -               (most-try
    -                (if (and base-size (> base-size 0))
    -                    (completion-try-completion
    -                     name candidates predicate (length name) md)
    -                  ;; If the `comps' are 0-based, the result should be
    -                  ;; the same with `comps'.
    -                  (completion-try-completion
    -                   name comps nil (length name) md)))
    -               (most (if (consp most-try) (car most-try)
    -                       (if most-try (car comps) "")))
    +               (most-try nil)
    +               (most "")
                    ;; Compare name and most, so we can determine if name is
                    ;; a prefix of most, or something else.
                    (compare (compare-strings name nil nil

The patch itself nullifies the calculation of the 'determ' thing that I
and presumably some other users don't value that much.  It doesn't
affect fido-mode's basic funcionality.

How did I benchmark?  Well, to measure the delay the user experiences
until all completions are presented I had to take out the
`while-no-input` in icomplete-exhibit so that this test would work:

    ;; After the form, type C-u C-x C-e C-m in quick succession
    (benchmark-run (completing-read "bla" obarray))

If I don't remove this `while-no-input`, icomplete will not lose time
showing all the completions and will instead select just the first one.
That's a very nice feature for actual use, but for this benchmark that
is not what I want: I want to measure the time to show all the
completions.

Then, the times presented by benchmark-run are the same that the user
sees if he waits to see the completions.  Now the values:

Before my patch:

    (1.802209488 5 1.3678843490000077)
    (1.609066281 4 1.1170432569999775)
    (1.878972079 5 1.3725165670000479)
    (1.901952581 5 1.3979494059999524)
    (1.820800064 5 1.3283940110000003)

After the patch:

    (0.552051921 1 0.3079724459999511)
    (0.58396499 1 0.3038616050000087)
    (0.861106587 2 0.6046198220000178)
    (0.611551175 1 0.30275532399997473)
    (0.62500199 1 0.3160454470000218)

Without the patch but with icomplete-vertical-mode:

    (0.645366711 1 0.3412892389999911)
    (0.6256968110000001 1 0.3234302760000105)
    (0.9716317630000001 2 0.6676939319999633)
    (0.6414442749999999 1 0.3325084230000357)
    (0.627684562 1 0.32241421699995954)

João