Re: CAT speedup

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: CAT speedup

Petter Risholm
On Mon, 1 Mar 2004, David Bateman wrote:

> Petter,
>
> In the quick reading of this patch, If I've understood it correctly,
> the classes like Matrix, etc now have a ::cat function that can be
> used directly. If this is true then there is nothing to stop me also
> using this function with user types?

Well, define directly :) You can implement ::cat in you own user types,
and instantiate cat_ra with the appropriate data type. But you will also
need the framework for calling ::cat which is in Fcat in data.cc. That is
you could either add to the existing user types which cat works for today,
or you can make your own function like cat_sparse which follows the
pattern defined in Fcat.

We would like to have a way of registering the datatypes that should be
used with cat, so that we don't have to hardcode it for all types in Fcat.
Unfortunately we are not there yet. The same goes for [].

petter

 operator ? Can this or has this been adapted to

> use the new functions? I'd really love is this operator could also be
> used with user types.
>
> Regards
> David
>
>
> According to Petter Risholm <[hidden email]> (on 02/29/04):
> > hi,
> >
> > I've reimplemented the cat function which has resulted in a considerable
> > speedup. As it is now, it should be comparable to matlab's cat function
> > when it comes to speed.
> >
> > The reason for the speedup comes mainly from elimination of all N-d
> > indexing which was the bottleneck in the old version.
> >
> > This patch also provides horzcat and vertcat. They are currently
> > called horzcat2 and vertcat2 since there already are a couple of .m
> > scripts for doing horzcat and vertcat (I'm pretty sure they are quite a
> > bit slower than my version for N-d concatenation, so I would recommend
> > removing those .m files from the distribution).
> >
> > See attachment for patch.
> >
> > ChangeLog:
> >
> > 2004-02-29  Petter Risholm <[hidden email]>
> >
> >         * mx-inlines.cc (MX_ND_CAT): delete macro.
> >         * dNDArray.h, chNDArray.h, CNDArray.h (cat): Change declaration.
> >         * dNDArray.cc (NDArray<T>::cat): Change defintion.
> >         * chNDArray.cc (charNDArray<T>::cat): Ditto.
> >         * CNDArray.cc (ComplexNDArray<T>::cat): Ditto.
> >         * Array.h (cat_ra): Change declaration.
> >         * Array.cc (cat_ra):
> >         Speed up implementation by avoiding N-d indexing.
> >
> > 2004-02-29  Petter Risholm <[hidden email]>
> >
> >         * Cell.h (cat): New function.
> >         * Cell.h (Cell::cat): Provide definition.
> >         * oct-map.h (cat): New function.
> >         * oct-map.cc (Octave_map::cat): Provide definition.
> >         * data.cc (Fcat): Speedup implementation.
> >         * data.cc (Fhorzcat): New function.
> >         * data.cc (Fvertcat): New function.
> >         * Array-tc.cc (INSTANTIATE_CAT): Instantiate cat function.
> >
> > Petter Risholm
> > 2004-02-29  Petter Risholm <[hidden email]>
> >
> > * mx-inlines.cc (MX_ND_CAT): delete macro.
> > * dNDArray.h, chNDArray.h, CNDArray.h (cat): Change declaration.
> > * dNDArray.cc (NDArray<T>::cat): Change defintion.
> > * chNDArray.cc (charNDArray<T>::cat): Ditto.
> > * CNDArray.cc (ComplexNDArray<T>::cat): Ditto.
> > * Array.h (cat_ra): Change declaration.
> > * Array.cc (cat_ra):
> > Speed up implementation by avoiding N-d indexing.
> >
> > 2004-02-29  Petter Risholm <[hidden email]>
> >
> > * Cell.h (cat): New function.
> > * Cell.h (Cell::cat): Provide definition.
> > * oct-map.h (cat): New function.
> > * oct-map.cc (Octave_map::cat): Provide definition.
> > * data.cc (Fcat): Speedup implementation.
> > * data.cc (Fhorzcat): New function.
> > * data.cc (Fvertcat): New function.
> > * Array-tc.cc (INSTANTIATE_CAT): Instantiate cat function.
>
> > Index: TEMPLATE-INST/Array-tc.cc
> > ===================================================================
> > RCS file: /cvs/octave/src/TEMPLATE-INST/Array-tc.cc,v
> > retrieving revision 1.16
> > diff -c -p -r1.16 Array-tc.cc
> > *** TEMPLATE-INST/Array-tc.cc 2003/11/25 05:41:36 1.16
> > --- TEMPLATE-INST/Array-tc.cc 2004/02/29 13:50:49
> > *************** template class Array<octave_value>;
> > *** 51,56 ****
> > --- 51,58 ----
> >
> >   INSTANTIATE_ARRAY_ASSIGN (octave_value, octave_value);
> >
> > + INSTANTIATE_CAT (octave_value);
> > +
> >   template class Array2<octave_value>;
> >
> >   template class ArrayN<octave_value>;
> > Index: Cell.cc
> > ===================================================================
> > RCS file: /cvs/octave/src/Cell.cc,v
> > retrieving revision 1.10
> > diff -c -p -r1.10 Cell.cc
> > *** Cell.cc 2003/11/15 12:51:20 1.10
> > --- Cell.cc 2004/02/29 13:50:49
> > *************** Cell::assign (const octave_value_list& i
> > *** 100,105 ****
> > --- 100,111 ----
> >     return *this;
> >   }
> >
> > + int
> > + Cell::cat (const Cell& ra_arg, int dim, int iidx, int move)
> > + {
> > +   return ::cat_ra (*this, ra_arg, dim, iidx, move);
> > + }
> > +
> >   /*
> >   ;;; Local Variables: ***
> >   ;;; mode: C++ ***
> > Index: Cell.h
> > ===================================================================
> > RCS file: /cvs/octave/src/Cell.h,v
> > retrieving revision 1.17
> > diff -c -p -r1.17 Cell.h
> > *** Cell.h 2004/01/21 19:55:36 1.17
> > --- Cell.h 2004/02/29 13:50:49
> > *************** public:
> > *** 96,101 ****
> > --- 96,103 ----
> >     // XXX FIXME XXX
> >     boolMatrix any (int dim = 0) const { return boolMatrix (); }
> >
> > +   int cat (const Cell& ra_arg, int dim, int iidx, int move);
> > +
> >     // XXX FIXME XXX
> >     bool is_true (void) const { return false; }
> >
> > Index: oct-map.h
> > ===================================================================
> > RCS file: /cvs/octave/src/oct-map.h,v
> > retrieving revision 1.30
> > diff -c -p -r1.30 oct-map.h
> > *** oct-map.h 2004/02/06 05:46:22 1.30
> > --- oct-map.h 2004/02/29 13:50:50
> > *************** Octave_map
> > *** 118,123 ****
> > --- 118,125 ----
> >
> >     int numel (void) const;
> >
> > +   int cat (const Octave_map& ra_arg, int dim, int iidx, int move);
> > +
> >     Octave_map& assign (const octave_value_list& idx, const Octave_map& rhs);
> >
> >     Octave_map& assign (const octave_value_list& idx, const std::string& k,
> > Index: oct-map.cc
> > ===================================================================
> > RCS file: /cvs/octave/src/oct-map.cc,v
> > retrieving revision 1.31
> > diff -c -p -r1.31 oct-map.cc
> > *** oct-map.cc 2004/02/02 18:31:09 1.31
> > --- oct-map.cc 2004/02/29 13:50:50
> > *************** Octave_map::numel (void) const
> > *** 88,93 ****
> > --- 88,100 ----
> >     return retval;
> >   }
> >
> > + int
> > + Octave_map::cat (const Octave_map& ra_arg, int dim, int iidx, int move)
> > + {
> > +   //return ::cat_ra (*this, ra_arg, dim, iidx, move);
> > +   return 0;
> > + }
> > +
> >   static string_vector
> >   equiv_keys (const Octave_map& a, const Octave_map& b)
> >   {
> > Index: data.cc
> > ===================================================================
> > RCS file: /cvs/octave/src/data.cc,v
> > retrieving revision 1.124
> > diff -c -p -r1.124 data.cc
> > *** data.cc 2004/02/16 15:23:22 1.124
> > --- data.cc 2004/02/29 13:50:53
> > *************** Software Foundation, 59 Temple Place - S
> > *** 40,45 ****
> > --- 40,47 ----
> >   #include "variables.h"
> >   #include "oct-obj.h"
> >   #include "utils.h"
> > + #include "Cell.h"
> > + #include "oct-map.h"
> >
> >   #define ANY_ALL(FCN) \
> >    \
> > *************** cat_add_dims (dim_vector& dv_new, const
> > *** 750,821 ****
> >     return true;
> >   }
> >
> > ! DEFUN (cat, args, ,
> > !   "-*- texinfo -*-\n\
> > ! @deftypefn {Built-in Function} {} cat (@var{dim}, @var{array1}, @var{array2}, @dots{}, @var{arrayN})\n\
> > ! Return the concatenation of N-d array objects, @var{array1}, @var{array2}, @dots{}, @var{arrayN} along dimension @var{dim}.\n\
> > ! \n\
> > ! @example\n\
> > ! @group\n\
> > ! A = ones (2, 2);\n\
> > ! B = zeros (2, 2);\n\
> > ! cat (2, A, B)\n\
> > ! @result{} ans =\n\
> > ! \n\
> > !      1 1 0 0\n\
> > !      1 1 0 0\n\
> > !      1 1 0 0\n\
> > !      1 1 0 0\n\
> > ! @end group\n\
> > ! @end example\n\
> > ! \n\
> > ! Alternatively, we can concatenate @var{A} and @var{B} along the\n\
> > ! second dimension the following way:\n\
> > ! \n\
> > ! @example\n\
> > ! @group\n\
> > ! [A, B].\n\
> > ! @end group\n\
> > ! @end example\n\
> > ! \n\
> > ! @var{dim} can be larger than the dimensions of the N-d array objects\n\
> > ! and the result will thus have @var{dim} dimensions as the\n\
> > ! following example shows:\n\
> > ! @example\n\
> > ! @group\n\
> > ! cat (4, ones(2, 2), zeros (2, 2))\n\
> > ! @result{} ans =\n\
> > ! \n\
> > !    ans(:,:,1,1) =\n\
> > ! \n\
> > !      1 1\n\
> > !      1 1\n\
> > ! \n\
> > !    ans(:,:,1,2) =\n\
> > !      0 0\n\
> > !      0 0\n\
> > ! @end group\n\
> > ! @end example\n\
> > ! \n\
> > ! @seealso{horzcat and vertcat}\n\
> > ! @end deftypefn")
> >   {
> >     octave_value retval;
> > !
> >     int dim = args(0).int_value () - 1;
> >
> >     if (error_state)
> >       {
> >         error ("cat: expecting first argument to be a integer");
> >         return retval;
> >       }
> > !
> > !   if (args.length () > 2 && (dim >= 0))
> >       {
> >         dim_vector  dv = args(1).dims ();
> > !
> > !       // I need to look into these conversions.
> > !
> >         for (int i = 2; i < args.length (); i++)
> >   {
> >    // add_dims constructs a dimension vector which holds the
> > --- 752,775 ----
> >     return true;
> >   }
> >
> > ! octave_value do_cat (const octave_value_list& args)
> >   {
> >     octave_value retval;
> > !
> >     int dim = args(0).int_value () - 1;
> >
> > +   int n_args = args.length ();
> > +
> >     if (error_state)
> >       {
> >         error ("cat: expecting first argument to be a integer");
> >         return retval;
> >       }
> > !
> > !   if (n_args > 2 && dim >= 0)
> >       {
> >         dim_vector  dv = args(1).dims ();
> > !
> >         for (int i = 2; i < args.length (); i++)
> >   {
> >    // add_dims constructs a dimension vector which holds the
> > *************** cat (4, ones(2, 2), zeros (2, 2))\n\
> > *** 823,942 ****
> >
> >    if (! cat_add_dims (dv, args(i).dims (), dim))
> >      {
> > !      // Dimensions do not match.
> >        return retval;
> >      }
> >   }
> >
> > !       NDArray cat_re = NDArray (dv, 0);
> >         ComplexNDArray cat_cx;
> >         charNDArray cat_ch;
> >
> >         // The final array can be of three types:
> > -       //
> > -       //     re cx ch
> > -       // --------------
> > -       // re |re cx ch
> > -       // cx |cx cx X
> > -       // ch |ch X  ch
> >         //
> >         // (X means incompatible).
> >
> > !       enum types { REAL, COMPLEX, CHAR } t = REAL;
> >
> > !       // Variable which tells us how much we have extended the
> > !       // variable along the dim dimension.
> > !
> > !       int curr_add_dims = 0;
> > !
> > !       // Tells us wether the array we concatenated had fewer dimensions
> > !       // than dim, such that we only add one dimension to
> > !       // curr_add_dims.
> > !
> > !       bool extended_dims = false;
> > !
> > !       // Start filling in values.
> > !
> > !       for (int i = 1; i < args.length (); i++)
> >   {
> > !  octave_value tmp = args (i);
> > !
> > !  dim_vector dv_arg = tmp.dims ();
> > !
> > !  // This variable tells us wether the the new value is has a
> > !  // number of dimension less than the final value.
> >
> > !  extended_dims = false;
> > !
> > !  if (t == REAL)
> >      {
> > !      if (tmp.is_complex_type ())
> >   {
> > !  cat_cx = ComplexNDArray (cat_re);
> > !
> > !  extended_dims =
> > !    cat_cx.cat (tmp.complex_array_value (), dim, curr_add_dims);
> > !
> > !  t = COMPLEX;
> >   }
> > !      else if (tmp.is_string ())
> >   {
> > !  // This is a hack to be able to convert a dNDArray
> > !  // to a chNDArray.
> >
> > !  cat_ch = charNDArray (octave_value (cat_re).char_array_value ());
> >
> > !  extended_dims =
> > !    cat_ch.cat (tmp.char_array_value (), dim, curr_add_dims);
> >
> > !  t = CHAR;
> >   }
> > !      else
> > ! extended_dims =
> > !  cat_re.cat (tmp.array_value(), dim, curr_add_dims);
> > !    }
> > !  else if (t == COMPLEX)
> > !    {
> > !      extended_dims =
> > ! cat_cx.cat (tmp.complex_array_value (), dim, curr_add_dims);
> > !    }
> > !  else if (t == CHAR)
> > !    {
> > !      if (tmp.is_complex_type ())
> >   {
> > !  error ("cannot convert complex type to character type");
> > !  return retval;
> > ! }
> > !      else
> > ! extended_dims =
> > !  cat_ch.cat (tmp.char_array_value (), dim, curr_add_dims);
> > !    }
> >
> > !  if (error_state)
> > !    {
> > !      // Wrong conversion in the last if statement.
> > !      return retval;
> > !    }
> >
> > !  // Keep track of how many dimensions have been added.
> >
> > !  if (extended_dims)
> > !    curr_add_dims++;
> > !  else
> > !    curr_add_dims += dv_arg (dim);
> >   }
> > !
> >         if (t == REAL)
> >   retval = octave_value (cat_re);
> >         else if (t == COMPLEX)
> >   retval = octave_value (cat_cx);
> >         else if (t == CHAR)
> >   retval = octave_value (cat_ch);
> >       }
> >     else
> >       print_usage ("cat");
> > !
> >     return retval;
> >   }
> >
> >   static octave_value
> > --- 777,1045 ----
> >
> >    if (! cat_add_dims (dv, args(i).dims (), dim))
> >      {
> > !      // Dimensions do not match.
> > !      // cat_add_dims printed a error msg
> >        return retval;
> >      }
> >   }
> >
> > !       NDArray cat_re;
> >         ComplexNDArray cat_cx;
> >         charNDArray cat_ch;
> > +       Cell cat_cell;
> > +       Octave_map cat_map;
> >
> >         // The final array can be of three types:
> >         //
> > +       //       re cx ch c
> > +       // ----------------
> > +       // re   |re cx ch X
> > +       // cx   |cx cx X  X
> > +       // ch   |ch X  ch X
> > +       // cell |X  X  X  c
> >         // (X means incompatible).
> >
> > !       enum types { REAL, COMPLEX, CHAR, CELL, MAP} t;
> >
> > !       // Initialize t to right value
> > !       if (args(1).is_cell ())
> >   {
> > !  t = CELL;
> > !  cat_cell = Cell (dv);
> > ! }
> > !       else if (args(1).is_map ())
> > ! {
> > !  error ("concatenation of structures is not yet implemented");
> > !  return retval;
> > !  // t = MAP;
> > !  // cat_map = Octave_map (dv);
> > ! }
> > !       else
> > ! {
> > !  t = REAL;
> > !  cat_re = NDArray (dv, 0);
> > ! }
> > !
> > !       int idx = 0;
> > !
> > !       dim_vector dv_first = args(1).dims ();
> > !
> > !       // n_moves tells us how many times we need to
> > !       // visit each argument.
> > !       //
> > !       // If we are concatenating a 2x2x2 array with a 2x2x2 array
> > !       // along the second dimensions, we do two iterations
> > !       // trough the arguments and move 2x2 elements from each
> > !       // of the arguments into the resulting array on each iteration.
> > !       int n_moves = 1;
> >
> > !       for (int i = dim + 1; i < dv_first.length (); i++)
> > ! n_moves *= dv_first(i);
> > !
> > !       for (int move = 0; move < n_moves ; move++)
> > ! {
> > !  for (int i = 1; i < n_args; i++)
> >      {
> > !      octave_value tmp = args (i);
> > !
> > !      if (t == MAP)
> >   {
> > !  error ("concatenation of structures is not yet implemented");
> > !  return retval;
> >   }
> > !      else if (t == CELL)
> >   {
> > !  if (! tmp.is_cell ())
> > !    {
> > !      error ("cannot convert argument to cell");
> > !      return retval;
> > !    }
> > !  else
> > !    {
> > ! Cell ra_tmp = args(i).cell_value ();
> > !
> > ! if (error_state)
> > !  return retval;
> >
> > ! idx = cat_cell.cat (ra_tmp, dim, idx, move);
> > !    }
> > ! }
> > !      else if (t == REAL)
> > ! {
> > !  if (tmp.is_complex_type ())
> > !    {
> > !      cat_cx = ComplexNDArray (cat_re);
> >
> > !      ComplexNDArray ra_tmp = tmp.complex_array_value ();
> > !
> > !      if (error_state)
> > ! return retval;
> > !
> > !      idx = cat_cx.cat (ra_tmp, dim, idx, move);
> > !
> > !      t = COMPLEX;
> > !    }
> > !  else if (tmp.is_string ())
> > !    {
> > !      // This is a hack to be able to convert a dNDArray
> > !      // to a chNDArray.
> > !
> > !      cat_ch = charNDArray (octave_value (cat_re).char_array_value ());
> >
> > !      charNDArray ra_tmp = tmp.char_array_value ();
> > !
> > !      if (error_state)
> > ! return retval;
> > !
> > !      idx = cat_ch.cat (ra_tmp, dim, idx, move);
> > !
> > !      t = CHAR;
> > !    }
> > !  else //if (tmp.is_real_type ())
> > !    {
> > !      NDArray ra_tmp = tmp.array_value ();
> > !
> > !      if (error_state)
> > ! return retval;
> > !
> > !      idx = cat_re.cat (ra_tmp, dim, idx, move);
> > !    }
> >   }
> > !      else if (t == COMPLEX)
> >   {
> > !  ComplexNDArray ra_tmp = tmp.complex_array_value ();
> >
> > !  if (error_state)
> > !    return retval;
> >
> > !  idx = cat_cx.cat (ra_tmp, dim, idx, move);
> > ! }
> > !      else if (t == CHAR)
> > ! {
> > !  if (tmp.is_complex_type ())
> > !    {
> > !      error ("cannot convert complex type to character type");
> > !      return retval;
> > !    }
> > !  else
> > !    {
> > !      charNDArray ra_tmp = tmp.char_array_value ();
> > !
> > !      if (error_state)
> > ! return retval;
> >
> > !      cat_ch.cat (ra_tmp, dim, idx, move);
> > !    }
> > ! }
> > !    }
> >   }
> > !
> >         if (t == REAL)
> >   retval = octave_value (cat_re);
> >         else if (t == COMPLEX)
> >   retval = octave_value (cat_cx);
> >         else if (t == CHAR)
> >   retval = octave_value (cat_ch);
> > +       else if (t == CELL)
> > + retval = octave_value (cat_cell);
> > +       else if (t == MAP)
> > + retval = octave_value (cat_map);
> >       }
> >     else
> >       print_usage ("cat");
> > !
> >     return retval;
> > + }
> > +
> > + DEFUN (horzcat2, args, ,
> > +   "-*- texinfo -*-\n\
> > + @deftypefn {Built-in Function} {} horzcat (@var{array1}, @var{array2}, @dots{}, @var{arrayN})\n\
> > + Return the horizontal concatenation of N-d array objects, @var{array1}, @var{array2}, @dots{}, @var{arrayN} along dimension @var{dim}.\n\
> > + \n\
> > + @seealso{cat and vertcat}\n\
> > + @end deftypefn")
> > + {
> > +   octave_value_list args_tmp = args;
> > +
> > +   int dim = 2;
> > +
> > +   octave_value d (dim);
> > +
> > +   args_tmp.prepend (d);
> > +
> > +   return do_cat(args_tmp);
> > + }
> > +
> > + DEFUN (vertcat2, args, ,
> > +   "-*- texinfo -*-\n\
> > + @deftypefn {Built-in Function} {} vertcat (@var{array1}, @var{array2}, @dots{}, @var{arrayN})\n\
> > + Return the vertical concatenation of N-d array objects, @var{array1}, @var{array2}, @dots{}, @var{arrayN} along dimension @var{dim}.\n\
> > + \n\
> > + @seealso{cat and horzcat}\n\
> > + @end deftypefn")
> > + {
> > +   octave_value_list args_tmp = args;
> > +
> > +   int dim = 1;
> > +
> > +   octave_value d (dim);
> > +
> > +   args_tmp.prepend (d);
> > +
> > +   return do_cat(args_tmp);
> > + }
> > +
> > + DEFUN (cat, args, ,
> > +   "-*- texinfo -*-\n\
> > + @deftypefn {Built-in Function} {} cat (@var{dim}, @var{array1}, @var{array2}, @dots{}, @var{arrayN})\n\
> > + Return the concatenation of N-d array objects, @var{array1}, @var{array2}, @dots{}, @var{arrayN} along dimension @var{dim}.\n\
> > + \n\
> > + @example\n\
> > + @group\n\
> > + A = ones (2, 2);\n\
> > + B = zeros (2, 2);\n\
> > + cat (2, A, B)\n\
> > + @result{} ans =\n\
> > + \n\
> > +      1 1 0 0\n\
> > +      1 1 0 0\n\
> > +      1 1 0 0\n\
> > +      1 1 0 0\n\
> > + @end group\n\
> > + @end example\n\
> > + \n\
> > + Alternatively, we can concatenate @var{A} and @var{B} along the\n\
> > + second dimension the following way:\n\
> > + \n\
> > + @example\n\
> > + @group\n\
> > + [A, B].\n\
> > + @end group\n\
> > + @end example\n\
> > + \n\
> > + @var{dim} can be larger than the dimensions of the N-d array objects\n\
> > + and the result will thus have @var{dim} dimensions as the\n\
> > + following example shows:\n\
> > + @example\n\
> > + @group\n\
> > + cat (4, ones(2, 2), zeros (2, 2))\n\
> > + @result{} ans =\n\
> > + \n\
> > +    ans(:,:,1,1) =\n\
> > + \n\
> > +      1 1\n\
> > +      1 1\n\
> > + \n\
> > +    ans(:,:,1,2) =\n\
> > +      0 0\n\
> > +      0 0\n\
> > + @end group\n\
> > + @end example\n\
> > + \n\
> > + @seealso{horzcat and vertcat}\n\
> > + @end deftypefn")
> > + {
> > +   return do_cat(args);
> >   }
> >
> >   static octave_value
>
> > Index: mx-inlines.cc
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/mx-inlines.cc,v
> > retrieving revision 1.31
> > diff -c -p -r1.31 mx-inlines.cc
> > *** mx-inlines.cc 2004/02/16 05:07:23 1.31
> > --- mx-inlines.cc 2004/02/29 13:39:46
> > *************** OP_DUP_FCN (conj, mx_inline_conj_dup, Co
> > *** 607,640 ****
> >   \
> >     return retval
> >
> > - #define MX_ND_CAT \
> > -  bool retval = false;\
> > -  \
> > -   dim_vector dv = ra_arg.dims (); \
> > -  \
> > -    Array<int> ra_idx (dv.length (), 0); \
> > -  \
> > -    for (int i = 0; i < ra_arg.length (); i++) \
> > -      { \
> > -        if (i != 0) \
> > - increment_index (ra_idx, dv, 0); \
> > -  \
> > -        Array<int> ra_idx2 = ra_idx; \
> > -  \
> > -        if (dim >= ra_idx2.length ()) \
> > - { \
> > -   ra_idx2.resize_and_fill (dim + 1, 0); \
> > -  \
> > -   retval = true; \
> > - } \
> > -  \
> > -        ra_idx2.elem (dim) = ra_idx2.elem (dim) + add_dim; \
> > -  \
> > -        elem (ra_idx2) =  ra_arg.elem (ra_idx); \
> > -      } \
> > -  \
> > -    return retval
> > -
> >   #endif
> >
> >   /*
> > --- 607,612 ----
> > Index: dNDArray.cc
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/dNDArray.cc,v
> > retrieving revision 1.16
> > diff -c -p -r1.16 dNDArray.cc
> > *** dNDArray.cc 2004/02/17 15:32:13 1.16
> > --- dNDArray.cc 2004/02/29 13:39:47
> > *************** NDArray::sum (int dim) const
> > *** 656,666 ****
> >     MX_ND_REAL_OP_REDUCTION (+= elem (iter_idx), 0);
> >   }
> >
> > ! bool
> > ! NDArray::cat (const NDArray& ra_arg, int dim, int add_dim)
> >   {
> > !   //  MX_ND_CAT;
> > !   return ::cat_ra (*this, ra_arg, dim, add_dim);
> >   }
> >
> >   NDArray
> > --- 656,665 ----
> >     MX_ND_REAL_OP_REDUCTION (+= elem (iter_idx), 0);
> >   }
> >
> > ! int
> > ! NDArray::cat (const NDArray& ra_arg, int dim, int iidx, int move)
> >   {
> > !   return ::cat_ra (*this, ra_arg, dim, iidx, move);
> >   }
> >
> >   NDArray
> > Index: dNDArray.h
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/dNDArray.h,v
> > retrieving revision 1.13
> > diff -c -p -r1.13 dNDArray.h
> > *** dNDArray.h 2004/02/16 19:02:32 1.13
> > --- dNDArray.h 2004/02/29 13:39:47
> > *************** public:
> > *** 86,92 ****
> >     NDArray prod (int dim = -1) const;
> >     NDArray sum (int dim = -1) const;
> >     NDArray sumsq (int dim = -1) const;
> > !   bool cat (const NDArray& ra_arg, int dim, int add_dim);
> >
> >     NDArray abs (void) const;
> >
> > --- 86,92 ----
> >     NDArray prod (int dim = -1) const;
> >     NDArray sum (int dim = -1) const;
> >     NDArray sumsq (int dim = -1) const;
> > !   int cat (const NDArray& ra_arg, int dim, int iidx, int move);
> >
> >     NDArray abs (void) const;
> >
> > Index: chNDArray.h
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/chNDArray.h,v
> > retrieving revision 1.6
> > diff -c -p -r1.6 chNDArray.h
> > *** chNDArray.h 2004/02/16 05:07:23 1.6
> > --- chNDArray.h 2004/02/29 13:39:47
> > *************** public:
> > *** 71,77 ****
> >
> >     boolNDArray all (int dim = -1) const;
> >     boolNDArray any (int dim = -1) const;
> > !   bool cat (const charNDArray& ra_arg, int dim, int add_dim);
> >
> >     charMatrix matrix_value (void) const;
> >
> > --- 71,77 ----
> >
> >     boolNDArray all (int dim = -1) const;
> >     boolNDArray any (int dim = -1) const;
> > !   int cat (const charNDArray& ra_arg, int dim, int iidx, int move);
> >
> >     charMatrix matrix_value (void) const;
> >
> > Index: chNDArray.cc
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/chNDArray.cc,v
> > retrieving revision 1.9
> > diff -c -p -r1.9 chNDArray.cc
> > *** chNDArray.cc 2004/02/16 16:22:43 1.9
> > --- chNDArray.cc 2004/02/29 13:39:48
> > *************** charNDArray::any (int dim) const
> > *** 48,57 ****
> >     MX_ND_ANY_ALL_REDUCTION (MX_ND_ANY_EVAL (elem (iter_idx) != ' '), false);
> >   }
> >
> > ! bool
> > ! charNDArray::cat (const charNDArray& ra_arg, int dim, int add_dim)
> >   {
> > !   MX_ND_CAT;
> >   }
> >
> >   charMatrix
> > --- 48,57 ----
> >     MX_ND_ANY_ALL_REDUCTION (MX_ND_ANY_EVAL (elem (iter_idx) != ' '), false);
> >   }
> >
> > ! int
> > ! charNDArray::cat (const charNDArray& ra_arg, int dim, int iidx, int move)
> >   {
> > !   return ::cat_ra(*this, ra_arg, dim, iidx, move);
> >   }
> >
> >   charMatrix
> > Index: CNDArray.cc
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/CNDArray.cc,v
> > retrieving revision 1.16
> > diff -c -p -r1.16 CNDArray.cc
> > *** CNDArray.cc 2004/02/17 15:32:13 1.16
> > --- CNDArray.cc 2004/02/29 13:39:49
> > *************** ComplexNDArray::sum (int dim) const
> > *** 677,686 ****
> >     MX_ND_COMPLEX_OP_REDUCTION (+= elem (iter_idx), Complex (0, 0));
> >   }
> >
> > ! bool
> > ! ComplexNDArray::cat (const ComplexNDArray& ra_arg, int dim, int add_dim)
> >   {
> > !   MX_ND_CAT;
> >   }
> >
> >   NDArray
> > --- 677,686 ----
> >     MX_ND_COMPLEX_OP_REDUCTION (+= elem (iter_idx), Complex (0, 0));
> >   }
> >
> > ! int
> > ! ComplexNDArray::cat (const ComplexNDArray& ra_arg, int dim, int iidx, int move)
> >   {
> > !   return ::cat_ra(*this, ra_arg, dim, iidx, move);
> >   }
> >
> >   NDArray
> > Index: CNDArray.h
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/CNDArray.h,v
> > retrieving revision 1.13
> > diff -c -p -r1.13 CNDArray.h
> > *** CNDArray.h 2004/02/16 19:02:32 1.13
> > --- CNDArray.h 2004/02/29 13:39:49
> > *************** public:
> > *** 87,93 ****
> >     ComplexNDArray prod (int dim = -1) const;
> >     ComplexNDArray sum (int dim = -1) const;
> >     ComplexNDArray sumsq (int dim = -1) const;
> > !   bool cat (const ComplexNDArray& ra_arg, int dim, int add_dim);
> >
> >     ComplexNDArray& insert (const NDArray& a, int r, int c);
> >     ComplexNDArray& insert (const ComplexNDArray& a, int r, int c);
> > --- 87,93 ----
> >     ComplexNDArray prod (int dim = -1) const;
> >     ComplexNDArray sum (int dim = -1) const;
> >     ComplexNDArray sumsq (int dim = -1) const;
> > !   int cat (const ComplexNDArray& ra_arg, int dim, int iidx, int move);
> >
> >     ComplexNDArray& insert (const NDArray& a, int r, int c);
> >     ComplexNDArray& insert (const ComplexNDArray& a, int r, int c);
> > Index: Array.h
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/Array.h,v
> > retrieving revision 1.85
> > diff -c -p -r1.85 Array.h
> > *** Array.h 2004/02/18 12:52:20 1.85
> > --- Array.h 2004/02/29 13:39:50
> > *************** public:
> > *** 526,533 ****
> >   // do that because of bugs in gcc prior to 3.3.
> >
> >   template <class T>
> > ! bool
> > ! cat_ra (Array<T>& ra_cat, const Array<T>& ra_arg, int dim, int add_dim);
> >
> >   template <class LT, class RT>
> >   /* friend */ int
> > --- 526,533 ----
> >   // do that because of bugs in gcc prior to 3.3.
> >
> >   template <class T>
> > ! int
> > ! cat_ra (Array<T>& ra, const Array<T>& ra_arg, int dim, int idx, int move);
> >
> >   template <class LT, class RT>
> >   /* friend */ int
> > *************** assign (Array<LT>& lhs, const Array<RT>&
> > *** 565,572 ****
> >     template T resize_fill_value (const T&); \
> >
> >   #define INSTANTIATE_CAT(T) \
> > !   template bool cat_ra (Array<T>& ra_cat, const Array<T>& ra_arg, \
> > !                         int dim, int add_dim)
> >
> >   #define INSTANTIATE_ARRAY_AND_ASSIGN(T) \
> >     INSTANTIATE_ARRAY (T); \
> > --- 565,572 ----
> >     template T resize_fill_value (const T&); \
> >
> >   #define INSTANTIATE_CAT(T) \
> > !   template int cat_ra (Array<T>& ra, const Array<T>& ra_arg, \
> > !                         int dim, int idx, int move)
> >
> >   #define INSTANTIATE_ARRAY_AND_ASSIGN(T) \
> >     INSTANTIATE_ARRAY (T); \
> > Index: Array.cc
> > ===================================================================
> > RCS file: /cvs/octave/liboctave/Array.cc,v
> > retrieving revision 1.106
> > diff -c -p -r1.106 Array.cc
> > *** Array.cc 2004/02/23 15:35:00 1.106
> > --- Array.cc 2004/02/29 13:39:53
> > *************** assignN (Array<LT>& lhs, const Array<RT>
> > *** 3066,3100 ****
> >   }
> >
> >   template <class T>
> > ! bool
> > ! cat_ra (Array<T>& ra_cat, const Array<T>& ra_arg, int dim, int add_dim)
> >   {
> > !   bool retval = false;
> > !
> > !   dim_vector dv = ra_arg.dims ();
> > !
> > !   Array<int> ra_idx (dv.length (), 0);
> > !
> > !   for (int i = 0; i < ra_arg.length (); i++)
> > !     {
> > !       if (i != 0)
> > ! increment_index (ra_idx, dv);
> > !
> > !       Array<int> ra_idx2 = ra_idx;
> > !
> > !       if (dim >= ra_idx2.length ())
> > ! {
> > !  ra_idx2.resize_and_fill (dim + 1, 0);
> > !
> > !  retval = true;
> > ! }
> > !
> > !       ra_idx2(dim) = ra_idx2(dim) + add_dim;
> > !
> > !       ra_cat(ra_idx2) = ra_arg(ra_idx);
> >       }
> > !
> > !   return retval;
> >   }
> >
> >   template <class T>
> > --- 3066,3093 ----
> >   }
> >
> >   template <class T>
> > ! int
> > ! cat_ra (Array<T>& ra, const Array<T>& ra_arg, int dim, int idx, int move)
> >   {
> > !   dim_vector dv_arg = ra_arg.dims ();
> > !
> > !   const T *arg_data = ra_arg.data ();
> > !
> > !   int numel_to_move = dv_arg(0);
> > !
> > !   int numel_arg = dv_arg.length ();
> > !
> > !   int ii_limit = dim+1 > numel_arg ? numel_arg : dim + 1;
> > !
> > !   for (int ii = 1; ii < ii_limit; ii++)
> > !     numel_to_move *= dv_arg(ii);
> > !
> > !   for (int j = 0; j < numel_to_move; j++)
> > !     {
> > !       ra.elem (idx++) = arg_data[numel_to_move * move + j];
> >       }
> > !
> > !   return idx;
> >   }
> >
> >   template <class T>
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: CAT speedup

David Bateman-3
According to Petter Risholm <[hidden email]> (on 03/01/04):

> On Mon, 1 Mar 2004, David Bateman wrote:
>
> > Petter,
> >
> > In the quick reading of this patch, If I've understood it correctly,
> > the classes like Matrix, etc now have a ::cat function that can be
> > used directly. If this is true then there is nothing to stop me also
> > using this function with user types?
>
> Well, define directly :) You can implement ::cat in you own user types,
> and instantiate cat_ra with the appropriate data type. But you will also
> need the framework for calling ::cat which is in Fcat in data.cc. That is
> you could either add to the existing user types which cat works for today,
> or you can make your own function like cat_sparse which follows the
> pattern defined in Fcat.
>
> We would like to have a way of registering the datatypes that should be
> used with cat, so that we don't have to hardcode it for all types in Fcat.
> Unfortunately we are not there yet. The same goes for [].

Yeah, it was basically this registration that I was talking about. In this
case if ::cat was part of octave_base and then Fcat wouldn't need to be
adapted for each new type.

Of course octave_base would just give the nice error message that ::cat has
not been implemeneted for this type. But, its presence in octave_base, then
makes it easily overloadable.

Cheers
D.

--
David Bateman                                [hidden email]
Motorola CRM                                 +33 1 69 35 48 04 (Ph)
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax)
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as:

[x] General Business Information
[ ] Motorola Internal Use Only
[ ] Motorola Confidential Proprietary


Reply | Threaded
Open this post in threaded view
|

Re: CAT speedup

John W. Eaton-6
On  1-Mar-2004, David Bateman <[hidden email]> wrote:

| Yeah, it was basically this registration that I was talking about. In this
| case if ::cat was part of octave_base and then Fcat wouldn't need to be
| adapted for each new type.
|
| Of course octave_base would just give the nice error message that ::cat has
| not been implemeneted for this type. But, its presence in octave_base, then
| makes it easily overloadable.

I don't think the cat functions should be member functions.  Instead,
they should be handled like other binary operators so we can install
cat functions that can handle mixed types efficiently.  But we can't
do it with the current binary operator tables because the cat function
requires an additional piece of information (dim) not used by the
other binary ops.

jwe