artzi@cpsvax.cps.msu.edu (Ytshak Artzi - CPS) (02/03/89)
Problem:
I need to implement (in Common Lisp) a structure with pointers. I will
use Pascal jargon to best describe it:
element : record
data : some_type
p1 :pointer_to_element
:
:
pk :pointer_to_element
end;
REM: k is a constant chosen (by me) not bigger than 10.
Catch: the number of pointers 'allocated' to each variable MUST be
random at the beginning of the program. Any suggestions will be
appreciated . I wish to be able to (randomly) create structures
with 3, 5 or 9 pointers for example.
Please don't propose an array of pointers with a flag randomly
chosen between 1 and 10.
Itzik.edward@ucbarpa.Berkeley.EDU (Edward Wang) (02/04/89)
In article <1710@cps3xx.UUCP> artzi@cpsvax.cps.msu.edu (Ytshak Artzi - CPS) writes:
< I need to implement (in Common Lisp) a structure with pointers. I will
<use Pascal jargon to best describe it:
<
< element : record
< data : some_type
< p1 :pointer_to_element
< :
< :
< pk :pointer_to_element
< end;
<
<REM: k is a constant chosen (by me) not bigger than 10.
<
<. . .
< Please don't propose an array of pointers with a flag randomly
< chosen between 1 and 10.
And may we ask why not?
How about not having a size field at all but use array-dimension
when you need to know?welch@tut.cis.ohio-state.edu (Arun Welch) (02/04/89)
In article <1710@cps3xx.UUCP>, artzi@cpsvax.cps.msu.edu (Ytshak Artzi - CPS) writes: > Problem: > > I need to implement (in Common Lisp) a structure with pointers. I will > use Pascal jargon to best describe it: > > element : record > data : some_type > p1 :pointer_to_element > : > : > pk :pointer_to_element > end; > Seeing as how this is lisp, why dont you just use a list? Unless your CL is incredibly inefficient, mapping over a list of 10 elements is gonna be plenty fast, and you'll probably take up less storage than the array. ...arun ---------------------------------------------------------------------------- Arun Welch Lisp Systems Programmer, Lab for AI Research, Ohio State University welch@cis.ohio-state.edu
raymond@ptolemy.arc.nasa.gov (Eric A. Raymond) (02/04/89)
In article <27884@ucbvax.BERKELEY.EDU> edward@ucbarpa.Berkeley.EDU.UUCP (Edward Wang) writes: >In article <1710@cps3xx.UUCP> artzi@cpsvax.cps.msu.edu (Ytshak Artzi - CPS) writes: >< I need to implement (in Common Lisp) a structure with pointers. I will >< Please don't propose an array of pointers with a flag randomly >< chosen between 1 and 10. > >How about not having a size field at all but use array-dimension >when you need to know? What about those things called lists? By the way, the beauty of Lisp is that you don't have to pre-type your variables. For example in (defstruct thing component1 component2 ...) you can setq anything (i.e. atom, list, array, structure) to any of the components. Don't worry about pointers in Lisp. It's not really that important a concept as it is in C or Pascal. The language shields you from the hassle (and in only a few instances does this really get in the way). -- Eric A. Raymond (raymond@pluto.arc.nasa.gov) Nothing left to do but :-) :-) :-)
Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) (02/06/89)
In article <33722@tut.cis.ohio-state.edu>, welch@tut (Arun Welch) writes: >> I need to implement (in Common Lisp) a structure with pointers. I will >> use Pascal jargon to best describe it: >> >> element : record >> data : some_type >> p1 :pointer_to_element >> : >> : >> pk :pointer_to_element >> end; >> > >Seeing as how this is lisp, why dont you just use a list? Unless your CL is >incredibly inefficient, mapping over a list of 10 elements is gonna be plenty >fast, and you'll probably take up less storage than the array. 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.) Bruce Krulwich
weinrich@lightning.rutgers.edu (Timothy M. Weinrich) (02/08/89)
From: Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) Subject: Re: pointers in Lisp Date: 5 Feb 89 18:21:47 GMT 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.) Are you taking into consideration (for example) the bounds-checking that would almost certainly get compiled into every array reference? Twinerik
Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) (02/09/89)
In article <Feb.7.11.41.26.1989.517@lightning.rutgers.edu>, weinrich@lightning (Timothy M. Weinrich) writes: > > 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.) > > Are you taking into consideration (for example) the bounds-checking >that would almost certainly get compiled into every array reference? 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. Bruce
barmar@think.COM (Barry Margolin) (02/09/89)
In article <Feb.7.11.41.26.1989.517@lightning.rutgers.edu> 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
barmar@think.COM (Barry Margolin) (02/09/89)
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
shebs@Apple.COM (Stanley Todd Shebs) (02/10/89)
In article <36238@think.UUCP> barmar@kulla.think.com.UUCP (Barry Margolin) writes: >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. Whoa! Which ones do you know for sure do cdr-coding?? I've not seen any myself, even after an extensive survey of systems, which wasn't surprising because you lose big if you don't have hardware support for forwarding ptrs... stan shebs shebs@apple.com
barmar@think.COM (Barry Margolin) (02/11/89)
In article <624@internal.Apple.COM> shebs@Apple.COM (Stanley Todd Shebs) writes: >In article <36238@think.UUCP> barmar@kulla.think.com.UUCP (Barry Margolin) writes: >>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. >Whoa! Which ones do you know for sure do cdr-coding?? I've not seen any >myself, even after an extensive survey of systems, which wasn't surprising >because you lose big if you don't have hardware support for forwarding ptrs... No, I don't know for sure. I thought I'd heard people from Lucid and/or Franz mention such things at X3J13 meetings, but perhaps I am either mistaken or I misunderstood. Maybe they only use CDR-coding in very restricted cases (if you never REPLACD in a CDR-coded list, you don't need forwarding pointers, so maybe there is a declaration that specifies this). Barry Margolin Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
alex@umbc3.UMBC.EDU (Alex S. Crain) (02/11/89)
Um, what exactly is a CRD-coded list? -- :alex Alex Crain Systems Programmer alex@umbc3.umbc.edu Univ Md Baltimore County nerwin!alex@umbc3.umbc.edu (NEW DOMAIN)
barmar@think.COM (Barry Margolin) (02/13/89)
In article <1648@umbc3.UMBC.EDU> alex@umbc3.umbc.edu.UMBC.EDU (Alex S. Crain) writes: > Um, what exactly is a CRD-coded list? CDR-coding is a technique for reducing the storage taken up by lists. Cons cells, which are the normal building blocks of lists, are more general than is frequently needed; they can be used to build arbitrary trees, but many Lisp data structures are simply linear lists, and don't take advantage of this generality. In CDR coding, each list element is represented using a single CAR pointer plus a two-bit CDR-code field. The CDR-code indicates how to compute the CDR of the list, and has three possible values: CDR-NORMAL, CDR-NEXT, and CDR-NIL. CDR-NORMAL indicates that the word is the CAR of a normal cons cell, so the following word contains a pointer to the cdr. CDR-NEXT means that the following word IS the cdr. And CDR-NIL means that this word was the last list element, and the cdr is implicitly NIL. A list where all the elements are CDR-NEXT (except, of course, for the last, which is CDR-NIL) will take up half as much storage as one that is all CDR-NORMAL. However, CDR-coding in general requires some additional architectural features, most importantly invisible pointers. If you RPLACD a cons that is CDR-NEXT or CDR-NIL there is no cdr cell to store into. Instead, you allocate a new CDR-NORMAL cons, copy the original car to the new one's car, and replace the original car cell with an invisible pointer to the new cons. An invisible pointer is a word that automatically gets dereferenced when you try to read its contents. Invisible pointers require hardware support to prevent an enormous performance hit. Barry Margolin Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
jeff@aiai.ed.ac.uk (Jeff Dalton) (02/17/89)
In article <624@internal.Apple.COM> shebs@Apple.COM (Stanley Todd Shebs) writes: In article <36238@think.UUCP> barmar@kulla.think.com.UUCP (Barry Margolin) writes: 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. Whoa! Which ones do you know for sure do cdr-coding?? I've not seen any myself, even after an extensive survey of systems, which wasn't surprising because you lose big if you don't have hardware support for forwarding ptrs... Eclisp, a Lisp for the Data General Eclipse computers, used internally at Data General, used cdr-coding. It may have exploited a "go inderect" that could be placed in a location (if indeed the Eclipse had such bits). "Conventional processors" can cover quite a variety of machines. Jeff Dalton, JANET: J.Dalton@uk.ac.ed AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton