Thread: faster allocating matrix

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715

    faster allocating matrix

    A while ago I read a thread about faster memory allocation for matrices which uses new operator efficiently and not through loop. I can't find that thread now, but if someone remember how it is done please post code here.
    Thank you

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Code:
    template <typename T>
    inline T** alloc_matrix(size_t rows, size_t columns)
    {
        return (T**)new char[rows * columns * sizeof(T)];
    }//alloc_matrix
    
    template <typename T>
    inline void free_matrix(T **m)
    {
        delete[] (char*)m;
    }//free_matrix
    
    
    int **matrix = alloc_matrix<int>(10, 10);
    ...
    free_matrix(matrix);
    - The returned memory is uninitialized.
    - If T is an object type, constructors and destructors are not called.

    gg

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    There are quite a few ways of going about this. What implementation you use depends on how you intend to index the matrix. Here's one way:
    Code:
    #include <iomanip>
    #include <iostream>
    
    template <typename T>
    class matrix {
    public:
      matrix ( int m, int n )
        : rows ( m ), cols ( n ) { data = new T[rows * cols]; }
        ~matrix() { delete [] data; }
      T& operator() ( int i, int j ) { return data[cols * i + j]; }
    private:
      int rows, cols;
      T *data;
    };
    
    int main()
    {
      matrix<int> m ( 2, 5 );
    
      for ( int i = 0; i < 2; i++ ) {
        for ( int j = 0; j < 5; j++ )
          m ( i, j ) = ( i + 1 ) * ( j + 1 );
      }
    
      for ( int i = 0; i < 2; i++ ) {
        for ( int j = 0; j < 5; j++ )
          std::cout<< std::left << std::setw ( 3 ) << m ( i, j );
        std::cout<<std::endl;
      }
    }
    My best code is written with the delete key.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> - If T is an object type, constructors and destructors are not called.
    Let me fix that....
    Code:
    template <typename T>
    inline T** alloc_matrix(size_t rows, size_t columns)
    {
        return (T**)new T[rows * columns];
    }//alloc_matrix
    
    template <typename T>
    inline void free_matrix(T **m)
    {
        delete[] (T*)m;
    }//free_matrix
    Which makes it near identical to Prelude's code, just not as OO

    gg

  5. #5
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Thanks guys, always very reliable!

  6. #6
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    Quote Originally Posted by Codeplug
    Let me fix that....
    Code:
    template <typename T>
    inline T** alloc_matrix(size_t rows, size_t columns)
    {
        return (T**)new T[rows * columns];
    }//alloc_matrix
    Which makes it near identical to Prelude's code, just not as OO
    Just to be tedious and pedantic, while you allocate the correct number of T's you then store the location of the first T in a pointer to a pointer. This aint even vaguely correct and why innocent looking c-style casts should be shunned for reinterpret_cast. Prelude's method, where you just break down and do the math to index in two dimentions is the way to go. What I think the OP was asking for, but is somewhat of a waste is something like
    Code:
    template <class T>
    T ** new_p2p_arr(int col, int row) {
        T **rowtbl = new T*[row];
        rowtbl[0] = new T[row*col];
        for(int i=1;i<row;i++) {
            rowtbl[i] = rowtbl[0] + i*col;
        }
        return rowtbl;
    }
    Now m[y][x] type syntax will work as expected, and it's clear that what we really have is just a lookup table for multiplication m[y] = base + y*col

  7. #7
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    There's no gain in using reinterpret_cast over a C cast in this situation.
    However, my original thoughts of using [][] to achieve an offset into the allocated array is indeed incorrect. [][] will perform two dereferences which doesn't work on a T array.

    I was totaly thinking [][] was identical to "data[cols * i + j]" - don't ask me why.

    Can I blame it on the beer? Sure I can.

    (Let me go check my other posts....)

    gg

  8. #8
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    Quote Originally Posted by Codeplug
    There's no gain in using reinterpret_cast over a C cast in this situation.
    If you never use the c-style casts then to do something like this you would need to use reinterpret_cast, rather than static_cast. So I guess I should say always use static_cast and if the compiler complains it probably has a point.
    I was totaly thinking [][] was identical to "data[cols * i + j]" - don't ask me why.

    Can I blame it on the beer? Sure I can.

    (Let me go check my other posts....)

    gg
    Yeah it's confusing as all get out. int *p and int a[3] act the same, p=a makes sense p[x] == a[x] works, so why don't int **p and int a[3][3] act the same. Really would be nice to have typedef's that could represent say int[30] then you could clealy say pointer to first of an unknown number of consecutive int[30]'s. Ah well, beer, now there's a good idea.

  9. #9
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by Codeplug
    I was totaly thinking [][] was identical to "data[cols * i + j]" - don't ask me why.
    Confunded T** with T[][]... Beer for sure

  10. #10
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    Quote Originally Posted by grib
    Really would be nice to have typedef's that could represent say int[30] then you could clealy say pointer to first of an unknown number of consecutive int[30]'s. Ah well, beer, now there's a good idea.
    Yes that would be very nice.


    Code:
    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    
    int main(void)
    {
    	typedef int INT_ARRAY_30[30];
    
    	INT_ARRAY_30* foo;   /* Declare a pointer to an array 30 of ints. */
    	int (*bar)[30];      /* Equivalent to foo without the use of typedef synonym. */
    
    	foo = new INT_ARRAY_30[20];                     /* C++ style allocation */
    	bar = (int (*)[30]) malloc(20 * sizeof(*bar));  /* C style allocation with ugly cast. */
    
    	for (int x = 0;x < 20;x++)
    	{
    		for (int y = 0;y < 30;y++)
    		{
    			foo[x][y] = y * x;
    			bar[x][y] = y + x;
    
    
    			printf("foo/bar[%d][%d] = %d, %d \n", x, y, foo[x][y], bar[x][y]);
    		}
    	}
    
    	delete [] foo;
    	free(bar);
    
    	getchar();
    	return 0;
    }
    MSDN C Language Reference: Interpreting More Complex Declarators

  11. #11
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Well I'm glad because of this discussion, but I've found what I searched for and that is Sang-drax's code:

    Code:
    //Allocate the actual data
    	int* rawData = new int[rows*cols];
     
    	//Allocate pointers to the data
    	int** data = new int*[rows];
     
    	//Point the pointers into the data
    	for (int i=0; i < rows; ++i){
    	data[i] = &rawData[cols*i];
    I found Prelude's code very useful for what I'm doing right now!

    Anyway I have one more question:
    Maybe some of you work with MATLAB.
    In MATLAB if you want to declare 2d array (matrix) say 3x3 you simply type this:
    A=[1 2 3;4 5 6;7 8 9];
    and that's it you have 3x3 matrix.

    Is this possible using string processing or what?
    I don't have that much knowledge to write program that will doing the same thing.
    I wonder how memory is allocated here. Maybe whole line is placet to some buffer first and then counted for elementes...?

    If someone knows a little about this please explain!
    Thanks

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Is this possible using string processing or what?
    Are you asking how MATLAB does it or how can you get similar functionality? I would imagine that MATLAB does something similar to the allocation loop:
    Code:
    // Pseudo-implementation with s == 1 2 3;4 5 6;7 8 9];
    int span;
    int ndim = count_sep ( s, span );
    int **mat = new int*[ndim];
    
    for ( int i = 0; i < ndim; i++ ) {
      mat[i] = new int[span];
      s = fill_span ( s, mat[i], span );
    }
    >I wonder how memory is allocated here.
    It really depends on how the thing is implemented internally. MATLAB could use a matrix buffer for all matrices and then allocate "just enough" memory after parsing the string, it could build a list of vectors, it could build a vector of vectors dynamically, it could use a static vector of vectors, we just don't know unless you can see the source. But as with everything, there are naive methods and there are methods that optimize for space or time or both.
    My best code is written with the delete key.

  13. #13
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    Code:
    //Allocate the actual data
    	int* rawData = new int[rows*cols];
     
    	//Allocate pointers to the data
    	int** data = new int*[rows];
     
    	//Point the pointers into the data
    	for (int i=0; i < rows; ++i){
    	data[i] = &rawData[cols*i];
    If you do this, then I imagine freeing the matrix would be different as well:
    Code:
    delete[] rawData;
    or
    delete[] data[0];
    Rather simpler I say, if it works.

    **EDIT**
    [edit2: snip]Oops, I thought MATLAB was a library [/edit2]
    Last edited by Hunter2; 11-15-2004 at 05:58 PM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  14. #14
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Quote Originally Posted by Hunter2
    Code:
    delete[] rawData;
    or
    delete[] data[0];
    Rather simpler I say, if it works.
    I think that both is needed:
    Code:
    delete [] data;
    delete [] rawData;
    The line delete [] data[0] look suspicious to me, I'm not sure that it will work the job.

  15. #15
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>delete [] data;
    Oops yeah, forgot you have to delete the pointer array too

    >>The line delete [] data[0] look suspicious to me
    I agree, looks fishy, but data[0] does point to the first element of the array you've allocated.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 05:57 PM
  3. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-14-2004, 12:19 AM
  4. Matrix and vector operations on computers
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 05-11-2004, 06:36 AM