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: Sun, 6 Jun 2021 03:25:20 +0300 Message-ID: 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; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="25016"; 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: 48841@debbugs.gnu.org To: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= , monnier@iro.umontreal.ca Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Jun 06 02:26:11 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 1lpgcF-0006CY-04 for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 06 Jun 2021 02:26:11 +0200 Original-Received: from localhost ([::1]:37890 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lpgcD-0005BG-C0 for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 05 Jun 2021 20:26:09 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:56134) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lpgc6-0005B5-RV for bug-gnu-emacs@gnu.org; Sat, 05 Jun 2021 20:26:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:38783) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lpgc6-0007YH-HH for bug-gnu-emacs@gnu.org; Sat, 05 Jun 2021 20:26:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1lpgc6-0005EG-CK for bug-gnu-emacs@gnu.org; Sat, 05 Jun 2021 20:26:02 -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 00:26:02 +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.162293913020053 (code B ref 48841); Sun, 06 Jun 2021 00:26:02 +0000 Original-Received: (at 48841) by debbugs.gnu.org; 6 Jun 2021 00:25:30 +0000 Original-Received: from localhost ([127.0.0.1]:50329 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lpgba-0005DM-6W for submit@debbugs.gnu.org; Sat, 05 Jun 2021 20:25:30 -0400 Original-Received: from mail-wr1-f42.google.com ([209.85.221.42]:37491) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lpgbY-0005D9-Aj for 48841@debbugs.gnu.org; Sat, 05 Jun 2021 20:25:28 -0400 Original-Received: by mail-wr1-f42.google.com with SMTP id i94so8116871wri.4 for <48841@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) Original-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) In-Reply-To: <87a6o3x5j7.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:208081 Archived-At: 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).