3 questions about arrays
in [Lisp]
|
From: Spiros Bousbouras on 5 Dec 2009 16:09 On Sat, 05 Dec 2009 11:13:19 +0100 pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: > Spiros Bousbouras <spibou(a)gmail.com> writes: > > I'm not sure what the "at a word level" part means but I believe I > > understand your overall gist. So what about those lisp systems which > > can't index their entire address space using their fixnums ? From what > > Pillsy said CLisp probably can't. > > More probably you will implement a bigarray data abstraction using an > array of arrays to store the data. > > Remember that ARRAY-TOTAL-SIZE-LIMIT may be as low as 1024, so if you > want to write a portable program you will have to implement this > bigarray abstraction anyway. The problem is that I may need to implement a bigarray even if I just want a programme to work on a specific 32-bit computer.
From: Pascal J. Bourguignon on 5 Dec 2009 16:20 Spiros Bousbouras <spibou(a)gmail.com> writes: > On Sat, 05 Dec 2009 11:13:19 +0100 > pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: >> Spiros Bousbouras <spibou(a)gmail.com> writes: >> > I'm not sure what the "at a word level" part means but I believe I >> > understand your overall gist. So what about those lisp systems which >> > can't index their entire address space using their fixnums ? From what >> > Pillsy said CLisp probably can't. >> >> More probably you will implement a bigarray data abstraction using an >> array of arrays to store the data. >> >> Remember that ARRAY-TOTAL-SIZE-LIMIT may be as low as 1024, so if you >> want to write a portable program you will have to implement this >> bigarray abstraction anyway. > > The problem is that I may need to implement a bigarray even if I just > want a programme to work on a specific 32-bit computer. Yes. However it's not a big problem: 1- it is easily solutionned in lisp, or 2- you can also easily switch to another implementation where the limit is big enough for you. -- __Pascal Bourguignon__
From: Spiros Bousbouras on 5 Dec 2009 16:27 On Sat, 5 Dec 2009 00:45:45 -0500 Raffael Cavallaro <raffaelcavallaro(a)pas.espam.s.il.vous.plait.mac.com> wrote: > On 2009-12-04 23:44:38 -0500, Spiros Bousbouras <spibou(a)gmail.com> said: > > > On the other hand it makes sense to expect that the maximum > > array size would depend on the actual amount of physical RAM installed > > in a computer so the standard is at fault for creating a connection > > between fixnum size and array size. > > Again, this is an *implementation* issue, not an issue with the > standard. Implementors are responsible for assuring that their fixnums > are large enough to address arrays that are reasonable on the platform. > The standard gives them the flexibility to do that, so any failure to > provide fixnums large enough to address reasonable sized arrays on that > platform is a failure of that specific implementation, not a flaw in > ANSI common lisp. No it's not necessarily a failure of the implementation because an implementation is also responsible for assuring that the fixnums it provides are as fast as possible for the the architecture on which the implementation is running. So for example if an implementation is running on a 32-bit computer then fixnums likely have to ([1]) be at most 32 bits. So there are at most 31 bits to represent positive numbers. This means that you cannot create an array with more than 2**31 elements even if the elements are just bits in which case the array would comfortably fit in memory. [1] When I say "have to" I mean it's a requirement of good design , not that the standard demands it. -- Who's your mama ?
From: Spiros Bousbouras on 5 Dec 2009 16:34 On Sat, 5 Dec 2009 05:42:42 +0000 (UTC) Kaz Kylheku <kkylheku(a)gmail.com> wrote: > On 2009-12-05, Spiros Bousbouras <spibou(a)gmail.com> wrote: > > On 04 Dec 2009 10:01:06 -0800 > > tar(a)sevak.isi.edu (Thomas A. Russ) wrote: > >> Spiros Bousbouras <spibou(a)gmail.com> writes: > >> > >> > > > 2. Why the requirement that the dimensions of an array are fixnums ? > >> > > > >> > > Why not? This is not a big restriction, if an implementation wants > >> > > bigger arrays, it only has to provide bigger fixnums. > >> > > >> > fixnums are supposed to be efficient , that's the criterion for > >> > choosing the size of fixnums not the maximum size of arrays. > >> > >> Yes. And you want to make sure array access is efficient. Thus the > >> limitation on only allowing fixnums as indicies > > > > No , you want to make sure that the programmer has the freedom to > > choose the trade-off which is most appropriate for his application. If > > he is willing to sacrifice some speed in order to gain larger arrays he > > should have that choice. > > The trade off is there. You are perfectly free to ask your Lisp for > an array biger than array-dimension-limit, And I would almost certainly get "no" for an answer :-D > and your implementation > is free to provide it to you. Not if it wants to conform to the standard. > In this case, you merely can't use the ANSI standard as a negotiation > tool. And that's the problem. I'm asking for fast fixnums plus arrays as large as the system can support plus standard conformance. I don't think that's a lot to ask for but I can't get it. -- - Do you speak any English ? - Of course I speak English. - I hope you don't mind if we move our men so that the two of us will have more room to groove.
From: Raffael Cavallaro on 5 Dec 2009 18:09
On 2009-12-05 16:27:22 -0500, Spiros Bousbouras <spibou(a)gmail.com> said: > So for example if an implementation is > running on a 32-bit computer then fixnums likely have to ([1]) be at > most 32 bits. So there are at most 31 bits to represent positive > numbers. This means that you cannot create an array with more than > 2**31 elements even if the elements are just bits in which case the > array would comfortably fit in memory. The purpose of the array data structure is to allow very fast random access to *any* content, not just bits (which seems to be your use case). For this to be possible the standard must mandate that array indices fit in machine words. See Duane's post above for more details. So to say that a 32-bit lisp can only have so many bits for fixnums/array-indices is to speak of an inerent limitation of that platform, not of the ansi spec. If you really want large bit arrays, use a 64-bit lisp with large fixnums/array-dimensions. For example, in Clozure CL64 array-total-size-limit is 72,057,594,037,927,936 which gives you over 9 million gigabytes worth of bit-array. -- Raffael Cavallaro |