3 questions about arrays
in [Lisp]
|
From: Thomas A. Russ on 8 Dec 2009 19:50 Spiros Bousbouras <spibou(a)gmail.com> writes: > So then the > question becomes why have ARRAY-DIMENSION-LIMIT and > ARRAY-TOTAL-SIZE-LIMIT at all ? Was it for backwards compatibility ? > Actually even before the standard was created , why would an > implementation introduce ARRAY-DIMENSION-LIMIT or > ARRAY-TOTAL-SIZE-LIMIT ? It seems simpler to me not to have these > constants and instead have MAKE-ARRAY and ADJUST-ARRAY return nil if > the requested array was too large. Well, let's assume for the sake of argument that these constants didn't exist and that the specification adopted your suggestion of just returning NIL if the sizes were too big. So, now you write a program and it fails because the array you asked for is too big and MAKE-ARRAY returns NIL. How do you then find out what the limit is? Do you then need to write a loop trying successively bigger values until you happen to locate the implementation limit? It seems far friendlier to mandate that this information is available, and much more useful to have it in a form that can be inspected by a program rather than hidden in the implementation notes in a loose-leaf binder on my bookshelf. Lots of these limits are exposed in Common Lisp (and often not in other languages), allowing programs to do some reasoning or testing before trying operations. It also makes it possible for such programs to provide more useful error messages to their users when limits are exceeded. I wrote a small bit-flags utility that used FIXNUMs to encode small bit vectors for storing binary option information. One of the items when defining a new class of such bit-flags was to make sure that the fixnum range was big enough for the number of flags one wanted to have. This involved checking the size of MOST-POSITIVE-FIXNUM against the number of bits required for the particular set of flags. -- Thomas A. Russ, USC/Information Sciences Institute
From: Tim Bradshaw on 8 Dec 2009 20:13 On 2009-12-08 23:12:51 +0000, Spiros Bousbouras <spibou(a)gmail.com> said: > I'm afraid I don't understand what issue you have in mind. I presume the issue is that the elements of such a bit array can not be addressed by the machine. To run into this problem a language implementation would need (a) to have bit arrays, and (b) to support integer types larger than the machine's (largest) pointer type. Actually, a simpler form of the same question might be: are there languages whose ISO/ANSI standard require that they should support arrays, with any element type, with more elements than the machine's largest pointer type can address?
From: Kaz Kylheku on 8 Dec 2009 20:16 On 2009-12-09, Tim Bradshaw <tfb(a)cley.com> wrote: > On 2009-12-08 23:12:51 +0000, Spiros Bousbouras <spibou(a)gmail.com> said: > >> I'm afraid I don't understand what issue you have in mind. > > I presume the issue is that the elements of such a bit array can not be > addressed by the machine. To run into this problem a language > implementation would need (a) to have bit arrays, and (b) to support > integer types larger than the machine's (largest) pointer type. > > Actually, a simpler form of the same question might be: are there > languages whose ISO/ANSI standard require that they should support > arrays, with any element type, with more elements than the machine's > largest pointer type can address? The answer is: there are, but all of them have gotos that do not return. So the idiot is stuck, not being able to evolve into a developer. :)
From: Spiros Bousbouras on 8 Dec 2009 20:30 On 07 Dec 2009 10:03:32 -0800 tar(a)sevak.isi.edu (Thomas A. Russ) wrote: > Spiros Bousbouras <spibou(a)gmail.com> writes: > > I suppose. But then you still end up with the situation that array > access will be, perhaps, unnecessarily slow. The issue is that you > would need to be prepared to do bignum arithmetic on all array accesses > unless there was specific information to the contrary. Which is the case with all other calculations involving integers. > And since the default in lisp is to not include type declarations, you > would end up with slow array access in the majority of cases. I think > that would be a bad trade-off on the part of the standard. It's the same trade-off functions like + , * , - etc. make. Do you also consider this a bad trade-off ? > > I'm not sure what you mean "not on the lisp". If you do your > > programming in Lisp then array size will obviously depend on the Lisp. > > A good Lisp implementation in turn will make optimal use of what the > > hardware and operating system make available. Actually this is true for > > every programming language ; luck has nothing to do with it. > > Well, I think it would be rather odd to find a programming language > implementation that changed the sizes of things based on the particular > hardware it is running on. No it wouldn't be odd at all , it happens all the time. > I mean, in C you wouldn't expect that "int" > would have its size depend on the amount of RAM installed. No but you would expect malloc() to return NULL or not based on how much memory you asked for and how much memory there is available. > > The problem here is that the standard does not allow a Lisp > > implementation to do this on the computer I'm using. It's a 32 bit > > computer so a fast fixnum should be at most 32 bits. I assume SBCL uses > > 2 bits for internal book-keeping. > > Actually, I believe that it uses 3, since fixnums are 29 bits long. * (- most-positive-fixnum most-negative-fixnum) 1073741823 The range covered is 2**30 so fixnums are 30 bits long. > Well, you as the programmer can always create larger bit vectors if you > really need them. As I've said myself many posts ago. > BTW, why do you need bit vectors with more than 500 million elements? I don't at present. As I've said in a previous post I'm curious i.e. I'm trying to understand why the standard says what it says. The mention of bit vectors was for illustration purposes , you could modify my examples to use something other than bit vectors > > It doesn't contradict my point if there are Lisp implementations , > > possibly many , where a similar conundrum does not arise. If there is > > even one Lisp implementation where the conundrum arises then the > > standard made a poor choice in enforcing the fixnum restriction. > > I think you have this backwards. As long as the standard allows an > implementation that doesn't have the problem, then the defect cannot be > in the standard. It must be in the implementation. When I wrote the quote above I was under the impression that the standard makes it impossible for an implementation to provide arrays with bignum indices. If that impression had been correct then the conundrum would arise by the combination of architecture and standard. But my impression was apparently mistaken so the conundrum does not arise because an implementation can provide arrays with bignum indices as an extension. > > Every time you pass from fixnums to bignums it is "potentially really > > bad for performance". This is something for the programmer to worry > > about. > > Except that the programmer can't really do anything about the internal > implementation of AREF. So it really is the language implementer that > has to worry about such things. And I want my array references to be > fast, thank you very much. Me too , I want my arrays fast and my women big breasted. > > The standard could offer a declaration by which the programmer > > could inform the compiler that the total size of an array will be > > a fixnum. That's how it works with everything else in Lisp : the > > language allows flexibility and if you want to increase performance you > > restrict your flexibility through the appropriate declarations. I don't > > see why array access should be different. > > I suppose. Although that would mean that by default array accesses > would be slow rather than fast. Only if you're a pessimist. If you're an optimist they would be fast as opposed to very fast. > > It's worth considering also that in the case of array access you may > > not even need a declaration at all. When you create the array or adjust > > its size the compiler knows if the (new) size is so large that it needs > > bignums or not. If not then it can automatically arrange for all access > > calculations to use fixnum arithmetic. > > Um, the compiler can only know this if the array dimensions are > compile-time constants. If you dynamically create an array, then the > compiler doesn't have this information. > > For example: > > (defun create-my-new-array (size) > (make-array (list size size) :element-type ...)) > > The compile can't possibly know if size is fixnum or bignum, unless you > put in type declarations.> > > Similarly > > (defun get-element (x y) > (aref *my-array* x y)) > > runs into similar problems. The implementation can internally have 2 aref functions , one for arrays whose size is a fixnum and another for arrays whose size is a bignum. Furthermore the implementation can arrange for the internal storage of arrays to include a pointer to the aref function which is the appropriate one for the specific array. So at the time an array is created it will be examined whether its size is a fixnum or not and its aref pointer will be assigned accordingly. Similarly when an array is adjusted. When the array is referenced then the pointer will be obtained and the appropriate aref function called. So the access time for arrays whose dimensions are only known at runtime requires only 1 additional pointer dereferencing relative to arrays whose dimensions are known at compile time. How much extra time that costs I don't know. Perhaps the optimizations some processors provide are so good as to reduce this extra time to 0. > So just get a > 64-bit lisp and all your problems will be solved. This is all well > within the range of design choices allowed by the standard. My "problems" were the questions I asked in my opening post and they couldn't possibly be answered by changing the Lisp I use. -- I don't understand why there are so many unsolved crimes. It seemed like every time I did something wrong, it was solved overnight. Joe Mammana
From: Spiros Bousbouras on 8 Dec 2009 20:38
On Mon, 7 Dec 2009 20:19:59 +0000 (UTC) Kaz Kylheku <kkylheku(a)gmail.com> wrote: > > Ah, but on x86, the only architecture Spiros knows about, My first computer had a Z80 so there. |