From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.bugs Subject: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Date: Thu, 08 Nov 2012 08:29:19 +0400 Message-ID: <509B351F.8040607@yandex.ru> 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; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1352349012 31191 80.91.229.3 (8 Nov 2012 04:30:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 8 Nov 2012 04:30:12 +0000 (UTC) Cc: Leo , 12796@debbugs.gnu.org, Kim Storm To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Thu Nov 08 05:30:21 2012 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TWJky-0003EQ-65 for geb-bug-gnu-emacs@m.gmane.org; Thu, 08 Nov 2012 05:30:20 +0100 Original-Received: from localhost ([::1]:35549 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TWJko-0001n5-NJ for geb-bug-gnu-emacs@m.gmane.org; Wed, 07 Nov 2012 23:30:10 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:49580) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TWJkl-0001lH-U9 for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 23:30:09 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TWJkk-0002yU-1h for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 23:30:07 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:44920) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TWJkj-0002sK-D4 for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 23:30:05 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1TWJkg-0007jv-HI for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 23:30:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Dmitry Gutov Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 08 Nov 2012 04:30: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.135234897429695 (code B ref 12796); Thu, 08 Nov 2012 04:30:02 +0000 Original-Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 04:29:34 +0000 Original-Received: from localhost ([127.0.0.1]:55170 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWJkE-0007it-1p for submit@debbugs.gnu.org; Wed, 07 Nov 2012 23:29:34 -0500 Original-Received: from forward1h.mail.yandex.net ([84.201.187.146]:33019) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWJk9-0007ii-KK for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 23:29:32 -0500 Original-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) Original-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) Original-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= User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 In-Reply-To: X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:66613 Archived-At: 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.