GNU bug report logs - #12796
Optimize `ido-completing-read' for larger lists with flex matching enabled

Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.

Package: emacs; Reported by: Dmitry Gutov <dgutov@HIDDEN>; dated Sun, 4 Nov 2012 06:02:01 UTC; Maintainer for emacs is bug-gnu-emacs@HIDDEN.
Did not alter fixed versions and reopened. Request was from Debbugs Internal Request <help-debbugs@HIDDEN> to internal_control <at> debbugs.gnu.org. Full text available.

Message received at 12796-done <at> debbugs.gnu.org:


Received: (at 12796-done) by debbugs.gnu.org; 10 Nov 2012 23:31:31 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Nov 10 18:31:30 2012
Received: from localhost ([127.0.0.1]:60286 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TXKWQ-0003E6-O7
	for submit <at> debbugs.gnu.org; Sat, 10 Nov 2012 18:31:30 -0500
Received: from ironport2-out.teksavvy.com ([206.248.154.182]:58331)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <monnier@HIDDEN>) id 1TXKWN-0003Dz-Vf
	for 12796-done <at> debbugs.gnu.org; Sat, 10 Nov 2012 18:31:28 -0500
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av0EAG6Zu09sr+ZY/2dsb2JhbABEtBGBCIIVAQEEAVYjEAsOJhIUGA0kiBwFugmQRAOIQppxgViDBw
X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206909592"
Received: from 108-175-230-88.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net)
	([108.175.230.88])
	by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA;
	10 Nov 2012 18:31:11 -0500
Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848)
	id 6D837AE4B5; Sat, 10 Nov 2012 18:31:11 -0500 (EST)
From: Stefan Monnier <monnier@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Message-ID: <jwvhaoxox28.fsf-monnier+emacs@HIDDEN>
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN> <509AD8AB.90703@HIDDEN>
	<m2hap0q2ed.fsf@HIDDEN> <jwvbof820mt.fsf-monnier+emacs@HIDDEN>
	<m2625ga6mg.fsf@HIDDEN> <jwvobj8gpiq.fsf-monnier+emacs@HIDDEN>
	<509E945F.6010601@HIDDEN> <jwvmwypoywl.fsf-monnier+emacs@HIDDEN>
	<509EDCB9.7040103@HIDDEN>
Date: Sat, 10 Nov 2012 18:31:11 -0500
In-Reply-To: <509EDCB9.7040103@HIDDEN> (Dmitry Gutov's message of "Sun, 11
	Nov 2012 03:01:13 +0400")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.8 (/)
X-Debbugs-Envelope-To: 12796-done
Cc: Leo <sdl.web@HIDDEN>, 12796-done <at> debbugs.gnu.org,
	Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -0.5 (/)

>>> With speed-up patches installed on both branches, I consider this fixed.
>> No, the use of with-local-quit is the main issue to solve.
> Do you mean `when-no-input' and the lack of its use?

Oh, yes, that's what I meant,


        Stefan




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796-done <at> debbugs.gnu.org:


Received: (at 12796-done) by debbugs.gnu.org; 10 Nov 2012 23:01:35 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Nov 10 18:01:35 2012
Received: from localhost ([127.0.0.1]:60233 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TXK3S-0002XM-PG
	for submit <at> debbugs.gnu.org; Sat, 10 Nov 2012 18:01:35 -0500
Received: from mail-lb0-f172.google.com ([209.85.217.172]:42880)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <raaahh@HIDDEN>) id 1TXK3Q-0002XE-Ln
	for 12796-done <at> debbugs.gnu.org; Sat, 10 Nov 2012 18:01:33 -0500
Received: by mail-lb0-f172.google.com with SMTP id y2so624134lbk.3
	for <12796-done <at> debbugs.gnu.org>; Sat, 10 Nov 2012 15:01:16 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject
	:references:in-reply-to:content-type:content-transfer-encoding;
	bh=avieI6OnLPbH30dmCvzOtRDRXJKX6fPNZgUPf5aDOlY=;
	b=NridZhMW+UUXYTu37JbAzq/7gy/2GiZCuPsxrcOZN9cUWgxPgdIIeI2dvWAaO6oLqn
	VppQdG5Fj2RJyW+YUKGwVei4MW81/KLG/5tQXRoxSyZb7ltIIHZilPUTdKsxsytoA/Lb
	GNu0OS6JkWbrbtijZ4UTP1W7Savm+MdjnpwMqokELAtJhg+lbn1eJdtRKKMkpVHDodPA
	eDWa/qAAHpIiCiLvpe/vDeWm+2w9hV9xD8n7TM20okgt2h9gvZgKXlzJn3wcpdU67cO6
	XIna3iDtDj2jqHV2a1PI0bkRfIVgusQTneEtXhk4OoKx4EcUKF/hKn3N13pEKPgZskOm
	BIJQ==
Received: by 10.152.106.212 with SMTP id gw20mr14294738lab.8.1352588474074;
	Sat, 10 Nov 2012 15:01:14 -0800 (PST)
Received: from [192.168.1.2] ([178.252.98.87])
	by mx.google.com with ESMTPS id z9sm287339lby.8.2012.11.10.15.01.12
	(version=SSLv3 cipher=OTHER); Sat, 10 Nov 2012 15:01:13 -0800 (PST)
Message-ID: <509EDCB9.7040103@HIDDEN>
Date: Sun, 11 Nov 2012 03:01:13 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Stefan Monnier <monnier@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN> <509AD8AB.90703@HIDDEN>
	<m2hap0q2ed.fsf@HIDDEN> <jwvbof820mt.fsf-monnier+emacs@HIDDEN>
	<m2625ga6mg.fsf@HIDDEN> <jwvobj8gpiq.fsf-monnier+emacs@HIDDEN>
	<509E945F.6010601@HIDDEN>
	<jwvmwypoywl.fsf-monnier+emacs@HIDDEN>
In-Reply-To: <jwvmwypoywl.fsf-monnier+emacs@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796-done
Cc: Leo <sdl.web@HIDDEN>, 12796-done <at> debbugs.gnu.org,
	Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -0.7 (/)

On 11.11.2012 2:51, Stefan Monnier wrote:
>> With speed-up patches installed on both branches, I consider this fixed.
>
> No, the use of with-local-quit is the main issue to solve.

Do you mean `when-no-input' and the lack of its use?




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796-done <at> debbugs.gnu.org:


Received: (at 12796-done) by debbugs.gnu.org; 10 Nov 2012 22:51:26 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Nov 10 17:51:26 2012
Received: from localhost ([127.0.0.1]:60198 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TXJtd-0002Hv-So
	for submit <at> debbugs.gnu.org; Sat, 10 Nov 2012 17:51:26 -0500
Received: from ironport2-out.teksavvy.com ([206.248.154.182]:11300)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <monnier@HIDDEN>) id 1TXJtc-0002Hp-GF
	for 12796-done <at> debbugs.gnu.org; Sat, 10 Nov 2012 17:51:24 -0500
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av0EAG6Zu09sr+ZY/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLDiYSFBgNJIgcBboJkEQDiEKacYFYgwc
X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206908677"
Received: from 108-175-230-88.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net)
	([108.175.230.88])
	by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA;
	10 Nov 2012 17:51:08 -0500
Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848)
	id 00369AE4B5; Sat, 10 Nov 2012 17:51:07 -0500 (EST)
From: Stefan Monnier <monnier@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Message-ID: <jwvmwypoywl.fsf-monnier+emacs@HIDDEN>
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN> <509AD8AB.90703@HIDDEN>
	<m2hap0q2ed.fsf@HIDDEN> <jwvbof820mt.fsf-monnier+emacs@HIDDEN>
	<m2625ga6mg.fsf@HIDDEN> <jwvobj8gpiq.fsf-monnier+emacs@HIDDEN>
	<509E945F.6010601@HIDDEN>
Date: Sat, 10 Nov 2012 17:51:07 -0500
In-Reply-To: <509E945F.6010601@HIDDEN> (Dmitry Gutov's message of "Sat, 10
	Nov 2012 21:52:31 +0400")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.8 (/)
X-Debbugs-Envelope-To: 12796-done
Cc: Leo <sdl.web@HIDDEN>, 12796-done <at> debbugs.gnu.org,
	Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -0.5 (/)

> With speed-up patches installed on both branches, I consider this fixed.

No, the use of with-local-quit is the main issue to solve.


        Stefan




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796-done <at> debbugs.gnu.org:


Received: (at 12796-done) by debbugs.gnu.org; 10 Nov 2012 17:52:52 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Nov 10 12:52:52 2012
Received: from localhost ([127.0.0.1]:59741 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TXFEh-0003RJ-R4
	for submit <at> debbugs.gnu.org; Sat, 10 Nov 2012 12:52:52 -0500
Received: from mail-la0-f44.google.com ([209.85.215.44]:46399)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <raaahh@HIDDEN>) id 1TXFEe-0003RA-TQ
	for 12796-done <at> debbugs.gnu.org; Sat, 10 Nov 2012 12:52:49 -0500
Received: by mail-la0-f44.google.com with SMTP id d3so10832lah.3
	for <12796-done <at> debbugs.gnu.org>; Sat, 10 Nov 2012 09:52:33 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject
	:references:in-reply-to:content-type:content-transfer-encoding;
	bh=6oIVjOGUziKHtBJetzrKF93f/6WUWB9fBTPWw/2fg6g=;
	b=HJpwKiiBY+A1NfnW26q9uofkSqRQwdV4tE3F2crsfry/xhDft9TmnT2CwBdoAqVWce
	6iaL09gyKUNnerIXyTSc7Rfy0gndNerSYRmwlBkkOSk4x0Lc30tl6c7m2J3cZWdH5MEE
	T49ZTDKoUU5rWcUT1sJagwv5VKUDMOySKIQ076aXj54eeiU5bnVw/lhJNKPTtm32GOnw
	UHHHL/swzyrw0Ne8FvZMb1z+KAifYqPR1cfPkUUwRhCSBgdhTGZs1yeo+FE52nLuJjoe
	2IneLc953PyWysT7kMOVIo8S+g2yp1esr0uRymaGhF7AgKTRS1tw4MbDp05mFrMU8GYk
	OAvw==
Received: by 10.112.30.227 with SMTP id v3mr5955581lbh.65.1352569953433;
	Sat, 10 Nov 2012 09:52:33 -0800 (PST)
Received: from [192.168.1.2] ([178.252.98.87])
	by mx.google.com with ESMTPS id ts2sm674015lab.10.2012.11.10.09.52.31
	(version=SSLv3 cipher=OTHER); Sat, 10 Nov 2012 09:52:32 -0800 (PST)
Message-ID: <509E945F.6010601@HIDDEN>
Date: Sat, 10 Nov 2012 21:52:31 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: 12796-done <at> debbugs.gnu.org
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN> <509AD8AB.90703@HIDDEN>
	<m2hap0q2ed.fsf@HIDDEN> <jwvbof820mt.fsf-monnier+emacs@HIDDEN>
	<m2625ga6mg.fsf@HIDDEN> <jwvobj8gpiq.fsf-monnier+emacs@HIDDEN>
In-Reply-To: <jwvobj8gpiq.fsf-monnier+emacs@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796-done
Cc: Kim Storm <storm@HIDDEN>, Stefan Monnier <monnier@HIDDEN>,
	Leo <sdl.web@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -0.7 (/)

With speed-up patches installed on both branches, I consider this fixed.




Notification sent to Dmitry Gutov <dgutov@HIDDEN>:
bug acknowledged by developer. Full text available.
Reply sent to Dmitry Gutov <dgutov@HIDDEN>:
You have taken responsibility. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 14:05:19 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Thu Nov 08 09:05:19 2012
Received: from localhost ([127.0.0.1]:55595 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TWSjP-0004sL-IT
	for submit <at> debbugs.gnu.org; Thu, 08 Nov 2012 09:05:19 -0500
Received: from ironport2-out.teksavvy.com ([206.248.154.182]:55593)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <monnier@HIDDEN>) id 1TWSjN-0004sE-BO
	for 12796 <at> debbugs.gnu.org; Thu, 08 Nov 2012 09:05:17 -0500
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av0EAG6Zu0/O+LEi/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLNBIUGA0kiBwFugmQRAOIQppxgViDBw
X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206731496"
Received: from 206-248-177-34.dsl.teksavvy.com (HELO pastel.home)
	([206.248.177.34])
	by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA;
	08 Nov 2012 09:05:14 -0500
Received: by pastel.home (Postfix, from userid 20848)
	id 5E92E59780; Thu,  8 Nov 2012 09:05:14 -0500 (EST)
From: Stefan Monnier <monnier@HIDDEN>
To: Leo <sdl.web@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Message-ID: <jwvobj8gpiq.fsf-monnier+emacs@HIDDEN>
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN> <509AD8AB.90703@HIDDEN>
	<m2hap0q2ed.fsf@HIDDEN> <jwvbof820mt.fsf-monnier+emacs@HIDDEN>
	<m2625ga6mg.fsf@HIDDEN>
Date: Thu, 08 Nov 2012 09:05:14 -0500
In-Reply-To: <m2625ga6mg.fsf@HIDDEN> (Leo's message of "Thu, 08 Nov 2012
	15:36:23 +0800")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: -0.0 (/)
X-Debbugs-Envelope-To: 12796
Cc: Kim Storm <storm@HIDDEN>, 12796 <at> debbugs.gnu.org,
	Dmitry Gutov <dgutov@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -0.5 (/)

>>> So do you mind installing the following small change for 24.3 that
>>> greatly improves ido performance:
>> I guess it's OK, yes.
> Can I incorporate your suggestion on removing the backtracking issue?

Not for 24.3, no, but on the trunk, of course, yes.

> I have found cases where flex matching perform badly but with your
> suggestion, for example, cut the time from 4.8s to 0.3s.

Cool,


        Stefan




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 07:36:38 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Thu Nov 08 02:36:38 2012
Received: from localhost ([127.0.0.1]:55289 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TWMfG-0003as-59
	for submit <at> debbugs.gnu.org; Thu, 08 Nov 2012 02:36:38 -0500
Received: from mail-da0-f44.google.com ([209.85.210.44]:53336)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <sdl.web@HIDDEN>) id 1TWMfE-0003al-1G
	for 12796 <at> debbugs.gnu.org; Thu, 08 Nov 2012 02:36:36 -0500
Received: by mail-da0-f44.google.com with SMTP id h15so1060423dan.3
	for <12796 <at> debbugs.gnu.org>; Wed, 07 Nov 2012 23:36:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=from:to:cc:subject:references:date:in-reply-to:message-id
	:user-agent:mime-version:content-type;
	bh=U094xmsfdObyTNgChqjRXRJaWO3a9TR7sdHmMHOy928=;
	b=OCTOcA84pQJ/B+ImA7NtUjJo/HKJkl2b5cLzjv/RzbP12FZQHtJJ0n1fIN7oJeLKws
	NefnAJeR2ZcXbCwBJSnSvCoyuYfl5N7+nmVDD3lW3n1z/ntecQGmxcHcNqXJ2SKZVx5F
	nosW5qXlKfb+ipRoPjkbdPew39/CHvtEBA1vdQrjcjDgi7GsdPx0kNoW4XLnoZVeT6UM
	EyNqnZUsgsGBvj2Z2QgH/jxQkPV6yyxNQuod/WOgMJopldk+6qPOXWrfoWfyOvn1ZnbK
	qTAYfhjSZJpJIrJp/0JzKr0NCVpY6O3YApa9G22sXXppDOrx30NQVwETk41TObcSenlO
	BvjQ==
Received: by 10.68.217.201 with SMTP id pa9mr21536340pbc.45.1352360195009;
	Wed, 07 Nov 2012 23:36:35 -0800 (PST)
Received: from Shidais-iMac.local ([119.255.41.67])
	by mx.google.com with ESMTPS id hs1sm15514747pbc.33.2012.11.07.23.36.31
	(version=TLSv1/SSLv3 cipher=OTHER);
	Wed, 07 Nov 2012 23:36:33 -0800 (PST)
From: Leo <sdl.web@HIDDEN>
To: Stefan Monnier <monnier@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN> <509AD8AB.90703@HIDDEN>
	<m2hap0q2ed.fsf@HIDDEN> <jwvbof820mt.fsf-monnier+emacs@HIDDEN>
Date: Thu, 08 Nov 2012 15:36:23 +0800
In-Reply-To: <jwvbof820mt.fsf-monnier+emacs@HIDDEN> (Stefan Monnier's message
	of "Wed, 07 Nov 2012 23:14:44 -0500")
Message-ID: <m2625ga6mg.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: -0.7 (/)
X-Debbugs-Envelope-To: 12796
Cc: Kim Storm <storm@HIDDEN>, 12796 <at> debbugs.gnu.org,
	Dmitry Gutov <dgutov@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -2.6 (--)

On 2012-11-08 12:14 +0800, Stefan Monnier wrote:
> Indeed.  This undesired behavior was introduced by the change to
> split-string introduced in Emacs-22, so the patch fixes a regression
> w.r.t Emacs-21.

Thanks for that information.

>
>> So do you mind installing the following small change for 24.3 that
>> greatly improves ido performance:
>
> I guess it's OK, yes.

Can I incorporate your suggestion on removing the backtracking issue? I
have found cases where flex matching perform badly but with your
suggestion, for example, cut the time from 4.8s to 0.3s.

The patch could look like this:

diff --git a/lisp/ido.el b/lisp/ido.el
index 31d5279d..0a740b2a 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3783,7 +3783,11 @@ (defun ido-set-matches-1 (items &optional do-full)
 	       ido-enable-flex-matching
 	       (> (length ido-text) 1)
 	       (not ido-enable-regexp))
-      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*"))
+      (setq re (concat (regexp-quote (string (aref ido-text 0)))
+		       (mapconcat (lambda (c)
+				    (concat "[^" (string c) "]*"
+					    (regexp-quote (string c))))
+				  (substring ido-text 1) "")))



Leo




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 04:29:34 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Nov 07 23:29:34 2012
Received: from localhost ([127.0.0.1]:55170 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TWJkE-0007it-1p
	for submit <at> debbugs.gnu.org; Wed, 07 Nov 2012 23:29:34 -0500
Received: from forward1h.mail.yandex.net ([84.201.187.146]:33019)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TWJk9-0007ii-KK
	for 12796 <at> debbugs.gnu.org; Wed, 07 Nov 2012 23:29:32 -0500
Received: from smtp4h.mail.yandex.net (smtp4h.mail.yandex.net [84.201.186.21])
	by forward1h.mail.yandex.net (Yandex) with ESMTP id EF2FA9E2959;
	Thu,  8 Nov 2012 08:29:15 +0400 (MSK)
Received: from smtp4h.mail.yandex.net (localhost [127.0.0.1])
	by smtp4h.mail.yandex.net (Yandex) with ESMTP id 7DB412C0110;
	Thu,  8 Nov 2012 08:29:15 +0400 (MSK)
Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87])
	by smtp4h.mail.yandex.net (nwsmtp/Yandex) with ESMTP id
	TEtW8iBB-TFtKRTgH; Thu,  8 Nov 2012 08:29:15 +0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail;
	t=1352348955; bh=uSkpEhmIs18hUJgWn8sG7weQ9SI1bMug9Y8NIqTfOK4=;
	h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:
	References:In-Reply-To:Content-Type:Content-Transfer-Encoding;
	b=bLTCLfmZBPv7vqQnTO2cXf5LDDFiMhrw4E29rUI+o2D+aQUAVNCJ3qkt6a+imarGY
	fV5Jgn2UfMvEhG+EvtqJuPArb69LlxTBgd+iuSeaZ8rUmFsBKtjS6P2EKMZu7OIacT
	ZZxJrIuwFdJxVrVNJmbbwZULxbTifG4vexCBR6U0=
Message-ID: <509B351F.8040607@HIDDEN>
Date: Thu, 08 Nov 2012 08:29:19 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Stefan Monnier <monnier@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<jwvliec97pr.fsf-monnier+emacs@HIDDEN>
In-Reply-To: <jwvliec97pr.fsf-monnier+emacs@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: Leo <sdl.web@HIDDEN>, 12796 <at> debbugs.gnu.org, Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

On 08.11.2012 6:05, Stefan Monnier wrote:
>> -      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*"))
>> +      (setq re (mapconcat #'regexp-quote (split-string ido-text "" t)
>> ".*"))
>
> Sounds like a good change.  Tho:
>
>     (mapconcat (lambda (c) (regexp-quote (string c))) ido-text ".*")
>
> would work as well.

Indeed. A two-character change offering massive speedup looks cuter, 
though. And easier to understand for casual readers.

> You could try to speed up the regexp matching some more by eliminating
> backtracking (which should mostly eliminate a few pathological cases):
>
>     (let ((first t))
>       (mapconcat (lambda (c)
>                    (if first
>                        (progn (setq first nil) (regexp-quote (string c)))
>                      (concat "[^" (string c) "]*"
>                              (regexp-quote (string c)))))
>                  ido-text ""))

Yep, this adds some further speedup especially with longer string.
To use the existing testing setup (numbers are a bit different in this 
session):

;; omt 18000 15 abcdefghzzzzz 0.042
;; nbt 18000 15 abcdefghzzzzz 0.040

;; omt 18000 45 abcdefghzzz123 0.127
;; nbt 18000 45 abcdefghzzz123 0.087

>> I'm still going to see if I can make while-no-input work here, though.
>
> Yes, that'd be very welcome.

I sent a patch that doesn't seem to break anything for me:

http://debbugs.gnu.org/cgi/bugreport.cgi?bug=12796#41

But in the light of the above numbers, it seems that (while-no-input) 
would almost always guard a section of code that takes 1/20th of a 
second to run, or less. Only useful when a user has floored "backspace", 
I think.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 04:14:46 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Nov 07 23:14:46 2012
Received: from localhost ([127.0.0.1]:55103 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TWJVu-0007Mi-Ih
	for submit <at> debbugs.gnu.org; Wed, 07 Nov 2012 23:14:46 -0500
Received: from ironport2-out.teksavvy.com ([206.248.154.182]:31967)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <monnier@HIDDEN>) id 1TWJVt-0007Mc-0l
	for 12796 <at> debbugs.gnu.org; Wed, 07 Nov 2012 23:14:45 -0500
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av0EAG6Zu0/O+LEi/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLNBIUGA0kiBwFugmQRAOIQppxgViDBw
X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206717905"
Received: from 206-248-177-34.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net)
	([206.248.177.34])
	by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA;
	07 Nov 2012 23:14:44 -0500
Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848)
	id B2DDCAE59E; Wed,  7 Nov 2012 23:14:44 -0500 (EST)
From: Stefan Monnier <monnier@HIDDEN>
To: Leo <sdl.web@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Message-ID: <jwvbof820mt.fsf-monnier+emacs@HIDDEN>
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN> <509AD8AB.90703@HIDDEN>
	<m2hap0q2ed.fsf@HIDDEN>
Date: Wed, 07 Nov 2012 23:14:44 -0500
In-Reply-To: <m2hap0q2ed.fsf@HIDDEN> (Leo's message of "Thu, 08 Nov 2012
	10:00:58 +0800")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: -0.0 (/)
X-Debbugs-Envelope-To: 12796
Cc: Kim Storm <storm@HIDDEN>, 12796 <at> debbugs.gnu.org,
	Dmitry Gutov <dgutov@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -1.9 (-)

>> From this bit in ido-set-matches-1:

> (if ido-enable-prefix 
>     (setq re (concat "\\`" re)))

> It seems not including the leading and trailing .* is intended.

Indeed.  This undesired behavior was introduced by the change to
split-string introduced in Emacs-22, so the patch fixes a regression
w.r.t Emacs-21.

> So do you mind installing the following small change for 24.3 that
> greatly improves ido performance:

I guess it's OK, yes.


        Stefan




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 02:05:57 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Nov 07 21:05:57 2012
Received: from localhost ([127.0.0.1]:55059 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TWHVF-0004T8-6i
	for submit <at> debbugs.gnu.org; Wed, 07 Nov 2012 21:05:57 -0500
Received: from ironport2-out.teksavvy.com ([206.248.154.182]:61712)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <monnier@HIDDEN>) id 1TWHVD-0004T0-1z
	for 12796 <at> debbugs.gnu.org; Wed, 07 Nov 2012 21:05:55 -0500
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av0EAG6Zu0/O+LEi/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLDiYSFBgNJIgcBboJkEQDiEKacYFYgwc
X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206712351"
Received: from 206-248-177-34.dsl.teksavvy.com (HELO ceviche.home)
	([206.248.177.34])
	by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA;
	07 Nov 2012 21:05:54 -0500
Received: by ceviche.home (Postfix, from userid 20848)
	id 5338A6610A; Wed,  7 Nov 2012 21:05:54 -0500 (EST)
From: Stefan Monnier <monnier@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Message-ID: <jwvliec97pr.fsf-monnier+emacs@HIDDEN>
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
Date: Wed, 07 Nov 2012 21:05:54 -0500
In-Reply-To: <5099DE35.2060402@HIDDEN> (Dmitry Gutov's message of "Wed, 07
	Nov 2012 08:06:13 +0400")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.8 (/)
X-Debbugs-Envelope-To: 12796
Cc: Leo <sdl.web@HIDDEN>, 12796 <at> debbugs.gnu.org, Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.8 (/)

> -      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*"))
> +      (setq re (mapconcat #'regexp-quote (split-string ido-text "" t)
> ".*"))

Sounds like a good change.  Tho:

   (mapconcat (lambda (c) (regexp-quote (string c))) ido-text ".*")

would work as well.
You could try to speed up the regexp matching some more by eliminating
backtracking (which should mostly eliminate a few pathological cases):

   (let ((first t))
     (mapconcat (lambda (c)
                  (if first
                      (progn (setq first nil) (regexp-quote (string c)))
                    (concat "[^" (string c) "]*"
                            (regexp-quote (string c)))))
                ido-text ""))

> I'm still going to see if I can make while-no-input work here, though.

Yes, that'd be very welcome.


        Stefan




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 02:02:43 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Nov 07 21:02:43 2012
Received: from localhost ([127.0.0.1]:55055 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TWHS6-0004Od-CL
	for submit <at> debbugs.gnu.org; Wed, 07 Nov 2012 21:02:42 -0500
Received: from mail-pb0-f44.google.com ([209.85.160.44]:55185)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <sdl.web@HIDDEN>) id 1TWHS4-0004OW-Mm
	for 12796 <at> debbugs.gnu.org; Wed, 07 Nov 2012 21:02:41 -0500
Received: by mail-pb0-f44.google.com with SMTP id ro8so1635494pbb.3
	for <12796 <at> debbugs.gnu.org>; Wed, 07 Nov 2012 18:02:41 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=from:to:cc:subject:references:date:in-reply-to:message-id
	:user-agent:mime-version:content-type;
	bh=fC8Q+zbu12kiC1qEVjMbpi68LAn/UZSIJJ2uzPu+ho8=;
	b=JBLoI0vbhHsUvWotFhLPf4usqx3+g4HxtHNZmaeslq0vWq80bYBD0pWEETp+60PnxQ
	y1NqdEQeILQA+AIfUYRw2aW1TET7qCNycSh7V1xKfqP4JbZwpRj+lJxN7lLFDIHU5Dbm
	6SIn+4tmJ/h5tM5i/MCV8BRstwRrKxFeHSU0vhXYPeIxNivplfaEeDiNNbBD3ibiwCue
	9V6dAwZymo3TbiCR6Bwej66ZTLjs2mRe+f3PloMXBob6aeKfbEbdEA+GcY9Aon3h9QcG
	/Umrbswzzd4AIJlxBuosFH9BxekMvE+PDjS9Md53l24DmJyLo3Vh0GRq0AybLUvC7D+6
	a3+g==
Received: by 10.68.115.75 with SMTP id jm11mr4630143pbb.28.1352340160946;
	Wed, 07 Nov 2012 18:02:40 -0800 (PST)
Received: from localhost ([119.255.41.67])
	by mx.google.com with ESMTPS id x8sm15202762paw.16.2012.11.07.18.02.37
	(version=TLSv1/SSLv3 cipher=OTHER);
	Wed, 07 Nov 2012 18:02:39 -0800 (PST)
From: Leo <sdl.web@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN> <509AD8AB.90703@HIDDEN>
Date: Thu, 08 Nov 2012 10:00:58 +0800
In-Reply-To: <509AD8AB.90703@HIDDEN> (Dmitry Gutov's message of "Thu, 08
	Nov 2012 01:54:51 +0400")
Message-ID: <m2hap0q2ed.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: -0.7 (/)
X-Debbugs-Envelope-To: 12796
Cc: Stefan Monnier <monnier@HIDDEN>, 12796 <at> debbugs.gnu.org,
	Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -2.6 (--)

On 2012-11-08 05:54 +0800, Dmitry Gutov wrote:
> It looks like, with either patch, flex matching is not the bottleneck
> anymore.

Excellent. The other patch is definitely simpler. So I prefer it.

Stefan, for concluding this bug, I think we should make this change.

From this bit in ido-set-matches-1:

(if ido-enable-prefix 
    (setq re (concat "\\`" re)))

It seems not including the leading and trailing .* is intended. So do
you mind installing the following small change for 24.3 that greatly
improves ido performance:

diff --git a/lisp/ido.el b/lisp/ido.el
index 31d5279d..c8bc0bb7 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3783,7 +3783,7 @@ (defun ido-set-matches-1 (items &optional do-full)
 	       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

Leo




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 21:54:54 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Nov 07 16:54:54 2012
Received: from localhost ([127.0.0.1]:54904 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TWDaH-0005KV-O9
	for submit <at> debbugs.gnu.org; Wed, 07 Nov 2012 16:54:54 -0500
Received: from forward3.mail.yandex.net ([77.88.46.8]:39340)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TWDaE-0005KK-36
	for 12796 <at> debbugs.gnu.org; Wed, 07 Nov 2012 16:54:52 -0500
Received: from smtp2.mail.yandex.net (smtp2.mail.yandex.net [77.88.46.102])
	by forward3.mail.yandex.net (Yandex) with ESMTP id D6329B416BD;
	Thu,  8 Nov 2012 01:54:49 +0400 (MSK)
Received: from smtp2.mail.yandex.net (localhost [127.0.0.1])
	by smtp2.mail.yandex.net (Yandex) with ESMTP id 915A5E205B2;
	Thu,  8 Nov 2012 01:54:49 +0400 (MSK)
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
	smW4Phda-snW4xXLg; Thu,  8 Nov 2012 01:54:49 +0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail;
	t=1352325289; bh=6o0CwF6hxdEg8l4hiBOqB9JYTGrYNVmaPh1/jHySJC4=;
	h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:
	References:In-Reply-To:Content-Type:Content-Transfer-Encoding;
	b=Y/xpeAUw/4zPenLrYk7z9xDzcu2ttK7arahx4cNLP0JVbcvKHWgI4W/INK1SplNq4
	N/79/eu+QvIWpCpAR4na3Je9xIPx/ms0zcKrg25vMG/biFt5rSfXRrKeH9TVIKDPQw
	ptUL6bAXX0mUBArxxtrpwB9DDHjNPOeWqSayHNt8=
Message-ID: <509AD8AB.90703@HIDDEN>
Date: Thu, 08 Nov 2012 01:54:51 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Leo <sdl.web@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
	<m2obj9pujc.fsf@HIDDEN>
In-Reply-To: <m2obj9pujc.fsf@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: Stefan Monnier <monnier@HIDDEN>, 12796 <at> debbugs.gnu.org,
	Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

On 07.11.2012 14:38, Leo wrote:
> On 2012-11-07 12:06 +0800, Dmitry Gutov wrote:
>> That was actually a good advice. As far as I can tell, most of the
>> speed improvement comes from the following change
>
> I seem to have some speedup on the flex matching part with the following
> patch.
>
> (tested on a ~9000 list with each item containing ~35 chars)
>
> ...

I've done some testing, see the setup and numbers at the end.

It looks like, with either patch, flex matching is not the bottleneck 
anymore. ido-hacks has some other functions changed or overridden, so if 
you're not satisfied with performance, you might want to look there.

(defun random-string (len)
   (let ((chars "1234567890abcdefghijklmnopqrstyvwxyz"))
     (apply 'string
            (loop for i from 1 to len
                  collect (aref chars (random (length chars)))))))

(defun random-dataset (size len)
   (loop for i from 1 to size
         collect (random-string len)))

(defmacro js2-time (form)
   "Evaluate FORM, discard result, and return elapsed time in sec"
   (declare (debug t))
   (let ((beg (make-symbol "--js2-time-beg--"))
         (delta (make-symbol "--js2-time-end--")))
     `(let ((,beg (current-time))
            ,delta)
        ,form
        (/ (truncate (* (- (float-time (current-time))
                           (float-time ,beg))
                        10000))
           10000.0))))

(defun ido-match-test (size len ido-text)
   (let ((items (random-dataset size len))
         (ido-cur-item 'list))
     (js2-time
      (ido-set-matches-1 items))))

;; *    size len        input  time
;; cis  9000 35 aaaaaaaaaa    0.06
;; cis 18000 15 aaaaaaaaaa    0.055
;; cis 18000 15 abcdefghzzzzz 0.057
;; omt  9000 35 aaaaaaaaaa    0.055 \
;; omt 18000 15 aaaaaaaaaa    0.054 + <- but the variance is bigger
;; omt 18000 15 abcdefghzzzzz 0.056 /
;; unp  9000 35 abcdefghzzzzz 0.82
;; unp 18000 15 abcdefghzzzzz 0.31

;; legend:
;; cis = ido-chars-in-string
;; ont = (split-string ido-text "" t)
;; unp = (split-string ido-text "")

;; bonus:
;; cis 18000 45 abcdefghzzz123 0.51
;; omt 18000 45 abcdefghzzz123 0.15
;; cis 18000 45 abcdefghzzz123 3.02




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 10:38:50 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Nov 07 05:38:50 2012
Received: from localhost ([127.0.0.1]:53461 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TW321-0003q5-Ig
	for submit <at> debbugs.gnu.org; Wed, 07 Nov 2012 05:38:50 -0500
Received: from mail-da0-f44.google.com ([209.85.210.44]:52392)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <sdl.web@HIDDEN>) id 1TW31z-0003pn-HY
	for 12796 <at> debbugs.gnu.org; Wed, 07 Nov 2012 05:38:48 -0500
Received: by mail-da0-f44.google.com with SMTP id h15so635732dan.3
	for <12796 <at> debbugs.gnu.org>; Wed, 07 Nov 2012 02:38:51 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=from:to:cc:subject:references:date:in-reply-to:message-id
	:user-agent:mime-version:content-type;
	bh=kHKVw9i/finU9phF3Di4Umhq9kmERbEIrhM503Z/Fr4=;
	b=cw9NhNpBeaYDspPioe8Yen8y3/vxwj3mO+0nVyZRQAPROf4EcXIuATnWRvFUI7PEoA
	cm+pO+3z5ndDbnkPc6rGeCpBbYdJjW5JcQbYO/YzE3u/TutEzs+9kYjYbxrGKTvWIVyq
	1Lf1QFkHZ4Cez/5KdlKk5x/Abv2qd7Rhx7UfDHDfRxuZ+Rr6EWdnnu6jIth0XbePbeJx
	qJjuUYsOVV+luPwanvEJ+FJn3wBXxols1nrFz9bIQeeBW7/1I6hTw8oIt63323JBSekI
	b9T9hAEMh70fT1ha3aBUboKUS8+83IUYvVKcyMInA485fZOUXJPYYkulx/6oL2cTvfcb
	FgaQ==
Received: by 10.68.217.201 with SMTP id pa9mr12385902pbc.45.1352284731154;
	Wed, 07 Nov 2012 02:38:51 -0800 (PST)
Received: from localhost ([119.255.41.67])
	by mx.google.com with ESMTPS id bd2sm14084425pab.36.2012.11.07.02.38.47
	(version=TLSv1/SSLv3 cipher=OTHER);
	Wed, 07 Nov 2012 02:38:50 -0800 (PST)
From: Leo <sdl.web@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN> <5099DE35.2060402@HIDDEN>
Date: Wed, 07 Nov 2012 18:38:31 +0800
In-Reply-To: <5099DE35.2060402@HIDDEN> (Dmitry Gutov's message of "Wed, 07
	Nov 2012 08:06:13 +0400")
Message-ID: <m2obj9pujc.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: Stefan Monnier <monnier@HIDDEN>, 12796 <at> debbugs.gnu.org,
	Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -0.7 (/)

On 2012-11-07 12:06 +0800, Dmitry Gutov wrote:
> That was actually a good advice. As far as I can tell, most of the
> speed improvement comes from the following change

I seem to have some speedup on the flex matching part with the following
patch.

(tested on a ~9000 list with each item containing ~35 chars)

diff --git a/ido.el b/ido.el
index 31d5279d..dc623110 100644
--- a/ido.el
+++ b/ido.el
@@ -3710,6 +3710,25 @@ (defun ido-get-bufname (win)
 		(cons buf ido-bufs-in-frame)))))
 
 ;;; FIND MATCHING ITEMS
+(defun ido-chars-in-string (chars str &optional prefix)
+  (let ((p 0)
+	(len (length chars))
+	c)
+    (catch 'exit
+      (when (zerop len)
+	(throw 'exit t))
+      (when (zerop (length str))
+	(throw 'exit nil))
+      (setq c (aref chars 0))
+      (when (and prefix (/= c (aref str 0)))
+	(throw 'exit nil))
+      (dotimes (i (length str))
+	(when (eq (aref str i) c)
+	  (setq p (1+ p))
+	  (when (>= p len)
+	    (throw 'exit t))
+	  (setq c (aref chars p))))
+      (>= p len))))
 
 (defun ido-set-matches-1 (items &optional do-full)
   ;; Return list of matches in items
@@ -3783,13 +3802,10 @@ (defun ido-set-matches-1 (items &optional do-full)
 	       ido-enable-flex-matching
 	       (> (length ido-text) 1)
 	       (not ido-enable-regexp))
-      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*"))
-      (if ido-enable-prefix
-	  (setq re (concat "\\`" re)))
       (mapc
        (lambda (item)
 	 (let ((name (ido-name item)))
-	   (if (string-match re name)
+	   (if (ido-chars-in-string ido-text name ido-enable-prefix)
 	       (setq matches (cons item matches)))))
        items))
     matches))




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 05:40:59 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Nov 07 00:40:59 2012
Received: from localhost ([127.0.0.1]:53284 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVyNm-0005Wm-NO
	for submit <at> debbugs.gnu.org; Wed, 07 Nov 2012 00:40:59 -0500
Received: from forward18.mail.yandex.net ([95.108.253.143]:41433)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TVyNg-0005Wb-Vu
	for 12796 <at> debbugs.gnu.org; Wed, 07 Nov 2012 00:40:56 -0500
Received: from smtp18.mail.yandex.net (smtp18.mail.yandex.net [95.108.252.18])
	by forward18.mail.yandex.net (Yandex) with ESMTP id B49131781991;
	Wed,  7 Nov 2012 09:40:56 +0400 (MSK)
Received: from smtp18.mail.yandex.net (localhost [127.0.0.1])
	by smtp18.mail.yandex.net (Yandex) with ESMTP id 7B8F118A03E6;
	Wed,  7 Nov 2012 09:40:56 +0400 (MSK)
Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87])
	by smtp18.mail.yandex.net (nwsmtp/Yandex) with ESMTP id
	etji8vcK-eujWxrUI; Wed,  7 Nov 2012 09:40:56 +0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail;
	t=1352266856; bh=UkTGooNT4neXz8FK5bApm6qrUrT9Cyaz+sBC3xzNZag=;
	h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:
	References:In-Reply-To:Content-Type:Content-Transfer-Encoding;
	b=WuRS3tnaOHmNhOppEO8XWlwtv7tNsrhvLB/c1L1apSuSmBAo7/XId520+B8O9fpwU
	P2C6CxhIetq5z06oH1RoQLgX6SVdwbzj5B77s78MkTw5ja4l4VDu/0RL6LjJwBg4U9
	v4HvtYNf9UbiuUJZcKQkaQKZHfcvY/9+79eBVknM=
Message-ID: <5099F46C.7060301@HIDDEN>
Date: Wed, 07 Nov 2012 09:41:00 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Kim Storm <storm@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
	<5096A046.6090908@HIDDEN> <509750B0.2030000@HIDDEN>
	<jwvd2zr4ixz.fsf-monnier+bug#12796@HIDDEN>
	<5098EE91.9000906@HIDDEN>
In-Reply-To: <5098EE91.9000906@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: Stefan Monnier <monnier@HIDDEN>, 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

On 06.11.2012 15:03, Kim Storm wrote:
> 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.

How does this look to you?

I added a new var because ido-rescan is unconditionally set to nil in 
many places.

By the way, is there a place where ido-rotate is set to anything but 
nil? Does this variable actually do anything?

=== modified file 'lisp/ido.el'
--- lisp/ido.el	2012-10-05 07:38:05 +0000
+++ lisp/ido.el	2012-11-07 05:34:53 +0000
@@ -1020,6 +1020,9 @@
  (defvar ido-rotate nil
    "Non-nil means we are rotating list of matches.")

+(defvar ido-interrupted nil
+  "Non-nil means calculation of matches was interrupted by keyboard 
input.")
+
  (defvar ido-text nil
    "Stores the users string as it is typed in.")

@@ -3778,9 +3781,14 @@

  (defun ido-set-matches ()
    ;; Set `ido-matches' to the list of items matching prompt
-  (when ido-rescan
-    (setq ido-matches (ido-set-matches-1 (reverse ido-cur-list) (not 
ido-rotate))
-	  ido-rotate nil)))
+  (when (or ido-rescan ido-interrupted)
+    (setq ido-interrupted t)
+    (while-no-input
+      (setq ido-matches (ido-set-matches-1 (reverse ido-cur-list)
+                                           (not ido-rotate))
+            ido-interrupted nil
+            ido-rotate nil))
+    (when ido-interrupted (setq ido-matches nil))))

  (defun ido-ignore-item-p (name re-list &optional ignore-ext)
    ;; Return t if the buffer or file NAME should be ignored.
@@ -4513,11 +4521,12 @@
  	      (exit-minibuffer)))

  	;; Insert the match-status information:
-	(ido-set-common-completion)
-	(let ((inf (ido-completions contents)))
-	  (setq ido-show-confirm-message nil)
-	  (ido-trace "inf" inf)
-	  (insert inf))
+        (unless ido-interrupted
+          (ido-set-common-completion)
+          (let ((inf (ido-completions contents)))
+            (setq ido-show-confirm-message nil)
+            (ido-trace "inf" inf)
+            (insert inf)))
  	))))

  (defun ido-completions (name)







Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 04:06:14 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Tue Nov 06 23:06:14 2012
Received: from localhost ([127.0.0.1]:53155 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVwu6-0003Nl-Gl
	for submit <at> debbugs.gnu.org; Tue, 06 Nov 2012 23:06:14 -0500
Received: from forward2.mail.yandex.net ([77.88.46.7]:39775)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TVwu1-0003NX-HZ
	for 12796 <at> debbugs.gnu.org; Tue, 06 Nov 2012 23:06:12 -0500
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)
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)
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=
Message-ID: <5099DE35.2060402@HIDDEN>
Date: Wed, 07 Nov 2012 08:06:13 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Leo <sdl.web@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
	<m2y5iep2or.fsf@HIDDEN>
In-Reply-To: <m2y5iep2or.fsf@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: Stefan Monnier <monnier@HIDDEN>, 12796 <at> debbugs.gnu.org,
	Kim Storm <storm@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

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.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 02:27:54 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Tue Nov 06 21:27:54 2012
Received: from localhost ([127.0.0.1]:53087 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVvMw-0006xy-Gi
	for submit <at> debbugs.gnu.org; Tue, 06 Nov 2012 21:27:54 -0500
Received: from mail-pb0-f44.google.com ([209.85.160.44]:55046)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <sdl.web@HIDDEN>) id 1TVvMv-0006xr-6f
	for 12796 <at> debbugs.gnu.org; Tue, 06 Nov 2012 21:27:53 -0500
Received: by mail-pb0-f44.google.com with SMTP id ro8so839049pbb.3
	for <12796 <at> debbugs.gnu.org>; Tue, 06 Nov 2012 18:27:59 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=from:to:cc:subject:references:date:in-reply-to:message-id
	:user-agent:mime-version:content-type;
	bh=L5P1pGT2F7kLyNVWh+EA86XVOMW3BccB6kofgv/3how=;
	b=v+fTmSDQlVoamlQqQYBvRtLk5VtIX5tz15oNh3IKMQ7u2dJkDuzxRX0xzyedOiOYf0
	ZPMe7w371YQoUQ2kYqpw/vtf4xYIBNw85lDzBwukxITW+AbykIvtBRzEunxg1yS7D+hm
	XvHnJJBqg1S211Wu8uHhnICPq2XlyCuWCuoqAcxPB3B3WTb3TU2Ori5sgrBl0RomEyn2
	qhVgL0Lx2JELFDGMhZxjoEOGAgKP8B6tySfLoXqFB44x83oTj2fqhZ11Ykm14xCe+gVM
	ExTj5rTvQPeJoJRvWvde8GXnJCSAx7pIDoN+V0de/MS0RhXk2AM9ZJEpm9i13b2vdD9i
	fmpw==
Received: by 10.68.253.230 with SMTP id ad6mr2679639pbd.84.1352255278980;
	Tue, 06 Nov 2012 18:27:58 -0800 (PST)
Received: from localhost ([119.255.41.67])
	by mx.google.com with ESMTPS id nf9sm12852165pbc.17.2012.11.06.18.27.56
	(version=TLSv1/SSLv3 cipher=OTHER);
	Tue, 06 Nov 2012 18:27:57 -0800 (PST)
From: Leo <sdl.web@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <50982835.2050106@HIDDEN>
Date: Wed, 07 Nov 2012 10:27:48 +0800
In-Reply-To: <50982835.2050106@HIDDEN> (Dmitry Gutov's message of "Tue, 06
	Nov 2012 00:57:25 +0400")
Message-ID: <m2y5iep2or.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

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.

> Doing some sort of preprocessing on the candidates list comes to mind
> (search tree?), but I don't immediately see a way of doing that for flex
> matching.

Leo




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 16:49:08 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Tue Nov 06 11:49:08 2012
Received: from localhost ([127.0.0.1]:52714 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVmKp-0007pa-BN
	for submit <at> debbugs.gnu.org; Tue, 06 Nov 2012 11:49:08 -0500
Received: from ispc3.dotserv.com ([178.20.216.13]:47359)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <storm@HIDDEN>) id 1TVmKn-0007pT-No
	for 12796 <at> debbugs.gnu.org; Tue, 06 Nov 2012 11:49:06 -0500
Received: from localhost (localhost [127.0.0.1])
	by ispc3.dotserv.com (Postfix) with ESMTP id C62A38013006B;
	Tue,  6 Nov 2012 17:45:52 +0100 (CET)
X-Virus-Scanned: Debian amavisd-new at ispc3.dotserv.com
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 lDY6tkrrDbnq; Tue,  6 Nov 2012 17:45:49 +0100 (CET)
Received: from [10.1.82.9] (1405ds6-amb.1.fullrate.dk [90.184.79.200])
	(Authenticated sender: storm@HIDDEN)
	by ispc3.dotserv.com (Postfix) with ESMTPSA id 746AE80103D98;
	Tue,  6 Nov 2012 17:45:49 +0100 (CET)
Message-ID: <50993EBC.7000502@HIDDEN>
Date: Tue, 06 Nov 2012 17:45:48 +0100
From: Kim Storm <storm@HIDDEN>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
	<5096A046.6090908@HIDDEN> <509750B0.2030000@HIDDEN>
	<jwvd2zr4ixz.fsf-monnier+bug#12796@HIDDEN>
	<5098EE91.9000906@HIDDEN> <50992F05.5090108@HIDDEN>
In-Reply-To: <50992F05.5090108@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.8 (/)
X-Debbugs-Envelope-To: 12796
Cc: Stefan Monnier <monnier@HIDDEN>, 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.8 (/)

On 2012-11-06 16:38, Dmitry Gutov wrote:
>> 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.
That is what I thought was the primary purpose of your patch.

But I now understand that it was aimed at supplying a shorter list of 
matches to start from "down the list".
That's definitely worth doing!

>> 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.
>
I wouldn't worry that much about memory consumption these days
- if you are really worried, create a ido-cache-max-matches custom variable
with the max length of matches that you want to cache. default nil 
meaning no limit.

So as long as the matches list is shorter than the original list and 
shorter than the max limit,
just cache the list.

> 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.
Right -- if the cache is less than say 25 elements long, I wouldn't 
expect the speedup to be noticable.

> 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.
Yes, for the problem at hand, I think your approach is just fine, so 
with a few tweaks as discussed above,
I support your patch.

Kim




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 15:42:02 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Tue Nov 06 10:42:02 2012
Received: from localhost ([127.0.0.1]:52654 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVlHu-0006M5-Ft
	for submit <at> debbugs.gnu.org; Tue, 06 Nov 2012 10:42:02 -0500
Received: from forward3.mail.yandex.net ([77.88.46.8]:36433)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TVlHq-0006Le-AH
	for 12796 <at> debbugs.gnu.org; Tue, 06 Nov 2012 10:42:01 -0500
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)
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)
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=
Message-ID: <50992F05.5090108@HIDDEN>
Date: Tue, 06 Nov 2012 19:38:45 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Kim Storm <storm@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
	<5096A046.6090908@HIDDEN> <509750B0.2030000@HIDDEN>
	<jwvd2zr4ixz.fsf-monnier+bug#12796@HIDDEN>
	<5098EE91.9000906@HIDDEN>
In-Reply-To: <5098EE91.9000906@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: Stefan Monnier <monnier@HIDDEN>, 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

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?




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 11:07:03 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Tue Nov 06 06:07:03 2012
Received: from localhost ([127.0.0.1]:51573 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVgzm-0007dN-TG
	for submit <at> debbugs.gnu.org; Tue, 06 Nov 2012 06:07:03 -0500
Received: from ispc3.dotserv.com ([178.20.216.13]:49257)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <storm@HIDDEN>) id 1TVgzl-0007cy-1F
	for 12796 <at> debbugs.gnu.org; Tue, 06 Nov 2012 06:07:02 -0500
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
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)
Received: from [10.1.82.9] (1405ds6-amb.1.fullrate.dk [90.184.79.200])
	(Authenticated sender: storm@HIDDEN)
	by ispc3.dotserv.com (Postfix) with ESMTPSA id 1C71780121B23;
	Tue,  6 Nov 2012 12:03:46 +0100 (CET)
Message-ID: <5098EE91.9000906@HIDDEN>
Date: Tue, 06 Nov 2012 12:03:45 +0100
From: Kim Storm <storm@HIDDEN>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Stefan Monnier <monnier@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
	<5096A046.6090908@HIDDEN> <509750B0.2030000@HIDDEN>
	<jwvd2zr4ixz.fsf-monnier+bug#12796@HIDDEN>
In-Reply-To: <jwvd2zr4ixz.fsf-monnier+bug#12796@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.8 (/)
X-Debbugs-Envelope-To: 12796
Cc: 12796 <at> debbugs.gnu.org, Dmitry Gutov <dgutov@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.8 (/)

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





Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 01:48:25 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Mon Nov 05 20:48:24 2012
Received: from localhost ([127.0.0.1]:51353 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVYHA-0003eI-FA
	for submit <at> debbugs.gnu.org; Mon, 05 Nov 2012 20:48:24 -0500
Received: from ironport2-out.teksavvy.com ([206.248.154.182]:3190)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <monnier@HIDDEN>) id 1TVYH9-0003eC-Cz
	for 12796 <at> debbugs.gnu.org; Mon, 05 Nov 2012 20:48:23 -0500
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av0EAG6Zu0/O+LEi/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLNBIUGA0kAYgbBboJkEQDiEKIfoRqiWuDHoFYgwc
X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="205886404"
Received: from 206-248-177-34.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net)
	([206.248.177.34])
	by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA;
	05 Nov 2012 20:45:14 -0500
Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848)
	id C5A30AE203; Mon,  5 Nov 2012 20:45:13 -0500 (EST)
From: Stefan Monnier <monnier@HIDDEN>
To: Kim F. Storm <storm@HIDDEN>, Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Message-ID: <jwvd2zr4ixz.fsf-monnier+bug#12796@HIDDEN>
References: <5096040B.50002@HIDDEN> <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
	<5096A046.6090908@HIDDEN> <509750B0.2030000@HIDDEN>
Date: Mon, 05 Nov 2012 20:45:13 -0500
In-Reply-To: <509750B0.2030000@HIDDEN> (Dmitry Gutov's message of "Mon, 05
	Nov 2012 09:37:52 +0400")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.8 (/)
X-Debbugs-Envelope-To: 12796
Cc: 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.8 (/)

[ 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).

> 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)?


        Stefan




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 5 Nov 2012 21:00:38 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Mon Nov 05 16:00:38 2012
Received: from localhost ([127.0.0.1]:51107 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVTmf-0004hU-SH
	for submit <at> debbugs.gnu.org; Mon, 05 Nov 2012 16:00:38 -0500
Received: from forward5h.mail.yandex.net ([84.201.186.23]:51170)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TVTma-0004h6-M9
	for 12796 <at> debbugs.gnu.org; Mon, 05 Nov 2012 16:00:35 -0500
Received: from smtp2h.mail.yandex.net (smtp2h.mail.yandex.net [84.201.187.145])
	by forward5h.mail.yandex.net (Yandex) with ESMTP id 5BCA8D009AE;
	Tue,  6 Nov 2012 00:57:23 +0400 (MSK)
Received: from smtp2h.mail.yandex.net (localhost [127.0.0.1])
	by smtp2h.mail.yandex.net (Yandex) with ESMTP id 2AA5B17000D4;
	Tue,  6 Nov 2012 00:57:23 +0400 (MSK)
Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87])
	by smtp2h.mail.yandex.net (nwsmtp/Yandex) with ESMTP id
	vMNOwRCt-vMNO4jk1; Tue,  6 Nov 2012 00:57:23 +0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail;
	t=1352149043; bh=UtCWFd5imMXqFNf/DuFVcIwh6xQPFJqJX59s5OTZzi0=;
	h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:
	Content-Type:Content-Transfer-Encoding;
	b=WGs0JhZt3yUh06SNVOvHZ9LLiqztFIYQaSogWRQVtsBZzLSgUict/oJPqMw6z0VFY
	7LWfsJjTbXe8zEyVOszhaK3rR8gsg3KotOIE81yf7SYTuVf3oqUuAH3g6WB+L08F/r
	9iJk5dQkz0wrPmUo6iFU97alkBSRV3oYKBZujLmw=
Message-ID: <50982835.2050106@HIDDEN>
Date: Tue, 06 Nov 2012 00:57:25 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: sdl.web@HIDDEN
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

Leo <sdl.web@HIDDEN> writes:

 > On 2012-11-04 13:58 +0800, Dmitry Gutov wrote:
 >> Any objections?
 >
 > This is special-cased optimisation which doesn't address the root cause
 > of the slowness. We need a better solution.

And the root cause is..?

Doing some sort of preprocessing on the candidates list comes to mind
(search tree?), but I don't immediately see a way of doing that for flex
matching.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 5 Nov 2012 05:41:01 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Mon Nov 05 00:41:01 2012
Received: from localhost ([127.0.0.1]:49603 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TVFQi-0004lU-HM
	for submit <at> debbugs.gnu.org; Mon, 05 Nov 2012 00:41:00 -0500
Received: from forward1h.mail.yandex.net ([84.201.187.146]:52357)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TVFQc-0004lA-M6
	for 12796 <at> debbugs.gnu.org; Mon, 05 Nov 2012 00:40:57 -0500
Received: from smtp4h.mail.yandex.net (smtp4h.mail.yandex.net [84.201.186.21])
	by forward1h.mail.yandex.net (Yandex) with ESMTP id 159DB9E1AA0;
	Mon,  5 Nov 2012 09:37:49 +0400 (MSK)
Received: from smtp4h.mail.yandex.net (localhost [127.0.0.1])
	by smtp4h.mail.yandex.net (Yandex) with ESMTP id D29442C006B;
	Mon,  5 Nov 2012 09:37:48 +0400 (MSK)
Received: from 127-240.nwlink.spb.ru (127-240.nwlink.spb.ru [178.252.127.240])
	by smtp4h.mail.yandex.net (nwsmtp/Yandex) with ESMTP id
	bltuBsgS-bmtiqsfq; Mon,  5 Nov 2012 09:37:48 +0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail;
	t=1352093868; bh=eD01NLAyEycDPxrK/utr5dFH3cl3UQbbolNTj0eS6uo=;
	h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:
	References:In-Reply-To:Content-Type:Content-Transfer-Encoding;
	b=nRQx67RKoYX6jg6ZDIGQe4/rS8Q965tYKoVLztj02aW74LpXb5qpt+wTehomgCn3I
	8kPLXZoc+jKj4PoNhgefJcKScuhEQW5L1bKWGS2V3KdCMPCBS7a9XAI4NPOvCZqA5i
	ad/I0Ju8slwC5SPpEnUgyMDnVBVKc8eI/niHHHxg=
Message-ID: <509750B0.2030000@HIDDEN>
Date: Mon, 05 Nov 2012 09:37:52 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Stefan Monnier <monnier@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
	<5096A046.6090908@HIDDEN>
In-Reply-To: <5096A046.6090908@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

On 04.11.2012 21:05, Dmitry Gutov wrote:
> On 04.11.2012 17:53, Stefan Monnier wrote:
>>> If I decide to type quickly but make a typo in one of the first
>>> characters,
>>> I often need to wait a few seconds until I can fix the typo or start
>>> anew.
>>
>> `while-no-input' (which AFAICT is used by ido) is supposed to interrupt
>> the computation as soon as you type the next input so you don't need
>> to wait.
>>
>> Are you saying that while-no-input doesn't work?
>
> I only see `while-no-input' used in one place there: in
> `ido-make-merged-file-list', and that function is only used in
> `find-file' mode.
>
> So yeah, using it around matching loops in `ido-set-matches-1' might be
> another way to optimize, provided the overhead is not too much.

Disregard the "overhead" remark, I misread what the macro does: it's not 
actually a looping construct.

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.

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 won't insist, though. I kind of decided to disable flex anyway and 
just use regexp matching sometimes.

--Dmitry




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 4 Nov 2012 17:08:18 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Nov 04 12:08:18 2012
Received: from localhost ([127.0.0.1]:49202 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TV3gH-0001Im-PK
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 12:08:18 -0500
Received: from forward20.mail.yandex.net ([95.108.253.145]:57656)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TV3gD-0001Ia-Rq
	for 12796 <at> debbugs.gnu.org; Sun, 04 Nov 2012 12:08:16 -0500
Received: from smtp18.mail.yandex.net (smtp18.mail.yandex.net [95.108.252.18])
	by forward20.mail.yandex.net (Yandex) with ESMTP id 2ECD0104076C;
	Sun,  4 Nov 2012 21:05:10 +0400 (MSK)
Received: from smtp18.mail.yandex.net (localhost [127.0.0.1])
	by smtp18.mail.yandex.net (Yandex) with ESMTP id 09FE818A04CE;
	Sun,  4 Nov 2012 21:05:09 +0400 (MSK)
Received: from 127-240.nwlink.spb.ru (127-240.nwlink.spb.ru [178.252.127.240])
	by smtp18.mail.yandex.net (nwsmtp/Yandex) with ESMTP id
	59jqZctN-59jWHp84; Sun,  4 Nov 2012 21:05:09 +0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail;
	t=1352048709; bh=Dbkz45DHxCJAPt9HXzXdko8s0niL4WuZvx+2X4AomOI=;
	h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:
	References:In-Reply-To:Content-Type:Content-Transfer-Encoding;
	b=CwOLy7cKzVUogzSiqAem0UMdqSMq93LQSZeaoXL9wGvt9WnbAS554bDonF7kOZu0V
	Fw1tzTS0L26oLzDSt63tOAkx86Zt/juEmF3XRvOGc7u2+UUjc/G2ODi1rFnE2NjcNO
	JEtrmPcYMWiVo5bno3Sel4DyPnNPdHOO0LYDOqk4=
Message-ID: <5096A046.6090908@HIDDEN>
Date: Sun, 04 Nov 2012 21:05:10 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: Stefan Monnier <monnier@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
References: <5096040B.50002@HIDDEN> <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
In-Reply-To: <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Debbugs-Envelope-To: 12796
Cc: 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: 0.1 (/)

On 04.11.2012 17:53, Stefan Monnier wrote:
>> If I decide to type quickly but make a typo in one of the first characters,
>> I often need to wait a few seconds until I can fix the typo or start anew.
>
> `while-no-input' (which AFAICT is used by ido) is supposed to interrupt
> the computation as soon as you type the next input so you don't need
> to wait.
>
> Are you saying that while-no-input doesn't work?

I only see `while-no-input' used in one place there: in 
`ido-make-merged-file-list', and that function is only used in 
`find-file' mode.

So yeah, using it around matching loops in `ido-set-matches-1' might be 
another way to optimize, provided the overhead is not too much.




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at 12796 <at> debbugs.gnu.org:


Received: (at 12796) by debbugs.gnu.org; 4 Nov 2012 13:57:06 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Nov 04 08:57:06 2012
Received: from localhost ([127.0.0.1]:48186 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TV0hC-0005II-DE
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 08:57:05 -0500
Received: from pruche.dit.umontreal.ca ([132.204.246.22]:46872)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <monnier@HIDDEN>) id 1TV0hA-0005Ht-Jn
	for 12796 <at> debbugs.gnu.org; Sun, 04 Nov 2012 08:57:01 -0500
Received: from fmsmemgm.homelinux.net (lechon.iro.umontreal.ca
	[132.204.27.242])
	by pruche.dit.umontreal.ca (8.14.1/8.14.1) with ESMTP id qA4Drxe9014283;
	Sun, 4 Nov 2012 08:53:59 -0500
Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848)
	id 0E278AE1F7; Sun,  4 Nov 2012 08:53:58 -0500 (EST)
From: Stefan Monnier <monnier@HIDDEN>
To: Dmitry Gutov <dgutov@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Message-ID: <jwv1ug9tr65.fsf-monnier+emacs@HIDDEN>
References: <5096040B.50002@HIDDEN>
Date: Sun, 04 Nov 2012 08:53:58 -0500
In-Reply-To: <5096040B.50002@HIDDEN> (Dmitry Gutov's message of "Sun, 04
	Nov 2012 09:58:35 +0400")
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-NAI-Spam-Flag: NO
X-NAI-Spam-Threshold: 5
X-NAI-Spam-Score: 0
X-NAI-Spam-Rules: 1 Rules triggered
	RV4392=0
X-NAI-Spam-Version: 2.2.0.9309 : core <4392> : streams <851555> : uri <1259935>
X-Spam-Score: -1.2 (-)
X-Debbugs-Envelope-To: 12796
Cc: 12796 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -2.5 (--)

> If I decide to type quickly but make a typo in one of the first characters,
> I often need to wait a few seconds until I can fix the typo or start anew.

`while-no-input' (which AFAICT is used by ido) is supposed to interrupt
the computation as soon as you type the next input so you don't need
to wait.

Are you saying that while-no-input doesn't work?


        Stefan




Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at submit <at> debbugs.gnu.org:


Received: (at submit) by debbugs.gnu.org; 4 Nov 2012 08:35:44 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Nov 04 03:35:44 2012
Received: from localhost ([127.0.0.1]:48053 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TUvgF-0005hX-Vy
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 03:35:44 -0500
Received: from eggs.gnu.org ([208.118.235.92]:53256)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <geb-bug-gnu-emacs@HIDDEN>) id 1TUvgD-0005hQ-BU
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 03:35:42 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <geb-bug-gnu-emacs@HIDDEN>) id 1TUvdJ-0007Xo-Qy
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 03:32:42 -0500
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org
X-Spam-Level: 
X-Spam-Status: No, score=-5.7 required=5.0 tests=BAYES_00,FREEMAIL_FROM,
	RCVD_IN_DNSWL_HI,RCVD_NUMERIC_HELO autolearn=ham version=3.3.2
Received: from lists.gnu.org ([208.118.235.17]:57298)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <geb-bug-gnu-emacs@HIDDEN>) id 1TUvdJ-0007Xk-NM
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 03:32:41 -0500
Received: from eggs.gnu.org ([208.118.235.92]:53316)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <geb-bug-gnu-emacs@HIDDEN>) id 1TUvdJ-0003VL-0k
	for bug-gnu-emacs@HIDDEN; Sun, 04 Nov 2012 03:32:41 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <geb-bug-gnu-emacs@HIDDEN>) id 1TUvdI-0007XT-6z
	for bug-gnu-emacs@HIDDEN; Sun, 04 Nov 2012 03:32:40 -0500
Received: from plane.gmane.org ([80.91.229.3]:35296)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <geb-bug-gnu-emacs@HIDDEN>) id 1TUvdI-0007XN-0m
	for bug-gnu-emacs@HIDDEN; Sun, 04 Nov 2012 03:32:40 -0500
Received: from list by plane.gmane.org with local (Exim 4.69)
	(envelope-from <geb-bug-gnu-emacs@HIDDEN>) id 1TUvdL-0000oa-OI
	for bug-gnu-emacs@HIDDEN; Sun, 04 Nov 2012 09:32:43 +0100
Received: from 182.48.109.8 ([182.48.109.8])
	by main.gmane.org with esmtp (Gmexim 0.1 (Debian))
	id 1AlnuQ-0007hv-00
	for <bug-gnu-emacs@HIDDEN>; Sun, 04 Nov 2012 09:32:43 +0100
Received: from sdl.web by 182.48.109.8 with local (Gmexim 0.1 (Debian))
	id 1AlnuQ-0007hv-00
	for <bug-gnu-emacs@HIDDEN>; Sun, 04 Nov 2012 09:32:43 +0100
X-Injected-Via-Gmane: http://gmane.org/
To: bug-gnu-emacs@HIDDEN
From: Leo <sdl.web@HIDDEN>
Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with
	flex matching enabled
Date: Sun, 04 Nov 2012 16:32:24 +0800
Lines: 7
Message-ID: <m1wqy1ix9j.fsf@HIDDEN>
References: <5096040B.50002@HIDDEN>
Mime-Version: 1.0
Content-Type: text/plain
X-Complaints-To: usenet@HIDDEN
X-Gmane-NNTP-Posting-Host: 182.48.109.8
Face: iVBORw0KGgoAAAANSUhEUgAAACgAAAAoAgMAAADxkFD+AAAADFBMVEUvT09qWs3/pQD///+J
	kUVcAAAAAWJLR0QAiAUdSAAAAAlwSFlzAAALEwAACxMBAJqcGAAAAAd0SU1FB9cBBwMLOd3veKQA
	AACuSURBVBjTldE9CgIxEAXgB+lEyFUC2wo5ikdZ8DSypxhMY7H9VuIVwlqkGRgnm59VsHGafIQ3
	CZlAtmKIRaHETgYa12lqvEsPYKf8wXHsPGfqPaUM0g9aJPKFXkmNQmSDqwzz4Fpgpz+6WAPY2z5o
	uPJJpu0uypcl4nyCibMLQ8lCiVjayLoQvw5LsVKQuHPRR958HZbOcVsKeepcLxpByjycGvnKmY+c
	MBvrtyjfe0vmuLvdq/kAAAAASUVORK5CYII=
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2)
Cancel-Lock: sha1:EXhd2RbntWWeOl4/xMD4Xx5KgiM=
X-detected-operating-system: by eggs.gnu.org: Genre and OS details not
	recognized.
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x
X-Received-From: 208.118.235.17
X-Spam-Score: -3.0 (---)
X-Debbugs-Envelope-To: submit
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -3.0 (---)

On 2012-11-04 13:58 +0800, Dmitry Gutov wrote:
> Any objections?

This is special-cased optimisation which doesn't address the root cause
of the slowness. We need a better solution.

Leo





Information forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.

Message received at submit <at> debbugs.gnu.org:


Received: (at submit) by debbugs.gnu.org; 4 Nov 2012 06:01:44 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Nov 04 01:01:44 2012
Received: from localhost ([127.0.0.1]:47942 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1TUtHD-0002KM-UH
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 01:01:44 -0500
Received: from eggs.gnu.org ([208.118.235.92]:44511)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <dgutov@HIDDEN>) id 1TUtHA-0002KD-BX
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 01:01:43 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <dgutov@HIDDEN>) id 1TUtEG-0005y9-VW
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 01:58:42 -0400
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org
X-Spam-Level: 
X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM,
	RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=unavailable version=3.3.2
Received: from lists.gnu.org ([208.118.235.17]:42564)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <dgutov@HIDDEN>) id 1TUtEG-0005y5-Rm
	for submit <at> debbugs.gnu.org; Sun, 04 Nov 2012 01:58:40 -0400
Received: from eggs.gnu.org ([208.118.235.92]:60597)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <dgutov@HIDDEN>) id 1TUtEF-0002Lp-DI
	for bug-gnu-emacs@HIDDEN; Sun, 04 Nov 2012 01:58:40 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <dgutov@HIDDEN>) id 1TUtED-0005xm-J0
	for bug-gnu-emacs@HIDDEN; Sun, 04 Nov 2012 01:58:39 -0400
Received: from forward10.mail.yandex.net ([77.88.61.49]:52629)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <dgutov@HIDDEN>) id 1TUtEC-0005xS-NV
	for bug-gnu-emacs@HIDDEN; Sun, 04 Nov 2012 01:58:37 -0400
Received: from smtp8.mail.yandex.net (smtp8.mail.yandex.net [77.88.61.54])
	by forward10.mail.yandex.net (Yandex) with ESMTP id 33AAF1020C6E
	for <bug-gnu-emacs@HIDDEN>; Sun,  4 Nov 2012 09:58:31 +0400 (MSK)
Received: from smtp8.mail.yandex.net (localhost [127.0.0.1])
	by smtp8.mail.yandex.net (Yandex) with ESMTP id 1E7671B60256
	for <bug-gnu-emacs@HIDDEN>; Sun,  4 Nov 2012 09:58:31 +0400 (MSK)
Received: from 127-240.nwlink.spb.ru (127-240.nwlink.spb.ru [178.252.127.240])
	by smtp8.mail.yandex.net (nwsmtp/Yandex) with ESMTP id
	wUla3uFl-wUlmY5xD; Sun,  4 Nov 2012 09:58:30 +0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail;
	t=1352008711; bh=Eg0+6rjvEK7ASpZUmxW5OYLy+BwEucg46opnL+7kxPc=;
	h=Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:
	Content-Type;
	b=TttCAER9h6JBOv5N76QPUc75qNAn3deN5ZcW4C9FliYDiYU9+CiVZ6BMlEQluwX2m
	Kt0tFx7LQme1dgbWBYeLgbuUI/370FJtj1wePdslXRsTgji1IwNXFgTmbmYFXB5Lk/
	+ucNbe6LqW+U1whV/DvrRjXFcTim3DGk2CUIYt0I=
Message-ID: <5096040B.50002@HIDDEN>
Date: Sun, 04 Nov 2012 09:58:35 +0400
From: Dmitry Gutov <dgutov@HIDDEN>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:16.0) Gecko/20121026 Thunderbird/16.0.2
MIME-Version: 1.0
To: bug-gnu-emacs@HIDDEN
Subject: Optimize `ido-completing-read' for larger lists with flex matching
	enabled
Content-Type: multipart/mixed; boundary="------------040105020803080507020409"
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.4.x-2.6.x [generic]
	[fuzzy]
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x
X-Received-From: 208.118.235.17
X-Spam-Score: -3.5 (---)
X-Debbugs-Envelope-To: submit
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -3.5 (---)

This is a multi-part message in MIME format.
--------------040105020803080507020409
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Tags: patch

Currently ido re-filters the full candidates list after every change in 
the minibuffer. With long candidates list and with flex matching enabled 
(like it's often the case with certain third-party packages, namely smex 
and ido-ubiquitous), as soon as ido switches to using flex matching, 
each update takes a noticeable fraction of a second. Even if there's no 
matches anymore for the current input.

If I decide to type quickly but make a typo in one of the first 
characters, I often need to wait a few seconds until I can fix the typo 
or start anew.

This patch adds a simple cache that keeps track of the current matching 
settings (prefix, regexp, or no), and checks the input against a 
previously entered string. If the latter is a prefix of the former (and 
regexp matching is disabled), then we can use the matches from the 
former input as the candidates list for the current one.

Any objections?

--------------040105020803080507020409
Content-Type: text/plain; charset=windows-1251;
 name="ido-speed.diff"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="ido-speed.diff"

=== modified file 'lisp/ChangeLog'
--- lisp/ChangeLog	2012-10-29 15:14:10 +0000
+++ lisp/ChangeLog	2012-11-04 04:55:08 +0000
@@ -1,3 +1,15 @@
+2012-11-04  Dmitry Gutov  <dgutov@HIDDEN>
+
+	* ido.el (ido-cache-prefix, ido-cache-matches, ido-cache-params):
+	New dynamic vars.
+	(ido-read-internal): Reset the above variables' values.
+	(ido-set-matches): Don't reverse the candidates list, leave it to
+	`ido-set-matches-1'.
+	(ido-use-matches-from-cache, ido-check-cache-params)
+	(ido-update-cache): New functions.
+	(ido-set-matches-1): Use the new functions; reverse the matches
+	list at the very end.
+
 2012-10-29  Stefan Monnier  <monnier@HIDDEN>
 
 	* vc/diff-mode.el (diff-context->unified): Don't get confused by "hunk

=== modified file 'lisp/ido.el'
--- lisp/ido.el	2012-10-05 07:38:05 +0000
+++ lisp/ido.el	2012-11-04 05:12:07 +0000
@@ -1143,6 +1143,11 @@
 ;; Dynamically bound in ido-read-internal.
 (defvar ido-completing-read)
 
+;; Matches cache data, only used when `ido-cur-item' is `list'.
+(defvar ido-cache-prefix)
+(defvar ido-cache-matches)
+(defvar ido-cache-params)
+
 ;;; FUNCTIONS
 
 (defun ido-active (&optional merge)
@@ -1852,6 +1857,9 @@
        ido-default-item
        ido-selected
        ido-final-text
+       ido-cache-prefix
+       ido-cache-matches
+       ido-cache-params
        (done nil)
        (icomplete-mode nil) ;; prevent icomplete starting up
        ;; Exported dynamic variables:
@@ -3692,7 +3700,7 @@
 
 ;;; FIND MATCHING ITEMS
 
-(defun ido-set-matches-1 (items &optional do-full)
+(defun ido-set-matches-1 (all-items &optional do-full)
   ;; Return list of matches in items
   (let* ((case-fold-search  ido-case-fold)
 	 (slash (and (not ido-enable-prefix) (ido-final-slash ido-text)))
@@ -3718,7 +3726,10 @@
 			     (not ido-process-ignore-lists)
 			     ido-enable-prefix
 			     (= (length ido-text) 0)))
-	 full-matches suffix-matches prefix-matches matches)
+         (items (if (ido-use-matches-from-cache)
+                    ido-cache-matches
+                  all-items))
+	 full-matches suffix-matches prefix-matches matches used-flex)
     (setq ido-incomplete-regexp nil)
     (condition-case error
         (mapc
@@ -3753,18 +3764,19 @@
     (when prefix-matches
       (ido-trace "prefix match" prefix-matches)
       ;; Bug#2042.
-      (setq matches (nconc prefix-matches matches)))
+      (setq matches (nconc matches prefix-matches)))
     (when suffix-matches
       (ido-trace "suffix match" (list text suffix-re suffix-matches))
-      (setq matches (nconc suffix-matches matches)))
+      (setq matches (nconc matches suffix-matches)))
     (when full-matches
       (ido-trace "full match" (list text full-re full-matches))
-      (setq matches (nconc full-matches matches)))
+      (setq matches (nconc matches full-matches)))
     (when (and (null matches)
 	       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 "") ".*")
+            used-flex t)
       (if ido-enable-prefix
 	  (setq re (concat "\\`" re)))
       (mapc
@@ -3772,16 +3784,51 @@
 	 (let ((name (ido-name item)))
 	   (if (string-match re name)
 	       (setq matches (cons item matches)))))
-       items))
+       (if (ido-check-cache-params t)
+           items
+         all-items)))
+    (setq matches (reverse matches))
+    (ido-update-cache matches used-flex)
     matches))
 
-
 (defun ido-set-matches ()
   ;; Set `ido-matches' to the list of items matching prompt
   (when ido-rescan
-    (setq ido-matches (ido-set-matches-1 (reverse ido-cur-list) (not ido-rotate))
+    (setq ido-matches (ido-set-matches-1 ido-cur-list (not ido-rotate))
 	  ido-rotate nil)))
 
+(defun ido-use-matches-from-cache ()
+  "Return t if `ido-set-matches-1' can use `ido-cache-matches'."
+  (and ido-cache-prefix (eq ido-cur-item 'list)
+       (not ido-enable-regexp)
+       (ido-check-cache-params)
+       (>= (length ido-text) (length ido-cache-prefix))
+       (string= ido-cache-prefix
+                (substring ido-text 0 (length ido-cache-prefix)))))
+
+(defun ido-check-cache-params (&optional flex)
+  "Check `ido-cache-params' against current parameters."
+  (let ((params ido-cache-params))
+    (if (and (or (not (plist-get params 'prefix)) ido-enable-prefix)
+             (or (plist-get params 'flex) (not flex)))
+        t
+      (setq ido-cache-prefix nil
+            ido-cache-matches nil))))
+
+(defun ido-update-cache (matches flex)
+  "Update values of `ido-cache-*' variables."
+  (when (and (or matches
+                 (zerop (length ido-cache-prefix)))
+             (eq ido-cur-item 'list)
+             (not ido-enable-regexp)
+             (<= (* 10 (length matches)) (length ido-cur-list)))
+    (setq ido-cache-prefix ido-text
+          ido-cache-matches matches)
+    (setq ido-cache-params
+          (plist-put (plist-put ido-cache-params
+                                'prefix ido-enable-prefix)
+                     'flex flex))))
+
 (defun ido-ignore-item-p (name re-list &optional ignore-ext)
   ;; Return t if the buffer or file NAME should be ignored.
   (or (member name ido-ignore-item-temp-list)


--------------040105020803080507020409--




Acknowledgement sent to Dmitry Gutov <dgutov@HIDDEN>:
New bug report received and forwarded. Copy sent to bug-gnu-emacs@HIDDEN. Full text available.
Report forwarded to bug-gnu-emacs@HIDDEN:
bug#12796; Package emacs. Full text available.
Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.
Last modified: Fri, 31 Oct 2014 17:00:04 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.