c++ vector, array 다차원 배열, 2d array를 1d처럼, 성능 주의점

Vector의 다차원 배열은 Array와 메모리 구조가 다르다.

Vector가 만약 2*2 배열이라면

행에 해당하는 부분은 stack에 저장되며

stack 저장되는 것은 상위 vector의  pointer, size, capacity이다.

이후 하위 vector는 힙에 저장되며

힙에 vector의 pointer, size, capacity가 저장된다.

하위 벡터의 pointer가 다시 자료가 존재하고 있는 heap을 가르키게 된다.

 

그리고 벡터가 띄엄띄엄 존재하면 성능상 손해다.

따라서 1d로 벡터를 만들어주는 클래스를 만들었다.

 

다차원 배열의 for loop을 위해서는 cache 방향으로 for loop 을 해야 한다.

성능 차이가 꽤 크다.

#include <stdio.h>
#include <array>
#include <vector>
#include <iostream>
#include <chrono>
 
// 행렬을 1D로 처리한다.
// Compile 시간에 확정한다
template <typename T, int ROW, int COL>
class Matrix
{
public:
    Matrix() : mMatrix(ROW* COL, 0) {
        mRow = ROW;
        mCol= COL;
    };
 
    T& operator()(int rowIdx, int colIdx)
    {
        const int idx = rowIdx * COL + colIdx;
        return mMatrix[idx];
    };
private:
    std::vector<T> mMatrix;
    int mRow;
    int mCol;
};
 
int main()
{
    // C style
    int matrix[5][5]; // stack
    int** pMatrix = new int* [5];
    for (int i = 0; i < 5; i++)
    {
        pMatrix[i] = new int[5];
    }
 
    for (int i = 0; i < 5; i++)
    {
        delete[] pMatrix[i];
    }
    delete[] pMatrix;
 
    // C++ Array, Vector 이용
    std::array<std::array<int, 3>, 3> fixedMatrix;
    fixedMatrix[1][1] = 5;
    fixedMatrix[2][2] = 1;
 
    //alias template
    using N2dMatrix33 = std::array<std::array<int, 3>, 3>;
    N2dMatrix33 fixedMatrix2;
    /// <summary>
    /// Vector의 다차원 배열은 메모리 구조가 다르다. 
    /// 2*2 vector을 예로 설명을 하면
    /// stack에 pointer, capacity, size가 올라 가고
    /// pointer가 가르키는 벡터는 힙에 있다.
    /// 이 힙에 다시 pointer, capacity, size가 올라 가고
    /// 힙이 다시 vector 의 값을 가르키게 된다.
    /// </summary>
    /// <returns></returns>
    std::vector<std::vector<int>> dynamicMatrix(3, std::vector<int>(3));
    dynamicMatrix[0][2] = 10;
    dynamicMatrix[1][1] = 5;
    // 띄엄 띄엄 벡터가 위치하면 이미지 처리 같은 것을 할때
    // 성능상 손해다. 따라서 1D 형식으로 붙이는게 좋다.
 
    // fixedMatrix[1][1] = 5;
    // dynamicMatrix[0][2] = 10;
 
 
 
    Matrix<int,10,10> mat;
    mat(3, 3) = 3;
    mat(4, 3) = mat(3, 3) * 10;
    std::cout << mat(4, 3) << std::endl;
 
    // 다차원 Array의 Loop 돌리기
    // Cache 방향으로 inner loop를 잡아야 한다
    // Col -> Row 방향으로 Looping
    //std::array<std::array<int, 10>, 10> mat2;
    int msize = 3000;
    int csize = 3000;
    std::vector<std::vector<int>> mat2(msize, std::vector<int>(csize));
    auto start = std::chrono::high_resolution_clock::now();
    for (int rowIdx = 0; rowIdx < msize; rowIdx++)
    {
        for (int colIdx = 0; colIdx < csize; colIdx++)
        {
            mat2[rowIdx][colIdx] += 1;
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end - start;
    std::cout << "First col speed: " << diff.count() << std::endl;
    // Row -> Col 방향으로 inner looping
    start = std::chrono::high_resolution_clock::now();
    for (int colIdx = 0; colIdx < csize; colIdx++)
    {
        for (int rowIdx = 0; rowIdx < msize; rowIdx++)
        {
            mat2[rowIdx][colIdx] += 1;
        }
    }
    end = std::chrono::high_resolution_clock::now();
    diff = end - start;
    std::cout << "First row speed: " << diff.count() << std::endl;
    return 0;
 
}