3 questions about arrays
in [Lisp]
|
From: Tamas K Papp on 9 Dec 2009 03:35 On Wed, 09 Dec 2009 02:10:36 +0000, Spiros Bousbouras wrote: > On 08 Dec 2009 16:50:54 -0800 > tar(a)sevak.isi.edu (Thomas A. Russ) wrote: >> 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? > > You would try smaller values rather than bigger but yes you would write > a loop. And you're not interested in the implementation limit , whatever > that is , but on whether you can get an array as big as you need to do > your job , at the time you ask for it and under the memory usage > situation of your programme. Now imagine that you are trying to implement bignum-array, as discussed before. For the sake of argument, suppose that you are doing this by slicing up a larger array to pieces that CL can manage. Then the size of these slices would be deduced from ARRAY-TOTAL-SIZE-LIMIT. HTH, Tamas
From: Tamas K Papp on 9 Dec 2009 03:39 On Tue, 08 Dec 2009 22:38:33 +0000, Spiros Bousbouras wrote: > On 6 Dec 2009 06:23:09 GMT > Tamas K Papp <tkpapp(a)gmail.com> wrote: >> On Sat, 05 Dec 2009 21:34:52 +0000, Spiros Bousbouras wrote: >> >> With the open source Lisps, you can define your own answer. > > Define my own answer ? What does that mean ? That you can just implement your own extensions. If they are good, they will be incorporated to the main branch, otherwise you just fork. >> > 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. >> >> You mean you don't have internet access to download 64 bit SBCL? > > Does the 64 bit SBCL run on a 32 bit computer ? If it does does it > provide the fastest fixnums for the architecture ? Oh, you didn't tell us that you were Robert Maas's cousin. But we figured it out eventually. Cheers, Tamas
From: Pillsy on 9 Dec 2009 12:43 On Dec 4, 11:44 pm, Spiros Bousbouras <spi...(a)gmail.com> wrote: > On 4 Dec 2009 15:54:00 GMT > Tamas K Papp <tkp...(a)gmail.com> wrote: [...] > > Eg if you are > > writing some method which handles array indexes, you can always rely > > on them being fixnums, regardless of the implementation. And then the > > implementation is allowed to say what it considers a fixnum, and if > > you don't like that, just pick another implementation. > What if you want to use a 32-bit computer ? Then you're basically screwed. OK, sure, today you "just" need a billion array elements, but tomorrow you'll need twice or three times as many and the problem will no longer have anything to do with the size of your fixnums. Or, you know, you could get a 64-bit computer. Cheers, Pillsy
From: Thomas A. Russ on 9 Dec 2009 14:36 Spiros Bousbouras <spibou(a)gmail.com> writes: > 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 ? The difference is that +, -, etc. are all user-level functions. That means I, as the programmer, have control over whether the declarations have some effect or not. The computations inside of AREF are not user-level functions, so there isn't anyway to make them efficient. I don't even think it would be really possible, even with some heroic compiler work. That is because it isn't enough to know that the indices for a particular AREF invocation are fixnums, but one has to also know that all of the dimensions of the array (or at least all but one?) are also fixnums. That is really well beyond what one could expect a compiler to be able to do. You are free to come up with your own generic array implementation that solves these problems, however. > > 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. And that happens exactly the same way in lisp as well. Fixnum sizes don't change, but any attempt to allocate memory will either work or fail based on what's available. MAKE-ARRAY is not a primitive allocation function like malloc. > > Well, you as the programmer can always create larger bit vectors if you > > really need them. > > As I've said myself many posts ago. So, what is the problem, then? It shouldn't be the responsibility of a language specification to provide all possible data structures for you. As long as the specfication allows you to create the data structure you want, why do you care? Just build what you need. > > 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. Well, we answered that question a long time ago: Implementation efficiency for array access. > The > mention of bit vectors was for illustration purposes , you could modify > my examples to use something other than bit vectors So this entire argument is really about nothing of any practical import at all? So it's all a large, albeit polite, flamefest? And it really does pretty much only apply to bitvectors. If you use anything other than bit vectors (maybe with the exception of strings), you end up with a situation where FIXNUMs are sufficient, given a reasonable implmentation, to address an array that takes up all available memory -- leaving no room for a program to actually do anything with that array. > > > 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. Even without that there isn't a problem with the standard, since it doesn't prevent you, the programmer, from creating an array implementation with bignum indices. Again, see my sketch of just such an implementation. > > > 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... Except that you also want something else, namely bignum indices, that will make your arrays not fast. It is an engineering tradeoff. You can't have both. Which do you want more? > > > > 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. Ok. So you are requiring a pointer dereference and a function call. With the need for the dereferencing, you eliminate the ability of the compiler to open-code the array access and completely dispense with even the function call. And you would have to do this every time inside a loop. I think you haven't really implemented a compiler or language interpreter, since this suggestion is really rather naive. In fact, a lot of your argumentation indicates that you rarely consider the real world ramifications of your theoretical suggestions. I will treat this thread as closed. -- Thomas A. Russ, USC/Information Sciences Institute
From: Pillsy on 9 Dec 2009 15:18
On Dec 8, 8:30 pm, Spiros Bousbouras <spi...(a)gmail.com> wrote: > On 07 Dec 2009 10:03:32 -0800 > t...(a)sevak.isi.edu (Thomas A. Russ) wrote: [...] > > 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. There are reasons to want to exactly represent 42! without wanting to use 42! as an array index. So there is a different set of trade-offs involved in saying that everything must be a fixnum and saying that array indices must be fixnums. Cheers, Pillsy |