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

[Luis F. Ortiz]

On Mon, 2006-11-20 at 19:10 -0500, Luis Ortiz wrote:
>     Folks:
>     
>     One of my engineers reported an odd performance problem in Octave,
>     which I am afraid to tackle without a little bit of guidance.
>     The first snippet of code he gave me to consider was:
>              x=zeros(100,50,100);
>              tic;
>              for i = 1:100
>                  z = x(:,:,i);
>              end
>              toc
>     
>     The second snippet of code he gave me to consider was:
>              x=zeros(5000,100);
>              tic;
>              for i = 1:100
>                  z = x(:,i);
>              end
>              toc
>     
>     Now the 2D form is about 22 times faster than the 3D form, even though
>     the amount of data being slung about is the same.
>     
>     It would seem to me that indexing operations involving :'s on all
>     dimensions except the last, where the index is a scalar, ought
>     to be particularly fast and easy.   Could any of you point me where
>     to look to fix this or tell what where I ought to add code
>     to support a faster way of doing this?
>     
>     I started by profiling a statically linked octave to see where it was
>     spending its time, and decided that it might be wiser for me
>     to ask first before diving deep and drowning.
>     
>     --Luis

Folks:   Since the time that I posted this message, I took the offered advice
and made a couple of small changes that gave me anywhere from
a 10-100X improvement in performance when indexing with all colons
except for one scalar.   We have been successfully using this patch
to Octave 2.9.9 for 2 months now and have noticed no ill effects.

However, there are some things I don't like about my patch, and I would
like to have advice on how to do it right.

1)  One of the methods patched is assign2(). It has the following signature:
>     template <class LT, class RT>
>     int
>     assign2 (Array<LT>& lhs, const Array<RT>& rhs, const LT& rfv)
This seems to me to be an attempt to support type conversions during the assignment.
But the code I wrote only works for the case where RT and LT are the same type.   What
is the right way to handle this?  Can it be done at runtime/compiletime? 
Is this ever instantiated with LT != RT?

2)  The copy_strips method is also useful for handling cases were indexes are all colons except
for a single range.   It would be very nice if there were assignment and indexing methods that could take
ranges as an input, instead of forcing them to be expanded into index vectors.

3) I am now in total agreement with this statement of JWE's:
>     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.
4) I need to find a way to integrate the unit tests I developed for this patch into the standard Octave test suite. 

5) Obviously, I need to see if this applies to 2.9.10 and fix it if it does not.


Anyways, any and all advice is welcome.

/ortiz/luis

13_SliceRef.patch
Description: Text Data

SliceAssign.m
Description: Text Data

SliceBench.m
Description: Text Data

SliceReference.m
Description: Text Data