• Ameer Armaly (16/16) Oct 19 2006 Hi all. After thinking about foreach_reverse and arrays, a rather stran...
• Jarrett Billingsley (7/18) Oct 19 2006 I really like the idea, though I'm not sure what kind of overhead it'd a...
• Bill Baxter (18/39) Oct 19 2006 It's a cute idea. But I fear it will cause pain outside the context you...
• Ameer Armaly (8/43) Oct 19 2006 Well, on one hand foreach is designed to avoid most of that, but even if...
• Reiner Pope (9/20) Oct 20 2006 This would be allowed by Norbert Nemec's strided arrays proposal (it's
• Bill Baxter (23/47) Oct 20 2006 Good point. In fact as I was responding about the -length idea, I was
• Larry Evans (19/23) Oct 21 2006 This sounds like something in Timothy Budd's book:

"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 

"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? 

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

"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.

Well, on one hand foreach is designed to avoid most of that, but even if you 
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. 

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?
 

This would be allowed by Norbert Nemec's strided arrays proposal (it's 
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

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?

 This would be allowed by Norbert Nemec's strided arrays proposal (it's 
 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

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 

This sounds like something in Timothy Budd's book:

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.