From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.bugs Subject: bug#48841: fido-mode is slower than ido-mode with similar settings Date: Mon, 7 Jun 2021 01:20:13 +0300 Message-ID: <35be6652-9c8d-ee21-e9eb-9598ad6777eb@yandex.ru> References: <87eedgy7pt.fsf@gmail.com> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@yandex.ru> <87a6o3x5j7.fsf@gmail.com> <87y2bnv5xc.fsf@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="29348"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 Cc: monnier@iro.umontreal.ca, 48841@debbugs.gnu.org To: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Mon Jun 07 00:21:10 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 1lq18o-0007UQ-0f for geb-bug-gnu-emacs@m.gmane-mx.org; Mon, 07 Jun 2021 00:21:10 +0200 Original-Received: from localhost ([::1]:38578 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lq18m-00033m-Dz for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 06 Jun 2021 18:21:08 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:57182) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lq18g-00033a-12 for bug-gnu-emacs@gnu.org; Sun, 06 Jun 2021 18:21:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:42567) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lq18f-00083r-Qc for bug-gnu-emacs@gnu.org; Sun, 06 Jun 2021 18:21:01 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1lq18f-0003tX-Km for bug-gnu-emacs@gnu.org; Sun, 06 Jun 2021 18:21:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Dmitry Gutov Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 06 Jun 2021 22:21: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.162301802214915 (code B ref 48841); Sun, 06 Jun 2021 22:21:01 +0000 Original-Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 22:20:22 +0000 Original-Received: from localhost ([127.0.0.1]:54113 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lq182-0003sV-Dd for submit@debbugs.gnu.org; Sun, 06 Jun 2021 18:20:22 -0400 Original-Received: from mail-wm1-f41.google.com ([209.85.128.41]:55914) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lq181-0003sJ-1z for 48841@debbugs.gnu.org; Sun, 06 Jun 2021 18:20:21 -0400 Original-Received: by mail-wm1-f41.google.com with SMTP id g204so8758346wmf.5 for <48841@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) Original-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) In-Reply-To: <87y2bnv5xc.fsf@gmail.com> Content-Language: en-US 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:208164 Archived-At: 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