www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - negative lengths and reverse pointers

reply "Ameer Armaly" <ameer_armaly hotmail.com> writes:
Hi all.  After thinking about foreach_reverse and arrays, a rather strange 
idea hit me: what if we had reverse arrays, where whenever you tried to 
access an element it would go backwards instead of forwards in a memmory 
block to find it?  This could be indicated by a negative length; if length 
is negative, the pointer points to the end of the memmory chunk as opposed 
to the beginning.  When you assign a negative length, all the compiler would 
have to do is find the endpoint of the positive version of the length you 
gave it and set the pointer to point to that.  This way array.reverse simply 
= array.length * -1, which would allow you to go through an array backwards 
with much more efficiency.  Kind of random, but might be useful; ideas?

-- 


Ameer
---
Life is either tragedy or comedy. Usually it's your choice. You can whine or 
you can laugh.
--Animorphs 
Oct 19 2006
next sibling parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Ameer Armaly" <ameer_armaly hotmail.com> wrote in message 
news:eh8mkk$728$1 digitaldaemon.com...
 Hi all.  After thinking about foreach_reverse and arrays, a rather strange 
 idea hit me: what if we had reverse arrays, where whenever you tried to 
 access an element it would go backwards instead of forwards in a memmory 
 block to find it?  This could be indicated by a negative length; if length 
 is negative, the pointer points to the end of the memmory chunk as opposed 
 to the beginning.  When you assign a negative length, all the compiler 
 would have to do is find the endpoint of the positive version of the 
 length you gave it and set the pointer to point to that.  This way 
 array.reverse simply = array.length * -1, which would allow you to go 
 through an array backwards with much more efficiency.  Kind of random, but 
 might be useful; ideas?

I really like the idea, though I'm not sure what kind of overhead it'd add to the implementation.. even in release mode, it'd have to figure out whether to index forwards or backwards based on the length of the array. Maybe someone could knock up a simple templated test case to see how it performs?
Oct 19 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Jarrett Billingsley wrote:
 "Ameer Armaly" <ameer_armaly hotmail.com> wrote in message 
 news:eh8mkk$728$1 digitaldaemon.com...
 Hi all.  After thinking about foreach_reverse and arrays, a rather strange 
 idea hit me: what if we had reverse arrays, where whenever you tried to 
 access an element it would go backwards instead of forwards in a memmory 
 block to find it?  This could be indicated by a negative length; if length 
 is negative, the pointer points to the end of the memmory chunk as opposed 
 to the beginning.  When you assign a negative length, all the compiler 
 would have to do is find the endpoint of the positive version of the 
 length you gave it and set the pointer to point to that.  This way 
 array.reverse simply = array.length * -1, which would allow you to go 
 through an array backwards with much more efficiency.  Kind of random, but 
 might be useful; ideas?

I really like the idea, though I'm not sure what kind of overhead it'd add to the implementation.. even in release mode, it'd have to figure out whether to index forwards or backwards based on the length of the array. Maybe someone could knock up a simple templated test case to see how it performs?

It's a cute idea. But I fear it will cause pain outside the context you describe. Take the classic: for(int i=0; i<array.length; i++) { ...array[i]... } Ouch, probably not the behavior I intended if someone passes me a negative length array. So maybe you make length always return a positive number? But then you've still lost pointer equivalence, so array[0] != (&array[0])[0]. Ok, so maybe you make the &-of-array-element operation smarter too, so that it knows that &array[0] should return the address of the last element. But you've still lost equivalence of array[1] and (&array[0])[1] Etc. Seems like you need to follow this through very carefully to find out all the ramifications. In the end I think the loss of interchangeability with a pointer is going to be an issue. --bb
Oct 19 2006
parent "Ameer Armaly" <ameer_armaly hotmail.com> writes:
"Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
news:eh9bdu$rvi$1 digitaldaemon.com...
 Jarrett Billingsley wrote:
 "Ameer Armaly" <ameer_armaly hotmail.com> wrote in message 
 news:eh8mkk$728$1 digitaldaemon.com...
 Hi all.  After thinking about foreach_reverse and arrays, a rather 
 strange idea hit me: what if we had reverse arrays, where whenever you 
 tried to access an element it would go backwards instead of forwards in 
 a memmory block to find it?  This could be indicated by a negative 
 length; if length is negative, the pointer points to the end of the 
 memmory chunk as opposed to the beginning.  When you assign a negative 
 length, all the compiler would have to do is find the endpoint of the 
 positive version of the length you gave it and set the pointer to point 
 to that.  This way array.reverse simply = array.length * -1, which would 
 allow you to go through an array backwards with much more efficiency. 
 Kind of random, but might be useful; ideas?

I really like the idea, though I'm not sure what kind of overhead it'd add to the implementation.. even in release mode, it'd have to figure out whether to index forwards or backwards based on the length of the array. Maybe someone could knock up a simple templated test case to see how it performs?

It's a cute idea. But I fear it will cause pain outside the context you describe. Take the classic: for(int i=0; i<array.length; i++) { ...array[i]... } Ouch, probably not the behavior I intended if someone passes me a negative length array. So maybe you make length always return a positive number? But then you've still lost pointer equivalence, so array[0] != (&array[0])[0]. Ok, so maybe you make the &-of-array-element operation smarter too, so that it knows that &array[0] should return the address of the last element. But you've still lost equivalence of array[1] and (&array[0])[1] Etc. Seems like you need to follow this through very carefully to find out all the ramifications. In the end I think the loss of interchangeability with a pointer is going to be an issue.

want to do what you describe, the .ptr property could become a function, taking an int and returning the address of the relative element. Therefore, array.ptr(x) is the address of element x, be it at the beginning or end of the block. Perhaps array.first could return the absolute first element or somesuch.
Oct 19 2006
prev sibling next sibling parent reply Reiner Pope <reiner.pope REMOVE.THIS.gmail.com> writes:
Ameer Armaly wrote:
 Hi all.  After thinking about foreach_reverse and arrays, a rather strange 
 idea hit me: what if we had reverse arrays, where whenever you tried to 
 access an element it would go backwards instead of forwards in a memmory 
 block to find it?  This could be indicated by a negative length; if length 
 is negative, the pointer points to the end of the memmory chunk as opposed 
 to the beginning.  When you assign a negative length, all the compiler would 
 have to do is find the endpoint of the positive version of the length you 
 gave it and set the pointer to point to that.  This way array.reverse simply 
 = array.length * -1, which would allow you to go through an array backwards 
 with much more efficiency.  Kind of random, but might be useful; ideas?
 

for multidimensional arrays, but it can also be useful for 1-dimensional arrays). This can indeed be a powerful feature, and his proposal milks that power, while syntactically separating strided arrays from normal arrays to avoid the overhead of checking the stride (which is equivalent to checking whether the length is negative in your example). Cheers, Reiner
Oct 20 2006
parent Bill Baxter <wbaxter gmail.com> writes:
Reiner Pope wrote:
 Ameer Armaly wrote:
 
 Hi all.  After thinking about foreach_reverse and arrays, a rather 
 strange idea hit me: what if we had reverse arrays, where whenever you 
 tried to access an element it would go backwards instead of forwards 
 in a memmory block to find it?  This could be indicated by a negative 
 length; if length is negative, the pointer points to the end of the 
 memmory chunk as opposed to the beginning.  When you assign a negative 
 length, all the compiler would have to do is find the endpoint of the 
 positive version of the length you gave it and set the pointer to 
 point to that.  This way array.reverse simply = array.length * -1, 
 which would allow you to go through an array backwards with much more 
 efficiency.  Kind of random, but might be useful; ideas?

for multidimensional arrays, but it can also be useful for 1-dimensional arrays). This can indeed be a powerful feature, and his proposal milks that power, while syntactically separating strided arrays from normal arrays to avoid the overhead of checking the stride (which is equivalent to checking whether the length is negative in your example). Cheers, Reiner

Good point. In fact as I was responding about the -length idea, I was thinking to myself, "I think that's possible with Numpy's strided arrays..." which is where Norbert took most of the ideas for the above proposal. (Or maybe Norbert was one of the creators of Numpy/Numeric?) Anyway, if you want to write a function that deals with the data in a numpy array at the raw memory level, you have two options: 1) get the stride values and use those in all your indexing operations. So if we're talking 1D arrays only, something like: for (i=0; i<array.length; i++) { val_i = *(array.base_ptr + i*array.stride); } 2) or you call a function that 'normalizes' the layout. If the array is in standard order, it's a no-op. Otherwise it returns you a copy of the data in the standard form. base_ptr = normalize(array) // may or may not == array.base_ptr for (i=0; i<array.length; i++) { val_i = base_ptr[i]; } It's very flexible and powerful, especially when you start talking about N-dimensional arrays. But there is a bit of overhead with always having to compute addresses wrt the stride value. --bb
Oct 20 2006
prev sibling parent Larry Evans <cppljevans cos-internet.com> writes:
On 10/19/2006 03:19 PM, Ameer Armaly wrote:
 Hi all.  After thinking about foreach_reverse and arrays, a rather strange 
 idea hit me: what if we had reverse arrays, where whenever you tried to 
 access an element it would go backwards instead of forwards in a memmory 
 block to find it?  This could be indicated by a negative length; if length 

http://web.engr.oregonstate.edu/~budd/Books/aplc/ In that, he had an "expansion vector" which was just the partial product of the array sizes. E.g. if the array sizes were 2,3,4, i.e. like a c array X x[2][3][4], then the expansion vector would be 1,2,6,24 hea also had an offset or something like that and then I think it was called direction, which was 1 when access was in the forward direction, and -1 when it was in the reverse direction. The offset was 0 when in the forward direction and 24(last value of expansion vector above) when in the reverse direction. Then to access the element i0,i1,i2, just multiply each by corresponding element in expanstion vector and multiply by the direction. There was a direction for each dimension and I don't recall the details. I can get the book from the library if you're interested and provide more details.
Oct 21 2006