Thread: Basic doubt about expression templates

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    28

    Basic doubt about expression templates

    Hello all,

    I am trying to use expression templates/template metaprogramming to solve matrix systems at compile time. Since I am just starting, I need some help to make sure I am on the right track.

    I tried out the following basic template in a file called "Matrix.h"(file attached). Below is the constructor for a two dimensional array.

    Code:
    template<class T, unsigned int r=1, unsigned int c=1> 
    class Matrix{
    private:
    	unsigned int rows, columns;
    	T **mat_data;
    	
    public:
    	Matrix() {
    		std::cout << "Constructor MATRIX" << std::endl;
    
    		rows=r;
    		columns=c;
    		create_matrix();
    		
    		for(int i=0; i<rows; i++){
    			for(int j=0; j<columns; j++){
    				mat_data[i][j]=0;
    				std::cout << "checking" << std::endl;
    
    			}
    		}		
    	}
    	
    	void create_matrix() {
    		try {
    			mat_data=new T *[rows];
    		}
    		catch (std::bad_alloc xa) {
    			std::cout << "Out of memory.\n";
    			exit(1);
    		}
    		
    		for (int row_count=0;row_count<rows;row_count++) {
    			try {
    				mat_data[row_count]=new T [columns];
    			}
    			catch (std::bad_alloc xa) {
    				std::cout << "Out of memory.\n";
    				exit(1);
    			}
    		}
    		
    		return;
    	}
    	
    };
    Just for checking, I made the empty constructor Matrix() produce an array with all rows x columns elements initialized to 0. I need to check if this is created at compile time. So I added the cout "checking".

    The main program has this code:
    Code:
       Matrix<float, 2, 2> m1;
    Should this produce an array m1 of 2x2 with all 0 and with four lines of "checking" when we compile using g++ main.cpp?

    Thanks in advance.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Yes, this should get you "checking" output 4 times.

    Do you expect the arrays that you only allocate at runtime be filled with 0-s at the compile-time?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    There are a couple of things...
    First off, know that class is an old keyword kept for backwards compatibility. typename is the proper keyword for saying a type in new C++.
    Don't name arguments "r" and "c". Give them proper names such as "rows", "columns".
    What is the point of assigning the rows and columns to member variables?
    Since you specify the dimensions at compile time, you don't need new! All you have to do is T mat_data[rows][cols].
    Your current code does also not delete properly. You are leaking memory. Very bad.
    Last edited by Elysia; 08-21-2010 at 09:29 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    You seem to be confused about a few things.

    In C++, "expression template" is a technique used to generate compile-time entities representing expression trees which can be "parsed" at compile-time or run-time; the technique only influences run-time behavior when "parsed" at run-time and only influences compile-time behavior when used with "template meta-programming".

    In C++, "template meta-programming" is a technique that provides abstract generation of arbitrary compile-time and run-time entities (these can be calculations); the technique only influences run-time behavior when it does because of the entities created during expansion.



    The goal of the "expression template" technique is simplifying or improving run-time behavior by exploiting aspects of of the expression trees it generates. In the case of matrices, you could greatly improve performance by only creating a single temporary to store and propagate the results of entire expressions.



    In order to perform calculations on matrices at compile-time, every construct used must be a compile-time construct.



    I am trying to use expression templates/template metaprogramming to solve matrix systems at compile time.
    You are failing miserably.

    The constructs you are using only generate a specific instance of a matrix class at compile-time which are then used in calculations performed at run-time.

    The "expression template" mechanism you are using only represents complex forwarding which is more costly than a natural mechanism because you are ultimately calling "new" in every application of the addition operator.

    The construct you are exposing don't fully qualify as "template meta-programming".

    I need to check if this is created at compile time.
    It isn't.

    The specific variation of the class is created at compile-time.

    An actual object, an instance of a matrix class and its storage, is not created until run-time.

    So I added the cout "checking".
    The `std::cout' object is a purely run-time construct. Even if you were using "template meta-programming" to perform these calculations at compile-time, your test would appear to fail.

    Should this produce an array m1 of 2x2 with all 0 and with four lines of "checking" when we compile using g++ main.cpp?
    No. It should not. It should produce four lines of "checking" at run-time. Constructors are not a compile-time construct.

    Soma

  5. #5
    Registered User
    Join Date
    Feb 2008
    Posts
    28
    Thank you very much for your responses Phantomotap and Elysia. I'll do some more reading before I write some more code and then I'll post again.

  6. #6
    Registered User
    Join Date
    Feb 2008
    Posts
    28
    After reading on expression templates particularly the link below, I have a few basic questions:
    AngelikaLanger.com - Expression Templates - Angelika Langer Training/Consulting

    The point to take home from these two examples is that compile-time computations are often recursive processes that take advantage of the recursive nature of the template instantiation process. What would be a function in a runtime computation is typically a class template in a compile-time computation. What would be the argument of a function in a runtime computation is typically a non-type template argument in a compile-time computation. What would be the return value of a function in a runtime computation is typically the a nested constant in the class template in a compile-time computation. And the condition that ends the recursion in a runtime computation is typically a template specialization in a compile-time computation. Equipped with this knowledge, it is no long stretch anymore to imagine how Erwin Unruh's prime number calculation was built on the exact same principles that we've been using in our two calculations.
    The above states that the return value should be a nested constant. With our example would that mean that the array mat_data would have to be const?

    In this example, the return value ret is not an enum value, but a static constant data member whose initialization triggers the recursion.
    I didn't understand the above statement. Does a static const member of a template force its instantiation at compile time? How would it differ by merely declaring the data member as only const?

    Since you specify the dimensions at compile time, you don't need new! All you have to do is T mat_data[rows][cols].
    Suppose my array is very large say 100000 by 100000. How would I ensure that there will not be stack overflow using static allocation? Or is dynamic allocation a completely different concept? I started using dynamic allocation using new when I started handling large arrays because then static allocation began to seg fault.

    Another question is the use of "inline"? Is it only a guideline to the compiler which will inline a function only if it performs a basic operation such as an assignment? If the function performs a larger operation, will the compiler treat it as a normal function despite the inline?


    The above questions are for me to understand what it takes to create a compile-time construct.
    In order to perform calculations on matrices at compile-time, every construct used must be a compile-time construct.

    Thanks in advance.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    First of all, know that these examples do not necessarily apply to yours. They are covering a compile time calculation, which results in a value.

    Quote Originally Posted by circuitbreaker View Post
    The above states that the return value should be a nested constant. With our example would that mean that the array mat_data would have to be const?

    I didn't understand the above statement. Does a static const member of a template force its instantiation at compile time? How would it differ by merely declaring the data member as only const?
    So the whole reason for using const and static is because the constant can be initialized directly inside the struct/class body.

    Suppose my array is very large say 100000 by 100000. How would I ensure that there will not be stack overflow using static allocation? Or is dynamic allocation a completely different concept? I started using dynamic allocation using new when I started handling large arrays because then static allocation began to seg fault.
    Then you have a problem, because new is a run-time construct and cannot be used at compile-time.

    Another question is the use of "inline"? Is it only a guideline to the compiler which will inline a function only if it performs a basic operation such as an assignment? If the function performs a larger operation, will the compiler treat it as a normal function despite the inline?
    Yes, it's only a suggestion (and allows multiple symbols with the same name, too, but that's another story). The compiler is free to inline the function if it deems it worth the time and if the function is not too complex.

    Trying to do a compile-time calculation with arrays is probably very tricky. I haven't done something like that myself, so I can't give examples.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Registered User
    Join Date
    Feb 2008
    Posts
    28
    Thanks for your response Elysia. Would also like some advice on the problem I am trying to solve.

    I am trying to solve differential equations involving matrices like y=A*x+B*u. Here y, x, u are vectors while A, B are matrices. The objective is to be able to solve them with low run-time. If the expressions can be written using operator overloading, the expressions will be in human readable form rather than nested for-loops.

    To reduce run-time, I tried to cut down on creation and destruction of temporary objects. So, I tried out expression templates. However, expression templates handle vectors element-by-element. I found this limitation in the following link:

    flipcode - Faster Vector Math Using Templates

    So instead I thought about template meta-programming. The idea is even if temporary objects are created and destroyed, its OK if they done at compile-time since compile-time can be large. Its run-time that I wish to maintain small. But even if I use template metaprogramming, I would be limted to solving equations of a certain size as I can't use new.

    I have almost run out of ideas. Should we try out projects like Blitz or Boost? Can anyone give me any pointers.

    Thanks in advance.

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    What I get from your post is that you wanted the equations to be human readable, so you turned to operator overloading, and when you discovered that lead to a lot of temporary objects being created and destroyed, you wanted to move the computations to compile time. Operator overloading must be serious business for you. If this is the only way that a run-time solution is lacking for you, then I would just write a function that solves differential equations and call it done. Operator overloading is just one idea, and when it starts to become an obstacle to greater priorities, you have to be willing to make choices. I personally think that "human readable" here should mean programmer readable, and regular functions are just that.

    My 2 cents anyway.

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I am trying to solve differential equations involving matrices like y=A*x+B*u. Here y, x, u are vectors while A, B are matrices.
    Okay. So, get started programming.

    The expression yields a very definite tree which can be exploited by specialization to create not a single temporary of a class type (only native temporaries are necessary) if only you are willing to do the work.

    However, expression templates handle vectors element-by-element.
    No. They don't.

    The "express templates" technique only generates a tree representation of an expression. It is your job, as the programmer, to parse the tree as you see fit.



    If this is the only way that a run-time solution is lacking for you, then I would just write a function that solves differential equations and call it done.
    That is ultimately what he should do even if he uses "expression template".

    The "expression templates" technique allows him to use operators to express the mathematics which should ultimately be manipulated for use as parameters to a "normal" implementation of the algorithms which exploits the fact that the entire expression is known.

    Soma

  11. #11
    Registered User
    Join Date
    Aug 2010
    Location
    India
    Posts
    4
    About the aspect of "template meta-programming". With the idea of being able to compute something at compile-time, I am looking at a way to create the specific variation of the class, instantiate an object of that class and initialize its content (the values) at compile-time.

    The specific variation of the class is created at compile-time.
    An actual object, an instance of a matrix class and its storage, is not created until run-time.
    I have the idea that if I could do that, I could then use "Expression Templates" in order to handle those objects and all this at compile-time.

    The first question is:
    1) Does that sound irrealistic or am I somehow on a good path?

    Then, the problem seems to be the initialization of the object. I thought about passing the values as template parameters:

    Code:
    template<typename T, unsigned int rows_arg, unsigned int columns_arg, T mat_arg[rows_arg][columns_arg]>
    class Matrix{
    private:
         static const unsigned int rows=rows_arg, columns=columns_arg;
         static const T* mat_data = mat_arg;
    public:
         ...
    };
    
    int main(){
         Matrix<int, 2, 2, {{3, 5 }, {7, 9 }}> m1;
         return 0;
    };
    But it seems this is not correct. So my second question is:
    2) Is it possible somehow to pass an array of dimension 2 as a template parameter?

    3) If not, is there any other way to initialize the static const member of a template class object?

    Thank you for your help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. function calling: basic doubt
    By doubty in forum C Programming
    Replies: 10
    Last Post: 06-23-2009, 02:31 AM
  2. Help with making a Math Expression DLL
    By MindWorX in forum C Programming
    Replies: 19
    Last Post: 07-19-2007, 11:37 PM
  3. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  4. recursion error
    By cchallenged in forum C Programming
    Replies: 2
    Last Post: 12-18-2006, 09:15 AM
  5. Question on l-values.
    By Hulag in forum C++ Programming
    Replies: 6
    Last Post: 10-13-2005, 04:33 PM