3 questions about arrays
in [Lisp]
|
From: Barry Margolin on 5 Dec 2009 05:58 In article <RylSm.7782$6p6.5066(a)newsfe05.ams2>, Spiros Bousbouras <spibou(a)gmail.com> wrote: > > Aref converts indexes to a flat row major index. What is multiplied > > with what is an exercise left to the reader. > > So the issue of multiplication doesn't even arise with vectors. The index has to be multiplied by the element size to get the memory address. Lisp references and immediate data types are typicaly a power of 2 in size, so this multiplication can usually be done using shifting, but that probably takes about the same amount of effort in the CPU. -- Barry Margolin, barmar(a)alum.mit.edu Arlington, MA *** PLEASE post questions in newsgroups, not directly to me *** *** PLEASE don't copy me on replies, I'll read them in the group ***
From: vippstar on 5 Dec 2009 06:08 On Dec 4, 1:29 am, Spiros Bousbouras <spi...(a)gmail.com> wrote: > Why the requirement that the dimensions of an array are fixnums ? If you want to allocate a bignum array, why don't you roll your own implementation of bignum-sized arrays that make use of fixnum-sized arrays? Then you'll be able to use all the memory your implementation provides portably.
From: Duane Rettig on 5 Dec 2009 14:51 On Dec 4, 2:04 pm, t...(a)sevak.isi.edu (Thomas A. Russ) wrote: > BTW, just for reference, here is the fixnum sizes for a number of lisps > that I happen to have easy access to. [ ... ] > 29 Allegro CL 5.0, 6.2, 7.0 Wow, these are old! Well, even though the newer 32-bit versions of Allegro CL haven't changed, with 29 bits plus sign bit, most of the architectures also have 64-bit versions, which also have 60 bits plus sign bit for fixnum size. Duane
From: Duane Rettig on 5 Dec 2009 15:03 On Dec 5, 2:58 am, Barry Margolin <bar...(a)alum.mit.edu> wrote: > In article <RylSm.7782$6p6.5...(a)newsfe05.ams2>, > Spiros Bousbouras <spi...(a)gmail.com> wrote: > > > > Aref converts indexes to a flat row major index. What is multiplied > > > with what is an exercise left to the reader. > > > So the issue of multiplication doesn't even arise with vectors. > > The index has to be multiplied by the element size to get the memory > address. Lisp references and immediate data types are typicaly a power > of 2 in size, so this multiplication can usually be done using shifting, > but that probably takes about the same amount of effort in the CPU. However, if the fixnum representation is selected so that the machine- integer represents precisely the number of bytes per natural word, then all arrays with natural-sized elements (e.g. 4 bytes on a 32-bit system and 8 bytes on a 64-bit system) are accessible with machine instructions using the fixnum indices as if they are machine integers, with no shifting needed. This is a strong reason why fixnum representations in most lisps are so similar. It also hints at why going ex-spec and potentially using bignums is such a losing proposition (since access using fixnums is _so_ fast). In fact, on machines which don't have a "shift-left-{2,3}-and-add" instruction (added especially for these array accesses in C) and which have C implementations which don't do strength reduction in array manipulation, these Lisp implementations stand a chance at actually _beating_ C implementations. Duane
From: Spiros Bousbouras on 5 Dec 2009 16:05
On Sat, 05 Dec 2009 05:54:30 -0500 Barry Margolin <barmar(a)alum.mit.edu> wrote: > In article <OylSm.7781$6p6.1940(a)newsfe05.ams2>, > Spiros Bousbouras <spibou(a)gmail.com> wrote: > > > The problem here is that the standard does not allow a Lisp > > implementation to do this on the computer I'm using. > > The standard doesn't prevent Lisp implementations from allowing bignum > array indices. It just doesn't require it, so portable applications > can't depend on it. Each array dimension has to be smaller than ARRAY-DIMENSION-LIMIT and ARRAY-DIMENSION-LIMIT has to be a fixnum therefore array dimensions have to be fixnums. Each array index has to be smaller than the corresponding dimension therefore each array index also has to be a fixnum. (I'm assuming that if a,b are integers and 0 <= a <= b and b is a fixnum then a also has to be a fixnum.) -- Who's your mama ? |