Sign in to follow this  
yahastu

Impossible challenge

Recommended Posts

I'm fairly sure there is no good solution to this problem, but there's no harm in posing it. Goal: a template sized matrix/vector class that is POD and has ".x, .y, .z" style access, and doesn't cause code bloat. One way to achieve this is by using an unnamed struct, which works in MSVC, but unfortunately doesn't work in other compilers:
template<unsigned M, unsigned N, typename Real>
struct matrix
{
    union{
        Real data[M*N];
	struct {Real x, y, z, w;};
    };

    //lots of member funcs
};


Another alternative is to use explicit template specialization. But the problem with that is twofold: 1) Code bloat because every member function must be rewritten. This could be somewhat minimized by using wrappers but still is quite ugly and makes code less maintainable. 2) Requires constructor to initialize data ptr, making it non-POD.
//generic version
template<unsigned M, unsigned N, typename Real>
struct matrix
{
    Real data[M*N];

    //lots of member funcs
};

template<typename Real>
struct matrix<2,1>
{
    const unsigned M = 2, N = 1;
    Real x,y;
    Real *data;
    
    matrix() : data(&x) {}

    //lots of member funcs
};

template<typename Real>
struct matrix<3,1>
{
    const unsigned M = 3, N = 1;
    Real x,y,z;
    Real *data;
    
    matrix() : data(&x) {}

    //lots of member funcs
};

template<typename Real>
struct matrix<4,1>
{
    const unsigned M = 4, N = 1;
    Real x,y,z,w;
    Real *data;
    
    matrix() : data(&x) {}

    //lots of member funcs
};



Now, we can get something very close to perfect by using member functions,
template<unsigned M, unsigned N, typename Real>
struct matrix
{
    Real data[M*N];

    const Real &x() const {	return data[0];	}
    const Real &y() const {	return data[1];	}
    const Real &z() const {	return data[2];	}
    const Real &w() const {	return data[3];	}
    Real &x() {	return data[0];	}
    Real &y() {	return data[1];	}
    Real &z() {	return data[2];	}
    Real &w() {	return data[3];	}

    //lots of member funcs
};



Unfortunately, calling code still has to use the unsightly ".x()" form. We could eliminate that necessity by using macros,
#define x x()
#define y y()
#define z z()

matrix<3,1> v;
v.x = 1;

#undef x
#undef y
#undef z



However, now we have to wrap these ugly macros around the calling code and abstain from using any variables called x y or z. Another alternative is to use __declspec(property), but this is also MSVC specific,
template<unsigned M, unsigned N, typename Real>
struct matrix
{
    Real data[M*N];

    Real get_x() const{ return data[0]; }
    Real get_y() const{ return data[1]; }
    Real get_z() const{ return data[2]; }
    void set_x(Real x){ data[0] = x; }
    void set_y(Real y){ data[1] = y; }
    void set_z(Real z){ data[2] = z; }

    __declspec(property(get = get_x, put = set_x)) Real x;
    __declspec(property(get = get_y, put = set_y)) Real y;
    __declspec(property(get = get_z, put = set_z)) Real z;


    //lots of member funcs
};



So in conclusion, I see only 2 portable ways, one relies on a horribly ugly macro hack, the other causes intolerable code bloat and loses POD. Then there are ways that achieve desired effect, but are Microsoft specific. Arggh.....any more ideas? [Edited by - yahastu on September 11, 2009 3:25:01 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by yahastu

Goal: a template sized matrix/vector class that is POD and has ".x, .y, .z" style access, and doesn't cause code bloat.


x,y,z access is only relevant for small vectors.

How would you express Matrix<200,200>?

And code bloat is somewhat less of a problem these days. If you have vector3 and vector4, then that's two classes.

Quote:
union{
Real data[M*N];
struct {Real x, y, z, w;};
};


So (M,N) can be (4,1), (2,2) and (1,4). I can't think of any practical reason where this would be applicable, since only other semantics differ. (4,1) and (1,4) are usually used in different context than (2,2), so x,y,z,w is misleading.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
There's also the static pointer to member array trick.


Yes, but that requires a constructor so breaks the POD requirement.

Quote:
x,y,z access is only relevant for small vectors.

How would you express Matrix<200,200>?


The reason I want x/y/z access is for syntax. This class is only for use with small sized matrices and vectors where performance is paramount. For larger matrices, it does not make sense to use stack allocation.

Quote:
And code bloat is somewhat less of a problem these days. If you have vector3 and vector4, then that's two classes.


Code bloat is problematic primarily because it makes the code less maintainable. It is also substantial because there would need to be 4 versions, and each one has about 30-40 member functions. I think that this might cause some small loss of performance, and since this class is designed specifically to be high performance, it is not acceptable to sacrifice even a small amount of performance for a stylistic improvement in my opinion.

Quote:

So (M,N) can be (4,1), (2,2) and (1,4). I can't think of any practical reason where this would be applicable, since only other semantics differ. (4,1) and (1,4) are usually used in different context than (2,2), so x,y,z,w is misleading.


It is not really a problem to have x/y/z/w available on matrices if the programmer knows they are only intended to be used on Nx1 vectors. Out of coincidence, the implementation may also allow it to work on 1xN vectors but that is not a requirement I care about because my library is consistent in using column vectors.

Share this post


Link to post
Share on other sites
Quote:
Original post by yahastu]

The reason I want x/y/z access is for syntax. This class is only for use with small sized matrices and vectors where performance is paramount. For larger matrices, it does not make sense to use stack allocation.


Ok... What are the limits then? What are the naming rules?

Can you provide realistic use cases on limits and naming convention?

Perhaps m.x.y? Or m[0].x? Or m.xw? I'm not entirely clear how this would add much semantic value for non-trivial types (2-, 3- and 4-D vectors).

Quote:
Code bloat is problematic primarily because it makes the code less maintainable. It is also substantial because there would need to be 4 versions, and each one has about 30-40 member functions. I think that this might cause some small loss of performance, and since this class is designed specifically to be high performance, it is not acceptable to sacrifice even a small amount of performance for a stylistic improvement in my opinion.


The code bloat related to templates usually refers to generated code, where there are many instantiations, perhaps some non-obvious ones, which cause the executable to bloat.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Quote:
Original post by yahastu
Yes, but that requires a constructor so breaks the POD requirement.

No, it doesn't.


I assumed you were referring to [6/27/2005 8:00:21 AM] (you didn't specify). I take it then you are referring to [6/27/2005 9:04:27 AM ?

The problem with that example is that it assumes a 3-dimensional vector. I can generalize it (as shown below), but this relies on a non-standard zero-sized array extension in MSVC.

Moreover, it also does not work for M < 4, which would require vec to be specialized for those 4 dimensions...in other words, it just takes the problem back to square one.


template<unsigned M>
struct vec
{
float x,y,z,w;
float data[ ((int)M-3) > 0 ? (M-3) : 0 ];

float &operator[](unsigned i)
{
return ((float*)this)[i];
}

const float &operator[](unsigned i) const
{
return ((float*)this)[i];
}
};




Quote:
Ok... What are the limits then? What are the naming rules?

Can you provide realistic use cases on limits and naming convention?

Perhaps m.x.y? Or m[0].x? Or m.xw? I'm not entirely clear how this would add much semantic value for non-trivial types (2-, 3- and 4-D vectors).


My requirements are:
1) Fully general; allows for any static size from 1,1 up to N,N
1) POD
2) No overhead
3) No specializations of the base class that require duplicating member functions

My desires is:
4) Able to access as ".x" or ".y" or ".z"

As it is easy to add ".x()" access support with all my requirements, the only syntactic improvement (imo) is exactly ".x", no variations.

The syntactic value I place upon this syntax is just because I find it to be more readable and "nice".

I have recently heard that newer versions of g++ do reputedly support anonymous structs, so that makes that option a bit more attractive. Is this widely supported as an extension by other compilers?

Share this post


Link to post
Share on other sites
Quote:
Original post by yahastu
I assumed you were referring to [6/27/2005 8:00:21 AM] (you didn't specify).

I thought that specifying "static pointer to member array trick" would make it obvious I was referring to the post involving a static pointer to member array.

Share this post


Link to post
Share on other sites
Honestly, if this is important to you (and you won't back down on any of your requirements), then you should just bite the bullet and move to code-generation. Biggest problem would be that you'd need to somehow know up front which specializations are required. Of course, I can't see wanting named member access for anything past four dimensions, and there are lots of good reasons to have your float3 and float4 be VERY different objects (SIMD alignment requirements...). So yeah, I don't have a great idea (I'm guessing you don't want to go the code-gen route), but I also think you're painting yourself into a corner with a pile of unrelated and at-odds requirements.

Share this post


Link to post
Share on other sites
Modern C++ Design discusses how to implement templatized mixins via inheritance. He creates a generic inherit_from template that takes a typelist and inherits from each item in the list. You can use a similar technique here. Note that boost provides boost::inherit which is a variadic template that achieves a similar effect.

Using this technique, what you would do is:

template<typename T, int Size>
class Matrix : public inherit_from<Repeat<T, Size> >
{
};

Repeat is something you'd define yourself that creates a boost::mpl::list of the appropriate size. Shouldn't be hard. This would make a class that inherits from T Size times. Of course you can't inherit from the same thing more than once, and you can't inherit from primitive types, so boost::inherit wouldn't work here. It would work to use the implementation discussed in Modern C++ Design however. Using that implementation, you would not be able to write m.x, m.y, m.z, m.w, but you would be able to write m.field<float, 0> or something similar, i don't remember 100%.

Share this post


Link to post
Share on other sites
Okay so that only shows how to access individual members as an array, rather than trying to access an array as individual members.

I don't believe there is a way besides explicit specialisation, or code generation.
How would one expect to have the compiler pick the names of the members and how many of them there are according to integer template parameters? I.e. what's to stop me from doing this:
matrix<1,2,float> m;
m.z = 42;
Whilst allowing this:
matrix<1,3,float> m;
m.z = 42;


A goal of avoiding explicit specialisation entirely, is nuts. There are certain operations such as cross-product that only make sense with a certain number of dimensions.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Okay so that only shows how to access individual members as an array, rather than trying to access an array as individual members.

I don't believe there is a way besides explicit specialization, or code generation.
How would one expect to have the compiler pick the names of the members and how many of them there are according to integer template parameters? I.e. what's to stop me from doing this:
matrix<1,2,float> m;
m.z = 42;
Whilst allowing this:
matrix<1,3,float> m;
m.z = 42;


A goal of avoiding explicit specialisation entirely, is nuts. There are certain operations such as cross-product that only make sense with a certain number of dimensions.



True, but you don't need explicit specialization for that.


template<int Rows, int Columns, class T>
class Matrix
{
public:
template<int OtherRows, int OtherColumns, class T> //Input matrix can have different dimensions
boost::enable_if<boost::equal_c<Columns, OtherRows>, void>::type //but only if Columns == Rows. The result of this expression is void, and thus this function returns void
Multiply(const Matrix<OtherRows, OtherColumns, T>& rhs)
{
}
};





writing m.Multiply(other) will only compile if m.Columns == other.Rows. For cross product you can do something similar. Cross product is only defined for 3 or 7-dimensional vectors, so you write it as:


boost::enable_if<boost::equal_c<Columns*Rows, 3>, void>::type
CrossProduct(const Matrix<Rows, Columns, T>& rhs)
{
}



Here the argument must be a matrix of the exact same type. The condition this time is that Columns*Rows == 3. The function doesn't exist otherwise. This condition might seem odd, but since 3 is prime the only possibilities are 1,3 and 3,1. This means it handles row major and column major vectors. Add an or clause for the dimension 7. Or better yet, do the following:


template<int Rows, int Columns>
struct supports_cross_product { enum { value = 0; } };

template<>
struct supports_cross_product<1, 3> { enum { value = 1; } };

template<>
struct supports_cross_product<1, 7> { enum { value = 1; } };

template<>
struct supports_cross_product<3, 1> { enum { value = 1; } };

template<>
struct supports_cross_product<7, 1> { enum { value = 1; } };

boost::enable_if<supports_cross_product<Rows, Columns>, void>::type
CrossProduct(const Matrix<Rows, Columns, T>& rhs)
{
}





The OP said he didn't want to use any template specialization because of code bloat, but this generates 0 code. It all resolves down to nothing.


Having the compiler pick the names is also possible via some template metaprogramming hackery. The method you would use is similar to what boost uses all over the place and they call "placeholders". There's an inherent limitation here, just as there is in boost, in that you can't have an unlimited of such "placeholders". They're all predefined, but in essence you would do something like this:


namespace matrix_vars
{
struct w { float w; };
struct x { float x; };
struct y { float y; };
struct z { float z; };

typedef boost::mpl::vector<x, y, z, w> default_vars;
}



template<int Rows, int Columns, class T, class VarNames = matrix_vars::default_vars>
class Matrix
: public inherit_from<get_n_vars<Rows*Columns, VarNames>::type>
{
public:
}





get_n_vars just walks through the VarNames list for a maximum of n items, making a new type list out of each one and stopping after that.

The end result of all this is that you inherit from each of the "placeholders", and so you get a public member with the correct name. If you want to change the way different items are mapped to different variable names, make up a new var_names list.

This might look like a ton of template stuff that's going to result in code bloat, but most of it is only compile-time type magic and doesn't result in extra code bloat.

In practice the "placeholder" classes will need to be a little more complicated, to allow for conversions and casting among other things, but nevertheless I think it's a good start.

[Edited by - cache_hit on September 12, 2009 9:13:40 PM]

Share this post


Link to post
Share on other sites
cache_hit,

Several bugs with your code first of all...


enum{ value = 1 };


not


enum{ value = 1; }


also, you forgot keyword "typename" on your use of enable_if.

when you write,


boost::enable_if<boost::equal_c<Columns*Rows, 3>, void>::type


I haven't used equal_c, but wouldn't it be better to have written,


boost::enable_if_c<Columns*Rows==3>::type


Quote:
Using that implementation, you would not be able to write m.x, m.y, m.z, m.w, but you would be able to write m.field<float, 0> or something similar


I think we can all agree that "m.field<float, 0>" is a much uglier syntax than "m.x()" which is trivial, so I see no advantage to that suggestion. However, I agree it would make sense to enable_if these accessors only for vectors of the appropriate size.

I'm still having a bit of trouble understanding this example,


template<int Rows, int Columns, class T, class VarNames = matrix_vars::default_vars>
class Matrix
: public inherit_from<get_n_vars<Rows*Columns, VarNames>::type>
{
public:
}



I never thought of using inheritance in this way...may this result in non-optimal alignment of the struct though?

Share this post


Link to post
Share on other sites
Also, this is a bit off topic, but there are several more problems in this:
a) you should have templated on an unsigned size
b) your return type here is void, but should be either Matrix<Rows,OtherColumns,T> or Matrix<Rows,OtherColumns,OtherT>
c) why not use operator*?
d) No need to resort to enable_if here, as it can be done more cleanly and simply without it
e) Even if using enable_if, there's no need to use equal_c because you could have just used enable_if_c


template<int OtherRows, int OtherColumns, class T> //Input matrix can have different dimensions
boost::enable_if<boost::equal_c<Columns, OtherRows>, void>::type //but only if Columns == Rows. The result of this expression is void, and thus this function returns void
Multiply(const Matrix<OtherRows, OtherColumns, T>& rhs)
{
}


I would do something like this instead:


template<unsigned P>
matrix<M,P,Real> operator*(const matrix<N,P,Real> &m) const;

Share this post


Link to post
Share on other sites
I basically just typed all that off the top of my head, so I'm not surprised at all that there's a lot of bugs :) I was mostly just trying to illustrate the idea, and leave the implementation details out.

I've only briefly looked over your comments, but they all seem valid. FWIW I had the Multiply functions return a void because that way there's no copy made. But it's just an implementation detail that can be changed to suit the needs of your library.

Quote:

I'm still having a bit of trouble understanding this example,


template<int Rows, int Columns, class T, class VarNames = matrix_vars::default_vars>

class Matrix

: public inherit_from<get_n_vars<Rows*Columns, VarNames>::type>

{

public:

}



It's easiest to understand if you consider how boost::inherit works. It takes every item passed to it, and just inherits from it. so

class foo : public inherit<a, b, c, d>
{
};

is equivalent to writing

class foo : public a, public b, public c, public d
{
};

because of this, you need to be careful about making sure the bases are POD types that don't inherit from anything else, or else you might run into the dreaded diamond. But the key point is that if a, b, c, and d contain public members, then foo contains those same public members. And if those members are classes that are convertible to float and allow assignment, then you actually do have foo.x, foo.y, foo.z syntax.

The point of the get_n_vars thing is that you might have some predefined compile-time limit of how many "embedded variables" like x, y, z, and w can be supported. In my example I specified a default mapping with the matrix::default_vars typelist, which contains placeholders x, y, z, w. This means matrix.x refers to matrix[0][0], matrix.y refers to matrix[0][1], etc. But matrices are different sizes and you might want different variable names. Specifying a different list such as <w, y, x, z> changes what member name accesses which variable. If you specify a 2x2 matrix but the list only has 3 items in it, then matrix[1][1] would be inaccessible through one of these embedded members. The idea is just that you specify a list of types, each of which knows how to access an item in the array. You pull out the first n of these items, where n = Rows*Columns and inherit from them. This way you get an embedded member variable for each item in the matrix.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this