ベクトル<int>が次の場合にベクトル<bool>より速い理由

Question

この現象は、LeetCode問題N-Queensをプログラムしたときに検出されます。

2つのバージョンのコードがありますが、唯一の違いは、私がハッシュテーブルを格納した方法です。一方はvector<int>を使用し、もう一方はvector<bool>を使用しています。次のように具体的には、コードの2つのバージョンがある：

バージョン1、 vector<int>、時間：4秒

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; 
} 
}; 

バージョン2、 vector<bool>、実行時間：12ミリ秒

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; 
} 
}; 

Iが知っているようvector<bool>は、bool変数（2バイトでもよい）ではなく1ビットを使用して各要素を格納し、vector<int>は4バイトを使用して各要素を格納する。だからvector<bool>はvector<int>よりも小さく見えます。しかし、それはなぜvector<int>よりも遅いのですか？

Answer 1

通常、単一ビットへのアクセスは、アドレス指定可能な単位（C++の用語ではバイト）を完了するよりも低速です。たとえば、バイトを書き込むには、write命令（mov on x86）を発行するだけです。ビットを書き込むには、それを含むバイトをロードし、ビット単位の演算子を使用してバイト内の正しいビットをセットし、結果のバイトを格納する必要があります。

ビットベクトルのコンパクトサイズはストレージ要件には適していますが、データが十分に大きくなってからキャッシュの問題が発生する場合を除いて、速度が低下します。

値を4バイトよりも高速にしたい場合は、vector<unsigned char>を試してください。

Answer 2

私の解釈：

ビットマップであるboolためvector<type>専門は、あります。それはストレージ（ベクトルストレージの1バイト= 8ブール）に関して非常に効率的ですが、実際にデータにアクセスすると悪化します。他のvectorの場合はn番目の要素には*([address of first element + n * sizeof(element)])でアクセスすることができますが、bool-out-of-byteストレージを取得するには、いくつかのビット操作を行う必要があります。それぞれが1つの真理値を表すintの配列を持つよりもかなり遅くなる可能性があります。