From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: pjb@informatimago.com (Pascal J. Bourguignon) Newsgroups: gmane.emacs.help Subject: Re: Vector and List Performance Date: Wed, 10 Jun 2009 10:24:38 +0200 Organization: Anevia SAS Message-ID: <7c63f45we1.fsf@pbourguignon.anevia.com> References: <7c63f5n48y.fsf@pbourguignon.informatimago.com> <4b62dc88-b861-4f9c-82d6-e175b2247c45@w40g2000yqd.googlegroups.com> <7cd49d6051.fsf@pbourguignon.informatimago.com> <629c22c4-bad6-43cd-9386-ca21713b088b@s16g2000vbp.googlegroups.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1244623353 18372 80.91.229.12 (10 Jun 2009 08:42:33 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 10 Jun 2009 08:42:33 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Wed Jun 10 10:42:31 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 1MEJO7-00043V-Va for geh-help-gnu-emacs@m.gmane.org; Wed, 10 Jun 2009 10:42:28 +0200 Original-Received: from localhost ([127.0.0.1]:44462 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MEJO7-0001jZ-Gm for geh-help-gnu-emacs@m.gmane.org; Wed, 10 Jun 2009 04:42:27 -0400 Original-Path: news.stanford.edu!headwall.stanford.edu!newsfeed.stanford.edu!news.tele.dk!news.tele.dk!small.news.tele.dk!tiscali!newsfeed1.ip.tiscali.net!proxad.net!feeder1-2.proxad.net!cleanfeed1-a.proxad.net!nnrp1-2.free.fr!not-for-mail Original-Newsgroups: gnu.emacs.help Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en X-Disabled: X-No-Archive: no User-Agent: Gnus/5.101 (Gnus v5.10.10) Emacs/22.2 (gnu/linux) Cancel-Lock: sha1:ODEyZTIzMzJhN2VhNTY2NjU1MWZiMDEwMTUyYzIwMWU4MjhiZTQ2Yg== Original-Lines: 45 Original-NNTP-Posting-Date: 10 Jun 2009 10:24:39 MEST Original-NNTP-Posting-Host: 88.170.236.224 Original-X-Trace: 1244622279 news-2.free.fr 14858 88.170.236.224:41591 Original-X-Complaints-To: abuse@proxad.net Original-Xref: news.stanford.edu gnu.emacs.help:169880 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:65110 Archived-At: Nordlöw writes: > On Jun 9, 2:51 pm, p...@informatimago.com (Pascal J. Bourguignon) > wrote: >> Nordlöw writes: >> > Aahh, we needed a macro instead: >> >> > (defmacro bench (&rest forms) >> >     "Convenience wrapper for benchmark-run-compiled." >> >     `(let ((n 10)) >> >        (/ (nth 0 (benchmark-run n ,@forms)) n))) >> >> > This gives a reasonable difference in performance. >> >> > By the way, does elisp lists have extra pointers to the middle of the >> > list (a skip-list)? >> >> No, because it wouldn't be efficient to have to maintain them. >> >> (let* ((c (list 7 8 9)) >>        (b (list* 4 5 6 c)) >>        (a (list* 1 2 3 b))) >>     (push -1 (cddr c))  (push -2 (cddr c))  ; you may have to update a big number of skip-lists! >>     (list a b c)) >> --> >> ((1 2 3 . #1=(4 5 6 . #2=(7 8 -2 -1 9))) #1# #2#) >> >> (deftype list () '(or null (cons t list))) ; nothing more. >> >> -- >> __Pascal Bourguignon__ > > I tested the performance difference and strangely the vector version > of my benchmarking is only faster when the number of elements exceeds > roughy 1000. Why is this? Shouldn' aref() always be faster than nth > regardless of the size of the sequence? How could we say? You don't provide the full source of what you tested. Check my other post in this thread, and see how faster the vector accesses are. Try the same form in your CL implementation, and report the results here. -- __Pascal Bourguignon__