Re: [Toon-members] Efficient (dynamic) slicing

[E. Rosten]

On Wed, 24 Feb 2010, Rafael Spring wrote:

> Hello gentlemen,
>
> I'd like to learn a little bit about efficient dynamic slicing of Vectors and 
> Matrices. Consider a situation where I hold a big Matrix in an object and 
> want to fill that Matrix blockwise giving slices of the Matrix to an external 
> function. Like this:



> void fillSubMatrix(Matrix<>& slice) {
> // write something to the sclice...
> }

The behaviour of a matrix (slice or not) is determined by a template 
parameter. You probably want a function defined more like this:

template<class B>
void fillSubMatrix(Matrix<Dynamic, Dynamic, double, B>& slice)
{
  //Write something to the slice
}

This allows the function to operate efficiently on any kind of matrix. 
Also Matrix<>& cannot be used to represent a slice of a Matrix.

> class MyMainMatrix {
> public:
> MyMainMatrix() : mMatrix(500, 10) {}
>
> void fillMatrix();
>
> private:
> TooN::Matrix<> mMatrix;
> };
>
> void MyMainMatrix::fillMatrix() {
> int inc = 5;    // could be any number or dynamic
>
> for (unsigned int i = 0; i < mMatrix.num_rows(); i += inc) {
>   fillSubMatrix(mMatrix.slice(i, 0, inc, mMatrix.num_cols()));
> }
> }
>
> Following thread 
> http://lists.nongnu.org/archive/html/toon-members/2007-06/msg00003.html there 
> seem to be performance penalties using dynamic slicing.

The problem depends on what you want to do with the slicing. The problem 
with that code is not that the slicing is dynamic, it is that the 
operation creates a dynamically sized temporary Vector, including data. 
This requires a new/delete pair and that is exceptionally slow.

The static sized example is fast because the compiler can allocate the 
temporary space on the stack, and probably optimizes it away anyway.

Temporary slice objects are cheap to create since they involve one pointer 
and 1 to 3 integer allocated on the stack.

> I assume the above 
> code would also result in a temporary object (storage allocated from the 
> heap) being constructed at each call to fillSubMatrix().
> Would the following code be any better?

I'm not sure it would compile. C++ would try to make a Matrix<> out of the 
slice (an allocation ans copy), but that would be a temporary and it won't 
let you take a non-const reference to a temporary.

> void fillSubMatrix(Matrix<-1, -1, double, TooN::Internal::Slice<-1, 1> >& 
> slice) {
> // write something to the sclice
> }

It looks like that would work. I use the template code above to avoid any 
reference to TooN internals, and to have generality across different kinds 
of slice.

-Ed

--
(You can't go wrong with psycho-rats.)(http://mi.eng.cam.ac.uk/~er258)

/d{def}def/f{/Times s selectfont}d/s{11}d/r{roll}d f 2/m{moveto}d -1
r 230 350 m 0 1 179{ 1 index show 88 rotate 4 mul 0 rmoveto}for/s 12
    d f pop 235 420 translate 0 0 moveto 1 2 scale show showpage