GNU bug report logs - #48841
fido-mode is slower than ido-mode with similar settings

Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.

Package: emacs; Reported by: Dmitry Gutov <dgutov@HIDDEN>; dated Sat, 5 Jun 2021 01:40:01 UTC; Maintainer for emacs is bug-gnu-emacs@HIDDEN.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 11 Jun 2021 17:09:18 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Fri Jun 11 13:09:18 2021
Received: from localhost ([127.0.0.1]:39863 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lrkej-000819-Kb
	for submit <at> debbugs.gnu.org; Fri, 11 Jun 2021 13:09:18 -0400
Received: from mail-wr1-f45.google.com ([209.85.221.45]:35525)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lrkeg-00080t-K4
 for 48841 <at> debbugs.gnu.org; Fri, 11 Jun 2021 13:09:16 -0400
Received: by mail-wr1-f45.google.com with SMTP id m18so6831653wrv.2
 for <48841 <at> debbugs.gnu.org>; Fri, 11 Jun 2021 10:09:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=from:to:cc:subject:references:date:in-reply-to:message-id
 :user-agent:mime-version:content-transfer-encoding;
 bh=KP0ZmxByNAbqDds4hVyYLDCrRC7HWkwWxEbZN4U21dE=;
 b=IxwOq0MqgHBxQIa9Nbvzevl15fMIkC0wd10uHBh9iYhdH1smNwOWi5pTDhSMDY9aEf
 Um6y3tBm5skqCpw9m3LDV2XyrrlSUfS13WM953qIVOlYvkM9C+wvaIbe37EQC2IbXHCJ
 4doUdckmyOaCBFRYp6J1k5xL4yVSgMsEgeuYQFBOC4dXs2QwmI77y389W3EMG5xntKdf
 fgGUBaFrTxzcHiZp9uSmYg5IGwxaj49xeAJX1EyhPTa5d6hhdcYwMaI6hjxwfWCmJR09
 z0dDUlml7nzYU5gIwNrMSyOlSItgarQF268IgjkKZ/SsEMG3ZGiKuhz0dVPgq4oK9O1u
 pelg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to
 :message-id:user-agent:mime-version:content-transfer-encoding;
 bh=KP0ZmxByNAbqDds4hVyYLDCrRC7HWkwWxEbZN4U21dE=;
 b=I0ARhDf0rhUUOrdlm0O/rGoNuVotVi4V7+D6nmbio2/xSeYPvDC+yMcoo+RRoiRxnC
 zZ9bnW3KluM00zkd4YWlxmkIuX61dAI54aNDkIWjPoB6olVFhcyMd3/43d2aYd8uN8RO
 /88l50R/R2QvAdirLyr7UKBsDqARR5up+LqQoTEz9rsC68HvrWl+DudDZECKYfU6Z9IZ
 RX44LGsYmu/Hggm2Ci8FXp8SBjPxy/QtyrSyY7ZsrGi7pppmQcCKdvKcESyC43nLmiaz
 Xygmtnq9FnM0q9W75FMYnw3tocWzSLFwgd28w6OnSKcgfw9UHEz0bS/vgdWbTdjnYJoT
 5Vhw==
X-Gm-Message-State: AOAM532KVo12RPGxbNKI0ASnQEiZaBPpivBU5rziLXvi7DZU0jWEfoC4
 L/5SU+VMQOIDlYTXWV24n2mYyr7jpsg=
X-Google-Smtp-Source: ABdhPJzjhQ/Wu+gV0Z6S0LXtfeORPQmffKHmFomPAF7eIOtItueJJDnNxVjJxIA1xgKK4DUD9hUuLg==
X-Received: by 2002:a5d:4089:: with SMTP id o9mr5202889wrp.195.1623431348187; 
 Fri, 11 Jun 2021 10:09:08 -0700 (PDT)
Received: from krug (a94-133-55-152.cpe.netcabo.pt. [94.133.55.152])
 by smtp.gmail.com with ESMTPSA id c7sm7775820wrs.23.2021.06.11.10.09.06
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Fri, 11 Jun 2021 10:09:07 -0700 (PDT)
From: =?utf-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN>
 <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN>
 <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN>
 <87y2bnv5xc.fsf@HIDDEN>
 <35be6652-9c8d-ee21-e9eb-9598ad6777eb@HIDDEN>
 <CALDnm510An-+2b31oT_TE0akNjU_KWA7iv9RjN1Hr-KXSZ68sw@HIDDEN>
 <d57185f3-c28a-8c48-a50c-0b4b8bdb95c8@HIDDEN>
 <CALDnm51En25oyL8i+g-_oxBtCgmts0skjqwNE8hBn66k_DyV_g@HIDDEN>
 <858682b2-b8fd-898b-bef3-97dbe5e4debc@HIDDEN>
Date: Fri, 11 Jun 2021 18:09:04 +0100
In-Reply-To: <858682b2-b8fd-898b-bef3-97dbe5e4debc@HIDDEN> (Dmitry Gutov's
 message of "Fri, 11 Jun 2021 05:19:03 +0300")
Message-ID: <87mtrwuy4v.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: Stefan Monnier <monnier@HIDDEN>, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Dmitry Gutov <dgutov@HIDDEN> writes:

> On 07.06.2021 11:52, Jo=C3=A3o T=C3=A1vora 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.

And if there were multiple value, you can bet the container for them
wouldn't be free ;-)

> 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).

Which lambda are we talking about?  Is it ` update-score-and-face`?  If
so, I would guess that the capture of `score-denominator` is what takes
space, and that space is no bigger than another variable in that let
scope.

>> 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.

But `length` of a string, in any sane string implementation, _is_
accessing "an already computed value".  Which likely lives just besides
the data.  In Emacs, it seems to be two pointers (8 bytes) apart from
the data.  In a system with 64bytes of L1/2/3 cache it still
theoretically makes up to 52 bytes come in "for free" after you read the
length.  But to be honest I tried a bit and haven't come up with
benchmarks to help confirm -- or help dispel -- this theory.  Maybe you
can distill your "weird" experiment down to a code snippet?

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

In a compiled CL system, I would expect the former to use the stack, and
the to use the heap, but it wouldn't make any difference in reading the
variable's value, I think.  But Elisp is byte-compiled, not natively
compiled (except for that thing now, haven't tried it), and i don't
understand how the byte-compiler chooses byte-codes so all bets are off.

> 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).

Very interesting.  I don't know what the matter is with modifying the
string itself.  Is it because we want to protect its 'face' property?
Maybe, but what's the harm in chaning it?  Maybe Stefan knows.  Stefan,
are you reading this far?

If we do want to protect the shared 'face' property -- and only 'face'
-- then we could very add some other property about face that the
frontend could read "just in time" before it itself makes a copy of the
string to display to the user.=20=20

This technique appears to be slightly simpler than using the hash-table
indirection you propose (we would need something like that if, for some
reason, we absolutely could not touch the string's property list.)

> Anyway, these are musing for the much-discussed future iteration of
> the API. With the current version, and tied by backward compatibility,

Maybe I'm missing something, but I don't see why my above idea requires
changing _that_ much of the API (a bit would change yes).  It's a matter
of letting frontends opt-out of the current readily-available
face-propertized completions and opt-into a display-time facility that
does this propertization.=20

But if the speedup is big, I'd revisit the rationale for requiring those
copies to be performed in the first place.  In my (very brief) testing
it doesn't hurt a bit to remove it.

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

Will take a look now.

Jo=C3=A3o




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 11 Jun 2021 02:19:15 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Thu Jun 10 22:19:15 2021
Received: from localhost ([127.0.0.1]:37923 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lrWlP-0002DL-Bj
	for submit <at> debbugs.gnu.org; Thu, 10 Jun 2021 22:19:15 -0400
Received: from mail-wr1-f46.google.com ([209.85.221.46]:41546)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lrWlM-0002D8-0X
 for 48841 <at> debbugs.gnu.org; Thu, 10 Jun 2021 22:19:14 -0400
Received: by mail-wr1-f46.google.com with SMTP id o3so4294788wri.8
 for <48841 <at> debbugs.gnu.org>; Thu, 10 Jun 2021 19:19:11 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:subject:to:cc:references:from:message-id:date:user-agent
 :mime-version:in-reply-to:content-language;
 bh=wj5EuA8ANQmlPd2nPzxl3lhKoHqXxF0/XggB9vFIOoY=;
 b=Ga6QZ3Yyi3s7iQojdKhvk9qo57ReFABYTy7xG1nxrhI2MXtHPnIcnyJJyQ1sC6IF52
 AvyWa7bjGi3xhqmNcXZrmJTjuv7MwG+sc7UU0ScpUHpmSbqJJB52aO45FzNS0n8OGEUQ
 hKRUTLi28pcTwKyzMYwjYzIX1vY4LIfPp8Nt1gnT9GfR1ykVxxvOXkhkAj5Jl09vrsQy
 y8zTFWiaurC2IM7RxtTOgaBS4d0N+gDfW6kH6BngGpRNI0qXzKsDXkLEIHl8SvQSx+b/
 uS37aY/WkYB44qWmAta4aEHPVBdNUF21OhLsEhldWagsSWk2fyjhDXSWiG2tQ2k74WyB
 cZ+g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:subject:to:cc:references:from:message-id
 :date:user-agent:mime-version:in-reply-to:content-language;
 bh=wj5EuA8ANQmlPd2nPzxl3lhKoHqXxF0/XggB9vFIOoY=;
 b=nHgPIjozb0UwMc30gMbhMt/FCWE54yfVnMo/nDwubadmtVGSevgimqZxmMkuWEtPVS
 o3Rdz7+5X0yBfxmQyABKlnbZFzWMVLhzoACqGeEKiX+GDFDRW16UvsB57JgkYJqTKghr
 V6H9Sgo0abeNZyuzYi+2DMM9CBUMsda3z+O/U9h5VKgBxgNbgcT5y4QpJ9aJjQ8wpL/J
 bPfsKHzqsIlvCkFU/dsPETHJsEUgPDUqChAgUBcJSBZ0jH88eOysnYctcSBWBxKsjpW9
 XoRpr3C3OyH/TQ2SHNyXmGZ1m5alY10TKLnrvJRwrsUbc+L0wHqRK9m7kax/q9qqSvsY
 dJKA==
X-Gm-Message-State: AOAM530VF5BzJwL9sCGF0W6Tk5rsC4WuVo3hQFCBHTQ047fcM/6KPYDX
 MW1R9ByP3trK2UeZxcHSFxxd4Qrn6k4=
X-Google-Smtp-Source: ABdhPJyAKBusvaaIqK80+XSE7+FozrzXuD4eABDRQj7bsk8td6+cmaILw8Cdxl/Gx8vDQNfu3j7YvA==
X-Received: by 2002:adf:d1c9:: with SMTP id b9mr1242584wrd.101.1623377945937; 
 Thu, 10 Jun 2021 19:19:05 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id k8sm5327836wrp.3.2021.06.10.19.19.04
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Thu, 10 Jun 2021 19:19:04 -0700 (PDT)
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN>
 <87y2bnv5xc.fsf@HIDDEN> <35be6652-9c8d-ee21-e9eb-9598ad6777eb@HIDDEN>
 <CALDnm510An-+2b31oT_TE0akNjU_KWA7iv9RjN1Hr-KXSZ68sw@HIDDEN>
 <d57185f3-c28a-8c48-a50c-0b4b8bdb95c8@HIDDEN>
 <CALDnm51En25oyL8i+g-_oxBtCgmts0skjqwNE8hBn66k_DyV_g@HIDDEN>
From: Dmitry Gutov <dgutov@HIDDEN>
Message-ID: <858682b2-b8fd-898b-bef3-97dbe5e4debc@HIDDEN>
Date: Fri, 11 Jun 2021 05:19:03 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
In-Reply-To: <CALDnm51En25oyL8i+g-_oxBtCgmts0skjqwNE8hBn66k_DyV_g@HIDDEN>
Content-Type: multipart/mixed; boundary="------------F6E563123C8DCDF34497F7F5"
Content-Language: en-US
X-Spam-Score: 0.5 (/)
X-Debbugs-Envelope-To: 48841
Cc: Stefan Monnier <monnier@HIDDEN>, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -0.5 (/)

This is a multi-part message in MIME format.
--------------F6E563123C8DCDF34497F7F5
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit

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.

--------------F6E563123C8DCDF34497F7F5
Content-Type: text/x-patch; charset=UTF-8;
 name="completion-pcm-score-struct.diff"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="completion-pcm-score-struct.diff"

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

--------------F6E563123C8DCDF34497F7F5--




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 7 Jun 2021 08:53:24 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Mon Jun 07 04:53:24 2021
Received: from localhost ([127.0.0.1]:54427 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lqB0d-0002fK-Lp
	for submit <at> debbugs.gnu.org; Mon, 07 Jun 2021 04:53:23 -0400
Received: from mail-pf1-f177.google.com ([209.85.210.177]:41769)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lqB0b-0002f3-0i
 for 48841 <at> debbugs.gnu.org; Mon, 07 Jun 2021 04:53:22 -0400
Received: by mail-pf1-f177.google.com with SMTP id x73so12576976pfc.8
 for <48841 <at> debbugs.gnu.org>; Mon, 07 Jun 2021 01:53:20 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=aM3peZxgz3qG7mfQMQnJl8cjmMJ9dxCDWM2MeMZFHAg=;
 b=j7Ur1G2B/HTudQdYEvzgBqDlqiUy/xTZDBsuNbNzgLTALKQlYA8TgdALNC2D+CV2u2
 sBp6CPARKJLoomQMaXC3io9MJ2tjZx4l7jWb2NuREw5PNeFF4pSDMi5mBMQmjija4y4D
 QuH5pTtkUafPpbFU7fR1yJXiKG62p/FtPPM61arr5OOms+0ptd7cbeh1IBTD+jCHywx+
 RXCTkUOqRgQg6M1lDvFlKvZ960jIr4se3V6N+RfQj8VBPa3u2pytrrJlSLY6AUILelFx
 vEA5bU2lMhLg2Flb+9FzciermEpvClpCpAKHjrmsVI96r+/oCx4LWMRrr1ystk/cVLhA
 4jnw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=aM3peZxgz3qG7mfQMQnJl8cjmMJ9dxCDWM2MeMZFHAg=;
 b=jRsXrBRBhZkCRP/LbdnXNRxsFKB3xtuPZHlviS7cHbEllbE6Q7cO131PblHeFHLmu2
 h0TO1TuaDXho1eNs0buXNlOLcC4VKnmdZaKnx2RcE/bPOrI5DwoPIjhkasr5ZfO0hp6s
 /fA9grfgKd3xTu52bhM6K7vSjo/YCbMzZQ8TfQ+4BBmj/F6kcma8OgjX08J0/xv/d798
 3OC7H13DtxFXnQj0qN1odtcKH5Y3kowM2WH6R2bL5rumjc9IQWb41zAmYyGspmdCaTli
 HqkpN/6K9MHQCwqWYvu4IJsiwA28/x9i8qV55Ah4GweOMnHVQrHFlElGBR9tGDWUSSFT
 MZZQ==
X-Gm-Message-State: AOAM531mCrZNm4yiZ7k/ej2RCJZoEbNqD7iqWlVy9XfDqiV7n+lo9AnA
 0AKsa2dsovEr0xmVFJTD7/Pdbi9ev/tNEzV9IAc=
X-Google-Smtp-Source: ABdhPJyGCFz5qsXjNnFAQnQoiim6k0rqfmqFIHlCbAQHUuYycHJXBYw7J23G9RD4wtEwUNQ07u2Qv3sqeJLrnzqV6Zk=
X-Received: by 2002:a65:63d2:: with SMTP id n18mr16905363pgv.447.1623055995062; 
 Mon, 07 Jun 2021 01:53:15 -0700 (PDT)
MIME-Version: 1.0
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN>
 <87y2bnv5xc.fsf@HIDDEN> <35be6652-9c8d-ee21-e9eb-9598ad6777eb@HIDDEN>
 <CALDnm510An-+2b31oT_TE0akNjU_KWA7iv9RjN1Hr-KXSZ68sw@HIDDEN>
 <d57185f3-c28a-8c48-a50c-0b4b8bdb95c8@HIDDEN>
In-Reply-To: <d57185f3-c28a-8c48-a50c-0b4b8bdb95c8@HIDDEN>
From: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
Date: Mon, 7 Jun 2021 09:52:59 +0100
Message-ID: <CALDnm51En25oyL8i+g-_oxBtCgmts0skjqwNE8hBn66k_DyV_g@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: Dmitry Gutov <dgutov@HIDDEN>
Content-Type: multipart/alternative; boundary="000000000000094bd205c4292c46"
X-Spam-Score: -0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: Stefan Monnier <monnier@HIDDEN>, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

--000000000000094bd205c4292c46
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Mon, Jun 7, 2021, 01:11 Dmitry Gutov <dgutov@HIDDEN> wrote:

> On 07.06.2021 02:49, Jo=C3=A3o T=C3=A1vora wrote:
>
> >     Same result, indeed. We should note, though, that
> >     completion-pcm--hilit-commonality has some steps that were added
> >     together with the 'flex' style, for it to work.
> >
> >
> > But nothing algorithmically aberrant, I think.
>
> Just some stuff adding work to GC, I think.
>

O(n) stuff being a property and a number on each string, small in
comparison to the string.

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.

> 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.

Jo=C3=A3o

--000000000000094bd205c4292c46
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D=
"gmail_attr">On Mon, Jun 7, 2021, 01:11 Dmitry Gutov &lt;<a href=3D"mailto:=
dgutov@HIDDEN">dgutov@HIDDEN</a>&gt; wrote:<br></div><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex">On 07.06.2021 02:49, Jo=C3=A3o T=C3=A1vora wrote:<br>
<br>
&gt;=C2=A0 =C2=A0 =C2=A0Same result, indeed. We should note, though, that<b=
r>
&gt;=C2=A0 =C2=A0 =C2=A0completion-pcm--hilit-commonality has some steps th=
at were added<br>
&gt;=C2=A0 =C2=A0 =C2=A0together with the &#39;flex&#39; style, for it to w=
ork.<br>
&gt; <br>
&gt; <br>
&gt; But nothing algorithmically aberrant, I think.<br>
<br>
Just some stuff adding work to GC, I think.<br></blockquote></div></div><di=
v dir=3D"auto"><br></div><div dir=3D"auto">O(n) stuff being a property and =
a number on each string, small in comparison to the string.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto"><div class=3D"gmail_quote"><blockquot=
e class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc sol=
id;padding-left:1ex">
Maybe moving all of them to parameters and return values (making it a <br>
static function and having the caller manage state) would help, I <br>
haven&#39;t tried that exactly.<br></blockquote></div></div><div dir=3D"aut=
o"><br></div><div dir=3D"auto">Normally, in those adventures you end up wit=
h the same allocations somewhere else, and uglier code. But you can try.</d=
iv><div dir=3D"auto"><br></div><div dir=3D"auto"><div class=3D"gmail_quote"=
><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1=
px #ccc solid;padding-left:1ex">
&gt; Might be noise, or you might be thrashing of CPU caches, who knows? If=
 <br>
&gt; the string length is on the same cache line as the contents of the <br=
>
&gt; string you&#39;re reading, then evicting that to go read the value of =
a <br>
&gt; boxed integer somewhere radically different is slow.<br>
<br>
But the string value is boxed as well, right?=C2=A0</blockquote></div></div=
><div dir=3D"auto"><br></div><div dir=3D"auto">The key is locality. If the =
string length and data happen to live nearby in memory (in the same box, so=
 to speak), there&#39;s a decent chance that reading one brings the other i=
nto the cache, and you get a nice hit depending on your subsequent operatio=
n.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">Here I&#39;m ju=
st speculating, as I said. In managed languages such as Lisps, it&#39;s som=
ewhat unpredictable. It&#39;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 &quot;weird&quot; results (which aren=
t 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. B=
jarne Stroustrup has one of those talks.</div><div dir=3D"auto"><br></div><=
div dir=3D"auto">Jo=C3=A3o</div><div dir=3D"auto"><br></div></div>

--000000000000094bd205c4292c46--




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 7 Jun 2021 02:05:51 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 22:05:51 2021
Received: from localhost ([127.0.0.1]:54223 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lq4eF-0000XT-8L
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 22:05:51 -0400
Received: from mail-wm1-f54.google.com ([209.85.128.54]:53944)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lq4eA-0000XD-RK
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 22:05:49 -0400
Received: by mail-wm1-f54.google.com with SMTP id h3so8977789wmq.3
 for <48841 <at> debbugs.gnu.org>; Sun, 06 Jun 2021 19:05:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:subject:to:cc:references:from:message-id:date:user-agent
 :mime-version:in-reply-to:content-language:content-transfer-encoding;
 bh=Qh3fWlA8R0G+DuOtNzp724Hh4UwP1QBX9ubO7NjSys0=;
 b=GYKFAoMh0ZvWXWzJI0ATJBJXAUEl/9OqRMasjnjOYHn/AqbPVxMLvDFP/qnqLaOrSg
 V8NqRM07LJvI7+TXXEAZjyInWDZCF+7wh25q27F8z6C8FRqAV/SJaNnprxiR9CPSHQve
 eq2o7QZHoz27wX+Nv9RvH+kH0HnBvSbbWB+5ASA3FISYXYGGXUUy+2TRnSLYhdA3kFNC
 xCzkhTQf6rQYnkunZzM7Mse5y6bB6ebV0rkVDblUpaOgfwo2UovHGMKazqsaRjyUeyHu
 sFTx8uKCrkECjL86l4mM/55wYAsUcn+PpVdFPLkRwQMkfalGoCnQsPaTtW3ssfvDXhCb
 I0xw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:subject:to:cc:references:from:message-id
 :date:user-agent:mime-version:in-reply-to:content-language
 :content-transfer-encoding;
 bh=Qh3fWlA8R0G+DuOtNzp724Hh4UwP1QBX9ubO7NjSys0=;
 b=RYEWqH7Y3jFfP0M2mElva+HsrjWsaGFUJKUV1g/vC0h5GxHAZcHIxMuEj7UsTiiM8u
 m3j0j4zV5XqUQgWkSjzOcHsgusziGuBHgOZsJbxOiG02ukX90sEMWcj/ni+061VaaKyg
 MwZikZvCc3hCx0F+MdszKGen5NStSMvKiVhnI9U6nU9vMwC5xmSeh9azm+2iDmdkrJJx
 vpRSwjZtbx8A/KnLM2MER0hd+L14xl+6/QSz18rDolO6BqPqFIz1TkTu38mG5llxLTWC
 qRDd8JONCcM47w+yq3uFIbeDV81oGVK01TaKbiHfOEaU164qhur9WdxgSS3FkB+/9K4O
 tvZg==
X-Gm-Message-State: AOAM53342/Igw7mzStdvW2dDEFZ2/TKKgKeBC+l98PWrqhe/+DoAT9Jn
 kYJk+yuvoVSyhcbSZM07SO+hEAPl71E=
X-Google-Smtp-Source: ABdhPJxUM1oSG+JRblYXYWljouB1tbxWOZH7vDC4T/DMOyTY/hzgXS1Wm10EKmS/kOpfMDx6jEP84g==
X-Received: by 2002:a1c:740b:: with SMTP id p11mr13978927wmc.94.1623024703737; 
 Sun, 06 Jun 2021 17:11:43 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id 89sm14715741wri.94.2021.06.06.17.11.42
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Sun, 06 Jun 2021 17:11:43 -0700 (PDT)
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN>
 <87y2bnv5xc.fsf@HIDDEN> <35be6652-9c8d-ee21-e9eb-9598ad6777eb@HIDDEN>
 <CALDnm510An-+2b31oT_TE0akNjU_KWA7iv9RjN1Hr-KXSZ68sw@HIDDEN>
From: Dmitry Gutov <dgutov@HIDDEN>
Message-ID: <d57185f3-c28a-8c48-a50c-0b4b8bdb95c8@HIDDEN>
Date: Mon, 7 Jun 2021 03:11:41 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
In-Reply-To: <CALDnm510An-+2b31oT_TE0akNjU_KWA7iv9RjN1Hr-KXSZ68sw@HIDDEN>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Spam-Score: 0.5 (/)
X-Debbugs-Envelope-To: 48841
Cc: Stefan Monnier <monnier@HIDDEN>, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -0.5 (/)

On 07.06.2021 02:49, João Távora wrote:

>     Same result, indeed. We should note, though, that
>     completion-pcm--hilit-commonality has some steps that were added
>     together with the 'flex' style, for it to work.
> 
> 
> But nothing algorithmically aberrant, I think.

Just some stuff adding work to GC, I think.

> By the way, I think you should be running benchmarks multiple times to 
> get times in the seconds range, and reduce noise. Multiple levels of CPU 
> cache and other factors like temp thottling may skew results when 
> running just one time.

Yeah, I repeat the action with each version for like a few dozen times, 
until I see the numbers stabilize, or just take the average.

>     Tried binding gc-cons-threshold to a high value, and even galling
>     garbage-collect-maybe (or not): that speeds it up, but adds some
>     unpredictable GC pauses later (though it would be nice to be able to
>     consolidate the pauses into one collection pass).
> 
> 
> Maybe in Elisp that's a good idea, in other lisps and other languages, 
> second-guessing the GC is a bad idea. I hear ours is so basic that 
> indeed it might be reasonable.

I never get good results with that.

>     Long story short, the patch I just installed, to reuse the match data,
>     brings the runtime down to
> 
>         Elapsed time: 0.066388s (0.050087s in 3 GCs)
> 
> 
> That's nice! but are you sure you're not seeing noise, too?

Pretty sure.

>     Tried other things like moving the update-score-and-face lambda out of
>     the mapcar loop - that didn't move a needle.
> 
> 
> If a lambda is non capturing of stuff inside the loop, only one copy of 
> it is ever made, I think. So it doesn't suprise me.

update-score-and-face references both variables in its closest binding 
form (score-numerator, score-denominator) and the parameter of its 
containing lambda (str).

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.

>     And a weird part: replacing all repeated (length str) calls with a
>     reference to an existing local binding makes it *slower* (back to the
>     original performance).
> 
> 
> 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? So the code needs to 
follow one indirection either way. Perhaps there's also overhead in 
looking up the lexical scope.

I also tried using the new-and-shiny length> and length=. This simply 
made no measurable difference.

> Just speculation of 
> course. Might just be noise or something else entirely.

This is highly reproducible. On my machine, at least.

Given how weird it is, I wouldn't just write about it without 
recompiling, restarting Emacs and measuring the scenario several times, 
with different versions of code.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 7 Jun 2021 01:55:50 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 21:55:50 2021
Received: from localhost ([127.0.0.1]:54199 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lq4UX-0000GS-SN
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 21:55:50 -0400
Received: from mail-oi1-f181.google.com ([209.85.167.181]:45746)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lq4UV-0000GE-9O
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 21:55:48 -0400
Received: by mail-oi1-f181.google.com with SMTP id w127so16495497oig.12
 for <48841 <at> debbugs.gnu.org>; Sun, 06 Jun 2021 18:55:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=1kM4TfMW4FOkcIwsTRHxD+Y3eNN6nT8MdBgp0go9NPA=;
 b=Z0pc1SoTDq7sWRL0MiK4IcahyAlcqiVTUWvjz383QquSySxOFPH7CydCKj8i9OkIkU
 DNF/GhqwToqYXXweH/kUhBnMreukAu3WpuXI906wO/R6BtrQhajOZ4xNcHqOg9IHDco/
 xOD4hVlEhgewzjVUJmWbqHjjOFfCDmOyD+InHVT4czpt0NWKVL28f3+sDt9Va5x1Pwl6
 LELJn3z8RuariKXrBANkfZOpyRUlGpDG+i4h9GcZ3XaVv2M0RklnCEW/rP/dpkASt7wR
 Dlovp5Xj+BTCr1VA8UL99YY1ArkBlpuXw+XipgDd3tng00eTQYGz8k0FWudr2588W4co
 6xOw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=1kM4TfMW4FOkcIwsTRHxD+Y3eNN6nT8MdBgp0go9NPA=;
 b=Vik08H6HKxS0yTAwRJPktZVyoKqRe6M6znDj43V/56zo2geqkwBdcX4GWYzwanxPn4
 RUled0WPE+So8fvcaO/c6/7JxqAFy4SL9xQM7mujLUhQ2LMtc9DImr7ZX9lqS6iVFXM0
 qqi86TyD7jkLQLtvy4xT9k9PlP0J01RuzY1EBPKJ+xJ/ceH/MzTLc3E9klMEtFjtcX6u
 1PT4OFHPPrFcaUYD3vgdQljBunoGB9LT8sdNBhFa6EAzCKSUxFo/QeX/KVLLKllqH42U
 +AWQH/6Csnz+RUgohO/3ecUlUgPe1fdgUzHOJysODWXNwDN/66eapYXXRTuOu6bwGAZx
 srkQ==
X-Gm-Message-State: AOAM530s+6l4G1Yfy+pBwslhUGc0F6koLfl2Kj7dUhP19BPB2mvYLCr5
 TfMneGUdGUKBN+XAOmjkDDaTyv1c9fdhCOC4K9VC+jX4
X-Google-Smtp-Source: ABdhPJyEYZlAGVCgEG6or1UxuvWk7c0MVYlCMBSqDQo9I4/f9i3iGRAnws90BI+zz+P6sKJOIrIsZKgHvTxOOCU9eZE=
X-Received: by 2002:a17:90a:1141:: with SMTP id
 d1mr17522806pje.56.1623022088420; 
 Sun, 06 Jun 2021 16:28:08 -0700 (PDT)
MIME-Version: 1.0
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN>
 <87tumbv5qh.fsf@HIDDEN> <5efda5a3-f7ed-ca90-9e70-b35eb1c24750@HIDDEN>
 <CALDnm51pYqMGbh7sYDxZ5dMV+6ntp5kaTrb7gfuiRD+LzeAKYg@HIDDEN>
 <31baa0d5-02e0-368d-7946-7a3b98a8a5ca@HIDDEN>
In-Reply-To: <31baa0d5-02e0-368d-7946-7a3b98a8a5ca@HIDDEN>
From: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
Date: Mon, 7 Jun 2021 00:27:55 +0100
Message-ID: <CALDnm536R1eYhHW-P8vf78EgyfjwZ4T0wV74Z0+vZjtT4Xt9Jw@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: Dmitry Gutov <dgutov@HIDDEN>
Content-Type: multipart/alternative; boundary="0000000000000afeb505c4214748"
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: Stefan Monnier <monnier@HIDDEN>, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

--0000000000000afeb505c4214748
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Sun, Jun 6, 2021, 23:21 Dmitry Gutov <dgutov@HIDDEN> wrote:

> On 06.06.2021 21:37, Jo=C3=A3o T=C3=A1vora wrote:
> > Bottom line is that something (TM) happened to speed up the whole thing
> > when I skipped over that whole part. I had vertical mode basically
> > visually equivalent to vertical, but quite slower.  After skipping that
> > part they became practically equivalent. And you yourself witnessed thi=
s
> > when switching yo vertical mode, which is when the skip is made.
>
> Yep.
>

By the way, earlier I meant to write:

"I had vertical mode basically visually equivalent to vertico.el, but quite
slower.  After skipping that part they became practically equivalent. "

 autocorrect on my phone had other ideas...

Jo=C3=A3o

--0000000000000afeb505c4214748
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D=
"gmail_attr">On Sun, Jun 6, 2021, 23:21 Dmitry Gutov &lt;<a href=3D"mailto:=
dgutov@HIDDEN">dgutov@HIDDEN</a>&gt; wrote:<br></div><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex">On 06.06.2021 21:37, Jo=C3=A3o T=C3=A1vora wrote:<br>
&gt; Bottom line is that something (TM) happened to speed up the whole thin=
g <br>
&gt; when I skipped over that whole part. I had vertical mode basically <br=
>
&gt; visually equivalent to vertical, but quite slower.=C2=A0 After skippin=
g that <br>
&gt; part they became practically equivalent. And you yourself witnessed th=
is <br>
&gt; when switching yo vertical mode, which is when the skip is made.<br>
<br>
Yep.<br></blockquote></div></div><div dir=3D"auto"><br></div><div dir=3D"au=
to">By the way, earlier I meant to write:</div><div dir=3D"auto"><br></div>=
<div dir=3D"auto"><span style=3D"font-family:sans-serif">&quot;I had vertic=
al mode basically</span>=C2=A0visually<span style=3D"font-family:sans-serif=
">=C2=A0equivalent to vertico.el,=C2=A0</span><span style=3D"font-family:sa=
ns-serif">but quite slower.=C2=A0 After skipping that</span>=C2=A0part<span=
 style=3D"font-family:sans-serif">=C2=A0they became practically equivalent.=
</span><span style=3D"font-family:sans-serif">=C2=A0&quot;</span></div><div=
 dir=3D"auto"><span style=3D"font-family:sans-serif"><br></span></div><div =
dir=3D"auto"><span style=3D"font-family:sans-serif">=C2=A0autocorrect on my=
 phone had other ideas...</span></div><div dir=3D"auto"><span style=3D"font=
-family:sans-serif"><br></span></div><div dir=3D"auto"><span style=3D"font-=
family:sans-serif">Jo=C3=A3o</span></div></div>

--0000000000000afeb505c4214748--




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 7 Jun 2021 01:36:54 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 21:36:54 2021
Received: from localhost ([127.0.0.1]:54179 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lq4CD-0008GP-RT
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 21:36:54 -0400
Received: from mail-pg1-f174.google.com ([209.85.215.174]:42786)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lq4CB-0008GA-Rj
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 21:36:53 -0400
Received: by mail-pg1-f174.google.com with SMTP id i34so6187912pgl.9
 for <48841 <at> debbugs.gnu.org>; Sun, 06 Jun 2021 18:36:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=MSh0ek3MqGWUtKtgZXaXrsqHaTuof9mIPeyiqOMQaDM=;
 b=H2RI+FkBP5d2J6WaIFfcrdqVdz9GuBOcvI0mIrpSEN4jXhavZvHfQAwsAcxXK/8sZI
 Dd1Co1qf6WDSQ6hlaeHWinW/+757acMPP716K3PWHYTFI6KmGgtlsb3OLRyzFLhoVO51
 o0GPZgWgheF9gS74AGVqjCVCUR8Q7IRGR+ulCiwDmJs9UBp6LDpco71zUSWgduj1Gfz2
 h04L5N/ZOZFmIIqpzRhqiv0gUcXV5ybMgSdaeX2Fa/B64pvHBL/aV/TvmAo6VVNY6ZAd
 JJM+cJjJGDvaDBp+MMeS3EakeC1QekUdb8npVHfy+uHgW/T3cEjX+jJca6cUNRg4lJtR
 iC4g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=MSh0ek3MqGWUtKtgZXaXrsqHaTuof9mIPeyiqOMQaDM=;
 b=U9u89oO8uHIScnEeEeTy/0rs6OQ0AkcK6vJMJnqga25WQ9WHaG3pzHll5EbkdmYA30
 0BPlPX8xySsdr1TRKeWrvnjn8lnwv3llaK/bDLLHUSY0rVpDo5t7aN3SXiANwyrT8WY7
 z7HVizOGsgmYGCDcyq+SZAKGc1jRqjwf8Bw084le7VmZ2/7D/yzBlqebWu1qOI2ya+Ie
 a8YjesDrQ4BKPrhHEV4aaUX+QfhY5PzK3AgMeX+qD0kFyfO0T41vxDFjmdshT182hNtf
 VQpHIUS2roBARXphCY7dejja18ZeiskKbttR2S6G1tJWixT5XWckj/BJzmz0z9di45yy
 relQ==
X-Gm-Message-State: AOAM532vWCgZewEC08cvOauKONM+B+gKS1oCuon0jMHbEjKgDGSi0p7o
 4at6Ev/V90fe+DiGmU746vkxFEq2jT/ahyt66nWeNUuq
X-Google-Smtp-Source: ABdhPJx+lBqSlHKaTg5m+Qel20kVW8wHY9Sb+rMeDFS9DhRHWsr9OssDBkZpnw13O64aLxprDtqHudYlCdingqlVW9g=
X-Received: by 2002:a17:902:ed8f:b029:110:a434:4d76 with SMTP id
 e15-20020a170902ed8fb0290110a4344d76mr9009369plj.52.1623023404154; Sun, 06
 Jun 2021 16:50:04 -0700 (PDT)
MIME-Version: 1.0
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN>
 <87y2bnv5xc.fsf@HIDDEN> <35be6652-9c8d-ee21-e9eb-9598ad6777eb@HIDDEN>
In-Reply-To: <35be6652-9c8d-ee21-e9eb-9598ad6777eb@HIDDEN>
From: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
Date: Mon, 7 Jun 2021 00:49:51 +0100
Message-ID: <CALDnm510An-+2b31oT_TE0akNjU_KWA7iv9RjN1Hr-KXSZ68sw@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: Dmitry Gutov <dgutov@HIDDEN>
Content-Type: multipart/alternative; boundary="0000000000007782bf05c421955f"
X-Spam-Score: -0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: Stefan Monnier <monnier@HIDDEN>, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

--0000000000007782bf05c421955f
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Sun, Jun 6, 2021, 23:20 Dmitry Gutov <dgutov@HIDDEN> wrote:

>
> >> And/or pick a different algorithm. E.g. Jaro-Winkler, which apparently
> >> is used in a lot of "fuzzy matching" implementations out there, it's
> >> pretty fast.
> >
> > That may be useful, but for other purposes.  If I understand correctly,
> > Jaro-Winkler is for finding the distante between two arbitrary strings,
> > where the first in not a subsequence of the second.  I bet google uses
> > stuff like that when you accitendally transpose characters.  Flex just
> > gives up.  Those other others algos still catch the match (and Google
> > than probably NL-scours your most intimate fears and checks with your

> local dictator before showing you typing suggestions)
>

Meant to write ML as in machine learning, not NL.

I'm not crazy about shuffling completion, but some people did indeed ask
> for it. The filtering step has to be more complex, though (you can't
> just construct a straightforward regexp to filter with).
>

I think you calculate the distance using one of these fancy multi-surname
algorithms , then do cutoff somewhere.

Same result, indeed. We should note, though, that
> completion-pcm--hilit-commonality has some steps that were added
> together with the 'flex' style, for it to work.
>

But nothing algorithmically aberrant, I think.

I did some instrumenting, replacing (completion-pcm--hilit-commonality
> pattern all) inside completion-flex-all-completions with
> (benchmark-progn (completion-pcm--hilit-commonality pattern all)).
> Recompiled between each change (interpreted mode gives very different
> numbers).
>
> Unmodified, the call takes ~85ms:
>
>    Elapsed time: 0.085520s (0.068406s in 4 GCs)
>


By the way, I think you should be running benchmarks multiple times to get
times in the seconds range, and reduce noise. Multiple levels of CPU cache
and other factors like temp thottling may skew results when running just
one time.

If I comment everything inside its first lambda except the returned
> value (making the function the same as #'identity), the time goes down
> to <1ms.
>
> Uncomment the 'copy-sequence' and 'string-match' calls (which one might
> suspect of garbage generation):
>
>    Elapsed time: 0.006380s
>
> Tried binding gc-cons-threshold to a high value, and even galling
> garbage-collect-maybe (or not): that speeds it up, but adds some
> unpredictable GC pauses later (though it would be nice to be able to
> consolidate the pauses into one collection pass).
>

Maybe in Elisp that's a good idea, in other lisps and other languages,
second-guessing the GC is a bad idea. I hear ours is so basic that indeed
it might be reasonable.

Long story short, the patch I just installed, to reuse the match data,
> brings the runtime down to
>
>    Elapsed time: 0.066388s (0.050087s in 3 GCs)
>

That's nice! but are you sure you're not seeing noise, too?

Tried other things like moving the update-score-and-face lambda out of
> the mapcar loop - that didn't move a needle.


If a lambda is non capturing of stuff inside the loop, only one copy of it
is ever made, I think. So it doesn't suprise me.

And a weird part: replacing all repeated (length str) calls with a
> reference to an existing local binding makes it *slower* (back to the
> original performance).


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. Just speculation of course. Might
just be noise or something else entirely.

Jo=C3=A3o

--0000000000007782bf05c421955f
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D=
"gmail_attr">On Sun, Jun 6, 2021, 23:20 Dmitry Gutov &lt;<a href=3D"mailto:=
dgutov@HIDDEN">dgutov@HIDDEN</a>&gt; wrote:</div><blockquote class=3D=
"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding=
-left:1ex">
<br>
&gt;&gt; And/or pick a different algorithm. E.g. Jaro-Winkler, which appare=
ntly<br>
&gt;&gt; is used in a lot of &quot;fuzzy matching&quot; implementations out=
 there, it&#39;s<br>
&gt;&gt; pretty fast.<br>
&gt; <br>
&gt; That may be useful, but for other purposes.=C2=A0 If I understand corr=
ectly,<br>
&gt; Jaro-Winkler is for finding the distante between two arbitrary strings=
,<br>
&gt; where the first in not a subsequence of the second.=C2=A0 I bet google=
 uses<br>
&gt; stuff like that when you accitendally transpose characters.=C2=A0 Flex=
 just<br>
&gt; gives up.=C2=A0 Those other others algos still catch the match (and Go=
ogle<br>
&gt; than probably NL-scours your most intimate fears and checks with your<=
/blockquote></div></div><div dir=3D"auto"><div class=3D"gmail_quote"><block=
quote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc=
 solid;padding-left:1ex">
&gt; local dictator before showing you typing suggestions)<br></blockquote>=
</div></div><div dir=3D"auto"><br></div><div dir=3D"auto">Meant to write ML=
 as in machine learning, not NL.</div><div dir=3D"auto"><br></div><div dir=
=3D"auto"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I&#39;m not crazy about shuffling completion, but some people did indeed as=
k <br>
for it. The filtering step has to be more complex, though (you can&#39;t <b=
r>
just construct a straightforward regexp to filter with).<br></blockquote></=
div></div><div dir=3D"auto"><br></div><div dir=3D"auto">I think you calcula=
te the distance using one of these fancy multi-surname algorithms , then do=
 cutoff somewhere.</div><div dir=3D"auto"><br></div><div dir=3D"auto"><div =
class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 0=
 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Same result, indeed. We should note, though, that <br>
completion-pcm--hilit-commonality has some steps that were added <br>
together with the &#39;flex&#39; style, for it to work.<br></blockquote></d=
iv></div><div dir=3D"auto"><br></div><div dir=3D"auto">But nothing algorith=
mically aberrant, I think.</div><div dir=3D"auto"><br></div><div dir=3D"aut=
o"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I did some instrumenting, replacing (completion-pcm--hilit-commonality <br>
pattern all) inside completion-flex-all-completions with <br>
(benchmark-progn (completion-pcm--hilit-commonality pattern all)). <br>
Recompiled between each change (interpreted mode gives very different <br>
numbers).<br>
<br>
Unmodified, the call takes ~85ms:<br>
<br>
=C2=A0 =C2=A0Elapsed time: 0.085520s (0.068406s in 4 GCs)<br></blockquote><=
/div></div><div dir=3D"auto"><br></div><div dir=3D"auto"><br></div><div dir=
=3D"auto">By the way, I think you should be running benchmarks multiple tim=
es to get times in the seconds range, and reduce noise. Multiple levels of =
CPU cache and other factors like temp thottling may skew results when runni=
ng just one time.</div><div dir=3D"auto"><br></div><div dir=3D"auto"><div c=
lass=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 =
0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
If I comment everything inside its first lambda except the returned <br>
value (making the function the same as #&#39;identity), the time goes down =
<br>
to &lt;1ms.<br>
<br>
Uncomment the &#39;copy-sequence&#39; and &#39;string-match&#39; calls (whi=
ch one might <br>
suspect of garbage generation):<br>
<br>
=C2=A0 =C2=A0Elapsed time: 0.006380s<br>
<br>
Tried binding gc-cons-threshold to a high value, and even galling <br>
garbage-collect-maybe (or not): that speeds it up, but adds some <br>
unpredictable GC pauses later (though it would be nice to be able to <br>
consolidate the pauses into one collection pass).<br></blockquote></div></d=
iv><div dir=3D"auto"><br></div><div dir=3D"auto">Maybe in Elisp that&#39;s =
a good idea, in other lisps and other languages, second-guessing the GC is =
a bad idea. I hear ours is so basic that indeed it might be reasonable.</di=
v><div dir=3D"auto"><br></div><div dir=3D"auto"><div class=3D"gmail_quote">=
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Long story short, the patch I just installed, to reuse the match data, <br>
brings the runtime down to<br>
<br>
=C2=A0 =C2=A0Elapsed time: 0.066388s (0.050087s in 3 GCs)<br></blockquote><=
/div></div><div dir=3D"auto"><br></div><div dir=3D"auto">That&#39;s nice! b=
ut are you sure you&#39;re not seeing noise, too?</div><div dir=3D"auto"><b=
r></div><div dir=3D"auto"><div class=3D"gmail_quote"><blockquote class=3D"g=
mail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-l=
eft:1ex">
Tried other things like moving the update-score-and-face lambda out of <br>
the mapcar loop - that didn&#39;t move a needle.</blockquote></div></div><d=
iv dir=3D"auto"><br></div><div dir=3D"auto">If a lambda is non capturing of=
 stuff inside the loop, only one copy of it is ever made, I think. So it do=
esn&#39;t suprise me.</div><div dir=3D"auto"><br></div><div dir=3D"auto"><d=
iv class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:=
0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
And a weird part: replacing all repeated (length str) calls with a <br>
reference to an existing local binding makes it *slower* (back to the <br>
original performance).</blockquote></div></div><div dir=3D"auto"><br></div>=
<div dir=3D"auto">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 o=
f the string you&#39;re reading, then evicting that to go read the value of=
 a boxed integer somewhere radically different is slow. Just speculation of=
 course. Might just be noise or something else entirely.</div><div dir=3D"a=
uto"><br></div><div dir=3D"auto">Jo=C3=A3o</div></div>

--0000000000007782bf05c421955f--




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 22:21:32 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 18:21:32 2021
Received: from localhost ([127.0.0.1]:54117 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lq199-0003ua-TY
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 18:21:32 -0400
Received: from mail-wr1-f53.google.com ([209.85.221.53]:45832)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lq197-0003uK-Fw
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 18:21:29 -0400
Received: by mail-wr1-f53.google.com with SMTP id z8so15262169wrp.12
 for <48841 <at> debbugs.gnu.org>; Sun, 06 Jun 2021 15:21:29 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:subject:to:cc:references:from:message-id:date:user-agent
 :mime-version:in-reply-to:content-language:content-transfer-encoding;
 bh=Xp5xZYra07gEC132g1qMNKIzGmLHyyiiu5CFwHRfxm8=;
 b=t38u11Hv8b+ojoflHwFP5QZdlxbJExQkwWPWnVyVjtcZ8kGuy0x5FJvix40959hzEX
 nxjNm7+nRhvPKzAo7ZFzJSLz8rNzoFkqIewcswvjiBUeQ9I5XjE7xyvOPY3/1JvcxKg6
 pE3JlSZziim+GBPg1Fop5FC0flyUWpkWy2spGxnITIZ2vdulj6vh0Yi+V698OOzL17bd
 B4EDvqhIxR8pBvgM8HfJ23wplJsJ5mFTfI+3lmXoLUTQSNczhM9cskTLNhKD0dCJyLvk
 J7AlsxqEGh4IYQB9tIDKJRmy+xyYpyBUykdKiBO898u3V6JEOk0b/O5r8VA2GqWKVoJy
 pPug==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:subject:to:cc:references:from:message-id
 :date:user-agent:mime-version:in-reply-to:content-language
 :content-transfer-encoding;
 bh=Xp5xZYra07gEC132g1qMNKIzGmLHyyiiu5CFwHRfxm8=;
 b=p/kqaec4NhxBqcQ/f9lR3lSxZotnMtAR1iOH5K9JRxNHHVlnkYYnHpYFYphhDZTrDd
 LvSA9uhOlonxu7CjQEVxKoZOxMcZd2qZLd3gF/Iv5woz0PmfeXJpp1FISYNfRMORG63g
 e18kYDUK7w7XAugHBXK4lloTt1AHeeXibOdQpv/WsjDfnYaDay3fH9DtACu6yMvjS0ea
 BJbF5WBwocFW+jx7hVpdgXgImHxxhU8zB13HiBAgWIXejl2iohwh2HARQceLwoppCkUE
 BEXHzGW+5ysBf+Ci6/k0Wl+DzWaxiTbE0LnpkcYecschFKIs/AthomB4lOy+nrckkGVA
 K3bA==
X-Gm-Message-State: AOAM5331SI9/Mt+NHhdTqNOQ0DZHTYWew8L4Cr/OYjnQQVX/OT4vk+kJ
 F/PnU7C8Ci7T8xKS9EqDWqC7BN1wJWE=
X-Google-Smtp-Source: ABdhPJxZ6NKOCOpIBdXcgWLFXo33ewkV6emnz1vozxUsf3Xu3q/EnCF7x1X9vvBvwm2cIAK5kLkjSA==
X-Received: by 2002:a5d:6e92:: with SMTP id k18mr14359689wrz.94.1623018083828; 
 Sun, 06 Jun 2021 15:21:23 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id b10sm16538208wrr.27.2021.06.06.15.21.22
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Sun, 06 Jun 2021 15:21:23 -0700 (PDT)
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN>
 <87tumbv5qh.fsf@HIDDEN> <5efda5a3-f7ed-ca90-9e70-b35eb1c24750@HIDDEN>
 <CALDnm51pYqMGbh7sYDxZ5dMV+6ntp5kaTrb7gfuiRD+LzeAKYg@HIDDEN>
From: Dmitry Gutov <dgutov@HIDDEN>
Message-ID: <31baa0d5-02e0-368d-7946-7a3b98a8a5ca@HIDDEN>
Date: Mon, 7 Jun 2021 01:21:22 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
In-Reply-To: <CALDnm51pYqMGbh7sYDxZ5dMV+6ntp5kaTrb7gfuiRD+LzeAKYg@HIDDEN>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Spam-Score: 0.5 (/)
X-Debbugs-Envelope-To: 48841
Cc: Stefan Monnier <monnier@HIDDEN>, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -0.5 (/)

On 06.06.2021 21:37, João Távora wrote:
> Bottom line is that something (TM) happened to speed up the whole thing 
> when I skipped over that whole part. I had vertical mode basically 
> visually equivalent to vertical, but quite slower.  After skipping that 
> part they became practically equivalent. And you yourself witnessed this 
> when switching yo vertical mode, which is when the skip is made.

Yep.

>   I'll check later in the week, away from my computer now.

Looking forward to it.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 22:20:22 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 18:20:22 2021
Received: from localhost ([127.0.0.1]:54113 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lq182-0003sV-Dd
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 18:20:22 -0400
Received: from mail-wm1-f41.google.com ([209.85.128.41]:55914)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lq181-0003sJ-1z
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 18:20:21 -0400
Received: by mail-wm1-f41.google.com with SMTP id g204so8758346wmf.5
 for <48841 <at> debbugs.gnu.org>; Sun, 06 Jun 2021 15:20:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:from:subject:to:cc:references:message-id:date:user-agent
 :mime-version:in-reply-to:content-language:content-transfer-encoding;
 bh=6xB7X+SdGtL2L6oP8WIEDQz7toaKPv+5Hm37Y2uyvgw=;
 b=a1KoxI9rJJqtL0BWSqrySt04YDTiiG9HggNeEDy9PJTU0sgcSMc4qM69t3n2Ld2nct
 +wC7pG1iaN+K1lfPXmQYZo//s/gyw4Fsm78NI1Vw0j7YP8Ju4UK/tHDyl2SGZg66V3a0
 1Hnki1o+vLQ2Bl9BptYN1jhwBUf2OA1DxIiFrZQfRRqjzZZyKgwxSUQPEOk6T8APVe8a
 7d0ME775pyw5+q1DHsIvqV4rBhzWTuaNecyOxsut/Xc1lOgUmRqAZSINDNYoGptOXd19
 DBKQqliXFdQ60CkL+FXg3kr5hcZ+BTcuQfQUwFxabnicdod2+XmqwULhTfB+Pitl18fC
 sUxg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:from:subject:to:cc:references:message-id
 :date:user-agent:mime-version:in-reply-to:content-language
 :content-transfer-encoding;
 bh=6xB7X+SdGtL2L6oP8WIEDQz7toaKPv+5Hm37Y2uyvgw=;
 b=LI+qC3/uCpCQTzOFHHPsINAQXgfYFxUvaEmfvhxVkmMtYhqV1EYPCk431Mj//AzLgM
 ufyVbBelDusZykgF4QDvA7AGgyeJ+sH1deX5rcW6v5KKA6J4fzjTFWDfm3CDdNy71/CF
 jnK0xOHYqW7SLMIWMgi/vf/QLEdD7LTRydWlaUt7jkhmS84dYoYY2HWWODLtpPKy3dN7
 FDuluOBPWiuCThCFgmbHepW4t/VqQtxGNAZp6N2+RUn1iBHCObKHuZ/PsttwvCKRBLTK
 EbgBCq9qMWmaRbyyTa2ptKxyV+LCfQnKDWzNF9dWsj7O6Gn+UFUkiD/KMZyv+wRx/8js
 w0Og==
X-Gm-Message-State: AOAM531v+/vT0EjkmMsGo1RLBsmJo7xmQTII+sfnn+xlDGAQEF/52ps3
 dAfYBvcNr5QE8n47eyghw0kXIH+Qbzc=
X-Google-Smtp-Source: ABdhPJxUNQiB4hfz0s0XMgQt0Ms9H8tU0km54ChLGjaVQn1cLavSa0X8onAIfrts/mYK5RIQEQFDtQ==
X-Received: by 2002:a7b:cbc4:: with SMTP id n4mr14439600wmi.153.1623018015138; 
 Sun, 06 Jun 2021 15:20:15 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id w13sm14973997wrc.31.2021.06.06.15.20.14
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Sun, 06 Jun 2021 15:20:14 -0700 (PDT)
From: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN>
 <87y2bnv5xc.fsf@HIDDEN>
Message-ID: <35be6652-9c8d-ee21-e9eb-9598ad6777eb@HIDDEN>
Date: Mon, 7 Jun 2021 01:20:13 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
In-Reply-To: <87y2bnv5xc.fsf@HIDDEN>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Spam-Score: 0.5 (/)
X-Debbugs-Envelope-To: 48841
Cc: monnier@HIDDEN, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -0.5 (/)

On 06.06.2021 09:54, João Távora wrote:

>> Perhaps not sorting exactly, but the scoring part? Lowering the
>> implementation into C might help, we discussed something like that in
>> the past.
> 
> Perhaps, all could be measured.  But I also remember explaining that
> scoring is basically free.  The flex algorithm search algorithm is
> greedy already, it doesn't backtrack.  Given a pattern 'foo' against
> 'fabrobazo', it takes 9 steps to see that it matches.  I can't see any
> other way to improve that, short of a something like a tottaly different
> string implementation.  The scoring's numeric calculations at each step
> are trivial.

Thanks, if it's indeed that fast, I might have a use for it as well, in 
a different context. ;-)

>> And/or pick a different algorithm. E.g. Jaro-Winkler, which apparently
>> is used in a lot of "fuzzy matching" implementations out there, it's
>> pretty fast.
> 
> That may be useful, but for other purposes.  If I understand correctly,
> Jaro-Winkler is for finding the distante between two arbitrary strings,
> where the first in not a subsequence of the second.  I bet google uses
> stuff like that when you accitendally transpose characters.  Flex just
> gives up.  Those other others algos still catch the match (and Google
> than probably NL-scours your most intimate fears and checks with your
> local dictator before showing you typing suggestions)

I'm not crazy about shuffling completion, but some people did indeed ask 
for it. The filtering step has to be more complex, though (you can't 
just construct a straightforward regexp to filter with).

>> I took an example like
>>
>>    (setq s (all-completions "" obarray))
>>    (setq ss (cl-delete-if-not (lambda (s) (string-match-p "a" s)) s))
>>
>> then
>>
>>    (benchmark 1 '(completion-all-completions "a" ss nil 1))
>>
>> prints 0.180s here, whereas a "pure Ruby" implementation of
>> Jaro-Winkler takes about 0.060s on the exact same set of strings. But
>> perhaps Ruby is just faster than Elisp, I don't have a good
>> comparison.
> 
> Go ahead and kill the scoring calculationg altogether in
> completion-pcm--hilit-commonality.  I bet it won't make a difference.
> If fact, for that experiment, try a simple substring search.

Same result, indeed. We should note, though, that 
completion-pcm--hilit-commonality has some steps that were added 
together with the 'flex' style, for it to work.

> I bet
> you're just seeing an inferior GC at work, or a string implementation
> that's made optimized for other stuff that Ruby's can't, like
> propertization.  Try making Ruby strings that mimic Elips if you've time
> to spare...

I did some instrumenting, replacing (completion-pcm--hilit-commonality 
pattern all) inside completion-flex-all-completions with 
(benchmark-progn (completion-pcm--hilit-commonality pattern all)). 
Recompiled between each change (interpreted mode gives very different 
numbers).

Unmodified, the call takes ~85ms:

   Elapsed time: 0.085520s (0.068406s in 4 GCs)

If I comment everything inside its first lambda except the returned 
value (making the function the same as #'identity), the time goes down 
to <1ms.

Uncomment the 'copy-sequence' and 'string-match' calls (which one might 
suspect of garbage generation):

   Elapsed time: 0.006380s

Tried binding gc-cons-threshold to a high value, and even galling 
garbage-collect-maybe (or not): that speeds it up, but adds some 
unpredictable GC pauses later (though it would be nice to be able to 
consolidate the pauses into one collection pass).

Long story short, the patch I just installed, to reuse the match data, 
brings the runtime down to

   Elapsed time: 0.066388s (0.050087s in 3 GCs)

Tried other things like moving the update-score-and-face lambda out of 
the mapcar loop - that didn't move a needle. Someone more familiar with 
the code might get further. But perhaps it's just the cost of executing 
this logic in Lisp 12000 times, and doing some of that in C would be the 
next step.

And a weird part: replacing all repeated (length str) calls with a 
reference to an existing local binding makes it *slower* (back to the 
original performance). Check this out:

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index d5a0118b7c..d7102245a2 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3544,7 +3544,7 @@ completion-pcm--hilit-commonality
                      score-numerator   (+ score-numerator (- b a)))
                     (unless (or (= a last-b)
                                 (zerop last-b)
-                               (= a (length str)))
+                               (= a end))
                       (setq
                        score-denominator (+ score-denominator
                                             1
@@ -3562,12 +3562,12 @@ completion-pcm--hilit-commonality
             ;; for that extra bit of match (bug#42149).
             (unless (= from match-end)
               (funcall update-score-and-face from match-end))
-           (if (> (length str) pos)
+           (if (> end pos)
                 (add-face-text-property
                  pos (1+ pos)
                  'completions-first-difference
                  nil str))
-           (unless (zerop (length str))
+           (unless (zerop end)
               (put-text-property
                0 1 'completion-score
                (/ score-numerator (* end (1+ score-denominator)) 1.0) 
str)))
@@ -3980,7 +3980,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




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 21:33:45 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 17:33:45 2021
Received: from localhost ([127.0.0.1]:54063 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lq0Ov-0002kd-JW
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 17:33:45 -0400
Received: from mail-pj1-f51.google.com ([209.85.216.51]:39516)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lq0Os-0002kO-0d
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 17:33:44 -0400
Received: by mail-pj1-f51.google.com with SMTP id
 o17-20020a17090a9f91b029015cef5b3c50so10654716pjp.4
 for <48841 <at> debbugs.gnu.org>; Sun, 06 Jun 2021 14:33:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=NPhMA2y8vLE5TrIVwEoGXz/FQcVSRu75PvU4MAYmN4g=;
 b=G7YFfDUkQGrl0AxEvvweDoFEcjJZQwlsZvYWUpRWUZkcYH4JzOSqepC5uYX5hgL/2k
 JXC0gxPVJkvkmlbFv3sO8DS1K8+coYz1o3wgv+dQzkZXtieVlWk5+7FzVMs2kcpBH5Al
 9ozhhyF1FzWnCG9DDx7LKtC5Bp9p2GG7wjoO9mspU/zeivanp6Z9BOKvnPysQGTHEQIW
 7begGfCT9Hbuphr5PUqvPGx/XqpbsdHeT3pZ/YDvlXE0c79CtuE5hyc7VIZKgW89fxJV
 l2RAaN7RJRZtOHN5QIY2eaavh3uxPB6kMPj/AtjEU6riq9ASqEAXc9X7ezQAOFbWjM2t
 pt4w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=NPhMA2y8vLE5TrIVwEoGXz/FQcVSRu75PvU4MAYmN4g=;
 b=BW/hG0xdGNH+cgbGpmCkwblGmFJreMj75kV3+2FT3pivIf5H4iYCIXZJhN5kevkYgZ
 o/0xbGFhlYVAH/fCMSC3gyPwRcoaYyveBnS5xHkjtvbckjsxEh/ovRKhBE5GLHj7J5Tk
 n+i5LntyBPVEYhIvaJuVntD/+q5r4V0+iF+sKeH8XnrLJTS3gjZKEvEH7kouRfCs7qEY
 X8mU/DNKnBaszF5xjY2kYzIFRn351aE0dTVkjkBkgtcr1DUbr6ryOOPH8EWW3Afdoeu4
 3Vl23xKE1F5uyjQVBQl3X5XAl+T0lpNRqG5583MEt03tX0rG9yMZeqrWT9I5cGNont1V
 HGng==
X-Gm-Message-State: AOAM530igLrpFaGOvbyQl3pYtPmbKAfml3QuuHUb0kpZeHsTUed2ZboB
 4GZ+XH14VMowJe3CC/YiVInAu2AY0GqIQzxVeFU=
X-Google-Smtp-Source: ABdhPJyE1wolXalDUCeqQI75AGiw09gZA3Ob+V6CNtpPBvUIXt2K7Ljb3akVClHxD4MJBWDc0WvgFGuMROvM3b6hLtA=
X-Received: by 2002:a17:902:8b8a:b029:108:7849:dae0 with SMTP id
 ay10-20020a1709028b8ab02901087849dae0mr14807401plb.36.1623015216200; Sun, 06
 Jun 2021 14:33:36 -0700 (PDT)
MIME-Version: 1.0
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN>
 <87tumbv5qh.fsf@HIDDEN> <jwv8s3mubk2.fsf-monnier+emacs@HIDDEN>
In-Reply-To: <jwv8s3mubk2.fsf-monnier+emacs@HIDDEN>
From: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
Date: Sun, 6 Jun 2021 22:33:22 +0100
Message-ID: <CALDnm50KzVmTB0GMux-9gMVUzz6-H5aj0jsoNwzAANmtx4nmYw@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: Stefan Monnier <monnier@HIDDEN>
Content-Type: multipart/alternative; boundary="0000000000006d3d5a05c41fad40"
X-Spam-Score: -0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org, Dmitry Gutov <dgutov@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

--0000000000006d3d5a05c41fad40
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Sun, Jun 6, 2021, 18:55 Stefan Monnier <monnier@HIDDEN> wrote:

> In practice I'd be surprised if it ever reaches the 20% mark of the time
> spent.


Personally, I'm usually suprised if less than 80% of my estimates aren't
totally off. :) Anyway, if not try-completion like I theorized, it should
be reasonably easy to pinpoint: something non-fido-essential in that else
branch is causing a real slowdown.

Jo=C3=A3o

>
>

--0000000000006d3d5a05c41fad40
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D=
"gmail_attr">On Sun, Jun 6, 2021, 18:55 Stefan Monnier &lt;<a href=3D"mailt=
o:monnier@HIDDEN">monnier@HIDDEN</a>&gt; wrote:</div><b=
lockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px =
#ccc solid;padding-left:1ex">
In practice I&#39;d be surprised if it ever reaches the 20% mark of the tim=
e spent.</blockquote></div></div><div dir=3D"auto"><br></div><div dir=3D"au=
to">Personally, I&#39;m usually suprised if less than 80% of my estimates a=
ren&#39;t totally off. :) Anyway, if not try-completion like I theorized, i=
t should be reasonably easy to pinpoint: something non-fido-essential in th=
at else branch is causing a real slowdown.</div><div dir=3D"auto"><br></div=
><div dir=3D"auto">Jo=C3=A3o</div><div dir=3D"auto"><div class=3D"gmail_quo=
te"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-lef=
t:1px #ccc solid;padding-left:1ex">=C2=A0<br>
</blockquote></div></div></div>

--0000000000006d3d5a05c41fad40--




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 18:37:29 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 14:37:29 2021
Received: from localhost ([127.0.0.1]:53881 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpxeL-0002Yv-23
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 14:37:29 -0400
Received: from mail-pg1-f170.google.com ([209.85.215.170]:43905)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lpxeH-0002Yg-BD
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 14:37:27 -0400
Received: by mail-pg1-f170.google.com with SMTP id e22so12096118pgv.10
 for <48841 <at> debbugs.gnu.org>; Sun, 06 Jun 2021 11:37:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=UayIdd/Hmwygy0E2HCpjkNrLxmEM9NXMmDfmmL2aajU=;
 b=BMNjqeEQZdYXqcjbcm8Zod9A7qO4zTps07KMJhftuQn+JKG0yFwmz2QXkTBG0OnRUY
 /vGK9SxawMe6VSywEUy2sueO9c1LQvI9VLVHw70ItskrwVHWHChN3442P/kyPYTfVaYm
 pfFCq+UJEpelkj+muVBGEN6xt9c0kxJddaVHCDGF+lFhzo0D4p1UMMSD0hQ5J0QQkS3o
 mbLz4S2x4+vE3iaw5L67BIoohc/uzge3otwBuxeMY9mkXkzBoyPSWJPfcIpqXYSe+4sL
 HF2KLaTVxXiqPLKbznCPGLjGMoD7rXKB1kyusn41ULVLBKS6PSJA7XBg7ZoqRBs65ReV
 KEzA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=UayIdd/Hmwygy0E2HCpjkNrLxmEM9NXMmDfmmL2aajU=;
 b=Lz8H80plUwjHK7LfECuCJ6ptHy7uJe8gmp0VY2J7Q3JZqlQRjGesUOIz5dt38Ezza8
 4JVvCnU9aaBpa1ffOphyI6T22qU94DQm4R9lENAj7EkcgHurB6JhC8q/pASYkzfwKkx4
 lLg9xFl34lKnylR8z01+LjokGr8LCYOTXYj2f8lvdqqmmQPbzcrW3H8IptpDwp4Jvcis
 QJ/h+wEr7Y3K7LTEiY79tBmFwdc8Nrb7AQC+N7lEdaBVn7wt7tkfjReTRZD8v9e2ST6n
 G1Gk/ipTa2JhV91qIOGlhJluNgtBExj2LVqV8leoH8Q2IXXwvSvEBbD9wHgpZIgPzOuU
 3cQg==
X-Gm-Message-State: AOAM532MDgShfDkz5N8mWKmAzDMcLZN/wA0VE0k0dSzo31uMwF2jthVv
 ++9C/4NK/dxDzZqltXzgyjI9ypg4BZtamDI2Z+8=
X-Google-Smtp-Source: ABdhPJz41XdKUlX0GgmTlPGJ83qQkJUwTPsfFZNzXPI6tygAlsXvU79h1t9+vCXmvB7Ba0Rt1p5ZRgrRDV18EfJW5yg=
X-Received: by 2002:a62:5547:0:b029:2ec:8f20:4e2 with SMTP id
 j68-20020a6255470000b02902ec8f2004e2mr12011622pfb.71.1623004639234; Sun, 06
 Jun 2021 11:37:19 -0700 (PDT)
MIME-Version: 1.0
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN>
 <87tumbv5qh.fsf@HIDDEN> <5efda5a3-f7ed-ca90-9e70-b35eb1c24750@HIDDEN>
In-Reply-To: <5efda5a3-f7ed-ca90-9e70-b35eb1c24750@HIDDEN>
From: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
Date: Sun, 6 Jun 2021 19:37:05 +0100
Message-ID: <CALDnm51pYqMGbh7sYDxZ5dMV+6ntp5kaTrb7gfuiRD+LzeAKYg@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: Dmitry Gutov <dgutov@HIDDEN>
Content-Type: multipart/alternative; boundary="000000000000fd8ce305c41d365f"
X-Spam-Score: -0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: Stefan Monnier <monnier@HIDDEN>, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

--000000000000fd8ce305c41d365f
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Sun, Jun 6, 2021, 17:55 Dmitry Gutov <dgutov@HIDDEN> wrote:

> On 06.06.2021 09:59, Jo=C3=A3o T=C3=A1vora wrote:
> > Very true, but here's the suprise: In the flex style, there are a_lot_
> > of "possible completions" for the null or very short patterns.  So thos=
e
> > calculations -- which were more than certainly thought up for prefix-is=
h
> > styles -- are quite slow (and also quite useless for flex).  At least
> > that's my theory.
>
> try-completion doesn't trigger any completion style machinery; only
> completion-try-completion does.
>

I have no idea if completion style stuff b is related. Just that else
branch is there to calculate some 'determ' thing and a cursory look
revealed try-completion calls being passed 'comps', or 'completions'.
Presumably lots of data given short flex style patterns. No idea what it
accomplishes, as I said.

Bottom line is that something (TM) happened to speed up the whole thing
when I skipped over that whole part. I had vertical mode basically visually
equivalent to vertical, but quite slower.  After skipping that part they
became practically equivalent. And you yourself witnessed this when
switching yo vertical mode, which is when the skip is made.

 I'll check later in the week, away from my computer now.

And are we talking about the 'try-completion' call which is guarded with
> (when icomplete-hide-common-prefix ...)?
>

No idea

>
> icomplete--fido-mode-setup sets that variable to nil.
>

May be.

Jo=C3=A3o

>

--000000000000fd8ce305c41d365f
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D=
"gmail_attr">On Sun, Jun 6, 2021, 17:55 Dmitry Gutov &lt;<a href=3D"mailto:=
dgutov@HIDDEN">dgutov@HIDDEN</a>&gt; wrote:<br></div><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex">On 06.06.2021 09:59, Jo=C3=A3o T=C3=A1vora wrote:<br>
&gt; Very true, but here&#39;s the suprise: In the flex style, there are a_=
lot_<br>
&gt; of &quot;possible completions&quot; for the null or very short pattern=
s.=C2=A0 So those<br>
&gt; calculations -- which were more than certainly thought up for prefix-i=
sh<br>
&gt; styles -- are quite slow (and also quite useless for flex).=C2=A0 At l=
east<br>
&gt; that&#39;s my theory.<br>
<br>
try-completion doesn&#39;t trigger any completion style machinery; only <br=
>
completion-try-completion does.<br></blockquote></div></div><div dir=3D"aut=
o"><br></div><div dir=3D"auto">I have no idea if completion style stuff b i=
s related. Just that else branch is there to calculate some &#39;determ&#39=
; thing and a cursory look revealed try-completion calls being passed &#39;=
comps&#39;, or &#39;completions&#39;. Presumably lots of data given short f=
lex style patterns. No idea what it accomplishes, as I said.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">Bottom line is that something (TM) ha=
ppened to speed up the whole thing when I skipped over that whole part. I h=
ad vertical mode basically visually equivalent to vertical, but quite slowe=
r.=C2=A0 After skipping that part they became practically equivalent. And y=
ou yourself witnessed this when switching yo vertical mode, which is when t=
he skip is made.</div><div dir=3D"auto"><br></div><div dir=3D"auto">=C2=A0I=
&#39;ll check later in the week, away from my computer now.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto"><div class=3D"gmail_quote"><blockquot=
e class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc sol=
id;padding-left:1ex">And are we talking about the &#39;try-completion&#39; =
call which is guarded with <br>
(when icomplete-hide-common-prefix ...)?<br></blockquote></div></div><div d=
ir=3D"auto"><br></div><div dir=3D"auto">No idea</div><div dir=3D"auto"><div=
 class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 =
0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
icomplete--fido-mode-setup sets that variable to nil.<br></blockquote></div=
></div><div dir=3D"auto"><br></div><div dir=3D"auto">May be.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">Jo=C3=A3o</div><div dir=3D"auto"><div=
 class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 =
0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
</blockquote></div></div></div>

--000000000000fd8ce305c41d365f--




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 17:55:16 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 13:55:16 2021
Received: from localhost ([127.0.0.1]:53837 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpwzU-0001O9-Dx
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 13:55:16 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:40707)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <monnier@HIDDEN>) id 1lpwzR-0001Nq-IM
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 13:55:15 -0400
Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1])
 by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 0D81680497;
 Sun,  6 Jun 2021 13:55:07 -0400 (EDT)
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
 by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 9441680240;
 Sun,  6 Jun 2021 13:55:05 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
 s=mail; t=1623002105;
 bh=Y2Yf7mmGeRVtwYUTw1aQq8xVaU3V4dqOpwvkUmh2/PE=;
 h=From:To:Cc:Subject:References:Date:In-Reply-To:From;
 b=MnePlB5GfoC1B9ACLNXNJ4jc9A6Tiv8jMEenZmcPuEsSYU1C07bsB7bHXglDfDKEk
 9dJx5wCkBBHeletib7ZIBFd18QPbXOdkj3UYlFjrRJwpEN0CTCrawmCFr++lgmGyB0
 qr0ygtyYveeQjfxQhNp0hnLX1EcOEwHMZWIVIcPkxTBNRhaofVUwcnmCs0wso/ABio
 7OVI8OXOe1im4KOKZL+yntsLdD3s/k0rvTsp99opE6/P6LbYRxzQzQoaCfz3R/Xh2T
 8iy30Zk0yMfZ92DG3stnjxIjbaaeDSWmTYhF2pOrPp/qaKVJT0tWz5KdxBBKUF+eFv
 nhwuhXAOC4QVw==
Received: from alfajor (69-196-163-239.dsl.teksavvy.com [69.196.163.239])
 by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 623201200E2;
 Sun,  6 Jun 2021 13:55:05 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
To: =?windows-1252?B?Sm/jbyBU4XZvcmE=?= <joaotavora@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
Message-ID: <jwv8s3mubk2.fsf-monnier+emacs@HIDDEN>
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN>
 <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN>
 <87tumbv5qh.fsf@HIDDEN>
Date: Sun, 06 Jun 2021 13:55:04 -0400
In-Reply-To: <87tumbv5qh.fsf@HIDDEN> (=?windows-1252?Q?=22Jo=E3o_T=E1vo?=
 =?windows-1252?Q?ra=22's?= message of "Sun, 06
 Jun 2021 07:59:02 +0100")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-SPAM-INFO: Spam detection results:  0
 ALL_TRUSTED                -1 Passed through trusted hosts only via SMTP
 AWL -0.020 Adjusted score from AWL reputation of From: address
 BAYES_00                 -1.9 Bayes spam probability is 0 to 1%
 DKIM_SIGNED               0.1 Message has a DKIM or DK signature,
 not necessarily valid
 DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
 DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
 domain
X-SPAM-LEVEL: 
X-Spam-Score: -2.3 (--)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org, Dmitry Gutov <dgutov@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -3.3 (---)

> Very true, but here's the suprise: In the flex style, there are a _lot_
> of "possible completions" for the null or very short patterns.  So those
> calculations -- which were more than certainly thought up for prefix-ish
> styles -- are quite slow (and also quite useless for flex).  At least
> that's my theory.

In the very worst possible case, `try-completion` will be just as slow
as the original computation of the set of possible completions.  So at
most it will double the total time (and this assumes we do basically
nothing else than a single call to `all-completions` to get the set of
candidates and then display them).
In practice I'd be surprised if it ever reaches the 20% mark of the time spent.


        Stefan





Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 16:55:10 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 12:55:10 2021
Received: from localhost ([127.0.0.1]:53790 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpw3J-0008FB-Qm
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 12:55:10 -0400
Received: from mail-wm1-f48.google.com ([209.85.128.48]:38640)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lpw3G-0008EX-7H
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 12:55:08 -0400
Received: by mail-wm1-f48.google.com with SMTP id
 t4-20020a1c77040000b029019d22d84ebdso11002627wmi.3
 for <48841 <at> debbugs.gnu.org>; Sun, 06 Jun 2021 09:55:06 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:subject:to:cc:references:from:message-id:date:user-agent
 :mime-version:in-reply-to:content-language:content-transfer-encoding;
 bh=gH+LCQWfnd/B/jYANhu5DTPhrcbesR6icVxjK/vwRMA=;
 b=tolzYKuQtSdziE8dNpf5mYKoBN76RRGOVXKQ1VThY58Ttytn/RwH9jXt1j+dfo5fSP
 eKX36KGPgGWw+LoddrRzH1w0XLLhQ4bknzh99aTJuJD6QOaUEffdcmbYBLRAR6v7iIgx
 fvZt3foRg9O0lwjbTdBilSTPKiO8RsB3J/nfPDr07k+U26nU4StRKf0aupYdNm8HLWiq
 Y2ZKi1hRjotijSwbZckxRwKXQmNUpfNKZHXUA/8QCXh+9GPfVfBQIoeZsvn2I8y/TbNB
 2w0QuP7L11THADkJXeVO6kCL8PAdT3LaDvaTow7EZLkUqW654iQXMTE+09YM2ygvYulO
 HNKQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:subject:to:cc:references:from:message-id
 :date:user-agent:mime-version:in-reply-to:content-language
 :content-transfer-encoding;
 bh=gH+LCQWfnd/B/jYANhu5DTPhrcbesR6icVxjK/vwRMA=;
 b=ElLdIEMEs2Yyiy2OnsKy7X1PkIKJF8DwS7yeXPa7bZe5upCky1vXY2OYqxBbAiY7EN
 ZHq02/kF2qYTMoz9JvV5MVhWjGCqDBs6eJNR5PaqGaWCHI8sEYyRu7wUifVk6eTQAyFJ
 Ufm2EUMgdf1BSU6u4ldNHMiKgSz0cDIS2DMtJUwb043HOEzys5Ywg9QxYro3IFQKv32Q
 F3cnqnnHlgmnzcyD7hFwr88LJ5qel+RuKg29X9C6RVy+44xK+1oAk5EVysCQFObbv9An
 31cF91LJT4sZIG2KF/HQxHggRLPwF2zbap9/BEnv5A1sf4sw/6gPYYCa1145WbgAMte+
 CaSg==
X-Gm-Message-State: AOAM533wEDNc/2pMEpjpb9ak9sc7gWWS3UhrRRYzNtfNmkV2o9Wmg6NR
 x4k51fB82NxvvdM3sBl0MXeZdAzqiGM=
X-Google-Smtp-Source: ABdhPJyHsUXpJZQFt6v3Wb7zeycigzPlgH5ity4AwUhH4R+gvg5WZLJuLlWKvZGP78dsCaP8n2T05Q==
X-Received: by 2002:a1c:8049:: with SMTP id b70mr980029wmd.92.1622998500237;
 Sun, 06 Jun 2021 09:55:00 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id k82sm15044478wmf.11.2021.06.06.09.54.59
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Sun, 06 Jun 2021 09:54:59 -0700 (PDT)
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>,
 Stefan Monnier <monnier@HIDDEN>
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN>
 <87tumbv5qh.fsf@HIDDEN>
From: Dmitry Gutov <dgutov@HIDDEN>
Message-ID: <5efda5a3-f7ed-ca90-9e70-b35eb1c24750@HIDDEN>
Date: Sun, 6 Jun 2021 19:54:58 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
In-Reply-To: <87tumbv5qh.fsf@HIDDEN>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Spam-Score: 0.5 (/)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -0.5 (/)

On 06.06.2021 09:59, João Távora wrote:
> Very true, but here's the suprise: In the flex style, there are a_lot_
> of "possible completions" for the null or very short patterns.  So those
> calculations -- which were more than certainly thought up for prefix-ish
> styles -- are quite slow (and also quite useless for flex).  At least
> that's my theory.

try-completion doesn't trigger any completion style machinery; only 
completion-try-completion does.

And are we talking about the 'try-completion' call which is guarded with 
(when icomplete-hide-common-prefix ...)?

icomplete--fido-mode-setup sets that variable to nil.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 06:59:16 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 02:59:16 2021
Received: from localhost ([127.0.0.1]:50514 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpmke-0008Qg-7p
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 02:59:16 -0400
Received: from mail-wr1-f45.google.com ([209.85.221.45]:39606)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lpmkY-0008QP-AZ
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 02:59:14 -0400
Received: by mail-wr1-f45.google.com with SMTP id l2so13742469wrw.6
 for <48841 <at> debbugs.gnu.org>; Sat, 05 Jun 2021 23:59:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=from:to:cc:subject:references:date:in-reply-to:message-id
 :user-agent:mime-version:content-transfer-encoding;
 bh=D/FgjubYlVB3UyvzhPfsFoMObSPBOZ08gD/3yeZ7BFM=;
 b=Xw7J9yr1M92Nbrxld8c7B4bYSmX80wsCYyl76BN8M7IjZEUCeWMAEBxsuy+gC9kaut
 T6q8H+2W/fF2CEX03FUJKZup4b1BoIfknr8gBaQVzCxXItu9Xg1PfeNXsVKYu5BxTp5+
 8apllLapg/hYw0j6UupIg4EcLnf7XLnmLQKpa3yItmgDOGj3mW1dZOPnycFxevEkTXqF
 X802MM3hET0TNWmQf7neQ0yriTBoMAsaKQiREZ3P8N3d4ZP7ZZTrnfY4Fm+V16cJT/dg
 qCH5C9+kaVdBfWUIVb9tcV+85FUe5siCp3x7or3cglHr/sBx5MWKyfzWWWpWHK38WWbO
 bjJg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to
 :message-id:user-agent:mime-version:content-transfer-encoding;
 bh=D/FgjubYlVB3UyvzhPfsFoMObSPBOZ08gD/3yeZ7BFM=;
 b=dKFo8ON5vUTR/xbgk9pGtpFA39xfqZOzdZAZu4ta8K7j7L+AJEJpAEn4QvVS/bJa6I
 rXZeOSoERcPqKL+hTDdNbkqjHA3RSgychSYJWL1aXZ1Mn3AmK+DUc3ZaSQsblEpDRnl/
 RjOXb892SRATFi5wb97nOU+z4W0XKLchzqi+QBfug76uiikSzM+ONrMDhPQ2tgjNbPvK
 +48qT1vqAz/fSjTg6hMMt8n4c2C8M64yaJqCtzErShCyySMggxvFyWtawXeSeIa1DwAt
 obexV2a+2wAhoWUYTzEvGRRbyhtu2CSPnMe8zHWJD2U0WHGiMefK79xv8rMbStiBK6sO
 9Mmg==
X-Gm-Message-State: AOAM531nsFc3hytUZH3njd3LrU11zbOAhs6Asa/cQ3fpERz1kmsHIlWo
 haOnWgOQj0ZGrwO4Ia0NQ2MJwlFTG4o=
X-Google-Smtp-Source: ABdhPJwkbaJ4FZOZqJ+mTC3XpgnSFtWq0YdTjbGczFrpscWhGCWmHFzGbmTTUV5KZrckevDpQRUE3Q==
X-Received: by 2002:a5d:6b52:: with SMTP id x18mr11222618wrw.11.1622962744217; 
 Sat, 05 Jun 2021 23:59:04 -0700 (PDT)
Received: from krug (a94-133-55-152.cpe.netcabo.pt. [94.133.55.152])
 by smtp.gmail.com with ESMTPSA id l10sm11678141wrm.2.2021.06.05.23.59.03
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Sat, 05 Jun 2021 23:59:03 -0700 (PDT)
From: =?utf-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
To: Stefan Monnier <monnier@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN>
 <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN> <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN>
Date: Sun, 06 Jun 2021 07:59:02 +0100
In-Reply-To: <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN> (Stefan Monnier's message
 of "Sat, 05 Jun 2021 22:34:53 -0400")
Message-ID: <87tumbv5qh.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org, Dmitry Gutov <dgutov@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Stefan Monnier <monnier@HIDDEN> writes:

>> Stefan knows best here.  Regardless of its use, it seems to require
>> another try-completion call in all the filtered candidates (which might
>> be very big) so that's probably where the extra lag comes from.
>
> IIRC the `try-completion` call is performed on the list of possible
> completions rather than on the original completion table, so it should
> be quite fast.  I'd be surprised if it is a significant portion of the
> overall time.

Very true, but here's the suprise: In the flex style, there are a _lot_
of "possible completions" for the null or very short patterns.  So those
calculations -- which were more than certainly thought up for prefix-ish
styles -- are quite slow (and also quite useless for flex).  At least
that's my theory.

Jo=C3=A3o




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 06:55:07 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 06 02:55:06 2021
Received: from localhost ([127.0.0.1]:50510 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpmgc-0008Kx-C9
	for submit <at> debbugs.gnu.org; Sun, 06 Jun 2021 02:55:06 -0400
Received: from mail-wr1-f41.google.com ([209.85.221.41]:46707)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lpmga-0008KN-Be
 for 48841 <at> debbugs.gnu.org; Sun, 06 Jun 2021 02:55:05 -0400
Received: by mail-wr1-f41.google.com with SMTP id a11so11828657wrt.13
 for <48841 <at> debbugs.gnu.org>; Sat, 05 Jun 2021 23:55:04 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=from:to:cc:subject:references:date:in-reply-to:message-id
 :user-agent:mime-version:content-transfer-encoding;
 bh=8svOU4tjQPHm28oClawcBoM27TLRHh2uRNoVyznm7BM=;
 b=jAqd/iW4RyUjcPqSpVpQN85IrGfJY7Lu7U5vKJcZZ1whLXULjMzcMYN8Q6v0yeuCsP
 BCUWMOjQJ5S0M9tId1YozZPda5ndFn8FNB4cbWnugGGNRx1EP77UBySt4bPFHcKDFF6n
 YQUm70dglbsozMX+Hbo29Ug4zVDddz020MZ0uuG9D3al//sWRywKjiL3ddc581HkrQJ+
 Pr7d5kbN0+tLM6K064tRjKU+AWUCh7K1DAvKbLRrondIxWGwWV5u9uLjKz4j4scdnnJI
 wn260Hlkh1chT2uKXm93CtPs4rQSX22Mc6Jcv9NxL54AB4bOXHdyVhmWvg12Q7Q5ky4e
 ESHQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to
 :message-id:user-agent:mime-version:content-transfer-encoding;
 bh=8svOU4tjQPHm28oClawcBoM27TLRHh2uRNoVyznm7BM=;
 b=HZqimXrTRoap/mDPvMLXzMYMaPU4kbOSwfLM1MdcxoVwi9QnZbW6h2LEqvXXyrchJL
 6lajOY9H4nhfGz6imfSY31Yh7SCXMfB/41hxO3QGsEqIxKoFlq2HMxAFyQd0gEnAssp4
 ULF1X9m3xxzP/FbaED/RwqEhkWcPXHaJPAg0bnyftkhXxX5DFf+dCI6cCS9BS7b8ysJH
 RhyzZDFiA8KmRmP/2gpvv62A62RU8qRcznXs9zyQyDXdNfq7gKNF09ZFw5dqs5rQ/NfB
 tbMFqligf26L9C5fm7m764XmGw/v53m/p7xmfVv/has7JjElmX9ydYBB2myo7KnN3ZMj
 uMEA==
X-Gm-Message-State: AOAM531BruKQJxvwpEOriaM0XDYns3clb165nnd3AAlwNimI5oSSej78
 wF4L+N6fmQXVhFSOn22h1kcgkkGbj4c=
X-Google-Smtp-Source: ABdhPJwlhxtEVcX5o9kk3H1nfUsvWJ5NtOUPqmG52LE39+JX2rvi6LAvfXm2VIV6gucCDFBhMmq09Q==
X-Received: by 2002:a5d:64c9:: with SMTP id f9mr9467877wri.121.1622962497990; 
 Sat, 05 Jun 2021 23:54:57 -0700 (PDT)
Received: from krug (a94-133-55-152.cpe.netcabo.pt. [94.133.55.152])
 by smtp.gmail.com with ESMTPSA id 125sm14121802wmb.34.2021.06.05.23.54.57
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Sat, 05 Jun 2021 23:54:57 -0700 (PDT)
From: =?utf-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN>
 <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN>
 <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN>
Date: Sun, 06 Jun 2021 07:54:55 +0100
In-Reply-To: <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN> (Dmitry Gutov's
 message of "Sun, 6 Jun 2021 03:25:20 +0300")
Message-ID: <87y2bnv5xc.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: monnier@HIDDEN, 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Dmitry Gutov <dgutov@HIDDEN> writes:

> On 06.06.2021 02:20, Jo=C3=A3o T=C3=A1vora wrote:
>> My bet is that the remaining lag is due to sorting.  In a dumb but
>> illustrative example, when given the pattern 'fmcro' flex-enabled
>> ido-mode pops 'flymake--backend-state-p--cmacro' to the top, while fido
>> mode selects the much more reasonable 'defmacro'.
>
> Perhaps not sorting exactly, but the scoring part? Lowering the
> implementation into C might help, we discussed something like that in
> the past.

Perhaps, all could be measured.  But I also remember explaining that
scoring is basically free.  The flex algorithm search algorithm is
greedy already, it doesn't backtrack.  Given a pattern 'foo' against
'fabrobazo', it takes 9 steps to see that it matches.  I can't see any
other way to improve that, short of a something like a tottaly different
string implementation.  The scoring's numeric calculations at each step
are trivial.

One way to verify this is to do the scoring, but simply disregard it for
sorting purposes.

> And/or pick a different algorithm. E.g. Jaro-Winkler, which apparently
> is used in a lot of "fuzzy matching" implementations out there, it's
> pretty fast.

That may be useful, but for other purposes.  If I understand correctly,
Jaro-Winkler is for finding the distante between two arbitrary strings,
where the first in not a subsequence of the second.  I bet google uses
stuff like that when you accitendally transpose characters.  Flex just
gives up.  Those other others algos still catch the match (and Google
than probably NL-scours your most intimate fears and checks with your
local dictator before showing you typing suggestions)

> I took an example like
>
>   (setq s (all-completions "" obarray))
>   (setq ss (cl-delete-if-not (lambda (s) (string-match-p "a" s)) s))
>
> then
>
>   (benchmark 1 '(completion-all-completions "a" ss nil 1))
>
> prints 0.180s here, whereas a "pure Ruby" implementation of
> Jaro-Winkler takes about 0.060s on the exact same set of strings. But
> perhaps Ruby is just faster than Elisp, I don't have a good
> comparison.

Go ahead and kill the scoring calculationg altogether in
completion-pcm--hilit-commonality.  I bet it won't make a difference.
If fact, for that experiment, try a simple substring search.  I bet
you're just seeing an inferior GC at work, or a string implementation
that's made optimized for other stuff that Ruby's can't, like
propertization.  Try making Ruby strings that mimic Elips if you've time
to spare...

> (The only J-W implementation in Elisp I have found yet --
> https://github.com/rdiankov/emacs-config/blob/master/.emacs-lisp/auto-com=
plete-1.3.1/fuzzy.el#L70
> -- is slower than the current scoring algo).

There you have it.

Jo=C3=A3o




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 02:35:03 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Jun 05 22:35:03 2021
Received: from localhost ([127.0.0.1]:50401 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpicx-0001xh-F6
	for submit <at> debbugs.gnu.org; Sat, 05 Jun 2021 22:35:03 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:5962)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <monnier@HIDDEN>) id 1lpicu-0001x9-QF
 for 48841 <at> debbugs.gnu.org; Sat, 05 Jun 2021 22:35:02 -0400
Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1])
 by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 455348091E;
 Sat,  5 Jun 2021 22:34:55 -0400 (EDT)
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
 by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id F00C780182;
 Sat,  5 Jun 2021 22:34:53 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
 s=mail; t=1622946893;
 bh=Pvtkr4jVWGi0EB0iHeipOtRHGH9utosN0azLOyY+OXg=;
 h=From:To:Cc:Subject:References:Date:In-Reply-To:From;
 b=I7Vq37i5x9WzLX0kMMrSWj0Q47LWavzTOVLkTfUd+aRZU9yR6v6AyvE5kstZivljA
 qhQgiG/XjjYxZCnIiu7PDKwfgANZTjfVIA7Czn32kGGSpqqNi9eVAW3TYMIKr72LAd
 SplW1ezMwOAbxg7CRRbbsB+y9rZ1wda6wEdVz65beOpEf/1kHW0FebaWyDwyL+A0S9
 IdewvPBukJXQIwBozZAsQMSPfDglbKeKbaiZMJEWWGqVmRHStdSZpGG4+y2HDqgMGK
 ME1JQXwbdqHjc/SNkxI0iHJNQe0B3SG6RLzyxOcrMcxZTM2eblzB0JqQ7w7N0inP6Z
 Js9UQEGwneFqg==
Received: from alfajor (69-196-163-239.dsl.teksavvy.com [69.196.163.239])
 by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id A38951202C2;
 Sat,  5 Jun 2021 22:34:53 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
To: =?windows-1252?B?Sm/jbyBU4XZvcmE=?= <joaotavora@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
Message-ID: <jwv1r9fvi2b.fsf-monnier+emacs@HIDDEN>
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN>
 <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN>
Date: Sat, 05 Jun 2021 22:34:53 -0400
In-Reply-To: <87a6o3x5j7.fsf@HIDDEN> (=?windows-1252?Q?=22Jo=E3o_T=E1vo?=
 =?windows-1252?Q?ra=22's?= message of "Sun, 06
 Jun 2021 00:20:28 +0100")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-SPAM-INFO: Spam detection results:  0
 ALL_TRUSTED                -1 Passed through trusted hosts only via SMTP
 AWL -0.024 Adjusted score from AWL reputation of From: address
 BAYES_00                 -1.9 Bayes spam probability is 0 to 1%
 DKIM_SIGNED               0.1 Message has a DKIM or DK signature,
 not necessarily valid
 DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
 DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
 domain
X-SPAM-LEVEL: 
X-Spam-Score: -2.3 (--)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org, Dmitry Gutov <dgutov@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -3.3 (---)

> Stefan knows best here.  Regardless of its use, it seems to require
> another try-completion call in all the filtered candidates (which might
> be very big) so that's probably where the extra lag comes from.

IIRC the `try-completion` call is performed on the list of possible
completions rather than on the original completion table, so it should
be quite fast.  I'd be surprised if it is a significant portion of the
overall time.


        Stefan





Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 00:25:30 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Jun 05 20:25:30 2021
Received: from localhost ([127.0.0.1]:50329 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpgba-0005DM-6W
	for submit <at> debbugs.gnu.org; Sat, 05 Jun 2021 20:25:30 -0400
Received: from mail-wr1-f42.google.com ([209.85.221.42]:37491)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lpgbY-0005D9-Aj
 for 48841 <at> debbugs.gnu.org; Sat, 05 Jun 2021 20:25:28 -0400
Received: by mail-wr1-f42.google.com with SMTP id i94so8116871wri.4
 for <48841 <at> debbugs.gnu.org>; Sat, 05 Jun 2021 17:25:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:subject:to:cc:references:from:message-id:date:user-agent
 :mime-version:in-reply-to:content-language:content-transfer-encoding;
 bh=OyKbGUaxzqqRRPXsYlvJT6X6qR6hOW9FB+ICq8Ii0O8=;
 b=ff6QakltRu3AYmhF1ybpdK+y+zNjgeOHowD1GM0XLCm8rr1veFjoB6ZEYdyp9fCam2
 RIM8PJDl9q5wyv9bUx7mZa1GLHEmDL9jxZ8M7hVV/e7z3YEW7jAFKyHz95ThP+maitjZ
 pLapwhMJpGRQ38ed1zmUtWrCw0x/OIh52HypucTtExkk5SpRMPJRlPXP+AHxqOtlq52k
 ZosMxR6wzPXxa+bHlMLYhydLXhtd/5T5XerInG051qLqZaaah6UHPbK0t31mWj2AdrQQ
 vmIhLpxSJGTnK/eM5Ww1Agrj4sEsNZGd53/ZCQsNrp6qfTRwCu8wuPQBiDBBzg2IjaLz
 hvoQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:subject:to:cc:references:from:message-id
 :date:user-agent:mime-version:in-reply-to:content-language
 :content-transfer-encoding;
 bh=OyKbGUaxzqqRRPXsYlvJT6X6qR6hOW9FB+ICq8Ii0O8=;
 b=XAGfctCMCjxU3gD8vLemh+X1dOPCybSPURQslrat8oeZEyTtIfXYs1ZxG+FcVcWNPP
 Cx4j3pIZmPiQHAmuqJ/qsCxN12BGg2WWwZCd4vR4LB/1vdpJR0rzJk8aWL/8JyMb60TH
 GoZJ7AcAi2J08MKVsJR4ci1V9Qi4RzAgFwEL0cPcbnRwKCTjMsr8bZE71eXnQZParZfN
 aOQc6cUCkqT+PmnC0KsMxCMQ8WjHYOO0gxAXnpetqCk1FZYwupaxt3ep3wqMj5g8oE6V
 fLyxM4uuJd4Sr2NZNPP99KWRfCgrAV8Fy8X1DN74bwSDfqOucvYkifWHKNnL3s62YWSA
 MRXg==
X-Gm-Message-State: AOAM531s8dw8y/cD9HJJ3OmN+yF8gGdkUs7j+o0pjCq9Nthas50QLusr
 4c2bNSgh+Qn93uRV93j+JnH34+SMfcw=
X-Google-Smtp-Source: ABdhPJxNFF2hHjfvaM1v8FfUn8Ke73bJfLruMsSFmbZifkJEb0Pd9X0Zx/8U31UrqtUxWw7L3moWPQ==
X-Received: by 2002:adf:ba07:: with SMTP id o7mr7103304wrg.160.1622939122593; 
 Sat, 05 Jun 2021 17:25:22 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id q1sm12723877wmq.48.2021.06.05.17.25.21
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Sat, 05 Jun 2021 17:25:22 -0700 (PDT)
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>,
 monnier@HIDDEN
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN>
From: Dmitry Gutov <dgutov@HIDDEN>
Message-ID: <dd69952b-bb7b-7e86-466c-c2117f839cc4@HIDDEN>
Date: Sun, 6 Jun 2021 03:25:20 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
In-Reply-To: <87a6o3x5j7.fsf@HIDDEN>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Spam-Score: -0.1 (/)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.1 (-)

On 06.06.2021 02:20, João Távora wrote:
> My bet is that the remaining lag is due to sorting.  In a dumb but
> illustrative example, when given the pattern 'fmcro' flex-enabled
> ido-mode pops 'flymake--backend-state-p--cmacro' to the top, while fido
> mode selects the much more reasonable 'defmacro'.

Perhaps not sorting exactly, but the scoring part? Lowering the 
implementation into C might help, we discussed something like that in 
the past.

And/or pick a different algorithm. E.g. Jaro-Winkler, which apparently 
is used in a lot of "fuzzy matching" implementations out there, it's 
pretty fast.

I took an example like

   (setq s (all-completions "" obarray))
   (setq ss (cl-delete-if-not (lambda (s) (string-match-p "a" s)) s))

then

   (benchmark 1 '(completion-all-completions "a" ss nil 1))

prints 0.180s here, whereas a "pure Ruby" implementation of Jaro-Winkler 
takes about 0.060s on the exact same set of strings. But perhaps Ruby is 
just faster than Elisp, I don't have a good comparison.

(The only J-W implementation in Elisp I have found yet -- 
https://github.com/rdiankov/emacs-config/blob/master/.emacs-lisp/auto-complete-1.3.1/fuzzy.el#L70 
-- is slower than the current scoring algo).




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 5 Jun 2021 23:42:49 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Jun 05 19:42:49 2021
Received: from localhost ([127.0.0.1]:50290 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpfwG-0004DW-WE
	for submit <at> debbugs.gnu.org; Sat, 05 Jun 2021 19:42:49 -0400
Received: from mail-wm1-f41.google.com ([209.85.128.41]:51945)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lpfwD-0004DH-KL
 for 48841 <at> debbugs.gnu.org; Sat, 05 Jun 2021 19:42:47 -0400
Received: by mail-wm1-f41.google.com with SMTP id r13so7571945wmq.1
 for <48841 <at> debbugs.gnu.org>; Sat, 05 Jun 2021 16:42:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:subject:to:cc:references:from:message-id:date:user-agent
 :mime-version:in-reply-to:content-language:content-transfer-encoding;
 bh=8Kmm/Fi9lwNonVukfgTpH5+OH6gFamvQ2hASIsfyGvg=;
 b=MaUDTnbX3uHZN8pF72nDshfjh7vpHGzGN7szT/7nGZgr6lHaFcceiEr3TcqTDApnSt
 EKbwGHjmqNnfiQwMb8z2jproLl9XQhxfhoNSMAechTsyeI4ER/b9a2idvt0FCMMs+1Ap
 08iHGlBfebQiXelG3JhfMRWGWYKvOXQwNLHNoiBPZiSzF4MzPB+XRr7C6suh3nJo3Vsh
 hsnvB34igg3K6Bg/Jg7LR5B+B6SLsFr3cSwu4XXOMwTkBKjnwi/nlfkzg7MqebgKhyT2
 GagS0kY8+LCZebKvDM6Jj+zcRIFm3fgUz52RRQ0tk+LVZYToLROWceSmuh7wJtlaPbjx
 apGg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:subject:to:cc:references:from:message-id
 :date:user-agent:mime-version:in-reply-to:content-language
 :content-transfer-encoding;
 bh=8Kmm/Fi9lwNonVukfgTpH5+OH6gFamvQ2hASIsfyGvg=;
 b=UZVwJnt4HT/CWkllxQqJAyQKbUEUkTUGdzj4V2kRC6wbDfQYaF9XyAQU7E47RRjnVg
 u/4oFlAYK2F9hUIA2Jgn4u/DeyN1dg1Y7bQrrrkxPg5/ivc5K/PSdRcX2UcvxWyXD8ub
 sU1Daa+GYCk9mMFG6bjVV5AFPPX+pylruHe6vW8X7geY97dzaMfe6x7ZnMlUsVZhFI2Y
 xl/Gq9+w2mOKWa88zH/CrowcGuPuBSu6nwQXi1Kvr+MEDv73Uy5UrljIiSe+nnB+AYKA
 GAH2v2x4X27yFTxmYffFxwhrGfj/mgyjTB+uFPc2e+AGXBkOU0c3eQONWbCipjmmgr0y
 YGow==
X-Gm-Message-State: AOAM530udsgGCmL1L/CMLNCs/Og8qIVdngJHbWZes/NqlzTVnK1fbvdR
 kMFgCtE6t0Bg3jzWcTzmTj2V+l1w5BM=
X-Google-Smtp-Source: ABdhPJxaG910IBcNYCXj4vn+umJ6mzFV+ziyapiARXTU3ST0S2hQIrqFpJtrttF9x4aojZ1fyCNYbg==
X-Received: by 2002:a1c:bd41:: with SMTP id n62mr9712529wmf.83.1622936559604; 
 Sat, 05 Jun 2021 16:42:39 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id i9sm4563019wrn.54.2021.06.05.16.42.38
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Sat, 05 Jun 2021 16:42:39 -0700 (PDT)
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>,
 monnier@HIDDEN
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
 <87a6o3x5j7.fsf@HIDDEN>
From: Dmitry Gutov <dgutov@HIDDEN>
Message-ID: <e90e9283-a943-1dcb-8dc2-1822f5f40127@HIDDEN>
Date: Sun, 6 Jun 2021 02:42:37 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
In-Reply-To: <87a6o3x5j7.fsf@HIDDEN>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Spam-Score: -0.1 (/)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.1 (-)

On 06.06.2021 02:20, João Távora wrote:
> Now, what I called here the "suffix-calculation logic" is what I also
> called the "[mplete] dance" back in the emacs-devel thread.  Truth is,
> it's always annoyed me in icomplete partially because I don't understand
> what it does exactly and how it is supposed to help me.  I suppose
> Stefan knows best here.  Regardless of its use, it seems to require
> another try-completion call in all the filtered candidates (which might
> be very big) so that's probably where the extra lag comes from.

Shouldn't this logic (whether it's used) be governed by the variable 
icomplete-hide-common-prefix?

Which icomplete--fido-mode-setup sets to nil (appropriately, given than 
ido-mode does not have this behavior). And looking at its behavior, it 
only does the "[mplete] dance" when there is only one match remaining.

Whether to make icomplete-hide-common-prefix affect even the "only one 
match" case is a matter of taste: I could personally find an argument 
for either choice. But we're seeing performance degradation when there 
are many matches, not one.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 5 Jun 2021 23:20:40 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Jun 05 19:20:40 2021
Received: from localhost ([127.0.0.1]:50278 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpfap-0003hM-QK
	for submit <at> debbugs.gnu.org; Sat, 05 Jun 2021 19:20:40 -0400
Received: from mail-wm1-f52.google.com ([209.85.128.52]:53015)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lpfan-0003h8-Hf
 for 48841 <at> debbugs.gnu.org; Sat, 05 Jun 2021 19:20:38 -0400
Received: by mail-wm1-f52.google.com with SMTP id f17so7550014wmf.2
 for <48841 <at> debbugs.gnu.org>; Sat, 05 Jun 2021 16:20:37 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=from:to:cc:subject:references:date:in-reply-to:message-id
 :user-agent:mime-version:content-transfer-encoding;
 bh=0SsC1OOXrvTZ7RCsaUmvBieks2UWV7DPo25x5rKzOcE=;
 b=DFLixvh5f+fcfVieEtE8GF+YVfVQKFRptRpTcONCU+uLyfr4wFvv1a61eNlFi4SW+6
 5YPRvs61hyvjdmEV8fg+6zfErHO3B6+RKyfYkl/YU6orCWb3GXrlxpmOM+Z97p0JpZA+
 js99W55jQaUrrU2wU5ACa9pgvTYCstVrnJcxg1FEUd83grFGQcLIujgnZEXT09gV5Ycr
 mX9Og//Oi5/HAT6EWWP1efDXykLTdz0BYU1UMqMcfZTAkLMCJvOuCkuDe81ccIJMLvvi
 8zuhodxXb3OzQ/0dngm/7UkS+vOwb7i5zKyU6XJKccqXy/DMEm8eKtngIVAnu05EvgMx
 IqVw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to
 :message-id:user-agent:mime-version:content-transfer-encoding;
 bh=0SsC1OOXrvTZ7RCsaUmvBieks2UWV7DPo25x5rKzOcE=;
 b=VUeG4UXqZIE8dxOMr9xET7quA1IqOX2CHwjV9H6f8F7Q4pcc4JxqtaoXXqbnoFL/Ax
 HeGE+sTulS3rhv6yDfmWfqfj6UneDhhAMoBh5S2gEHk+cPY3PBI0YeCSiX8PkZuMaXIu
 jh3DxoqOxQc3ekL7G34F25tXaHXJeNaL2mt92hk/JwNU34KoW9kZabUdnOwNtJEFuyMd
 W9NiTNgqRYSHUhoSDCOHcCPNLbMFOjZpKP8E314Vkpw78WdsW0walZl3umyKEd0p52ov
 WRhA6JwB4DBBmXxeR4VlaGiUO/VMN/x8XGUSkGkZ3MK2zlQ9agLSFttjktcjVMnpPU/6
 lm8w==
X-Gm-Message-State: AOAM530qJWgKezzWFYiu6Qx6GY8kkPp0laGaWyzLj8ZjmIKPtclgfiu6
 hUJc6snBmpqH8xc8NH9gnhebMBKFnT8=
X-Google-Smtp-Source: ABdhPJw55fhtCielN9mVkgNpmg950Hy3yE07XM/cG3Y0weNe3lBCikLBzApWvv2t51NMoaJjJlHSow==
X-Received: by 2002:a7b:c935:: with SMTP id h21mr9886969wml.183.1622935231304; 
 Sat, 05 Jun 2021 16:20:31 -0700 (PDT)
Received: from krug ([89.180.147.196])
 by smtp.gmail.com with ESMTPSA id m65sm9698039wmm.19.2021.06.05.16.20.30
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Sat, 05 Jun 2021 16:20:30 -0700 (PDT)
From: =?utf-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>, monnier@HIDDEN
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN>
 <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
Date: Sun, 06 Jun 2021 00:20:28 +0100
In-Reply-To: <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN> (Dmitry Gutov's
 message of "Sun, 6 Jun 2021 02:02:24 +0300")
Message-ID: <87a6o3x5j7.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Dmitry Gutov <dgutov@HIDDEN> writes:

> On 05.06.2021 12:35, Jo=C3=A3o T=C3=A1vora wrote:
>> Thanks for the report.  Before I try reproducing, can you try with
>> fido-vertical-mode and tell us it if that changes anything?  I think I
>> remember that skipping some suffix-calculation logic saved on a few
>> traversals of the big list of symbol completions.
>
> Why, yes it is. fido-vertical-mode is definitely snappier with such
> settings.
>
> Maybe still not on the level of ido-mode, but at least halfway there,
> compared to the "horizontal" version.

Yes, that is also my assessment after trying your recipe.  fido-mode +
fido-vertical-mode is not quite as snappy as ido-ubiquitous-mode, but
decently close.

My bet is that the remaining lag is due to sorting.  In a dumb but
illustrative example, when given the pattern 'fmcro' flex-enabled
ido-mode pops 'flymake--backend-state-p--cmacro' to the top, while fido
mode selects the much more reasonable 'defmacro'.

Now, what I called here the "suffix-calculation logic" is what I also
called the "[mplete] dance" back in the emacs-devel thread.  Truth is,
it's always annoyed me in icomplete partially because I don't understand
what it does exactly and how it is supposed to help me.  I suppose
Stefan knows best here.  Regardless of its use, it seems to require
another try-completion call in all the filtered candidates (which might
be very big) so that's probably where the extra lag comes from.

So, in summary, to speed this up for whomever is _not_ using
fido-vertical-mode, either we manage to speed up that part of
icomplete.el, or we get rid of it completely (at least for fido-mode).
For reference, it lives in an "else" branch of one of the "if"s in
icomplete-completions.

Jo=C3=A3o




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 5 Jun 2021 23:02:36 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Jun 05 19:02:36 2021
Received: from localhost ([127.0.0.1]:50267 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpfJL-0003Io-VK
	for submit <at> debbugs.gnu.org; Sat, 05 Jun 2021 19:02:36 -0400
Received: from mail-wr1-f44.google.com ([209.85.221.44]:37504)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lpfJI-0003IZ-1w
 for 48841 <at> debbugs.gnu.org; Sat, 05 Jun 2021 19:02:35 -0400
Received: by mail-wr1-f44.google.com with SMTP id i94so8002319wri.4
 for <48841 <at> debbugs.gnu.org>; Sat, 05 Jun 2021 16:02:31 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:subject:to:cc:references:from:message-id:date:user-agent
 :mime-version:in-reply-to:content-language:content-transfer-encoding;
 bh=JU2U9i9tR5/J5jRlQzNoMiQZL0ctlSMRNqfK0DBoyTk=;
 b=Mnz9r1+3fj7JvwTr0gxCBBNgt0kmu8SycH4hQ9Th8NTkXcPVn5vCXhfhKPPZ8MVfSy
 2UWpVizneoDJT8POBQG9lo02PZyJhsHNUkdKJSp40vmIGO4C6Ms9OR1ukKxeXhsrhfY+
 czLNOVn6llHZMfxrAcnriSXVIwr5o77bqCLUa8S9pbuVTsFZInsImVxR6T8B024mk47X
 9sHj6MwZZKHSbwnM+f0JGzowzupYKQQIcBIdUhhGXWv/xBXzOWDtL7ENzmR9uLcAgLQx
 sCHdJMBJ37/SHXKucnEEF87t9x69NW1WY3KQ76i5jV3A+ph5kUFF3ApGpfK71KQJTMHH
 DRkA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:subject:to:cc:references:from:message-id
 :date:user-agent:mime-version:in-reply-to:content-language
 :content-transfer-encoding;
 bh=JU2U9i9tR5/J5jRlQzNoMiQZL0ctlSMRNqfK0DBoyTk=;
 b=nawbUF1bUvhGI33/Kr6cpKU+PnahiQj+z+mX42gUZl9V//4bpDiBWKmqlEPSFVDuPh
 jNmpsPTIjvG2pvoG297kiXrWkfxmuEd1bBdB7qEin4qIFDDJ8iLnBjX8vA/LOTXhB0UW
 ww3Km8kkEVKHNEfWwlzQChmlnLqnv51ZmiunIUuKb1lNx2IwBX2bHQtgsAvMEfeYPOTQ
 wX0D+xlRQ7Nv64/zM7qd2lYU9twVn/mt0iG+II/DFUqe1ISUKk56cnkYWHdJgAsW6Yxt
 D/qjB+DmFIZeKXgT6l160EVl+bMJn/3VAYxX6Ql6NmAjK/jraB/qxioWkE2jpWqfPKnP
 l13A==
X-Gm-Message-State: AOAM533Brvm3/ZZBVWddepY7E99pB2jHlm+JoIeFMebR61hF3tWAfp3F
 xtp4/i9qhc3eVOgRhVKS36DGSreEEC4=
X-Google-Smtp-Source: ABdhPJwLIFzu20krXXcJTTg9RC5wxKK4rzYvjA7ItWpK7bhXDUrGwblEYI6sUUZgYELSimoJ220nQA==
X-Received: by 2002:a05:6000:1089:: with SMTP id
 y9mr10122564wrw.412.1622934146156; 
 Sat, 05 Jun 2021 16:02:26 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id l22sm12147641wmq.28.2021.06.05.16.02.25
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Sat, 05 Jun 2021 16:02:25 -0700 (PDT)
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
 <87eedgy7pt.fsf@HIDDEN>
From: Dmitry Gutov <dgutov@HIDDEN>
Message-ID: <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@HIDDEN>
Date: Sun, 6 Jun 2021 02:02:24 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
In-Reply-To: <87eedgy7pt.fsf@HIDDEN>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Spam-Score: -0.1 (/)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.1 (-)

On 05.06.2021 12:35, João Távora wrote:
> Thanks for the report.  Before I try reproducing, can you try with
> fido-vertical-mode and tell us it if that changes anything?  I think I
> remember that skipping some suffix-calculation logic saved on a few
> traversals of the big list of symbol completions.

Why, yes it is. fido-vertical-mode is definitely snappier with such 
settings.

Maybe still not on the level of ido-mode, but at least halfway there, 
compared to the "horizontal" version.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at 48841 <at> debbugs.gnu.org:


Received: (at 48841) by debbugs.gnu.org; 5 Jun 2021 09:35:58 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Jun 05 05:35:58 2021
Received: from localhost ([127.0.0.1]:48309 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpSig-0002Bh-WE
	for submit <at> debbugs.gnu.org; Sat, 05 Jun 2021 05:35:58 -0400
Received: from mail-wr1-f45.google.com ([209.85.221.45]:34682)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <joaotavora@HIDDEN>) id 1lpSic-0002BR-OR
 for 48841 <at> debbugs.gnu.org; Sat, 05 Jun 2021 05:35:54 -0400
Received: by mail-wr1-f45.google.com with SMTP id q5so11686848wrm.1
 for <48841 <at> debbugs.gnu.org>; Sat, 05 Jun 2021 02:35:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=from:to:cc:subject:references:date:in-reply-to:message-id
 :user-agent:mime-version:content-transfer-encoding;
 bh=TnMwxKzpBBNmQzIjgnZWGBDk8pMUauUg4V4iVjHucTQ=;
 b=rt5uQu2f8wb4I2PgkhctHhJKouAr6ul+71f7lvs/MpAvf4dvhmwS1ESTXPIHaXqoRk
 3Os+Aentp8NddVZjklZQsG/AcP49LVxVyd00DuLOHrCEehxAoth+psm3yw4UPnpqzGwe
 AA5J36FkZiqk7xgnr3Rx1vzSkLEDICunz7nFifwC5QNHocRQumkf9sW54iF3439Lm1eb
 8JsWyebnCBJSZwMNDnM7te+KbfUufPLXyc8QHZCJxj9LQdqhBrJY3IYNZ3Mx4+d94Wkg
 2VEcPKtmfxEflw4c5ohFi/sVZh2QqZ1wsRNhlLQhkcZ8YkiFsd6Zu482G8bQIJydcPYR
 UybA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to
 :message-id:user-agent:mime-version:content-transfer-encoding;
 bh=TnMwxKzpBBNmQzIjgnZWGBDk8pMUauUg4V4iVjHucTQ=;
 b=Uif/sDXHBHWzXbnH9bjPuMYRQma3GEPa0lraBZ/7IqHCvbAOm1IAaW6Wf7khIY+Kso
 kY6l+/DNbzVr0VTNwwmvyxXHNTnvMsbNd0jwRUmkbwW3vNwBYc+rfPQdEUWIWuv0F8X3
 Yd/wChbm71Ke8S9We2guJ3Qe22b2km4IyT/kdkj5CGtr8IkmAaoM8r9TGwrL+7X6fMpY
 jl/e2Jzyos2fQuKdrc9pyDmCB0jOrqtBlNIoxyp6tEVHeE8yndKpdtjVP5/Gyv4TyE79
 Iwf1RWcGcpxwGrcupoQ6w73OJgkJfioz6G6Ij+mN8wEn+QmMCWC8eiEW4nPCyeUzO4Pe
 1uSw==
X-Gm-Message-State: AOAM530T/+lmI8lfAhUVuveaD9m1p7jUS0gBEHD9xNQy2yMMjT5VB3Y0
 9XscxHAuRZAqZRN+NJGE6a90cgMb5iw=
X-Google-Smtp-Source: ABdhPJyFzoljKpdA/XFiBVZK8by2Af1wORL5Gm35fx9JCj/VzcV4CICBDkQOvMLuAV02Y7bXQljWgQ==
X-Received: by 2002:a5d:5182:: with SMTP id k2mr7835541wrv.381.1622885744273; 
 Sat, 05 Jun 2021 02:35:44 -0700 (PDT)
Received: from krug ([89.180.146.244])
 by smtp.gmail.com with ESMTPSA id v8sm10034203wrc.29.2021.06.05.02.35.43
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Sat, 05 Jun 2021 02:35:43 -0700 (PDT)
From: =?utf-8?B?Sm/Do28gVMOhdm9yYQ==?= <joaotavora@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#48841: fido-mode is slower than ido-mode with similar settings
References: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
Date: Sat, 05 Jun 2021 10:35:42 +0100
In-Reply-To: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN> (Dmitry Gutov's
 message of "Sat, 5 Jun 2021 04:39:49 +0300")
Message-ID: <87eedgy7pt.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: 48841
Cc: 48841 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Dmitry Gutov <dgutov@HIDDEN> writes:

> I'm comparing
>
>   ido-mode
>   with ido-ubiquitous-mode (for support for arbitrary completion
>   tables), available at
>   https://github.com/DarwinAwardWinner/ido-completing-read-plus
>   with (setq ido-enable-flex-matching t), of course
>
> versus
>
>  fido-mode
>  with
>    (setq icomplete-compute-delay 0)
>    (setq icomplete-show-matches-on-no-input t)
>    (setq icomplete-max-delay-chars 0)
>
> The values chosen for behavior maximally close to ido.
>
> Try something like:
>
>  - Start a session with personal config and a number of loaded
>    packages (so that there are a lot of functions defined in obarray)
>  - Type 'C-h f'
>  - Type 'a', then type 'b'.
>  - Delete 'b', type it again, see how quickly you can make the
>    completions update.
>
> With ido, the updates seem instant (probably due to some magic in
> ido-completing-read-plus); with fido, there is some lag. Not huge, but
> easy enough to notice.

Thanks for the report.  Before I try reproducing, can you try with
fido-vertical-mode and tell us it if that changes anything?  I think I
remember that skipping some suffix-calculation logic saved on a few
traversals of the big list of symbol completions.

Jo=C3=A3o





Information forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.

Message received at submit <at> debbugs.gnu.org:


Received: (at submit) by debbugs.gnu.org; 5 Jun 2021 01:39:58 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Fri Jun 04 21:39:58 2021
Received: from localhost ([127.0.0.1]:48094 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lpLI6-0007c6-7W
	for submit <at> debbugs.gnu.org; Fri, 04 Jun 2021 21:39:58 -0400
Received: from lists.gnu.org ([209.51.188.17]:47576)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <raaahh@HIDDEN>) id 1lpLI3-0007bx-K8
 for submit <at> debbugs.gnu.org; Fri, 04 Jun 2021 21:39:57 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:51402)
 by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <raaahh@HIDDEN>) id 1lpLI3-0002Ak-Cb
 for bug-gnu-emacs@HIDDEN; Fri, 04 Jun 2021 21:39:55 -0400
Received: from mail-wr1-x435.google.com ([2a00:1450:4864:20::435]:41812)
 by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128)
 (Exim 4.90_1) (envelope-from <raaahh@HIDDEN>) id 1lpLI1-0000Ay-Gw
 for bug-gnu-emacs@HIDDEN; Fri, 04 Jun 2021 21:39:55 -0400
Received: by mail-wr1-x435.google.com with SMTP id h8so10956018wrz.8
 for <bug-gnu-emacs@HIDDEN>; Fri, 04 Jun 2021 18:39:53 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=sender:to:from:subject:message-id:date:user-agent:mime-version
 :content-language:content-transfer-encoding;
 bh=w+Vi8Fpo1tJdAAFVOptzaAe9XHfZKDU/nqNQTPxTR6M=;
 b=i1crFa30B8GbHmqBOb8TCrma99l4X3pCSu8mm2DpDqZAmATZPVnIoWKcKkXWxui3uP
 Y9yUsQGvIBtbWEKAzO2+ymC9lh3ix/x88kvjzWOZ87ffOUggEnV3Ue2w/2XvQt1M7C96
 JAiJcr2ottLrpRq0TngXylxhpVWJowpc1yjP5s8E+XavGA3ypZL+YOtl7p4IuW5yGYxy
 LzFjwx6R0q5Kfhjem5Whvx6GkcFvx+lgL6p7z8i9tagXcGSyEFu4ixCxZVmko1RDsOZX
 /BZDE+7btFdKwh2xMr7UG8+TyoZc0FVEPX7TJ/+VJyyJw7lPUF7TVeY3EnPNvUhheBP0
 j/Iw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:sender:to:from:subject:message-id:date
 :user-agent:mime-version:content-language:content-transfer-encoding;
 bh=w+Vi8Fpo1tJdAAFVOptzaAe9XHfZKDU/nqNQTPxTR6M=;
 b=bJzkqYalNQ5ijdZqUKaUglFwLMaZUy8yBaWmKAMVLU/e04eTy2qcz6hoT/ChfOvait
 revbsKaIcnv4OEFmkGhjypCKNmSkvFhOxq3rwOWpbKpYQgvN/gnIP5D5fH0YyB+sx0HK
 TKKWcZF1K6oP50xLxMGb+VuujI7q5AGcUkLlXQ8zh+Ld+7pYQxAOg6XpRUsCxO3O2KqV
 4kjlyG/pRmxuTTK+xQBz5VnQQivSghoZKOkJRwbm8bFKqftxQ3nTzCUmx2WJcEJdkjTe
 2SUjdLuX6IUTyAIqtBdqTZyRbMn0XV7Z1Ek+JpEbIHIMvSrfUtY9ijBQXUQk3GpLs7q0
 ZqpQ==
X-Gm-Message-State: AOAM533itREXD0GDI8RhX1y9EN9bKsDDcPJ18hm6c84FoZ/1EVDJj8FE
 1QVCjkzUZdmsHJafyed4uSAf8LSCPrw=
X-Google-Smtp-Source: ABdhPJxbX4wtdl7i73Z5mS/SwhBb5vA7FPw2IDcoYR5voDsdcL+48ylHkJhr83sLsLyrfYPaFNm+9Q==
X-Received: by 2002:adf:fa0f:: with SMTP id m15mr6275716wrr.379.1622857191261; 
 Fri, 04 Jun 2021 18:39:51 -0700 (PDT)
Received: from [192.168.0.6] ([46.251.119.176])
 by smtp.googlemail.com with ESMTPSA id u7sm2846858wrt.18.2021.06.04.18.39.50
 for <bug-gnu-emacs@HIDDEN>
 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
 Fri, 04 Jun 2021 18:39:50 -0700 (PDT)
To: bug-gnu-emacs@HIDDEN
From: Dmitry Gutov <dgutov@HIDDEN>
Subject: fido-mode is slower than ido-mode with similar settings
Message-ID: <f94541d3-5f93-9a23-8256-3bbc453f127a@HIDDEN>
Date: Sat, 5 Jun 2021 04:39:49 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.1
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Received-SPF: pass client-ip=2a00:1450:4864:20::435;
 envelope-from=raaahh@HIDDEN; helo=mail-wr1-x435.google.com
X-Spam_score_int: -14
X-Spam_score: -1.5
X-Spam_bar: -
X-Spam_report: (-1.5 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
 DKIM_VALID=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.249,
 FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001 autolearn=no autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -0.8 (/)
X-Debbugs-Envelope-To: submit
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.8 (-)

I'm comparing

   ido-mode
   with ido-ubiquitous-mode (for support for arbitrary completion 
tables), available at 
https://github.com/DarwinAwardWinner/ido-completing-read-plus
   with (setq ido-enable-flex-matching t), of course

versus

  fido-mode
  with
    (setq icomplete-compute-delay 0)
    (setq icomplete-show-matches-on-no-input t)
    (setq icomplete-max-delay-chars 0)

The values chosen for behavior maximally close to ido.

Try something like:

  - Start a session with personal config and a number of loaded packages 
(so that there are a lot of functions defined in obarray)
  - Type 'C-h f'
  - Type 'a', then type 'b'.
  - Delete 'b', type it again, see how quickly you can make the 
completions update.

With ido, the updates seem instant (probably due to some magic in 
ido-completing-read-plus); with fido, there is some lag. Not huge, but 
easy enough to notice.




Acknowledgement sent to Dmitry Gutov <dgutov@HIDDEN>:
New bug report received and forwarded. Copy sent to bug-gnu-emacs@HIDDEN. Full text available.
Report forwarded to bug-gnu-emacs@HIDDEN:
bug#48841; Package emacs. Full text available.
Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.
Last modified: Fri, 11 Jun 2021 17:15:01 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.