Attn: Patch (Fcat and [] for defined types)

[David Bateman]

Find attached a patch that creates the CATOP function in the way previously
discussed. The purpose of this patch is to make the concatenation operators
and Fcat functions available to user types.

The patch replaces the "[]" operator and the Fcat, Fhorzcat and Fvertcat
functions. It is faster than the "[]" in all cases, but is slower than the
Fcat functions for a case like

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

but is much much faster than

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

The slowup of the first case on my machine is before = 0.15s, after = 0.25s,
so is not major. I can't figure out why this slow up is happening, as the
code is functionally the same, and the slow-up scales with the size of
the arrays being concatenated. For this reason I don't believe the slow-up
is due to the overhead of the function dereferencing of the catop functions
and the passing of "octave_value"s rather than the basic array types. Even
given this slow-up I believe this patch is well worth accepting.

The patch passes all of the "make check" tests and I've tested it reasonably
well on a few other cases. The only user visible change that I'm aware of is
that

a = ["a", 101, 102];

will report a warning twice for the implicit conversions to a string,
is warn_num_to_str is non-zero, when previously the warning was only
reported once. This is due to the fact that the warning is issued in
the catop function itself, rather than in the "[]" as previously

The changelog for this patch is

liboctave
---------
        * Array.cc, Array.h (cat_ra): Delete

        * Array.h, Array-C.cc, Array-d.cc, Array-ch.cc (INSTANTIAT_ARRAY_CAT): 
        Delete

        * dNDArray.cc, dNDArray.h, CNDArray.cc, CNDArray.h, chNDArray.cc, 
        chNDArray.h (cat): Delete
        
        * Array.cc (Array<T>::insert): Copy data in NDArray version

        * dNDArray.cc, dNDArray.h, CNDArray.cc, CNDArray.h, chNDArray.cc, 
        chNDArray.h (concat): New function used for concatenation that does
        an indexed copy of one array into another

        * dim-vector.h (concat): New function to concatenate dim_vectors

        * CNDArray.cc, CNDArray.h (insert): New function for insertion of one
        NDArray into another

src
---
        * ops.h (CATOPDECL, DEFCATOPX, DEFCATOP, DEFCATOP_FB, DEFNDCATOP_FN, 
        CATOP_NONCONFORMANT, INSTALL_CATOP): New macros
        
        * OPERATORS/op-b-b.cc, OPERATORS/op-b-bm.cc, OPERATORS/op-bm-b.cc, 
        OPERATORS/op-bm-bm.cc, OPERATORS/op-cell.cc, OPERATORS/op-chm.cc, 
        OPERATORS/op-cm-cm.cc, OPERATORS/op-cm-cs.cc, OPERATORS/op-cm-m.cc, 
        OPERATORS/op-cm-s.cc, OPERATORS/op-cs-cm.cc, OPERATORS/op-cs-cs.cc, 
        OPERATORS/op-cs-m.cc, OPERATORS/op-cs-s.cc, OPERATORS/op-m-cm.cc, 
        OPERATORS/op-m-cs.cc, OPERATORS/op-m-m.cc, OPERATORS/op-m-s.cc, 
        OPERATORS/op-range.cc, OPERATORS/op-s-cm.cc, OPERATORS/op-s-cs.cc, 
        OPERATORS/op-s-m.cc, OPERATORS/op-s-s.cc (CATOPDECL, DEFCATOPX,
        DEFCATOP, DEFCATOP_FB, DEFNDCATOP_FN, CATOP_NONCONFORMANT,
        INSTALL_CATOP): Use them to define concatenation functions

        * TEMPLATE-INST/Array-tc.cc (INSTANTIATE_ARRAY_CAT): Delete

        * pt-mat.cc (tree_matrix::rvalue): Rewrite code to use new 
        concatenation binary operators 

        * data.cc (cat_add_dims): delete (now dim_vector::concat)

        * data.cc (do_cat): Rewrite code to use new concatenation binary 
        operators 

        * ov-typeinfo.cc (cat_op_fcn): Instantiate the array of cat functions
        
        * ov-typeinfo.cc, ov-typeinfo.h (register_cat_op, do_register_cat_op,
        do_lookup_cat_op): New functions

        * ov-typeinfo.cc, ov-typeinfo.h (cat_ops): Lookup table of binary
        concatentaion operators

        * ov-typeinfo.h (lookup_cat_op): New function

        * ov.cc (gripe_cat_op, gripe_cat_op_conv, do_cat_op): New functions

        * ov.h (cat_op_fcn): Definition

        * ov.h (resize, do_cat_op): New functions

        * version.h (OCTAVE_API_VERSION): Bump version to api-v9

        * Cell.cc, Cell.h, oct-map.cc, oct-map.h (cat): Delete

        * Cell.cc, Cell.h, oct-map.cc, oct-map.h (concat): New function
        
        * ov-base.cc, ov-base.h, ov-scalar.h, ov-complex.h, ov-bool.h, 
        ov-range.h, ov-base-mat.h, (resize): New function

Regards
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_v3
Description: Text document