Почему вектор <int> быстрее, чем вектор <bool> в следующем случае

Question

Это явление обнаружено, когда я запрограммировал для проблемы LeetCode N-Queens.

У меня есть две версии принятого кода, единственная разница между которыми заключается в том, как я хранил хеш-таблицу, один использует vector<int>, а другой использует vector<bool>. Конкретно, две версии кода следующим образом:

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

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

Как я знаю что vector<bool> хранит каждый элемент с использованием 1 бит, а не переменной bool (может быть 2 байта), а vector<int> хранит каждый элемент с использованием 4 байтов. Таким образом, vector<bool> кажется более мелким, чем vector<int>. Однако почему он медленнее vector<int>?

Answer 1

Доступ к отдельным битам обычно медленнее, чем для завершения адресных единиц (байты в слоге C++). Например, чтобы написать байт, вы просто выписываете инструкцию записи (mov на x86). Чтобы записать немного, вам нужно загрузить байт, содержащий его, использовать побитовые операторы для установки правильного бита в байте, а затем сохранить полученный байт.

Компактный размер битового вектора хорош для требований к хранению, но это приведет к замедлению, за исключением случаев, когда ваши данные становятся достаточно большими, чтобы проблемы кеширования играли роль.

Если вы хотите иметь скорость и по-прежнему быть более эффективным, чем 4 байта на значение, попробуйте vector<unsigned char>.

Answer 2

Моя интерпретация:

Там в vector<type> специализация для bool, который является битовая карта; это очень эффективно в отношении хранения (1 бит векторного хранилища = 8 bool), но хуже при фактическом доступе к данным; для любого другого vector вы можете просто получить доступ к элементу на n-м месте на *([address of first element + n * sizeof(element)]), но для получения bool-out-by-byte хранилища вам неизбежно понадобится выполнить некоторые бит-операции, которые в периоды больших кэши, может быть значительно медленнее, чем просто массив из int s, представляющий по одному значению истины.