Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!decwrl!decvax!ima!think!barmar From: barmar@think.COM (Barry Margolin) Newsgroups: comp.lang.lisp Subject: Re: pointers in Lisp Message-ID: <36253@think.UUCP> Date: 8 Feb 89 22:27:40 GMT References: <1710@cps3xx.UUCP> <33722@tut.cis.ohio-state.edu> <49734@yale-celray.yale.UUCP> <50041@yale-celray.yale.UUCP> Sender: news@think.UUCP Reply-To: barmar@kulla.think.com.UUCP (Barry Margolin) Organization: Thinking Machines Corporation, Cambridge, MA Lines: 43 In article <50041@yale-celray.yale.UUCP> Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) writes: >You're right, I wasn't. People who have sent me mail have said they >find the breakeven point to be around 5-10 elements, so if your sequence >is longer then you should use an array, otherwise a list may be better. Be careful with such general statements. You didn't say what Lisp implementations, what architectures, etc. I just tried some experiements on my Symbolics 3640 running Genera 7.2, and AREF is faster than NTH except in one insignificant case. My test was: (defun test (index repetitions) (let ((length (1+ index))) (let ((array (make-array length)) (list (make-list length))) (without-interrupts (dotimes (i repetitions) ;; nothing -- to determine loop overhead )) (without-interrupts (dotimes (i repetitions) (aref array index))) (without-interrupts (dotimes (i repetitions) (nth index list)))))) The results were that an AREF takes about 2.5 microseconds, and NTH takes about 13+4N microseconds. I was able to reduce the 13 to 8 by removing the argument checking from NTH, and got it down to 6 by making it compile inline instead of as a function call. But AREF is still faster. The only time I managed to get a list access to be faster was when the first argument to NTH was the constant 0. The compiler special-cases NTH when the first argument is a constant from 0 to 9 and generates the appropriate series of CAR and CDR instructions. In these cases, NTH 0 (i.e. CAR) takes about 1 microsecond, and NTH 1-9 takes about 2.5+.5N microseconds, putting AREF between NTH 0 and NTH 1. Barry Margolin Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar