1

I am developing a 4x4 matrix C++ class for my 3D geometry library. I am a bit confused about how to represent the matrix data values in a more efficient way.

That's because The Matrix and Quaternions FAQ says:

Using two dimensional arrays also incurs a CPU performance penalty in that C compilers will often make use of multiplication operations to resolve array index operations. So, it is more efficient to stick with linear arrays.

  1. Is access to multidimensional array are really that slow than to a linear array?
  2. Should I really prefer linear array over multidimensional to store 4x4 matrix data values?
ezpresso
  • 7,896
  • 13
  • 62
  • 94
  • At a minimum there are ways to generate poor locality of reference on them without it being obvious that you have done so. You *can* do that with 1D arrays, too, but are less likely to when writing naive code. – dmckee --- ex-moderator kitten Nov 06 '12 at 19:45
  • 1
    I've tested and came to conclusion: yes, linear arrays are faster (especially if some dimensions are power of two) and and it is easier to allocate memory for them (accessing isn't an issue too, you may define convenient macro). But you better do some tests by yourself. – J X Nov 06 '12 at 19:47
  • 1
    2D arrays are linear in memory. It depends on how you access it and your cache. Given array[i][j], if you have index i is the outter loop or inner performance will very. I forget how to get the best performance. – andre Nov 06 '12 at 20:09
  • If you have a fixed-size matrix, then using a two dimensional array is fine. The memory will be allocated just as efficiently as with a one dimensional array. It is true, that multiplications are involved to access an element, but that would be true for a one dimensional array as well, since you would need to use elements[i*n_cols+j]. – Vaughn Cato Nov 10 '12 at 15:09
  • Possible duplicate of [1D or 2D array, what's faster?](https://stackoverflow.com/questions/17259877/1d-or-2d-array-whats-faster) – Porcupine Sep 16 '17 at 10:25

2 Answers2

3

Most implementations I know use a 1D array with wrappers either via MACROS or methods to access the 2D data. I myself can't say which is faster and I can hardly see a case where this would really matter.

However this being said I would still recommend using 1D arrays for the following reasons:

  1. easier to allocate and release dynamically (If you want to allocate your data dynamically and maintain the matrix[i][j] pattern then you are allocating an array of arrays - slower to allocate more bug prone, you have to release each array separately)
  2. if you allocate dynamically and have to copy the data to a 3d party library say OpenGL or OpenCV you are into some trouble since they need the data to be contiguous.
  3. It will be easier to store and read the matrix from files or other persistent storage.
  4. even if you don't allocate dynamically you will have to do all sorts of ugly castings to handle the transfer of memory to 3d party libraries.
  5. it's super easy to create a structure with methods to have efficient 2d access to your data without multiplications or unclear indexing. Or for that matter use MACROS to encapsulate the ugly multiplications for you.
  6. You could even create a structure to look like the next sample and maintain the same benefits of a 1d array with the readability of a 2d array:

template<typename T>
struct Matrix4x4
{
    struct index
    {
        int row, col;
        index(int r = 0, int c = 0)
            : row(r), col(c){}
        index(index const & cp)
            : row(cp.row), col(cp.col)
        {
        }
        //Assignment ommited for brevity
    };
    /*
        Constructors, Assignments etc. ommited for brevity
    */
    T m00, m01, m02, m03;
    T m10, m11, m12, m13;
    T m20, m21, m22, m23;
    T m30, m31, m32, m33;

    T * toArray() const
    {
        return &m00;
    }
    T * toArray()
    {
        return &m00;
    }

    T * row(int r)
    {
        return (&m00) + r*4;
    }
    T * row(int r) const
    {
        return (&m00) + r*4;
    }

    T & operator()(int r, int c)
    {
        return *row(r)[c];
    }
    T const & operator()(int r, int c) const
    {
        return *row(r)[c];
    }

    T & operator[](index const & idx)
    {
        return row(idx.row)[idx.col];
    }
    T const & operator[](index const & idx) const
    {
        return row(idx.row)[idx.col];
    }

};

In your code you can do:

typedef Matrix4x4<double> Matrix4x4d;

Matrix4x4d mat;
/* You can do any of the following */
mat.m23 = 6.0;
mat(2,3) = 6.0;
mat[Matrix4x4d::index(2,3)] = 6.0;
mat.row(2)[3] = 6.0;
mat.toArray()[2*4 + 3] = 6.0;

#define M(m,r,c) (*((&m.m00) + r*4 + c))

M(mat,2,3) = 6.0;

I myself implemented several matrix libraries over the years and always opted for the 1d solution.

Sebastian Cabot
  • 1,812
  • 14
  • 18
0

You can store pointers to one-dimensional arrays in the first dimension, and then store one-dimensional arrays with length of your rows in the second dimension.

From what I recall, an indirection is less costly than a multiplication.

The syntax in accessing / editing the members is the same. The only difference is when you allocate / deallocate the array.

John
  • 15,990
  • 10
  • 70
  • 110
  • What you describe here is *not* a 2D array, it is a data structure often called a "ragged array" or "jagged array". Yes, you can access it with the same `[][]` syntax as a 2D array. None-the-less it is a distinct use of memory. – dmckee --- ex-moderator kitten Nov 06 '12 at 19:50
  • 1
    Ragged arrays are generally much more expensive than 2D arrays. While integer multiplication is a bit slower than addition, indirection is much, much slower. – David Hammen Nov 06 '12 at 19:53
  • What you say is correct. The OP can instantiate it and use it as if it were a plain-old 2D array, though. The memory allocation is transparent in that context. – John Nov 06 '12 at 19:54
  • @DavidHammen I guess I'm going on old information. I thought it was the opposite. – John Nov 06 '12 at 20:00
  • Indirection was faster in the 1960's. These days a memory access is much slower than a multiplication. – stark Nov 07 '12 at 01:20