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

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

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

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

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

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

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.