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 01:54:51 +0400 Message-ID: <509AD8AB.90703@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 1352325309 16615 80.91.229.3 (7 Nov 2012 21:55:09 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 7 Nov 2012 21:55:09 +0000 (UTC) Cc: 12796@debbugs.gnu.org, Kim Storm To: Leo Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Wed Nov 07 22:55:18 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 1TWDag-0005eE-4F for geb-bug-gnu-emacs@m.gmane.org; Wed, 07 Nov 2012 22:55:18 +0100 Original-Received: from localhost ([::1]:46329 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TWDaX-0004Aw-1P for geb-bug-gnu-emacs@m.gmane.org; Wed, 07 Nov 2012 16:55:09 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:53794) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TWDaU-00049Q-9U for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 16:55:07 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TWDaT-0001Tr-2a for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 16:55:06 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:44653) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TWDaS-0001SX-OH for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 16:55:04 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1TWDaQ-0005Kr-Bk for bug-gnu-emacs@gnu.org; Wed, 07 Nov 2012 16:55: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: Wed, 07 Nov 2012 21:55: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.135232529420495 (code B ref 12796); Wed, 07 Nov 2012 21:55:02 +0000 Original-Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 21:54:54 +0000 Original-Received: from localhost ([127.0.0.1]:54904 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWDaH-0005KV-O9 for submit@debbugs.gnu.org; Wed, 07 Nov 2012 16:54:54 -0500 Original-Received: from forward3.mail.yandex.net ([77.88.46.8]:39340) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWDaE-0005KK-36 for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 16:54:52 -0500 Original-Received: from smtp2.mail.yandex.net (smtp2.mail.yandex.net [77.88.46.102]) by forward3.mail.yandex.net (Yandex) with ESMTP id D6329B416BD; Thu, 8 Nov 2012 01:54:49 +0400 (MSK) Original-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) Original-Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp2.mail.yandex.net (nwsmtp/Yandex) with ESMTP id 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= 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:66601 Archived-At: 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