Two-Dimensional Dynamic Arrays

Discussion in 'C++' started by Peter Olcott, Nov 25, 2005.

  1. Peter Olcott

    Peter Olcott Guest

    I need to know how to get the solution mentioned below to work. The
    solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:

    > http://groups.google.com/group/comp.lang.c /msg/db577c43260a5310?hl
    >
    >Another way is to create a one dimensional array and handle the
    >indexing yourself (index = row * row_size + col). This is readily
    >implemented in template classes that can create dynamically allocated
    >multi-dimensional arrays of any element type and number of
    >dimensions.


    What would be the syntax for created a template that allowed a
    one dimensional dynamic array, to be addressed using the conventional
    syntax for accessing a two dimensional array? I am thinking that this
    must be some sort of operator[] overloading.

    Thanks,


    Peter Olcott
     
    Peter Olcott, Nov 25, 2005
    #1
    1. Advertising

  2. Peter Olcott wrote:
    > I need to know how to get the solution mentioned below to work. The
    > solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:
    >
    >
    >>http://groups.google.com/group/comp.lang.c /msg/db577c43260a5310?hl
    >>
    >>Another way is to create a one dimensional array and handle the
    >>indexing yourself (index = row * row_size + col). This is readily
    >>implemented in template classes that can create dynamically allocated
    >>multi-dimensional arrays of any element type and number of
    >>dimensions.

    >
    >
    > What would be the syntax for created a template that allowed a
    > one dimensional dynamic array, to be addressed using the conventional
    > syntax for accessing a two dimensional array? I am thinking that this
    > must be some sort of operator[] overloading.


    http://groups.google.com/group/comp.lang.c/msg/909f01d9b4f1d9bd?hl=en&

    I knew I answered this once before - I think there is an FAQ as well..

    Here is the example code from that posting.

    #include <vector>

    template <typename w_elem_type>
    class matrix
    {
    public:
    typedef int t_Size;

    t_Size m_columns;
    t_Size m_rows;

    std::vector<w_elem_type> m_data;

    matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
    : m_columns( i_columns ),
    m_rows( i_rows ),
    m_data( i_columns * i_rows )
    {
    }

    w_elem_type * operator[]( t_Size i_index )
    {
    return & ( m_data[ i_index * m_rows ] );
    }

    template <typename w_Type, int w_columns, int w_rows>
    matrix( const w_Type (&i_array)[w_columns][w_rows] )
    : m_columns( w_columns ),
    m_rows( w_rows ),
    m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
    {
    }

    };

    #include <iostream>

    double array[3][4] = {
    { 1.0, 2.0, 3.3, 4.4 },
    { 1.0, 2.0, 3.3, 4.4 },
    { 1.0, 2.0, 3.3, 4.5 },

    };

    int main()
    {
    matrix<float> mat1( 3, 4 );
    matrix<float> mat2;
    matrix<float> mat3( array );

    mat2 = mat3;

    std::cout << mat2[2][3] << "\n";

    }
     
    Gianni Mariani, Nov 25, 2005
    #2
    1. Advertising

  3. Peter Olcott

    Peter Olcott Guest

    That looks like an excellent solution. I need absolutely top performance.
    You mentioned :

    some extensive matrix libraries you could use
    and ones that are very efficient if the dimensions
    are known.

    Could you provide me a link or other reference to these?
    Thanks again for your top notch assistance.

    "Gianni Mariani" <> wrote in message
    news:...
    > Peter Olcott wrote:
    >> I need to know how to get the solution mentioned below to work. The
    >> solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:
    >>
    >>
    >>>http://groups.google.com/group/comp.lang.c /msg/db577c43260a5310?hl
    >>>
    >>>Another way is to create a one dimensional array and handle the
    >>>indexing yourself (index = row * row_size + col). This is readily
    >>>implemented in template classes that can create dynamically allocated
    >>>multi-dimensional arrays of any element type and number of
    >>>dimensions.

    >>
    >>
    >> What would be the syntax for created a template that allowed a
    >> one dimensional dynamic array, to be addressed using the conventional
    >> syntax for accessing a two dimensional array? I am thinking that this
    >> must be some sort of operator[] overloading.

    >
    > http://groups.google.com/group/comp.lang.c/msg/909f01d9b4f1d9bd?hl=en&
    >
    > I knew I answered this once before - I think there is an FAQ as well..
    >
    > Here is the example code from that posting.
    >
    > #include <vector>
    >
    > template <typename w_elem_type>
    > class matrix
    > {
    > public:
    > typedef int t_Size;
    >
    > t_Size m_columns;
    > t_Size m_rows;
    >
    > std::vector<w_elem_type> m_data;
    >
    > matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
    > : m_columns( i_columns ),
    > m_rows( i_rows ),
    > m_data( i_columns * i_rows )
    > {
    > }
    >
    > w_elem_type * operator[]( t_Size i_index )
    > {
    > return & ( m_data[ i_index * m_rows ] );
    > }
    >
    > template <typename w_Type, int w_columns, int w_rows>
    > matrix( const w_Type (&i_array)[w_columns][w_rows] )
    > : m_columns( w_columns ),
    > m_rows( w_rows ),
    > m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
    > {
    > }
    >
    > };
    >
    > #include <iostream>
    >
    > double array[3][4] = {
    > { 1.0, 2.0, 3.3, 4.4 },
    > { 1.0, 2.0, 3.3, 4.4 },
    > { 1.0, 2.0, 3.3, 4.5 },
    >
    > };
    >
    > int main()
    > {
    > matrix<float> mat1( 3, 4 );
    > matrix<float> mat2;
    > matrix<float> mat3( array );
    >
    > mat2 = mat3;
    >
    > std::cout << mat2[2][3] << "\n";
    >
    > }
     
    Peter Olcott, Nov 25, 2005
    #3
  4. Peter Olcott

    Peter Olcott Guest

    Oh yeah, I only need very fast addressing of the elements
    of the Matrix. I will likely be moving up or down matrix rows
    about five times as often as moving across matrix columns.

    "Gianni Mariani" <> wrote in message
    news:...
    > Peter Olcott wrote:
    >> I need to know how to get the solution mentioned below to work. The
    >> solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:
    >>
    >>
    >>>http://groups.google.com/group/comp.lang.c /msg/db577c43260a5310?hl
    >>>
    >>>Another way is to create a one dimensional array and handle the
    >>>indexing yourself (index = row * row_size + col). This is readily
    >>>implemented in template classes that can create dynamically allocated
    >>>multi-dimensional arrays of any element type and number of
    >>>dimensions.

    >>
    >>
    >> What would be the syntax for created a template that allowed a
    >> one dimensional dynamic array, to be addressed using the conventional
    >> syntax for accessing a two dimensional array? I am thinking that this
    >> must be some sort of operator[] overloading.

    >
    > http://groups.google.com/group/comp.lang.c/msg/909f01d9b4f1d9bd?hl=en&
    >
    > I knew I answered this once before - I think there is an FAQ as well..
    >
    > Here is the example code from that posting.
    >
    > #include <vector>
    >
    > template <typename w_elem_type>
    > class matrix
    > {
    > public:
    > typedef int t_Size;
    >
    > t_Size m_columns;
    > t_Size m_rows;
    >
    > std::vector<w_elem_type> m_data;
    >
    > matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
    > : m_columns( i_columns ),
    > m_rows( i_rows ),
    > m_data( i_columns * i_rows )
    > {
    > }
    >
    > w_elem_type * operator[]( t_Size i_index )
    > {
    > return & ( m_data[ i_index * m_rows ] );
    > }
    >
    > template <typename w_Type, int w_columns, int w_rows>
    > matrix( const w_Type (&i_array)[w_columns][w_rows] )
    > : m_columns( w_columns ),
    > m_rows( w_rows ),
    > m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
    > {
    > }
    >
    > };
    >
    > #include <iostream>
    >
    > double array[3][4] = {
    > { 1.0, 2.0, 3.3, 4.4 },
    > { 1.0, 2.0, 3.3, 4.4 },
    > { 1.0, 2.0, 3.3, 4.5 },
    >
    > };
    >
    > int main()
    > {
    > matrix<float> mat1( 3, 4 );
    > matrix<float> mat2;
    > matrix<float> mat3( array );
    >
    > mat2 = mat3;
    >
    > std::cout << mat2[2][3] << "\n";
    >
    > }
     
    Peter Olcott, Nov 25, 2005
    #4
  5. Peter Olcott wrote:
    > That looks like an excellent solution. I need absolutely top performance.
    > You mentioned :
    >
    > some extensive matrix libraries you could use
    > and ones that are very efficient if the dimensions
    > are known.
    >
    > Could you provide me a link or other reference to these?


    Google "C++ matrix" gives a plethora of answers. Quite a while ago I
    looked at some of these but I didn't get involved with the project so I
    can't give you any real feedback.

    What I mean by "dimensions are known" is "known at compile time". If
    they are known at compile time, you don't need to perform dynamic memory
    allocation and you can enable some usual compiler optimizations (like
    loop unrolling).

    For somthing like a 3D graphics library, this would be ideal since it
    predominantly uses a 4x4 matrices (Homogeneous Coordinates) and 1x4
    vectors and so much of the code can be unrolled and the compiler has a
    much better chance of optimizing it.

    See below, the matrix example now with the row and column sizes known.

    template <typename w_elem_type, unsigned w_rows, unsigned w_columns>
    class matrix
    {
    public:

    typedef w_elem_type value_type;
    static const unsigned m_columns = w_columns;
    static const unsigned m_rows = w_rows;

    value_type m_data[ m_rows ][ m_columns ];

    typedef w_elem_type row_value_type[ m_columns ];

    matrix()
    : m_data()
    {
    }

    row_value_type & operator[]( unsigned i_index )
    {
    return m_data[ i_index ];
    }

    template <typename w_elem_intype>
    matrix(
    const w_elem_intype (&i_array)[m_rows][m_columns]
    )
    {
    copy_matrix( i_array );
    }

    template <typename w_elem_intype>
    matrix(
    const matrix<w_elem_intype, m_rows, m_columns > & i_array
    )
    {
    copy_matrix( i_array.m_data );
    }

    template <typename w_elem_intype>
    matrix & operator=(
    const w_elem_intype (&i_array)[m_rows][m_columns]
    )
    {
    copy_matrix( i_array );
    return * this;
    }

    template <typename w_elem_intype>
    matrix & operator=(
    const matrix<w_elem_intype, m_rows, m_columns > & i_array
    )
    {
    copy_matrix( i_array.m_data );
    return * this;
    }

    private:

    template <typename w_elem_intype>
    void copy_matrix( w_elem_intype (&i_array)[m_rows][m_columns] )
    {
    w_elem_type * l_elem = & m_data[ 0 ][ 0 ];
    w_elem_intype * l_from = & i_array[ 0 ][ 0 ];

    for ( unsigned l_i = 0; l_i < m_columns * m_rows; ++ l_i )
    {
    l_elem[ l_i ] = l_from[ l_i ];
    }
    }

    };



    #include <iostream>

    double array[3][4] = {
    { 1.0, 2.0, 3.3, 4.4 },
    { 1.0, 2.0, 3.3, 4.4 },
    { 1.0, 2.0, 3.3, 4.5 },
    };

    int main()
    {
    matrix<float, 3, 4> mat1;
    matrix<float, 3, 4> mat2;
    matrix<float, 3, 4> mat3( array );

    mat2 = mat3;

    matrix<double, 3, 4> mat2d = mat2;
    mat2d = mat3;

    std::cout << mat2[2][3] << "\n";
    }
     
    Gianni Mariani, Nov 25, 2005
    #5
  6. Peter Olcott

    Peter Olcott Guest

    I tested the performance of the code below and it took 150 ms,
    as opposed to 4.5 ms for a conventional two dimensional array.
    I am going to work on making a faster version tonight. I am
    guessing that it might have to have a kludge interface:
    void SetData(int ROW, int COL, UINT Data);
    UINT GetData(int ROW, int COL);

    "Gianni Mariani" <> wrote in message
    news:...
    > Peter Olcott wrote:
    >> I need to know how to get the solution mentioned below to work. The
    >> solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:
    >>
    >>
    >>>http://groups.google.com/group/comp.lang.c /msg/db577c43260a5310?hl
    >>>
    >>>Another way is to create a one dimensional array and handle the
    >>>indexing yourself (index = row * row_size + col). This is readily
    >>>implemented in template classes that can create dynamically allocated
    >>>multi-dimensional arrays of any element type and number of
    >>>dimensions.

    >>
    >>
    >> What would be the syntax for created a template that allowed a
    >> one dimensional dynamic array, to be addressed using the conventional
    >> syntax for accessing a two dimensional array? I am thinking that this
    >> must be some sort of operator[] overloading.

    >
    > http://groups.google.com/group/comp.lang.c/msg/909f01d9b4f1d9bd?hl=en&
    >
    > I knew I answered this once before - I think there is an FAQ as well..
    >
    > Here is the example code from that posting.
    >
    > #include <vector>
    >
    > template <typename w_elem_type>
    > class matrix
    > {
    > public:
    > typedef int t_Size;
    >
    > t_Size m_columns;
    > t_Size m_rows;
    >
    > std::vector<w_elem_type> m_data;
    >
    > matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
    > : m_columns( i_columns ),
    > m_rows( i_rows ),
    > m_data( i_columns * i_rows )
    > {
    > }
    >
    > w_elem_type * operator[]( t_Size i_index )
    > {
    > return & ( m_data[ i_index * m_rows ] );
    > }
    >
    > template <typename w_Type, int w_columns, int w_rows>
    > matrix( const w_Type (&i_array)[w_columns][w_rows] )
    > : m_columns( w_columns ),
    > m_rows( w_rows ),
    > m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
    > {
    > }
    >
    > };
    >
    > #include <iostream>
    >
    > double array[3][4] = {
    > { 1.0, 2.0, 3.3, 4.4 },
    > { 1.0, 2.0, 3.3, 4.4 },
    > { 1.0, 2.0, 3.3, 4.5 },
    >
    > };
    >
    > int main()
    > {
    > matrix<float> mat1( 3, 4 );
    > matrix<float> mat2;
    > matrix<float> mat3( array );
    >
    > mat2 = mat3;
    >
    > std::cout << mat2[2][3] << "\n";
    >
    > }
     
    Peter Olcott, Nov 25, 2005
    #6
  7. Peter Olcott

    Peter Olcott Guest

    #define UINT unsigned int
    const int Width = 3000;
    const int Height = 2000;
    UINT Array01[Width][Height];
    ArrayType2D Array02;
    UINT Array03[Width][Height];


    class ArrayType2D {
    private:
    UINT* Array;
    int last_row;
    public:
    ArrayType2D(){ Array = new UINT [Width * Height]; };
    ~ArrayType2D(){ delete [] Array; };
    UINT operator[](int N){ return Array[N]; };
    void SetRow(int ROW) { last_row = ROW * Width; };
    UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
    UINT GetPixel(int COL){ return Array[last_row + COL]; }
    void SetPixel(int COL, UINT DATA){ Array[last_row + COL] = DATA; }
    void SetPixel(int ROW, int COL, UINT DATA){ Array[(ROW * Width) + COL] = DATA; }
    };

    void Test04(int HEIGHT, int WIDTH) {
    for (int ROW = 0; ROW < HEIGHT; ROW++) {
    Array02.SetRow(ROW);
    for (int COL = 0; COL < WIDTH; COL++)
    Array03[ROW][COL] = Array02.GetPixel(COL);
    }
    }

    The above code accesses a dynamic two-dimensional array
    about fifteen percent faster than a conventional two-dimensional
    array is accessed, if the data is to be accessed in the order
    specified, moving through all the columns in a row, and then
    moving to the next row. If the data is to accessed in a different
    order such as moving through all the rows, and then moving to
    the next column, the above code would need to be adapted.
    Also one must make sure that the data is stored in the single
    dimension array in the order corresponding to this different
    access order.

    Now if I could only have the following function
    UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
    work with conventional Array02[ROW][COL] syntax, and find a way
    to make it at least as fast as conventional array access (right now it is only
    57% as fast), then I would be happier.



    "Gianni Mariani" <> wrote in message news:...
    > Peter Olcott wrote:
    >> I need to know how to get the solution mentioned below to work. The
    >> solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:
    >>
    >>
    >>>http://groups.google.com/group/comp.lang.c /msg/db577c43260a5310?hl
    >>>
    >>>Another way is to create a one dimensional array and handle the
    >>>indexing yourself (index = row * row_size + col). This is readily
    >>>implemented in template classes that can create dynamically allocated
    >>>multi-dimensional arrays of any element type and number of
    >>>dimensions.

    >>
    >>
    >> What would be the syntax for created a template that allowed a
    >> one dimensional dynamic array, to be addressed using the conventional
    >> syntax for accessing a two dimensional array? I am thinking that this
    >> must be some sort of operator[] overloading.

    >
    > http://groups.google.com/group/comp.lang.c/msg/909f01d9b4f1d9bd?hl=en&
    >
    > I knew I answered this once before - I think there is an FAQ as well..
    >
    > Here is the example code from that posting.
    >
    > #include <vector>
    >
    > template <typename w_elem_type>
    > class matrix
    > {
    > public:
    > typedef int t_Size;
    >
    > t_Size m_columns;
    > t_Size m_rows;
    >
    > std::vector<w_elem_type> m_data;
    >
    > matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
    > : m_columns( i_columns ),
    > m_rows( i_rows ),
    > m_data( i_columns * i_rows )
    > {
    > }
    >
    > w_elem_type * operator[]( t_Size i_index )
    > {
    > return & ( m_data[ i_index * m_rows ] );
    > }
    >
    > template <typename w_Type, int w_columns, int w_rows>
    > matrix( const w_Type (&i_array)[w_columns][w_rows] )
    > : m_columns( w_columns ),
    > m_rows( w_rows ),
    > m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
    > {
    > }
    >
    > };
    >
    > #include <iostream>
    >
    > double array[3][4] = {
    > { 1.0, 2.0, 3.3, 4.4 },
    > { 1.0, 2.0, 3.3, 4.4 },
    > { 1.0, 2.0, 3.3, 4.5 },
    >
    > };
    >
    > int main()
    > {
    > matrix<float> mat1( 3, 4 );
    > matrix<float> mat2;
    > matrix<float> mat3( array );
    >
    > mat2 = mat3;
    >
    > std::cout << mat2[2][3] << "\n";
    >
    > }
     
    Peter Olcott, Nov 26, 2005
    #7
  8. Peter Olcott wrote:
    > #define UINT unsigned int

    Use a typedef here - avoid macros where possible
    typedef unsigned int UINT;
    > const int Width = 3000;
    > const int Height = 2000;

    these could be template parameters.

    > UINT Array01[Width][Height];
    > ArrayType2D Array02;
    > UINT Array03[Width][Height];
    >
    >
    > class ArrayType2D {
    > private:
    > UINT* Array;
    > int last_row;
    > public:


    // oops - using the default copy constructor - will cause
    // delete [] Array to be called multiple times (and leak)
    // if the array is ever copied. (same goes for assignment
    // operator.)

    > ArrayType2D(){ Array = new UINT [Width * Height]; };
    > ~ArrayType2D(){ delete [] Array; };
    > UINT operator[](int N){ return Array[N]; };
    > void SetRow(int ROW) { last_row = ROW * Width; };
    > UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
    > UINT GetPixel(int COL){ return Array[last_row + COL]; }
    > void SetPixel(int COL, UINT DATA){ Array[last_row + COL] = DATA; }
    > void SetPixel(int ROW, int COL, UINT DATA){ Array[(ROW * Width) + COL] = DATA; }
    > };
    >
    > void Test04(int HEIGHT, int WIDTH) {
    > for (int ROW = 0; ROW < HEIGHT; ROW++) {
    > Array02.SetRow(ROW);
    > for (int COL = 0; COL < WIDTH; COL++)
    > Array03[ROW][COL] = Array02.GetPixel(COL);
    > }
    > }
    >
    > The above code accesses a dynamic two-dimensional array
    > about fifteen percent faster than a conventional two-dimensional
    > array is accessed, if the data is to be accessed in the order
    > specified, moving through all the columns in a row, and then
    > moving to the next row. If the data is to accessed in a different
    > order such as moving through all the rows, and then moving to
    > the next column, the above code would need to be adapted.
    > Also one must make sure that the data is stored in the single
    > dimension array in the order corresponding to this different
    > access order.
    >
    > Now if I could only have the following function
    > UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
    > work with conventional Array02[ROW][COL] syntax, and find a way
    > to make it at least as fast as conventional array access (right now it is only
    > 57% as fast), then I would be happier.
    >


    Did you check out the last example I posted ? Since you know the size
    of your array at compile time, you can use somthing like that. On a
    good optimizing compiler, this one would be just about as fast at copies
    as you can get.

    Is the Test04 function the only test you want ?

    SetRow buys you very little in terms of performance (as implemented).
     
    Gianni Mariani, Nov 26, 2005
    #8
  9. Peter Olcott

    Guest

    , Nov 26, 2005
    #9
  10. Peter Olcott

    Peter Olcott Guest

    "Gianni Mariani" <> wrote in message news:...
    > Peter Olcott wrote:
    >> #define UINT unsigned int

    > Use a typedef here - avoid macros where possible
    > typedef unsigned int UINT;
    >> const int Width = 3000;
    >> const int Height = 2000;

    > these could be template parameters.
    >
    >> UINT Array01[Width][Height];
    >> ArrayType2D Array02;
    >> UINT Array03[Width][Height];
    >>
    >>
    >> class ArrayType2D {
    >> private:
    >> UINT* Array;
    >> int last_row;
    >> public:

    >
    > // oops - using the default copy constructor - will cause
    > // delete [] Array to be called multiple times (and leak)
    > // if the array is ever copied. (same goes for assignment
    > // operator.)
    >
    >> ArrayType2D(){ Array = new UINT [Width * Height]; };
    >> ~ArrayType2D(){ delete [] Array; };
    >> UINT operator[](int N){ return Array[N]; };
    >> void SetRow(int ROW) { last_row = ROW * Width; };
    >> UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
    >> UINT GetPixel(int COL){ return Array[last_row + COL]; }
    >> void SetPixel(int COL, UINT DATA){ Array[last_row + COL] = DATA; }
    >> void SetPixel(int ROW, int COL, UINT DATA){ Array[(ROW * Width) + COL] = DATA; }
    >> };
    >>
    >> void Test04(int HEIGHT, int WIDTH) {
    >> for (int ROW = 0; ROW < HEIGHT; ROW++) {
    >> Array02.SetRow(ROW);
    >> for (int COL = 0; COL < WIDTH; COL++)
    >> Array03[ROW][COL] = Array02.GetPixel(COL);
    >> }
    >> }
    >>
    >> The above code accesses a dynamic two-dimensional array
    >> about fifteen percent faster than a conventional two-dimensional
    >> array is accessed, if the data is to be accessed in the order
    >> specified, moving through all the columns in a row, and then
    >> moving to the next row. If the data is to accessed in a different
    >> order such as moving through all the rows, and then moving to
    >> the next column, the above code would need to be adapted.
    >> Also one must make sure that the data is stored in the single
    >> dimension array in the order corresponding to this different
    >> access order.
    >>
    >> Now if I could only have the following function
    >> UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
    >> work with conventional Array02[ROW][COL] syntax, and find a way
    >> to make it at least as fast as conventional array access (right now it is only
    >> 57% as fast), then I would be happier.
    >>

    >
    > Did you check out the last example I posted ? Since you know the size of your array at compile time, you can use somthing like
    > that. On a


    I know it at run time, not compile time. I will take your other
    suggestion (above) and repost an updated copy. The current
    version seems to work just as fast as the build-in matrix, and
    only lacks conventional double operator[] syntax~~~~>Data[row][col]
    the next poster posted material that I will study on this. Thanks for all
    your help.


    > good optimizing compiler, this one would be just about as fast at copies as you can get.
    >
    > Is the Test04 function the only test you want ?
    >
    > SetRow buys you very little in terms of performance (as implemented).
    >
     
    Peter Olcott, Nov 26, 2005
    #10
  11. Peter Olcott

    Peter Olcott Guest

    "Gianni Mariani" <> wrote in message news:...
    > // oops - using the default copy constructor - will cause
    > // delete [] Array to be called multiple times (and leak)
    > // if the array is ever copied. (same goes for assignment
    > // operator.)


    //
    // Array2D.h 2005-11-26 9:32 AM
    //
    #define UINT unsigned int
    //
    class ArrayType2D {
    private:
    int Size;
    int Width;
    int Height;
    UINT* Array;
    bool Allocated;
    void Copy(ArrayType2D& Array2);
    public:
    ArrayType2D();
    ArrayType2D(ArrayType2D& Array2) { Copy(Array2); };
    ~ArrayType2D() { if (Allocated) delete [] Array; };
    UINT operator[](int N) { return Array[N]; };
    ArrayType2D& operator=(ArrayType2D& Array2) { Copy(Array2); return *this; };
    UINT* operator&() { return Array; };
    UINT Get(int ROW, int COL) { return Array[ROW * Width + COL]; };
    void Set(int ROW, int COL, UINT DATA) { Array[ROW * Width + COL] = DATA; }
    const int size() { return Size; };
    const int width() { return Width; };
    const int height() { return Height; };
    void Allocate(int Height, int Width);
    };

    void ArrayType2D::Copy(ArrayType2D& Array2) {
    if (this->Allocated)
    delete [] Array;
    this->Width = Array2.Width;
    this->Height = Array2.Height;
    this->Size = Array2.Size;;
    this->Array = new UINT [this->Size];
    }

    ArrayType2D::ArrayType2D() {
    Size = 0;
    Width = 0;
    Height = 0;
    Array = NULL;
    Allocated = false;
    }

    inline void ArrayType2D::Allocate(int Height, int Width) {
    if (Allocated)
    delete [] Array;
    this->Width = Width;
    this->Height = Height;
    this->Size = Width * Height;
    this->Array = new UINT [Size];
    }
     
    Peter Olcott, Nov 26, 2005
    #11
  12. Peter Olcott

    Peter Olcott Guest

    This was very helpful. Not only did it provide an excellent solution,
    it also analyzed all of my alternatives. If you want very high speed
    and ease of use, on creating a multi-dimensional array from dynamic
    memory, operator() is the way to go. I will post my latest update
    shortly.

    <> wrote in message news:...
    >
    > Gianni Mariani wrote:
    >
    >> w_elem_type * operator[]( t_Size i_index )
    >> {
    >> return & ( m_data[ i_index * m_rows ] );
    >> }

    >
    > This FAQ entry might be of interest:
    > http://www.parashift.com/c -faq-lite/operator-overloading.html#faq-13.11
    >
    > See also 13.10 right above it.
    >
     
    Peter Olcott, Nov 27, 2005
    #12
  13. Peter Olcott

    Peter Olcott Guest

    I goofed your code works perfectly.
    I could not get the last function to compile on MSVC++ 6.0,
    but after I stripped this function out and properly benchmarked
    the speed it was superb. It exactly matched a statically defined
    matrix. Also I got to use the double operator[], that I wanted.
    Because of these reasons, I must say that your code is the best
    possible code according to any possible criterion measure of
    a method to create a dynamically allocated two-dimensional array.

    matrix.cpp
    matrix.cpp(27) : error C2265: '<Unknown>' : reference to a zero-sized array is illegal
    matrix.cpp(34) : see reference to class template instantiation 'matrix<w_elem_type>' being compiled
    matrix.cpp(27) : error C2265: '<Unknown>' : reference to a zero-sized array is illegal
    matrix.cpp(47) : see reference to class template instantiation 'matrix<float>' being compiled
    matrix.cpp(27) : error C2087: '<Unknown>' : missing subscript
    matrix.cpp(47) : see reference to class template instantiation 'matrix<float>' being compiled
    matrix.cpp(49) : error C2664: '__thiscall matrix<float>::matrix<float>(int,int)' : cannot convert parameter 1 from 'double [3][4]'
    to 'int'
    This conversion requires a reinterpret_cast, a C-style cast or function-style cast
    matrix.cpp(55) : warning C4508: 'main' : function should return a value; 'void' return type assumed


    #include <vector> // Line (1) of matrix.cpp identical copy of your code

    template <typename w_elem_type>
    class matrix
    {
    public:
    typedef int t_Size;

    t_Size m_columns;
    t_Size m_rows;

    std::vector<w_elem_type> m_data;

    matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
    : m_columns( i_columns ),
    m_rows( i_rows ),
    m_data( i_columns * i_rows )
    {
    }

    w_elem_type * operator[]( t_Size i_index )
    {
    return & ( m_data[ i_index * m_rows ] );
    }

    template <typename w_Type, int w_columns, int w_rows>
    matrix( const w_Type (&i_array)[w_columns][w_rows] )
    : m_columns( w_columns ),
    m_rows( w_rows ),
    m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
    {
    }

    };

    #include <iostream>

    double array[3][4] = {
    { 1.0, 2.0, 3.3, 4.4 },
    { 1.0, 2.0, 3.3, 4.4 },
    { 1.0, 2.0, 3.3, 4.5 },

    };

    int main()
    {
    matrix<float> mat1( 3, 4 );
    matrix<float> mat2;
    matrix<float> mat3( array );

    mat2 = mat3;

    std::cout << mat2[2][3] << "\n";

    }
     
    Peter Olcott, Nov 27, 2005
    #13
  14. Peter Olcott

    Peter Olcott Guest

    "Gianni Mariani" <> wrote in message news:...
    > Peter Olcott wrote:
    >> I goofed your code works perfectly.
    >> I could not get the last function to compile on MSVC++ 6.0,

    >
    > MSCV6 is ancient. Do you "have to" use it ?


    Currently yes. The performance of your code is superb and
    allows me to accomplish my execution well within my real-time
    constraints. I am posting my adaptations to your code below.
    All that I did is add a little more functionality.

    >
    >> but after I stripped this function out and properly benchmarked

    >
    > It seems like it's picking the wrong vector constructor. I think there is another constructor vector( pointer, size ) that you
    > could use.
    >
    >> the speed it was superb. It exactly matched a statically defined
    >> matrix. Also I got to use the double operator[], that I wanted.
    >> Because of these reasons, I must say that your code is the best
    >> possible code according to any possible criterion measure of
    >> a method to create a dynamically allocated two-dimensional array.

    >
    > Good luck !


    //
    // Matrix.h 2005-11-27 11:45 AM Dynamic Two-Dimensional Array Template
    //
    // comp.lang.c++ message from Gianni Mariani Nov 24, 2005 at 9:21 pm
    // http://groups.google.com/group/comp.lang.c /msg/a9092f0f6c9bf13a
    // Adapted by Peter Olcott resize() and operator&() added.
    //
    #include <vector>

    template <typename w_elem_type>
    class matrix
    {
    public:
    typedef int t_Size;

    t_Size m_rows;
    t_Size m_columns;

    std::vector<w_elem_type> m_data;

    matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
    : m_columns( i_columns ),
    m_rows( i_rows ),
    m_data( i_columns * i_rows )
    {
    }

    w_elem_type* operator&(){ return &m_data[0]; };

    void resize( t_Size i_columns, t_Size i_rows );

    w_elem_type * operator[]( t_Size i_index ) {
    return & ( m_data[ i_index * m_rows ] );
    }

    };

    template <typename w_elem_type>
    void matrix<w_elem_type>::resize( t_Size i_columns, t_Size i_rows ) {
    m_rows = i_rows;
    m_columns = i_columns;
    m_data.resize(i_columns * i_rows );
    }
     
    Peter Olcott, Nov 27, 2005
    #14
  15. wrote:
    > Gianni Mariani wrote:
    >
    >
    >> w_elem_type * operator[]( t_Size i_index )
    >> {
    >> return & ( m_data[ i_index * m_rows ] );
    >> }

    >
    >
    > This FAQ entry might be of interest:
    > http://www.parashift.com/c -faq-lite/operator-overloading.html#faq-13.11
    >
    > See also 13.10 right above it.
    >


    That FAQ is a classic case of premature optimization.

    It's quite easy to turn [A] into (A,B) with no loss of performance
    (on a good optimizing compiler). Also, the compiler probably has built
    in optimizations that know how to deal with stride and may get confused
    when dealing with (A,B) like functor calls.

    Give me an example where [A] is slower than (A,B) (using an decent
    optimizer) and we'll see if we can fix it. Otherwise I declare the FAQ
    hogwash.
     
    Gianni Mariani, Nov 27, 2005
    #15
  16. Peter Olcott wrote:
    > I goofed your code works perfectly.
    > I could not get the last function to compile on MSVC++ 6.0,


    MSCV6 is ancient. Do you "have to" use it ?

    > but after I stripped this function out and properly benchmarked


    It seems like it's picking the wrong vector constructor. I think there
    is another constructor vector( pointer, size ) that you could use.

    > the speed it was superb. It exactly matched a statically defined
    > matrix. Also I got to use the double operator[], that I wanted.
    > Because of these reasons, I must say that your code is the best
    > possible code according to any possible criterion measure of
    > a method to create a dynamically allocated two-dimensional array.


    Good luck !
     
    Gianni Mariani, Nov 27, 2005
    #16
  17. Peter Olcott

    Guest

    Gianni Mariani wrote:
    > wrote:
    > > Gianni Mariani wrote:
    > >
    > >
    > >> w_elem_type * operator[]( t_Size i_index )
    > >> {
    > >> return & ( m_data[ i_index * m_rows ] );
    > >> }

    > >
    > >
    > > This FAQ entry might be of interest:
    > > http://www.parashift.com/c -faq-lite/operator-overloading.html#faq-13.11
    > >
    > > See also 13.10 right above it.
    > >

    >
    > That FAQ is a classic case of premature optimization.
    >
    > It's quite easy to turn [A] into (A,B) with no loss of performance
    > (on a good optimizing compiler).


    Oh really??!! Tell me then, how exactly is the compiler going to hide
    the internal representiation of the matrix when you have exposed it
    with the first [] operator??!! How is the compiler going to decide to
    use column major instead of row major, or visa-versa, when it is the
    better way to represent the matrix for the particular needs, when you
    have created a dependency on row major by using the [] operator to
    return rows??!!

    Hint: the compiler cannot do anything to change your algorithms to a
    more optomized nature for the problem you want to solve, especially
    when you have created such dependencies. In fact, with your function
    there not even the programmer can. Since this is perfectly laid out in
    the FAQ I have to assume you never read it and/or totally missed the
    point.

    Also, the compiler probably has built
    > in optimizations that know how to deal with stride and may get confused
    > when dealing with (A,B) like functor calls.


    Hogwash. Assuming that op[][] and (x,y) would operate in the same
    manner (meaning () just returned [][]) then at worst you have an inline
    function call to [A+B] on your internal array. There is 0 performance
    hit there (unless maybe you are in debug mode on some compilers) and
    there is absolutely no difference to the compiler whatsoever.

    As the FAQ says, there is never a time when () is worst than [][].

    What exactly do you think the diff is between [] and () that would make
    you think the compiler would get more confused over one vs. the other?

    >
    > Give me an example where [A] is slower than (A,B) (using an decent
    > optimizer) and we'll see if we can fix it.


    Go back and read the FAQ - it gives just such an example. Also keep
    the definition of the word, "encapsulation," in mind as you read it and
    try to realize what you have done by tossing out &vector[x] to
    artificially create [x][y]. I mean, why even offer the protection of
    the class boundary if you are going to bypass it like that??!!

    Hint: not only have you created a dependency on the internals of your
    own class in a rather icky way you have created a dependency on how the
    std::vector class is implemented. It is highly unlikely to be
    implemented in any other way but the standard does not guarantee that
    behavior. Point is that dependencies now exist that never should exist
    in a well structured program; these are the things that create code rot
    right off the bat.

    Otherwise I declare the FAQ
    > hogwash.


    That is of course your own perogative. A smarter person, however,
    might decide to learn from it. I really doubt you actually read that
    FAQ and comprehended what it was saying because the things you are
    saying don't leave much doubt.
     
    , Nov 27, 2005
    #17
  18. Peter Olcott

    Kai-Uwe Bux Guest

    wrote:

    >
    > Gianni Mariani wrote:
    >> wrote:
    >> > Gianni Mariani wrote:
    >> >
    >> >
    >> >> w_elem_type * operator[]( t_Size i_index )
    >> >> {
    >> >> return & ( m_data[ i_index * m_rows ] );
    >> >> }
    >> >
    >> >
    >> > This FAQ entry might be of interest:
    >> >

    http://www.parashift.com/c -faq-lite/operator-overloading.html#faq-13.11
    >> >
    >> > See also 13.10 right above it.
    >> >

    >>
    >> That FAQ is a classic case of premature optimization.
    >>
    >> It's quite easy to turn [A] into (A,B) with no loss of performance
    >> (on a good optimizing compiler).

    >
    > Oh really??!! Tell me then, how exactly is the compiler going to hide
    > the internal representiation of the matrix when you have exposed it
    > with the first [] operator??!! How is the compiler going to decide to
    > use column major instead of row major, or visa-versa, when it is the
    > better way to represent the matrix for the particular needs, when you
    > have created a dependency on row major by using the [] operator to
    > return rows??!!


    The FAQ makes the claim that the [][] interface is less flexible. This is
    *not* true in general. The FAQ somehow seems to assume that the only way of
    realizing the [][] interface is that operator[] returns an array or
    something similar that exposes the internal representation of the matrix
    class. However, you do not need to expose the internal representation at
    all. The most easy way of doing this, would probably be a proxy:

    struct matrix {

    typedef unsigned long size_type;

    int& operator() ( size_type row, size_type col ) {
    return ( whatever(row,col) );
    }

    struct row_proxy {

    matrix & the_matrix;
    size_type the_row;

    row_proxy ( matrix & A, size_type r )
    : the_matrix ( A )
    , the_row ( r )
    {}

    int& operator[] ( size_type col ) {
    return( the_matrix.whatever(the_row,col) );
    }

    };

    row_proxy operator[] ( size_type row ) {
    return( row_proxy( *this, row ) );
    }

    // some internal representation to implement whatever goes here:
    // ...

    }; // matrix


    Note that in expressions like A[row][col], the proxy should be optimized
    away be a moderately smart optimizing compiler.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Nov 27, 2005
    #18
  19. Peter Olcott

    Guest

    Kai-Uwe Bux wrote:
    > wrote:
    >
    > >
    > > Gianni Mariani wrote:
    > >> wrote:
    > >> > Gianni Mariani wrote:
    > >> >
    > >> >
    > >> >> w_elem_type * operator[]( t_Size i_index )
    > >> >> {
    > >> >> return & ( m_data[ i_index * m_rows ] );
    > >> >> }
    > >> >
    > >> >
    > >> > This FAQ entry might be of interest:
    > >> >

    > http://www.parashift.com/c -faq-lite/operator-overloading.html#faq-13.11
    > >> >
    > >> > See also 13.10 right above it.
    > >> >
    > >>
    > >> That FAQ is a classic case of premature optimization.
    > >>
    > >> It's quite easy to turn [A] into (A,B) with no loss of performance
    > >> (on a good optimizing compiler).

    > >
    > > Oh really??!! Tell me then, how exactly is the compiler going to hide
    > > the internal representiation of the matrix when you have exposed it
    > > with the first [] operator??!! How is the compiler going to decide to
    > > use column major instead of row major, or visa-versa, when it is the
    > > better way to represent the matrix for the particular needs, when you
    > > have created a dependency on row major by using the [] operator to
    > > return rows??!!

    >
    > The FAQ makes the claim that the [][] interface is less flexible. This is
    > *not* true in general. The FAQ somehow seems to assume that the only way of
    > realizing the [][] interface is that operator[] returns an array or
    > something similar that exposes the internal representation of the matrix
    > class.


    As is done in the above code.

    However, you do not need to expose the internal representation at
    > all. The most easy way of doing this, would probably be a proxy:
    >
    > struct matrix {
    >
    > typedef unsigned long size_type;
    >
    > int& operator() ( size_type row, size_type col ) {
    > return ( whatever(row,col) );
    > }
    >
    > struct row_proxy {
    >
    > matrix & the_matrix;
    > size_type the_row;
    >
    > row_proxy ( matrix & A, size_type r )
    > : the_matrix ( A )
    > , the_row ( r )
    > {}
    >
    > int& operator[] ( size_type col ) {
    > return( the_matrix.whatever(the_row,col) );
    > }
    >
    > };
    >
    > row_proxy operator[] ( size_type row ) {
    > return( row_proxy( *this, row ) );
    > }
    >
    > // some internal representation to implement whatever goes here:
    > // ...
    >
    > }; // matrix


    That is an aweful lot of work just to get a particular syntax that just
    ends up using the equivilant of (x,y).
    >
    >
    > Note that in expressions like A[row][col], the proxy should be optimized
    > away be a moderately smart optimizing compiler.


    Are you sure? Have you tested this theory of yours with your own
    compiler? I think you are expecting rather a lot from your compiler if
    you expect that it will actually optimize out objects you tell it to
    create; even more if you expect all compilers to do so. You could be
    right but honestly that seems like a lot to expect, especially when the
    alternative answer (different syntax, no proxy) is much more easily
    optimized away and is already much more optimized than your answer
    without any intelligence on behalf of the compiler.

    IMO there is a balance that you need to achieve between being overly
    agressive with your optimizations and depending on the compiler to do
    your work for you. Adding a bunch of unnecissary code and objects to
    create a specific syntax and expecting the compiler to just magically
    get rid of it all is a little to far into the later area for me.
     
    , Nov 27, 2005
    #19
  20. Peter Olcott

    Kai-Uwe Bux Guest

    wrote:

    >
    > Kai-Uwe Bux wrote:
    >> wrote:
    >>
    >> >
    >> > Gianni Mariani wrote:
    >> >> wrote:
    >> >> > Gianni Mariani wrote:
    >> >> >
    >> >> >
    >> >> >> w_elem_type * operator[]( t_Size i_index )
    >> >> >> {
    >> >> >> return & ( m_data[ i_index * m_rows ] );
    >> >> >> }
    >> >> >
    >> >> >
    >> >> > This FAQ entry might be of interest:
    >> >> >

    >> http://www.parashift.com/c -faq-lite/operator-overloading.html#faq-13.11
    >> >> >
    >> >> > See also 13.10 right above it.
    >> >> >
    >> >>
    >> >> That FAQ is a classic case of premature optimization.
    >> >>
    >> >> It's quite easy to turn [A] into (A,B) with no loss of performance
    >> >> (on a good optimizing compiler).
    >> >
    >> > Oh really??!! Tell me then, how exactly is the compiler going to hide
    >> > the internal representiation of the matrix when you have exposed it
    >> > with the first [] operator??!! How is the compiler going to decide to
    >> > use column major instead of row major, or visa-versa, when it is the
    >> > better way to represent the matrix for the particular needs, when you
    >> > have created a dependency on row major by using the [] operator to
    >> > return rows??!!

    >>
    >> The FAQ makes the claim that the [][] interface is less flexible. This is
    >> *not* true in general. The FAQ somehow seems to assume that the only way
    >> of realizing the [][] interface is that operator[] returns an array or
    >> something similar that exposes the internal representation of the matrix
    >> class.

    >
    > As is done in the above code.


    True, but somewhat irrelevant. The FAQ item 13.11 does not specifically talk
    about the *above code*. Also, I do not read the claim

    >> >> It's quite easy to turn [A] into (A,B) with no loss of performance
    >> >> (on a good optimizing compiler).


    as a claim about the particular implementation given up the thread.


    > However, you do not need to expose the internal representation at
    >> all. The most easy way of doing this, would probably be a proxy:
    >>
    >> struct matrix {
    >>
    >> typedef unsigned long size_type;
    >>
    >> int& operator() ( size_type row, size_type col ) {
    >> return ( whatever(row,col) );
    >> }
    >>
    >> struct row_proxy {
    >>
    >> matrix & the_matrix;
    >> size_type the_row;
    >>
    >> row_proxy ( matrix & A, size_type r )
    >> : the_matrix ( A )
    >> , the_row ( r )
    >> {}
    >>
    >> int& operator[] ( size_type col ) {
    >> return( the_matrix.whatever(the_row,col) );
    >> }
    >>
    >> };
    >>
    >> row_proxy operator[] ( size_type row ) {
    >> return( row_proxy( *this, row ) );
    >> }
    >>
    >> // some internal representation to implement whatever goes here:
    >> // ...
    >>
    >> }; // matrix

    >
    > That is an aweful lot of work just to get a particular syntax that just
    > ends up using the equivilant of (x,y).


    Actually, one would need to do a little more to support const correct
    programming. I just wanted to illustrate the concept.

    However, that does not invalidate the point that [][] does not, in itself,
    make a commitment to exposing the internals of a matrix class.


    >> Note that in expressions like A[row][col], the proxy should be
    >> optimized away be a moderately smart optimizing compiler.

    >
    > Are you sure? Have you tested this theory of yours with your own
    > compiler?


    As I discovered, this is not a theory of mine: actually it is a theory in
    the FAQ. See 13.12, last paragraph. (It so happens, that the FAQ actually
    covers the proxy approach. I did realize that after writing the message. So
    the FAQ is not really off base. I guess, its author chose a policy of
    stepwise refinement in the exposition.)

    > I think you are expecting rather a lot from your compiler if
    > you expect that it will actually optimize out objects you tell it to
    > create; even more if you expect all compilers to do so. You could be
    > right but honestly that seems like a lot to expect, especially when the
    > alternative answer (different syntax, no proxy) is much more easily
    > optimized away and is already much more optimized than your answer
    > without any intelligence on behalf of the compiler.


    I think that optimizing away redundant temporary object presents no problem
    if the functions returning/creating these objects are inlined. After
    inlining, everything boils down to a local data flow analysis problem
    essentially on par with any other redundant code removal, e.g., removing
    unused local variables.


    > IMO there is a balance that you need to achieve between being overly
    > agressive with your optimizations and depending on the compiler to do
    > your work for you. Adding a bunch of unnecissary code and objects to
    > create a specific syntax and expecting the compiler to just magically
    > get rid of it all is a little to far into the later area for me.


    Now, we are down to real design considerations. I tend to agree with you.
    Personally, I would provide [][] only for interfacing with other code that
    needs it.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Nov 28, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alf P. Steinbach
    Replies:
    0
    Views:
    436
    Alf P. Steinbach
    Aug 18, 2003
  2. John Harrison
    Replies:
    4
    Views:
    6,928
    Default User
    Aug 19, 2003
  3. Icosahedron
    Replies:
    8
    Views:
    657
    Vivek
    Aug 21, 2003
  4. Kev Jackson
    Replies:
    2
    Views:
    114
  5. Wirianto Djunaidi
    Replies:
    2
    Views:
    203
    Wirianto Djunaidi
    Apr 29, 2008
Loading...

Share This Page