From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Tassilo Horn Newsgroups: gmane.emacs.help Subject: Re: Vector and List Performance Date: Mon, 08 Jun 2009 21:57:29 +0200 Message-ID: <8763f6mrbq.fsf@thinkpad.tsdh.de> References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1244491100 22751 80.91.229.12 (8 Jun 2009 19:58:20 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 8 Jun 2009 19:58:20 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Mon Jun 08 21:58:16 2009 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1MDkz1-0000AN-1s for geh-help-gnu-emacs@m.gmane.org; Mon, 08 Jun 2009 21:58:15 +0200 Original-Received: from localhost ([127.0.0.1]:52901 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MDkz0-00044U-7m for geh-help-gnu-emacs@m.gmane.org; Mon, 08 Jun 2009 15:58:14 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1MDkyb-00044F-Oo for help-gnu-emacs@gnu.org; Mon, 08 Jun 2009 15:57:49 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1MDkyW-0003zb-C0 for help-gnu-emacs@gnu.org; Mon, 08 Jun 2009 15:57:48 -0400 Original-Received: from [199.232.76.173] (port=47910 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MDkyW-0003zY-6c for help-gnu-emacs@gnu.org; Mon, 08 Jun 2009 15:57:44 -0400 Original-Received: from main.gmane.org ([80.91.229.2]:56683 helo=ciao.gmane.org) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1MDkyV-0006x9-Ni for help-gnu-emacs@gnu.org; Mon, 08 Jun 2009 15:57:43 -0400 Original-Received: from list by ciao.gmane.org with local (Exim 4.43) id 1MDkyS-0007cg-Jf for help-gnu-emacs@gnu.org; Mon, 08 Jun 2009 19:57:41 +0000 Original-Received: from p54af1032.dip0.t-ipconnect.de ([84.175.16.50]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 08 Jun 2009 19:57:40 +0000 Original-Received: from tassilo by p54af1032.dip0.t-ipconnect.de with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 08 Jun 2009 19:57:40 +0000 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 41 Original-X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: p54af1032.dip0.t-ipconnect.de User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.94 (gnu/linux) Cancel-Lock: sha1:VoqmyDa/B2NRkj/ml5seM6GFnSI= X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:65052 Archived-At: Nordlöw writes: Hi! > (defun bench (&rest forms) > "Convenience wrapper for benchmark-run-compiled." > (/ (nth 0 (benchmark-run 1024 forms)) 1024)) > > (let ((length 1000000)) > (cons > (bench (aref (make-vector length 0) (/ length 2))) > (bench (nth (/ length 2) (make-list length 0))) > )) > > Strangely I can't seem to find any significant different in > performance when accessing the middle element in a long vector and > long list. Shouldn't the random access performance be the big > difference between vectors and lists? What have I missed? I think that there's some optimization under the hood. Actually, you always access the same place in the list/vector. With real random access, you get the expected result: --8<---------------cut here---------------start------------->8--- (defun bench () (let* ((len 1000000) (vec (make-vector len 0)) (lst (make-list len 0)) (times 50000)) (cons (/ (car (benchmark-run times (aref vec (random len)))) times) (/ (car (benchmark-run times (nth (random len) lst))) times)))) (bench) ==> (1.5999999999999999e-09 . 1.2723999999999999e-06) --8<---------------cut here---------------end--------------->8--- So random access on a vector is about 1000 times faster. Bye, Tassilo