In C++, why array is much faster than std::vector?

Question

This is related to LeetCode 552. Student Attendance Record II. The question is fairly simple.

The first code snippet relates to use array to initialize DP and DP_new. The code runs like 50 ms.

The second code snippet relates to use vector of vector to initialize DP and DP_new. The code runs more than 2000 ms.

The only difference between those two code snippets is that I use array or std::vector to initilize data structure "DP" and "DP_new".

Why is there a huge performance gap?

class Solution {
public:
    int checkRecord(int n) {
        int mod = pow(10, 9) + 7;
        int DP[2][3];                       //using array here
        memset(DP, 0, sizeof(DP));
        DP[1][0] = 1;
        DP[0][0] = 1;
        DP[0][1] = 1;
        for (int i = 1; i < n; ++i) {
            int DP_new[2][3];
            memset(DP_new, 0, sizeof(DP_new));            //using array here
            DP_new[1][2] = DP[1][1];
            DP_new[1][1] = DP[1][0];
            DP_new[1][0] = ((((((DP[0][0] + DP[0][1]) % mod + DP[0][2]) % mod) + DP[1][0]) % mod + DP[1][1]) % mod + DP[1][2]) % mod;
            DP_new[0][2] = DP[0][1];
            DP_new[0][1] = DP[0][0];
            DP_new[0][0] = ((DP[0][0] + DP[0][1]) % mod + DP[0][2]) % mod;       
            swap(DP, DP_new);
        }
        return ((((((DP[0][0] + DP[0][1]) % mod + DP[0][2]) % mod) + DP[1][0]) % mod + DP[1][1]) % mod + DP[1][2]) % mod;
    }
};

class Solution {
public:
    int checkRecord(int n) {
        int mod = pow(10, 9) + 7;
        vector<vector<int>> DP(2, vector<int>(3, 0));       //use 2D vector here
        DP[1][0] = 1;
        DP[0][0] = 1;
        DP[0][1] = 1;
        for (int i = 1; i < n; ++i) {
            vector<vector<int>> DP_new(2, vector<int>(3, 0));     //use 2D vector here
            DP_new[1][2] = DP[1][1];
            DP_new[1][1] = DP[1][0];
            DP_new[1][0] = ((((((DP[0][0] + DP[0][1]) % mod + DP[0][2]) % mod) + DP[1][0]) % mod + DP[1][1]) % mod + DP[1][2]) % mod;
            DP_new[0][2] = DP[0][1];
            DP_new[0][1] = DP[0][0];
            DP_new[0][0] = ((DP[0][0] + DP[0][1]) % mod + DP[0][2]) % mod;       
            swap(DP, DP_new);
        }
        return ((((((DP[0][0] + DP[0][1]) % mod + DP[0][2]) % mod) + DP[1][0]) % mod + DP[1][1]) % mod + DP[1][2]) % mod;
    }
};

This is the LeetCode C++ compiler.

Answer 1

Allocating memory on the heap is extremely slow, because it has to do a linear search for a chunk large enough to hold your data. In fact, the degenerate case of running out of memory means that you first checked every single chunk of physical and swap memory and came up empty.

Contrast that to a plain old array like in your first example, and the difference is easily explainable. It's all allocation speed.

Edit: I just saw your edit that you're using asan, that further exacerbates the problem by allocating very large chunks of memory around your every allocation.