From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Newsgroups: gmane.emacs.bugs Subject: bug#48841: fido-mode is slower than ido-mode with similar settings Date: Sun, 06 Jun 2021 07:54:55 +0100 Message-ID: <87y2bnv5xc.fsf@gmail.com> References: <87eedgy7pt.fsf@gmail.com> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@yandex.ru> <87a6o3x5j7.fsf@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="2662"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: monnier@iro.umontreal.ca, 48841@debbugs.gnu.org To: Dmitry Gutov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Jun 06 08:56:09 2021 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lpmhc-0000Uv-GT for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 06 Jun 2021 08:56:08 +0200 Original-Received: from localhost ([::1]:43860 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lpmhb-00043N-JE for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 06 Jun 2021 02:56:07 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:48596) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lpmhW-00043F-BV for bug-gnu-emacs@gnu.org; Sun, 06 Jun 2021 02:56:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:38964) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lpmhW-0001Fl-4t for bug-gnu-emacs@gnu.org; Sun, 06 Jun 2021 02:56:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1lpmhW-0008MG-07 for bug-gnu-emacs@gnu.org; Sun, 06 Jun 2021 02:56:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 06 Jun 2021 06:56:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 48841 X-GNU-PR-Package: emacs Original-Received: via spool by 48841-submit@debbugs.gnu.org id=B48841.162296250732058 (code B ref 48841); Sun, 06 Jun 2021 06:56:01 +0000 Original-Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 06:55:07 +0000 Original-Received: from localhost ([127.0.0.1]:50510 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lpmgc-0008Kx-C9 for submit@debbugs.gnu.org; Sun, 06 Jun 2021 02:55:06 -0400 Original-Received: from mail-wr1-f41.google.com ([209.85.221.41]:46707) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lpmga-0008KN-Be for 48841@debbugs.gnu.org; Sun, 06 Jun 2021 02:55:05 -0400 Original-Received: by mail-wr1-f41.google.com with SMTP id a11so11828657wrt.13 for <48841@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) Original-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) In-Reply-To: (Dmitry Gutov's message of "Sun, 6 Jun 2021 03:25:20 +0300") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:208088 Archived-At: Dmitry Gutov 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