3 questions about arrays
in [Lisp]
|
From: Kaz Kylheku on 6 Dec 2009 10:03 On 2009-12-06, Pascal J. Bourguignon <pjb(a)informatimago.com> wrote: > Kaz Kylheku <kkylheku(a)gmail.com> writes: > >> On 2009-12-05, Spiros Bousbouras <spibou(a)gmail.com> wrote: >>> 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. >> >> So you propose that if a program asks for an oversized array, bigger >> than array-dimension-limit, and the implementation gives it to the program, >> the implementation is not conforming to the standard? > > No, it would be non conforming on the part of the program. But that's a completely different claim. Of course it's nonconforming on the part of the program. It's also nonconforming to open a socket, create a thread, or request UTF-8 encoding for a stream.
From: Kaz Kylheku on 6 Dec 2009 10:08 On 2009-12-05, Spiros Bousbouras <spibou(a)gmail.com> wrote: > 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. An array of 2**32 elements will also fit comfortably into memory if they are bits. A computer with 32 bit addresses which reference bytes is not capable of addressing every bit of every byte in its address space. Can you name one programming language whose ANSI or ISO standard requires implementations to overcome this issue in their implementation of bit arrays?
From: Barry Margolin on 6 Dec 2009 11:41 In article <20091206070419.887(a)gmail.com>, Kaz Kylheku <kkylheku(a)gmail.com> wrote: > On 2009-12-05, Spiros Bousbouras <spibou(a)gmail.com> wrote: > > 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. > > An array of 2**32 elements will also fit comfortably into memory if they > are bits. > > A computer with 32 bit addresses which reference bytes is not capable > of addressing every bit of every byte in its address space. > > Can you name one programming language whose ANSI or ISO standard > requires implementations to overcome this issue in their implementation > of bit arrays? How many other languages even HAVE bit arrays as a standard language feature? The simple answer to this whole thread is that when we were writing the standard, we created this limit as a lowest common denominator. We didn't want the standard to be dependent on how bit arrays are represented and the number of bits in a byte. We didn't want to force implementations to perform bignum arithmetic when doing array indexing, because this is supposed to be a fast operation -- we wanted Lisp arrays to be as fast as arrays in other languages. Bit arrays already have inherent inefficiency. Few CPUs support bit array indexing natively, so it has to be done by splitting the index into a byte or word index and offset, then shift/mask to get that bit (there might be a machine instruction for this). Requiring the first step to use bignums would make things even worse. As I said in another post, implementations can offer this if they wish. This part of the standard is a restriction on conforming programs, not implementations. If you need something like this in a portable application, write your own API, and use conditional compilation to translate it to native array indexing on implementations that support it, otherwise use an array of arrays. -- 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: Kaz Kylheku on 6 Dec 2009 15:11 On 2009-12-06, Barry Margolin <barmar(a)alum.mit.edu> wrote: > In article <20091206070419.887(a)gmail.com>, > Kaz Kylheku <kkylheku(a)gmail.com> wrote: > >> On 2009-12-05, Spiros Bousbouras <spibou(a)gmail.com> wrote: >> > 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. >> >> An array of 2**32 elements will also fit comfortably into memory if they >> are bits. >> >> A computer with 32 bit addresses which reference bytes is not capable >> of addressing every bit of every byte in its address space. >> >> Can you name one programming language whose ANSI or ISO standard >> requires implementations to overcome this issue in their implementation >> of bit arrays? > > How many other languages even HAVE bit arrays as a standard language > feature? One is C++. :) The std::vector<bool> template can be implemented as a specialization which packs bits. And, guess what, we run into limitations. The size and index values are of std::vector<T>::size_type. Typically, this will be some fixed with like 32 bits. In the libstdc++ implementation, this is typedefed to size_t, which is going to be 32 on 32 bit machines. So you can ``only'' have only 2**32-1 bools in that implementation; 500 megs worth of bits.
From: Tim Bradshaw on 6 Dec 2009 17:48
On 2009-12-05 04:44:33 +0000, Spiros Bousbouras <spibou(a)gmail.com> said: > So the issue of multiplication doesn't even arise with vectors. For > arrays which are not vectors it could be handled with appropriate > declarations. Again , see my reply to Paul Wallich. Yes, it does. Most (all?) modern systems are byte-addressed. So unless your array is not an array of bytes, the implementation will have to multiply or divide, typically by a power of two, to get the reference. |