Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!pasteur!agate!ucbvax!decwrl!decvax!ima!think!barmar From: barmar@think.COM (Barry Margolin) Newsgroups: comp.lang.lisp Subject: Re: pointers in Lisp Message-ID: <36238@think.UUCP> Date: 8 Feb 89 18:05:32 GMT References: <1710@cps3xx.UUCP> <33722@tut.cis.ohio-state.edu> <49734@yale-celray.yale.UUCP> Sender: news@think.UUCP Reply-To: barmar@kulla.think.com.UUCP (Barry Margolin) Organization: Thinking Machines Corporation, Cambridge, MA Lines: 40 In article weinrich@lightning.rutgers.edu (Timothy M. Weinrich) writes: > From: Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) > A variable-sized array will be both faster and smaller than a > list. (Unless you're using a CDR-coded LISP on a LM, in which > case they're the same.) Note that Lispms aren't the only Lisps with CDR-coding. I believe that a number of Lisps for conventional processors do CDR-coding these days. It's a time/space tradeoff in these cases. While you are correct that an array and a CDR-coded list are about the same size (an array may have an extra word or two of header), accessing an arbitrary element of a CDR-coded list is NOT as fast as accessing an array element. Even with CDR-coding, accessing the Nth element of a list is still O(N), while it is O(1) for an array. Actually, you could make CDR-coded list accesses as fast as arrays if there were a field in each list element that specifies how long the chain of CDR-NEXT elements following it is; if N is less than this then array-style access can be used instead of sequential access. I think this scheme would require too many bits, because it needs to be useful for long lists or it isn't worthwhile (perhaps some low-order bits could be dropped and the result shifted, i.e. the field could specify how many multiples of 32 or 64 CDR-NEXT elements follow). Also, it makes RPLACD of a CDR-NEXT element really slow, because it must go back and update all the predecessors. > Are you taking into consideration (for example) the bounds-checking >that would almost certainly get compiled into every array reference? On Lispms the bounds checking takes no time because it occurs in parallel with the data access. On conventional machines the compiler can usually be told not to generate bounds checking, usually by the use of OPTIMIZE proclamations and declarations. Barry Margolin Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar