From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Leo Newsgroups: gmane.emacs.bugs Subject: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Date: Wed, 07 Nov 2012 18:38:31 +0800 Message-ID: References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1352284759 18706 80.91.229.3 (7 Nov 2012 10:39:19 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 7 Nov 2012 10:39:19 +0000 (UTC) Cc: 12796@debbugs.gnu.org, Kim Storm To: Dmitry Gutov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Wed Nov 07 11:39:27 2012 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TW32c-0007hK-6j for geb-bug-gnu-emacs@m.gmane.org; Wed, 07 Nov 2012 11:39:26 +0100 Original-Received: from localhost ([::1]:60269 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TW32S-0002mD-MW for geb-bug-gnu-emacs@m.gmane.org; Wed, 07 Nov 2012 05:39:16 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:42246) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TW32L-0002lA-6D for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 05:39:15 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TW32J-0002zk-Me for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 05:39:09 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:43212) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TW32J-0002zg-F2 for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 05:39:07 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1TW32E-0003qc-CM for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 05:39:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Leo Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 07 Nov 2012 10:39:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 12796 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 12796-submit@debbugs.gnu.org id=B12796.135228473014767 (code B ref 12796); Wed, 07 Nov 2012 10:39:02 +0000 Original-Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 10:38:50 +0000 Original-Received: from localhost ([127.0.0.1]:53461 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TW321-0003q5-Ig for submit@debbugs.gnu.org; Wed, 07 Nov 2012 05:38:50 -0500 Original-Received: from mail-da0-f44.google.com ([209.85.210.44]:52392) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TW31z-0003pn-HY for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 05:38:48 -0500 Original-Received: by mail-da0-f44.google.com with SMTP id h15so635732dan.3 for <12796@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== Original-Received: by 10.68.217.201 with SMTP id pa9mr12385902pbc.45.1352284731154; Wed, 07 Nov 2012 02:38:51 -0800 (PST) Original-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) In-Reply-To: <5099DE35.2060402@yandex.ru> (Dmitry Gutov's message of "Wed, 07 Nov 2012 08:06:13 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:66573 Archived-At: 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))