Re: 3D versus 2D Indexing and the Speed Thereof

[John W. Eaton]

On 29-Nov-2006, Luis F. Ortiz wrote:

| On Tue, 2006-11-21 at 03:16 -0500, John W. Eaton wrote:
| > OTOH, if Octave's Array class knew how to do slices and if we
| > recognized these operations as slices, then the time should be
| > constant here, not proportional to the number of elements copied.
| 
| So, lets pretend that I added a method to the Array class that looked
| something like this:
| 
|         // Maybe this should be in ArrayRep??
|         template <class T>
|         void
|         Array<T>::strip_gather(Array<T>& source, octave_idx_type
|         dest_offset, octave_idx_type source_offset,
|                            octave_idx_type element_count , 
|                          octave_idx_type strip_count ,
|                          octave_idx_type strip_stride)
|         {
|                 T *raw_source, *raw_dest;
|                 raw_source = & ( source.xelem(source_offset) );
|                 raw_dest = & ( xelem(dest_offset) );
|                 for (octave_idx_type i = 0 ; i < strip_count; ++i)
|                  {
|                     bcopy(raw_source,raw_dest,sizeof(T)*element_count);
|                     raw_source += strip_stride;
|                     raw_dest += element_count;
|                  }
|         }

You need to be careful to preserve the copy-on-write semantics of the
Array class.  The above doesn't appear to do that.

Also, bcopy?  Have we just hit a time warp?

| What this method would do is gather strips consisting of a fixed number
| of elements separated by a fixed stride into a contiguous strip. 
| If we then combined this with some functions which could detect some
| special cases, like the following:
| 
|         // Find a single non-colon equivalent index.
|         // Returns -1 if there is more than one or there are none
|         octave_idx_type
|         nearly_colon_equiv (const Array<idx_vector>& ra_idx,
|                          const dim_vector& frozen_lengths)
|         {
|           octave_idx_type idx_n = ra_idx.length ();
|           int n = frozen_lengths.length ();
|           octave_idx_type not_colon_equiv = -1;
|           assert (idx_n == n);
|           for (octave_idx_type i = 0; i < n; i++)
|             {
|               if ( ! ra_idx(i).is_colon_equiv (frozen_lengths(i)))
|                 {
|                   if ( not_colon_equiv == -1 )
|                     not_colon_equiv = i;
|                   else
|                     return -1;
|                 }
|             }
|           return not_colon_equiv;
|         }
| 
| We could then think about handling a variety of special cases.  Here is
| some pseudo-code for some of the 1D/2D/nD cases that could be done
| faster with these new functions:
| 
| [...7 special cases...]

Is it necessary to have these as special cases, or is there some way
to express this idea so that everything is handled neatly by one
relatively simple function?

BTW, the first thing I would like to do with the code that indexes
Array objects is get rid of the way indices are attached to the Array
object, and simply pass them in as arguments to the functions that
need them.  That would allow us to eliminate the set_index, get_idx,
index_count, and clear_index functions and the idx and idx_count data
members in the Array class.

jwe