3 questions about arrays
in [Lisp]
|
From: Spiros Bousbouras on 3 Dec 2009 19:52 On Fri, 04 Dec 2009 01:10:12 +0100 pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: > Spiros Bousbouras <spibou(a)gmail.com> writes: > > > 1. (setq *PRINT-ARRAY* t) > > (make-array 1) > > > > Is this undefined behavior ? > > No, it is implementation dependant, but not undefined. The HS page on make-array says "If initial-element is not supplied, the consequences of later reading an uninitialized element of new-array are undefined unless either initial-contents is supplied or displaced-to is non-nil". In order to print the elements of the array doesn't the implementation need to read them ? If yes then it's undefined behavior. > > 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. On the other hand the maximum size of arrays should be what the operating system can handle even if it means that part of the array would be in swap memory. > Really, the reason is that Common Lisp is not purely a high level > programming language, it is specified in such a way that > implementation can easily be efficient. If you allowed bignums as > index for arrays, each AREF would imply a bignum multiplication, which > would be slow. Multiply what with what ? > Moreover, there would be no point, because in general > the size of arrays slots is one word, and fixnum is all you need to > index all the words you can store in memory. (eg. with a 32-bit > processor, a fixnum of 30-bit is enough to index the whole memory. Is it ? > Why would you want a bigger index?). > > 3. Even if there is good reason that the dimensions of an array be > > fixnums you cannot do (make-array most-positive-fixnum) but the most > > you can do is (make-array (1- most-positive-fixnum)) because the page > > for ARRAY-DIMENSION-LIMIT says that it's a fixnum and "The upper > > exclusive bound on each individual dimension of an array". Why not make > > it an inclusive bound ? > > (0 1 2 3 4) How many elements? 5 , so ? In fact if the point for the limitation in the size of arrays is to never have a bignum as an array subscript then each dimension could be up to (1+ most-positive-fixnum) so the definition of ARRAY-DIMENSION-LIMIT should be different in order to allow for such a possibility. -- Who's your mama ?
From: Paul Wallich on 3 Dec 2009 20:49 Spiros Bousbouras wrote: > On Fri, 04 Dec 2009 01:10:12 +0100 > pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: >> Spiros Bousbouras <spibou(a)gmail.com> writes: >> >>> 1. (setq *PRINT-ARRAY* t) >>> (make-array 1) >>> >>> Is this undefined behavior ? >> No, it is implementation dependant, but not undefined. > > The HS page on make-array says "If initial-element is not supplied, the > consequences of later reading an uninitialized element of new-array are > undefined unless either initial-contents is supplied or displaced-to is > non-nil". In order to print the elements of the array doesn't the > implementation need to read them ? If yes then it's undefined behavior. > >>> 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. On the > other hand the maximum size of arrays should be what the operating > system can handle even if it means that part of the array would be in > swap memory. Nuh-uh. 1) That's already the case in plenty of CL implementations -- unless a lot of people have 60 bits of physical memory they're not telling anyone about. (Even on 32-bit operating systems, a single fixnum-denominated array can already use up at least all of physical memory and quite possibly more, depending on what's in the array.) 2) Now array-size limit depends not on the lisp but on the OS and the disks you have handy and how much someone allocated for /swap and what other programs are running. Good luck with that. Or do you just mean the maximum allocatable file size, in which case array-size limit varies dynamically with the contents of the array? 3) Abandoning the fixnum limit, especially given adjustability, is potentially really bad for performance even for arrays that aren't bigger than that limit; if you want really bad performance, you can roll it yourself. 4) The problem has historically been with array-size-limit rather smaller than the fixnum limit. Speaking of which, does anyone remember the source of a quote that goes something like "There's a problem with arrays larger than memory; in particular, they have to be paged in twice to create them"? paul
From: Ron Garret on 3 Dec 2009 20:57 In article <873a3rlg5u.fsf(a)galatea.local>, pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: > Kaz Kylheku <kkylheku(a)gmail.com> writes: > > > On 2009-12-04, Pascal J. Bourguignon <pjb(a)informatimago.com> wrote: > >>> for ARRAY-DIMENSION-LIMIT says that it's a fixnum and "The upper > >>> exclusive bound on each individual dimension of an array". Why not make > >>> it an inclusive bound ? > >> > >> (0 1 2 3 4) How many elements? > > > > Wrong. The bound is on the dimension, which is the number of elements, not > > on > > the index of the highest element. So if the array-dimension-limit is 5, > > it being exlusive means that you can make an array that has up to 4 > > elements, > > which are addressed from 0 to 3. > > > > Why array-dimension-limit is an exclusive limit is probably for historic > > reasons. > > > > Maybe when Lisp was standardized, implementations did not agree whether or > > not > > this limit is inclusive or exclusive. If implementations don't agree about > > a > > parameter like this, what can you recommend to programmers? Treat it as > > exclusive, of course! That's the weaker, more portable assumption. > > > > Or maybe all of the implementations had the exclusive behavior, which > > would have been codified as-is. > > And again, once you have filled the memory with your array, you need > at least one word to store the only instruction that can make you > program up, so there's no point in going to fixnum+1. And if you find yourself concerned with such issues you are almost certainly doing something wrong. rg
From: Tamas K Papp on 4 Dec 2009 03:57 On Fri, 04 Dec 2009 00:52:28 +0000, Spiros Bousbouras wrote: > On Fri, 04 Dec 2009 01:10:12 +0100 > pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: >> Spiros Bousbouras <spibou(a)gmail.com> writes: >> >> > 1. (setq *PRINT-ARRAY* t) >> > (make-array 1) >> > >> > Is this undefined behavior ? >> >> No, it is implementation dependant, but not undefined. > > The HS page on make-array says "If initial-element is not supplied, the > consequences of later reading an uninitialized element of new-array are > undefined unless either initial-contents is supplied or displaced-to is > non-nil". In order to print the elements of the array doesn't the > implementation need to read them ? If yes then it's undefined behavior. Indeed, and Pascal corrected his reply above. >> > 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. On the other hand > the maximum size of arrays should be what the operating system can > handle even if it means that part of the array would be in swap memory. Fixnums _can_ be made efficient, if the implementation allows that (but it is not obligated to do it). I would guess that the underlying motivation behind making array sizes fixnum is that one can address elements using row-major-aref and fixnum arithmetic, which is indeed a very efficient thing to do in most reasonable implementations. You are approaching this problem from the wrong perspective. There is nothing to prevent fixnums from being very large, and you can use them to address your array, so there is no effective limitation. >> Really, the reason is that Common Lisp is not purely a high level >> programming language, it is specified in such a way that implementation >> can easily be efficient. If you allowed bignums as index for arrays, >> each AREF would imply a bignum multiplication, which would be slow. > > Multiply what with what ? Aref converts indexes to a flat row major index. What is multiplied with what is an exercise left to the reader. > 5 , so ? In fact if the point for the limitation in the size of arrays > is to never have a bignum as an array subscript then each dimension > could be up to (1+ most-positive-fixnum) so the definition of > ARRAY-DIMENSION-LIMIT should be different in order to allow for such a > possibility. Again, that is not the point. The point is that row major indexes are fixnums. See array-row-major-index. I am curious: why are you worried about this? Have you ran into a difficulty where, for example, you find fixnums on 64-bit SBCL limiting? Tamas
From: Pillsy on 4 Dec 2009 10:19
On Dec 4, 3:57 am, Tamas K Papp <tkp...(a)gmail.com> wrote: [...] > I am curious: why are you worried about this? Have you ran into a > difficulty where, for example, you find fixnums on 64-bit SBCL > limiting? The fixnums on some popular implementations (like CLISP on my 32-bit XP machine) have a dramatically smaller range. 17 million element arrays really are too small for many applications. Cheers, Pillsy |