From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Kim Storm Newsgroups: gmane.emacs.bugs Subject: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Date: Tue, 06 Nov 2012 12:03:45 +0100 Message-ID: <5098EE91.9000906@cua.dk> References: <5096040B.50002@yandex.ru> <5096A046.6090908@yandex.ru> <509750B0.2030000@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 1352199911 6401 80.91.229.3 (6 Nov 2012 11:05:11 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 6 Nov 2012 11:05:11 +0000 (UTC) Cc: 12796@debbugs.gnu.org, Dmitry Gutov To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Tue Nov 06 12:05:21 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 1TVgy5-0001SL-Ol for geb-bug-gnu-emacs@m.gmane.org; Tue, 06 Nov 2012 12:05:17 +0100 Original-Received: from localhost ([::1]:47609 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVgxw-0006sq-Jj for geb-bug-gnu-emacs@m.gmane.org; Tue, 06 Nov 2012 06:05:08 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:49724) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVgxp-0006mK-5j for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 06:05:07 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TVgxf-0007q5-GM for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 06:05:01 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:41322) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVgxf-0007q1-D6 for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 06:04:51 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1TVh0j-0007eX-IS for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 06:08:01 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Kim Storm Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Tue, 06 Nov 2012 11:08:01 +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.135220002329352 (code B ref 12796); Tue, 06 Nov 2012 11:08:01 +0000 Original-Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 11:07:03 +0000 Original-Received: from localhost ([127.0.0.1]:51573 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVgzm-0007dN-TG for submit@debbugs.gnu.org; Tue, 06 Nov 2012 06:07:03 -0500 Original-Received: from ispc3.dotserv.com ([178.20.216.13]:49257) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVgzl-0007cy-1F for 12796@debbugs.gnu.org; Tue, 06 Nov 2012 06:07:02 -0500 Original-Received: from localhost (localhost [127.0.0.1]) by ispc3.dotserv.com (Postfix) with ESMTP id 95AF08042778C; Tue, 6 Nov 2012 12:03:49 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at ispc3.dotserv.com Original-Received: from ispc3.dotserv.com ([127.0.0.1]) by localhost (ispc3.dotserv.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 13kbz3QZwPOg; Tue, 6 Nov 2012 12:03:46 +0100 (CET) Original-Received: from [10.1.82.9] (1405ds6-amb.1.fullrate.dk [90.184.79.200]) (Authenticated sender: storm@cua.dk) by ispc3.dotserv.com (Postfix) with ESMTPSA id 1C71780121B23; Tue, 6 Nov 2012 12:03:46 +0100 (CET) User-Agent: Mozilla/5.0 (X11; Linux x86_64; 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:66526 Archived-At: On 2012-11-06 02:45, Stefan Monnier wrote: > [ Hi Kim, can you give me your opinion on this? ] > >> To try it, I just wrapped in it the "busy" part of `ido-set-matches-1' - >> and indeed, no more waiting a several seconds after button >> mashing. It's a bit buggy so far, but that's to be expected. > To eliminate the buggy behavior, it should probably be put elsewhere, > maybe directly in ido-exhibit (the post-command-hook). Sounds right, but I a bit worried that some of the state information may get corrupted if arbitrarily interrupted by user input. If someone proposes a patch, I'll look at it. > >> The caching approach still feels faster in most cases, and is instantaneous >> in cases when we're editing input and have few or no matches for the current >> input (if we're backspacing, then only when no matches). It has room for >> usability improvements, too. > I'm not opposed to caching, actually. I think the two are independent: > it's important that a slow computation of the completion-data doesn't > force the user to edit slowly. But it's also good to optimize the > computation itself such that interrupting the computation > happens rarely. > > I'm not familiar with the ido.el code, so I find it difficult to judge > if your approach to caching is right. Kim could you take a look (the > patch can be seen at http://debbugs.gnu.org/12796)? I looked at the caching patch, and it looks alright (in the sense that I don't think it will break ido behaviour.) I'm not sure how efficient the caching is though. As far as I can see, it only caches the most recent (non-empty) list of matches, i.e. the shortest list corresponding to the longest "successful" user input in the minibuffer. So if the user has to backtrack beyond that point, I don't really see how the caching will help, as the cache is then invalidated. Also, I don't quite understand why this condition is needed: (<= (* 10 (length matches)) (length ido-cur-list))) It seems to me to only cache a list of matches that has reduced the set of matches by a factor 10 - if the aim is to reduce processing time for long lists, even reducing by a factor of 2 may be noticable ? But maybe the intention of this line was to stop caching once the list has become short than 1/10th of the original list? In that case, the operator should be <= I think ? I any case, I'm not opposed to adding some form of caching here, and the proposed patch seems on the right track, but I'm not convinced that it is the optimal approach. Kim