Re: Help with [] for defined types

[David Bateman]

Paul/Andy,

Here is a patch of where I'm upto, as its late here after a long night 
writing this patch last night. In any case it appears to work though I
have a slow up for

a = randn(1000); tic; b = cat(1,a,a); toc
a = randn(1000); tic; b = [a,a]; toc

where there is a slow down of a factor of 2, while funnily there is a speed 
up for

a = randn(1000); tic; b = cat(1,a,a*1i); toc
a = randn(1000); tic; b = [a*1i,a]; toc

of a factor of 50!!! In any case I'll try to figure out why I'm
getting the slow-up. It hasn't received all that much testing yet,
which is I why I don't consider it fit for submission yet, but its
damn close. There are probably also things like the promotions of one
type to another I haven't got right yet.... I also haven't due the
concatenation operators for the new int/uint types yet as the CVS
doesn't build at the moment. For this reason I'm also working on a
patched up version of a CVS from a few weeks ago before the int/uint
stuff went in. The patch should apply with a little fuzz against other
newish CVS version.

So this is so you can have a look and see if you guys think this is
the right way to go.... Andy, for the sparse stuff all you'd need to
write is a few functions

octave_sparse::resize
DEFCATOP_FN ()
INSTALL_CATOP () 

and any code needed by DEFCATOP_FN. With that and this patch you'd
then get Fcat, Fhorzcat, Fvertcat and "[]" all working.

Cheers
David


According to Paul Kienzle <address@hidden> (on 07/08/04):
> 
> On Jul 8, 2004, at 5:50 AM, David Bateman wrote:
> 
> >Paul,
> >
> >I've basically written most of the code for a CATOP function with a
> >binary lookup table similar to BINOP functions
> >
> >According to Paul Kienzle <address@hidden> (on 
> >07/08/04):
> >>dispatch could be extended so that it searches the entire
> >>argument list for the given type.   0.0I wouldn't want to try
> >>to support a specific list of types since octave makes
> >>heavy use of dynamic interpretation of the argument list.
> >>
> >>I don't want to create a type hierarchy like matlab, perl, etc.,
> >>but what do we do when someone uses:
> >>
> >>    cat(sparse(), full(), galois())
> >>
> >>In this case, obviously it is galois, but somehow 3rd party
> >>types would need to negotiate what to use.  Not very pretty.
> >
> >What I suggest is that this is implemented as
> >
> >     cat(cat(sparse(),full()), galois())
> >
> >with the proviso on memory you discuss below. The first cat would 
> >promote the
> >sparse matrix to a full() as defined by the function
> >
> >NDArray concat (const Sparse& ra, const NDArray& rb, Array<int>& 
> >ra_idx)
> >
> >and the second similarly to a Galois type as
> >
> >galois concat (const NDArray& ra, const galois& rb, Array<int>& ra_idx)
> >
> >It is assumed that the first argument is already resized to the final
> >dimension and the make_unique is NOT called so that the data in ra is
> >in fact altered in the return matrix. This is proviso is needed to
> >prevent multiple copies of the block being made. Thus the function
> >concat is a little dangerous as it alters the input arguments. However
> >as I expect it will only be used in Fcat and the "[]" operator I don't
> >think this is an issue. In the case of a promotion of ra to a different
> >type, then the data in ra must be copied.
> >
> >>Also not pretty is defining pairwise ops between types from
> >>different packages.
> >
> >Why?
> 
> This is a restatement of the type explosion problem.  I guess it will
> work out that the types which care about each other will either
> have each other as prereqs or be part of the same package.
> 
> >It is only the case of promotion of the return type that will cause
> >problems, and frankly this is a case that will arrive due to lazy 
> >coding
> >of the dot-m files, so it doesn't bother me if that case is slightly
> >inefficient. The funny thing is that  cat(galois(), full(), sparse())
> >would be much much efficient that cat(sparse(), full(), galois()) due
> >to the fact that there would be no promotion needed.
> >
> >The simplicity of only defining binary ops makes me feel that the
> >performance hit for the type promotion is a small price to pay. The
> >pay off of the binary operator approach is the easily defined 
> >dependency
> >on promotion of the types.
> 
> Okay, so the idea is that if you are really concerned, then
> use explicit conversion.  E.g.,
> 
>        [ mytype(data); data; data; mytypestuff ]
> 
> I'm not sure this would work for something like complex, since
> 1+0i is real.  Maybe we need an explicit complex() constructor?
> 
> >>For efficiency you want to walk the whole arg list to []
> >>and determine the final type and dimensions before
> >>building anything.
> >
> >Yeah, I know, I found out the hard way. I have a working version of 
> >CATOP
> >that doesn't determine the final size initially and just walks the 
> >list. It
> >is twice as slow with 2 like sized args, 4 times as slow with 3 like 
> >size
> >args, etc. In any case it was a good learning experience and I've 
> >mostly
> >rewritten the CATOP stuff to initialize the matrix first. I had to 
> >define
> >a resize function as part of the octave_value class that also promotes
> >scalars to matrices. So the core of Fcat becomes
> >
> >       octave_value tmp (args(1));
> >       tmp.resize (dv);
> >       Array<int> ra_idx (dv.length (), 0);
> >       for (int i = 2; i < n_args; i++)
> >         {
> >           dim_vector dv_tmp = args (i-1).dims ();
> >           ra_idx (dim) += (dim > dv_tmp.length () ? 1 : dv_tmp (dim));
> >           tmp = do_cat_op (tmp, args (i), ra_idx);
> >           if (error_state)
> >             return retval;
> >         }
> >       retval = tmp;
> >
> >>The tricky bit again is to decide what type to assign
> >>when two different user types are being used
> >>simultaneously.  I guess that's a problem for the
> >>user type installer to deal with.
> >
> >This is where the binary definition of the CATOP makes sense. All of 
> >this
> >is determined by an appropriate lookup table. This is why I prefer the
> >binary operator approach, with preallocation of the memory.
> 
> Okay.  Only other detail you might want to consider is
> an eventual implementation of types in m-files.  Is this
> going to be possible/convenient, and maybe compatible?
> 
> Paul Kienzle
> address@hidden

-- 
David Bateman                                address@hidden
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

patch.cat_v2
Description: Text document