From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: =?utf-8?Q?=C3=93scar_Fuentes?= Newsgroups: gmane.emacs.devel Subject: Re: fix for bug 10994 breaks ido customizations in major way Date: Sun, 05 May 2013 17:26:08 +0200 Message-ID: <87ip2xsb1r.fsf@wanadoo.es> References: <87ip2zm89w.fsf@wanadoo.es> <87vc6xsnhb.fsf@wanadoo.es> <87r4hlsjnj.fsf@wanadoo.es> <87mws9sg1a.fsf@wanadoo.es> <87y5btjy6v.fsf@uwakimon.sk.tsukuba.ac.jp> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1367767594 9363 80.91.229.3 (5 May 2013 15:26:34 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 5 May 2013 15:26:34 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun May 05 17:26:32 2013 Return-path: Envelope-to: ged-emacs-devel@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 1UZ0pY-0008BB-87 for ged-emacs-devel@m.gmane.org; Sun, 05 May 2013 17:26:28 +0200 Original-Received: from localhost ([::1]:52928 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UZ0pX-0005tT-S2 for ged-emacs-devel@m.gmane.org; Sun, 05 May 2013 11:26:27 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:33925) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UZ0pS-0005rj-Q5 for emacs-devel@gnu.org; Sun, 05 May 2013 11:26:25 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UZ0pR-0006iX-LT for emacs-devel@gnu.org; Sun, 05 May 2013 11:26:22 -0400 Original-Received: from plane.gmane.org ([80.91.229.3]:33840) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UZ0pR-0006iF-FA for emacs-devel@gnu.org; Sun, 05 May 2013 11:26:21 -0400 Original-Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1UZ0pP-00085B-MM for emacs-devel@gnu.org; Sun, 05 May 2013 17:26:19 +0200 Original-Received: from 149.red-83-40-116.dynamicip.rima-tde.net ([83.40.116.149]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 05 May 2013 17:26:19 +0200 Original-Received: from ofv by 149.red-83-40-116.dynamicip.rima-tde.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 05 May 2013 17:26:19 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 47 Original-X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: 149.red-83-40-116.dynamicip.rima-tde.net User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) Cancel-Lock: sha1:+hv4a0ikpCHjmI5hCe0oAcRvYno= X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 80.91.229.3 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:159343 Archived-At: "Stephen J. Turnbull" writes: > Óscar Fuentes writes: > > > So it seems that delete-dups is faster for strings than symbols. > > My interpretation is different: something is broken in the benchmarks > (or in the estimate that the CPUs are of comparable performance). I estimated that the CPUs are of similar performance because Leo reports 2 seconds for 10321 items and here it takes 12.5 seconds for 27000 items. Then items count ratio is 27000/10321 = 2.6, time ratio is 12.5/2 = 6.25 and the expected time ratio given O(n^2) complexity for the same CPU is 2.6^2 = 6.76. However, (let ((choices)) (dotimes (i 10321) (push (make-symbol (format "s%d" i)) choices)) (benchmark-run 10 (delete-dups choices))) takes 6.26 seconds which is quite faster than the 19.9 seconds reported by Leo. Maybe a L2 cache effect (2.4GHz Intel Q6600 with 4 MB L2 cache for each pair of cores.) > Comparing symbols for equality is a pointer comparison. Comparing > strings for equality is a pointer comparison, followed by more work > (some variation on a memcmp) in case of failure. Yep. A similar benchmark with strings instead of symbols: (let ((choices)) (dotimes (i 10321) (push (format "%d" i) choices)) (benchmark-run 10 (delete-dups choices))) takes 15.2 seconds, 1.5 per iteration. Now, why delete-dups takes just 0.7 seconds for a list of strings a bit *larger* than the one used above? The only difference is that those strings follow the pattern directory/filename (it's the output of `git ls-files') However, the real issue being discussed here is if avoiding the overhead of delete-dups on ido-completing-read warrants breaking some extensions on a catastrophic way.