c++ 3D matrix using vector poor performance

Question

hello all I was trying to convert this matlab code into c++. BTW can also use openCV.

 imageData = toolbox.bayer.ColorOrder.cat( imageData, 0, 3);

this is imageData before

1   2   3   4   5   6   7   8   9   10
11  12  13  14  15  16  17  18  19  20
21  22  23  24  25  26  27  28  29  30
31  32  33  34  35  36  37  38  39  40

this is image data after:

val(:,:,1) =

 1     3     5     7     9
21    23    25    27    29

val(:,:,2) =

 2     4     6     8    10
22    24    26    28    30

val(:,:,3) =

11    13    15    17    19
31    33    35    37    39

val(:,:,4) =

12    14    16    18    20
32    34    36    38    40

here is my c++ code I'm getting int** can't change that...

vector<vector<vector<double> > > Utilities::MatrixConcat(int **raw_frame, int _width, int _height)
{
    vector<vector<vector<double> > > imageData;
    imageData.resize(_height/2);
    for (int i = 0; i < _height/2; ++i) 
    {
        imageData[i].resize(_width/2);

        for (int j = 0; j < _width/2; ++j)
        {
            imageData[i][j].resize(4);
        }
    }
    //[x][y][0]
    for (int h = 0; h < _height/2; h++)
    {       
        for (int w = 0; w < _width/2; w++)
        {           
            imageData[h][w][0] = raw_frame[2*h][2*w];           
        }
    }
    //[x][y][1]
    for (int h = 0; h < _height/2; h++)
    {       
        for (int w = 0; w < _width/2; w++)
        {           
            imageData[h][w][1] = raw_frame[2*h][2*w+1];
        }
    }

    for (int h = 0; h < _height/2; h++)
    {       
        for (int w = 0; w < _width/2; w++)
        {           
            imageData[h][w][2] = raw_frame[2*h+1][2*w];
        }
    }

    for (int h = 0; h < _height/2; h++)
    {       
        for (int w = 0; w < _width/2; w++)
        {           
            imageData[h][w][3] = raw_frame[2*h+1][2*w+1];
        }
    }
return imageData;
}

My problem is that my matrix (not the one for testing) is 4000X3000 which means this function takes too long. can you explain what is taking so long and how can I optimize this?

I can use openCV as well to convert this 2D matrix into a 3D matrix.

Update:

here is the test i have built for getting the same result

int** gili = new int*[4];
    for (int i = 0; i < 4; i++)
    {
        gili[i] = new int[10];
    } 

    for (int i = 0,k=1; i < 4; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            gili[i][j] = k;
            k++;
        }
    }
    vector<vector<vector<double> > > imageData = Utilities::MatrixConcat(gili,10,4);

Answer 1

There are two problems with your code, the data structure and the access order.

Data structure
A vector of vectors of vectors is probably not the most efficient data structure, because each access via the index operators involves some degree of pointer chasing. This could be somewhat mitigated by using iterators (where possible) or you build a wrapper around a single vector/array that allows you to translate a three dimensional position into an index for that container.

A simple 3D matrix implementation could look like this:

class Matrix3D{
private:
    size_t sizeX, sizeY, sizeZ;
    std::vector<double> data;
    size_t getIdx(size_t x, size_t y, size_t z) const {
        return x + sizeX*y + sizeX*sizeY*z;
    }

public:
    Matrix3D(size_t X, size_t Y, size_t Z) :sizeX(X), sizeY(Y), sizeZ(Z),data(X*Y*Z){}
    double& operator()(size_t x, size_t y, size_t z){ return data[getIdx(x, y, z)]; }
    double operator() (size_t x, size_t y, size_t z) const{ return data[getIdx(x, y, z)]; }

    //arithmetic operators
};

Or if the dimensions are a compile time constant:

    template<size_t sizeX, size_t sizeY, size_t sizeZ>
class Matrix3D_ConstDim{
private:    
    std::unique_ptr<std::array<double,sizeX*sizeY*sizeZ>> data;
    size_t getIdx(size_t x, size_t y, size_t z) const {
        return x + sizeX*y + sizeX*sizeY*z;
    }
public:
    Matrix3D_ConstDim(){
        data = std::make_unique<std::array<double, sizeX*sizeY*sizeZ>>();
    }
    double& operator()(size_t x, size_t y, size_t z){ return (*data)[getIdx(x, y, z)]; }
    double operator() (size_t x, size_t y, size_t z) const{ return (*data)[getIdx(x, y, z)]; }
    //arithmetic operators
};

Usage :

int main() {
    Matrix3D m1(10, 5, 4);
    m1(1, 2, 3) = 4.5;
    std::cout << m1(1, 2, 3) << std::endl;

    Matrix3D_ConstDim<10, 5, 4> m2;
    m2(1, 2, 3) = 4.5;
    std::cout << m2(1, 2, 3) << std::endl;
}

Element access
The second (and probably more important) thing is sequential access. If you want to iterate over all elements in your matrix, make sure that you access the elements in the same order as they are layed out in memory. As a result, almost all accesses will result in a cache hit (even when the first element in a cache line is accessed, you'll have - thanks to prefetching - a high chance for a l1 cache hit. It might also allow your compiler to perform auto-vertorization of your code. That means the compiler will use special instructions, to perform multiple iterations of the loop at the same time.
If you e.g wanted to initialize above matrixes the code could look like this:

    for (size_t z = 0; z < 4; ++z){
        for (size_t y = 0; y < 4; ++y){
            for (size_t x = 0; x < 4; ++x){ //<-- inner most loop changes X
                m1(x, y, z) = x*(y + 1)*(z + 2); //<-- arbitrary values
            }
        }
    }