From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.bugs Subject: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Date: Wed, 07 Nov 2012 08:06:13 +0400 Message-ID: <5099DE35.2060402@yandex.ru> References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1352261233 21725 80.91.229.3 (7 Nov 2012 04:07:13 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 7 Nov 2012 04:07:13 +0000 (UTC) Cc: 12796@debbugs.gnu.org, Kim Storm To: Leo Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Wed Nov 07 05:07:22 2012 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TVwvC-0002rm-1R for geb-bug-gnu-emacs@m.gmane.org; Wed, 07 Nov 2012 05:07:22 +0100 Original-Received: from localhost ([::1]:46246 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVwv2-0001Rl-OQ for geb-bug-gnu-emacs@m.gmane.org; Tue, 06 Nov 2012 23:07:12 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:41419) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVwv0-0001Rg-4l for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 23:07:10 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TVwuz-0002XX-48 for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 23:07:10 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:42904) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVwuy-0002XQ-Pg for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 23:07:09 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1TVwus-0003Ol-8x for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 23:07:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Dmitry Gutov Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 07 Nov 2012 04:07:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 12796 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 12796-submit@debbugs.gnu.org id=B12796.135226117413008 (code B ref 12796); Wed, 07 Nov 2012 04:07:02 +0000 Original-Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 04:06:14 +0000 Original-Received: from localhost ([127.0.0.1]:53155 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVwu6-0003Nl-Gl for submit@debbugs.gnu.org; Tue, 06 Nov 2012 23:06:14 -0500 Original-Received: from forward2.mail.yandex.net ([77.88.46.7]:39775) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVwu1-0003NX-HZ for 12796@debbugs.gnu.org; Tue, 06 Nov 2012 23:06:12 -0500 Original-Received: from smtp3.mail.yandex.net (smtp3.mail.yandex.net [77.88.46.103]) by forward2.mail.yandex.net (Yandex) with ESMTP id 71FB812A1434; Wed, 7 Nov 2012 08:06:13 +0400 (MSK) Original-Received: from smtp3.mail.yandex.net (localhost [127.0.0.1]) by smtp3.mail.yandex.net (Yandex) with ESMTP id 2BAD91BA0832; Wed, 7 Nov 2012 08:06:13 +0400 (MSK) Original-Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp3.mail.yandex.net (nwsmtp/Yandex) with ESMTP id 68BipxI4-6CBWkcXY; Wed, 7 Nov 2012 08:06:12 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352261173; bh=/L+/WInJ0MoHn3tbIyTsuq3JOqpKW9eYDvNrEMIXtZg=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=dg6/60HEUf+C/Gbdlv5XpGtA8Pu69bB4rRoTFKt02ArwoNk7dXM14UIrRI79CQxVZ TWB97ERqZz24DEImXLwjuSxtCQ5pEq1HZfPUIUh/x2LDZoWUVD1h+aDT+cLGd8c6ET TEaRnz/ZxfoldUclVs8z8r8fXtTzqdwzCj6mgdiY= User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 In-Reply-To: X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 140.186.70.43 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.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:66565 Archived-At: On 07.11.2012 6:27, Leo wrote: > On 2012-11-06 04:57 +0800, Dmitry Gutov wrote: >> And the root cause is..? > > I haven't looked. So maybe you could use a profiler to find where it is. > It seems string-match in flex matching is slow. I think we should make > sure the computation is optimised. There are third party libs such as > ido-hacks.el which might have some ideas. That was actually a good advice. As far as I can tell, most of the speed improvement comes from the following change: === modified file 'lisp/ido.el' --- lisp/ido.el 2012-10-05 07:38:05 +0000 +++ lisp/ido.el 2012-11-07 03:40:57 +0000 @@ -3764,7 +3764,7 @@ ido-enable-flex-matching (> (length ido-text) 1) (not ido-enable-regexp)) - (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*")) + (setq re (mapconcat #'regexp-quote (split-string ido-text "" t) ".*")) (if ido-enable-prefix (setq re (concat "\\`" re))) (mapc :) Then there's this (from ido-set-matches-1's defadvice's docstring): "This advice makes it a good deal faster, by caching narrowed choices lists." Which looks like it's doing something with hashtables similar to what I proposed to do with a stack. With approximately the same performance improvement (which is only visible with the change above reverted). Anyway, with my data sets (all Emacs functions or all Emacs vars, 12000 and 4000 items respectively), the one-line change makes flex matching about as fast as I can type, so I guess we'll leave implementing cache until someone else complains. Feel free to ping me then. I'm still going to see if I can make while-no-input work here, though.