Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Why does my code slow down when i replace arrays with stl vectors, in c++, are arrays more faster than vectors?

Below is the code I used for comparing:

// Example program
#include <iostream>
#include <string>
#include <vector>
#include <chrono>
using namespace std::chrono;
using namespace std;
            
bool existHelperArrayVersion(string &word, int i, int u_i, int u_j, vector<vector<char>>& Board)
{
    if(i>=word.length())
    {
        return true;
    }
    else
    {
        bool answer  = false;      
        if(Board[u_i][u_j] == word[i])
        {
            char temp             = Board[u_i][u_j];
            Board[u_i][u_j]       = '?';
            int row_len           = Board.size();  
            int col_len           = Board[0].size();

            // Uses Array
            int row_offset[4]={0,  0, 1, -1};
            int col_offset[4]={1, -1, 0,  0};
            
            for(int k=0; k<4; k++)
            {
                int v_i = u_i + row_offset[k];
                int v_j = u_j + col_offset[k];
                
                if( !(0 >v_i || v_i >= row_len || 0>v_j || v_j >= col_len)  && (Board[v_i][v_j] != '?'))
                    answer |= existHelperArrayVersion(word, i+1, v_i, v_j, Board);
            }
               
            if(i+1 == word.length())
                answer |= true;
            Board[u_i][u_j] = temp;
        }
        return answer;
    }
}

bool existHelperVectorVersion(string &word, int i, int u_i, int u_j, vector<vector<char>>& Board)
{
    if(i>=word.length())
    {
        return true;
    }
    else
    {
        bool answer  = false;
        if(Board[u_i][u_j] == word[i])
        {
            char temp             = Board[u_i][u_j];
            Board[u_i][u_j]       = '?';
            int row_len           = Board.size();  
            int col_len           = Board[0].size();

            //Uses Vectors
            vector<int> row_offset = {0,  0, 1, -1};
            vector<int> col_offset = {1, -1, 0,  0};
            
            for(int k=0; k<4; k++)
            {
                int v_i = u_i + row_offset[k];
                int v_j = u_j + col_offset[k];
                
                if( !(0 >v_i || v_i >= row_len || 0>v_j || v_j >= col_len)  && (Board[v_i][v_j] != '?'))
                    answer |= existHelperVectorVersion(word, i+1, v_i, v_j, Board);
            }
               
            if(i+1 == word.length())
                answer |= true;
            Board[u_i][u_j] = temp;
        }
        return answer;
    }
}

bool exist(vector<vector<char>>& board, string word, int option) 
{
    if(option == 0)
        cout << "----ARRAY------\n";
    else if(option == 1)
        cout << "---VECTOR-----\n";
        
    bool answer   = false;
    for(int i=0; i<board.size(); i++)
    {
        for(int j=0; j<board[i].size(); j++)
        {
            if(option == 0)
                answer |= existHelperArrayVersion( word, 0, i, j, board);
            else if(option == 1)
                answer |= existHelperVectorVersion( word, 0, i, j, board);
                
            if(answer)
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    
    string word                 =   "AAAAAAAAAAAAAAB";
    vector<vector<char>> board  =   {{'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'}};

    auto start    = high_resolution_clock::now();
    bool answer   = exist(board, word, 0);
    auto stop     = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken when Using C-style Array : " << duration.count() << " microseconds" << endl;
    
    start         = high_resolution_clock::now();
    answer        = exist(board, word, 1);
    stop          = high_resolution_clock::now();
    duration      = duration_cast<microseconds>(stop - start);
    cout << "Time taken when Using STL vector    : " << duration.count() << " microseconds" << endl;
    
}

output

----ARRAY------
Time taken when Using C-style Array : 112931 microseconds
---VECTOR-----
Time taken when Using STL vector    : 330641 microseconds

As you can see the array version of my function performs on average 3 times faster than that of its Vector version. (I ran it multiple times and got similar results)

Question:
Are vectors really that slow compared to arrays?
I thought their performance was supposed to be on par.
This is the URL I run it on an online environment http://cpp.sh/6x22b

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>Solution :

        vector<int> row_offset = {0,  0, 1, -1};
        vector<int> col_offset = {1, -1, 0,  0};

this causes 2 heap allocations of data (almost) every time the function is called.

        int row_offset[4]={0,  0, 1, -1};
        int col_offset[4]={1, -1, 0,  0};

this does not cause 2 heap allocations of data (almost) every time the function is called.

std::vector<int> foo = {1,2,3} is similar to int* foo = new int[]{1,2,3}, not int foo[] = {1,2,3} in creation costs.

std::array<int, 3> foo={1,2,3}

is the std library version of "fixed size buffer with data in it". std::vector is a dynamically sized buffer.

Here is a live example where I swapped std::vector for std::array, and changed the C-array version to dynamically create and destroy the arrays. You’ll notice the time swaps.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading