Why is the vector <int> faster than the vector <bool> in the following case

Question

This phenomenon is detected when I programmed the LeetCode N-Queens problem.

I have two versions of the accepted code, the only difference between which is how I stored the hash table, one uses vector<int> and the other uses vector<bool> . To be specific, two versions of the code are as follows:

Version 1, vector<int> , Duration: 4 ms

 class Solution { public: void dfs(vector<string>& crtrst, vector<vector<string>>& finalrsts, int row, vector<int>& mup, vector<int>& m45dgr, vector<int>& m135dgr) { int n = crtrst.size(); if (row == n) { finalrsts.push_back(crtrst); return; } for (int j=0; j<n; j++) { if (mup[j] && m45dgr[j-row+n-1] && m135dgr[row+j]) { crtrst[row][j] = 'Q'; mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = 0; dfs(crtrst,finalrsts,row+1,mup,m45dgr,m135dgr); crtrst[row][j] = '.'; mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = 1; } } } vector<vector<string>> solveNQueens(int n) { vector<vector<string>> finalrsts; vector<string> crtrst(n,string(n,'.')); vector<int> mup(n,1); vector<int> m45dgr(2*n-1,1); // degree 45: '\' vector<int> m135dgr(2*n-1,1); // degree 135: '/'; int row = 0; dfs(crtrst,finalrsts,row,mup,m45dgr,m135dgr); return finalrsts; } }; 

Version 2, vector<bool> , Duration: 12 ms

 class Solution { public: void dfs(vector<string>& crtrst, vector<vector<string>>& finalrsts, int row, vector<bool>& mup, vector<bool>& m45dgr, vector<bool>& m135dgr) { int n = crtrst.size(); if (row == n) { finalrsts.push_back(crtrst); return; } for (int j=0; j<n; j++) { if (mup[j] && m45dgr[j-row+n-1] && m135dgr[row+j]) { crtrst[row][j] = 'Q'; mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = false; dfs(crtrst,finalrsts,row+1,mup,m45dgr,m135dgr); crtrst[row][j] = '.'; mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = true; } } } vector<vector<string>> solveNQueens(int n) { vector<vector<string>> finalrsts; vector<string> crtrst(n,string(n,'.')); vector<bool> mup(n,true); vector<bool> m45dgr(2*n-1,true); // degree 45: '\' vector<bool> m135dgr(2*n-1,true); // degree 135: '/'; int row = 0; dfs(crtrst,finalrsts,row,mup,m45dgr,m135dgr); return finalrsts; } }; 

As I know, vector<bool> stores each element using 1 bit, not the bool variable (maybe 2 bytes), and vector<int> stores each element using 4 bytes. Thus, vector<bool> seems thinner than vector<int> . However, why is it slower than vector<int> ?

Answer 1

Access to single bits is usually slower than to complete address units (bytes in C ++ linguistic). For example, to write a byte, you simply write out a write instruction (mov on x86). To write a bit, you need to load the byte containing it, use bitwise operators to set the correct bit in the byte, and then save the received byte.

The compact bit vector size is good for storage requirements, but it will slow down unless your data gets big enough for caching issues to play a role.

If you want speed and are still more efficient than 4 bytes per value, try vector<unsigned char> .

Answer 2

My interpretation:

There is a vector<type> specialization for bool , which is a bitmap; which is very efficient with respect to storage (1 bit of vector storage = 8 bool), but worse with actual data access; for any other vector you can simply access the element at the nth position *([address of first element + n * sizeof(element)]) , but in order to get the bool-out-by-byte-store you will inevitably have to do some a bit operation, which during times of large caches can be significantly slower than just an array of int s, each representing one true value.