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: Tue, 06 Nov 2012 19:38:45 +0400 Message-ID: <50992F05.5090108@yandex.ru> References: <5096040B.50002@yandex.ru> <5096A046.6090908@yandex.ru> <509750B0.2030000@yandex.ru> <5098EE91.9000906@cua.dk> 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 1352216403 30814 80.91.229.3 (6 Nov 2012 15:40:03 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 6 Nov 2012 15:40:03 +0000 (UTC) Cc: 12796@debbugs.gnu.org To: Kim Storm Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Tue Nov 06 16:40:11 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 1TVlG3-0000ZO-8v for geb-bug-gnu-emacs@m.gmane.org; Tue, 06 Nov 2012 16:40:07 +0100 Original-Received: from localhost ([::1]:59544 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVlFu-0005Mf-Bj for geb-bug-gnu-emacs@m.gmane.org; Tue, 06 Nov 2012 10:39:58 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:38274) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVlFr-0005MM-Dw for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 10:39:56 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TVlFn-0003KC-3C for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 10:39:55 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:42403) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TVlFm-0003K8-Nt for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 10:39:51 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1TVlIr-0006NE-W1 for bug-gnu-emacs@gnu.org; Tue, 06 Nov 2012 10:43: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: Tue, 06 Nov 2012 15:43: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.135221652224436 (code B ref 12796); Tue, 06 Nov 2012 15:43:01 +0000 Original-Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 15:42:02 +0000 Original-Received: from localhost ([127.0.0.1]:52654 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVlHu-0006M5-Ft for submit@debbugs.gnu.org; Tue, 06 Nov 2012 10:42:02 -0500 Original-Received: from forward3.mail.yandex.net ([77.88.46.8]:36433) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVlHq-0006Le-AH for 12796@debbugs.gnu.org; Tue, 06 Nov 2012 10:42:01 -0500 Original-Received: from smtp2.mail.yandex.net (smtp2.mail.yandex.net [77.88.46.102]) by forward3.mail.yandex.net (Yandex) with ESMTP id AF7F2B40B9A; Tue, 6 Nov 2012 19:38:44 +0400 (MSK) Original-Received: from smtp2.mail.yandex.net (localhost [127.0.0.1]) by smtp2.mail.yandex.net (Yandex) with ESMTP id 77EC8E20610; Tue, 6 Nov 2012 19:38:44 +0400 (MSK) Original-Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp2.mail.yandex.net (nwsmtp/Yandex) with ESMTP id chWqBJCk-chWCfVJr; Tue, 6 Nov 2012 19:38:43 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352216324; bh=Pzs//BhqK8tk72Py6tqDneGg283oDsmjGz+deTyqLpE=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=EbQRVXdFkfMf4/bX3x+g6Tn1Hzp8KkkWiqiuBKhXT/UgYr/ykejTHemI6BvY8dovQ YVOpFy/U640QfUD4nmud4wirdhG2nYRSY/3YrXV9x/aXKV9Uzm4TiKKbczsVt1PtIb ZHe0ypx+X364ykrVyVc6ozIbSzvgappnB0985zNs= User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 In-Reply-To: <5098EE91.9000906@cua.dk> 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:66530 Archived-At: On 06.11.2012 15:03, Kim Storm wrote: >> 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. That's true, backtracking was not a priority. But see below. > 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 ? No, the idea is to limit memory consumption (which may be a bit premature) and make sure that the filtered matches list is smaller enough than the original to justify saving it. I probably should change 10 to a smaller constant, like 3 or 2. On the "stop caching" front, we can add a lower bound check, comparing the matches length to an absolute or relative value. This way, doing a few backspaces from a sufficiently narrowed state won't trigger a full recomputation. To go further than that, it shouldn't be hard to keep a stack of caches for the current input string as it's typed, but I suspect memory consumption may be a bigger concern in this case. WDYT?