Re: [boost] [PQS] Resizable vectors/matrices

From: Leland Brown (lelandbrown_at_[hidden])
Date: 2006-06-16 17:14:31

--- Janek Kozicki <janek_listy_at_[hidden]> wrote:

> One last note: above design does not allow to resize
> vectors and
> matrices in runtime. This limits the library usage.
> Should there be
> added a slower complementary library that will allow
> to resize data in
> runtime? Any ideas?

I agree this is useful, and also that it has a
run-time penalty.  But I have an idea to reduce that
penalty, as well as reducing the work for the library
implementer to add this feature, without having to
write a whole parallel library.  I had hoped to add
this to my own matrix library, but I haven't yet. 
(Actually, I need this capability, but I'm using a
less efficient workaround for now.)

A standard way to implement dynamically-sized data
structures is to use dynamic (heap) memory allocation,
which can be costly.  Data sized at compile time, on
the other hand, can be allocated efficiently on the
stack.  A compromise that works in many situations is
to set a maximum size for each object at compile-time,
allocate memory for the maximum size, and then only
use part of the structure depending on its current
size set at run-time.  This allows the data and its
operations to have an adjustable size (up to a
predetermined maximum) while avoiding heap allocation
- the best of both worlds.

As an example of how this can be implemented, suppose
we augment our vector template with an extra template
argument of type bool, which tells if the vector is
resizable - e.g.:

    vector<3,double,false>  // 3D vector of double
    vector<5,double,true>   // vector *up to* 5D

The resizable vector needs an extra member to store
the actual current size, and that size should be used
as the upper limit in loops, instead of the size in
the template argument (see example below).

Both kinds of vectors can be implemented with one
definition, by inheriting from separately specialized
base classes.  Here's an example:

    template< int N, bool resizable >
    class vector_base {};

    template< int N >
    class vector_base< N, false >
    {
        const int _n = N;  // size is constant
    };

    template< int N >
    class vector_base< N, true >
    {
    public:
        // check 1<=new_size<=N and set _n = new_size
        void resize( int new_size );
    private:
        int _n;  // actual size set at run-time
    };

Then a single vector implementation works for both:

    template< int N, type T, bool resizable >
    class vector : vector_base< N, resizable >
    {
    public:
        T magnitude();
        ...
    private:
        T elements[N];
    };

    template< int N, type T, bool resizable >
    T vector< N, T, resizable >::magnitude()
    {
        typedef ... T_squared;
        T_squared sum = elements[0] * elements[0];
        for (int i=1; i<_n; ++i)  // use _n, not N
        {
             sum += elements[i] * elements[i];
        }
        return sqrt( sum );
    }

Note that for resizable vectors, _n is variable, but
for fixed-size vectors, _n is a compile-time constant,
allowing the compiler to do optimizations like loop
unrolling, as you'd expect for a fixed-size vector.

Operations such as dot product require validating that
both vectors have the same size.  Again, if both are
fixed-size vectors, this comparison is a compile-time
constant and can be optimized out.

FWIW, I'm not happy with the syntax above of adding an
extra bool parameter.  For my code, I planned to use a
negative value of N to indicate resizable:

    vector<3,double>      // fixed 3D vector
    vector<-5,double>     // up to 5D vector
    matrix<4,-14,double>  // 4x1 to 4x14 matrix
    matrix<-14,4,double>  // 1x4 to 14x4 matrix
    matrix<-6,-6,double>  // both values resizable

but this is admittedly nonintuitive (though it does
make both the library and user code more concise).

BTW, this is where I'd really like to see templatized
typedefs in C++, allowing us to define:

    template< int N, type T >
    typedef vector< N, T, false > fixed_vector;

    template< int N, type T >
    typedef vector< N, T, true > resizable_vector;

Thus we'd have:

    fixed_vector<N,T>
    resizable_vector<N,T>

while using the common vector template defined above.

In _The Design and Evolution of C++_, Bjarne
Stroustrup says adding templatized typedefs would be a
"technically trivial" extension, but questions the
wisdom of the idea.  Perhaps there's been some
discussion about this topic in Boost?

-- Leland

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com