Использует вектор булевых значений медленнее, чем динамический битрейт?

Question

Использует вектор булевых значений медленнее, чем динамический битбит?

Я только что слышал о динамическом битрейтеровании boost, и мне было интересно, стоит ли проблемы. Могу ли я просто использовать вектор булевых значений?

Answer 1

Здесь многое зависит от того, сколько булевых значений вы работаете.

Оба битового набора и vector<bool> обычно используют упакованное представление, в котором булевский хранится как только один бит.

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

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

Если вы используете много булевых элементов (например, реализуя решетку Eratosthenes), при установке большего количества из них в кеше почти всегда будет получена чистая прибыль. Сокращение использования памяти принесет вам гораздо больше, чем потеря бит.

Большинство аргументов против std::vector<bool> возвращаются к тому факту, что он не является стандартным контейнером (т. Е. Не соответствует требованиям к контейнеру). ИМО, это в основном вопрос ожиданий - так как он говорит vector, многие люди ожидают, что это контейнер (другие типы векторов), и они часто отрицательно реагируют на то, что vector<bool> не является контейнером.

Если вы используете вектор так, чтобы на самом деле требовать, чтобы он был контейнером, то вы, вероятно, захотите использовать какую-либо другую комбинацию - либо deque<bool>, либо vector<char> может работать нормально. Подумайте прежде чем сделать это, хотя - есть много советов (паршивая, IMO), что vector<bool> следует избегать в целом, с небольшим или без объяснения причин, почему следует избегать вообще, или при каких обстоятельствах это делает реальное разница с вами.

Да, бывают ситуации, когда что-то еще будет работать лучше. Если вы находитесь в одной из таких ситуаций, использование чего-то другого - это, безусловно, хорошая идея. Но сначала убедитесь, что вы действительно в одной из этих ситуаций. Любой, кто скажет вам (например), что «Herb говорит, что вы должны использовать vector<char>», без большого объяснения о связанных с этим компромиссах не следует доверять.

Давайте дадим реальный пример. Так как это было упомянуто в комментариях, давайте рассмотрим Решето Эратосфена:

#include <vector> 
#include <iostream> 
#include <iterator> 
#include <chrono> 

unsigned long primes = 0; 

template <class bool_t> 
unsigned long sieve(unsigned max) { 
    std::vector<bool_t> sieve(max, false); 
    sieve[0] = sieve[1] = true; 

    for (int i = 2; i < max; i++) { 
     if (!sieve[i]) { 
      ++primes; 
      for (int temp = 2 * i; temp < max; temp += i) 
       sieve[temp] = true; 
     } 
    } 
    return primes; 
} 

// Warning: auto return type will fail with older compilers 
// Fine with g++ 5.1 and VC++ 2015 though. 
// 
template <class F> 
auto timer(F f, int max) { 
    auto start = std::chrono::high_resolution_clock::now(); 
    primes += f(max); 
    auto stop = std::chrono::high_resolution_clock::now(); 

    return stop - start; 
} 

int main() { 
    using namespace std::chrono; 

    unsigned number = 100000000; 

    auto using_bool = timer(sieve<bool>, number); 
    auto using_char = timer(sieve<char>, number); 

    std::cout << "ignore: " << primes << "\n"; 
    std::cout << "Time using bool: " << duration_cast<milliseconds>(using_bool).count() << "\n"; 
    std::cout << "Time using char: " << duration_cast<milliseconds>(using_char).count() << "\n"; 
} 

Мы использовали достаточно большой массив, который мы можем ожидать, большая часть его занимает основную память. Я также пошел в небольшую боль, чтобы гарантировать, что только вещь, которая меняется от одного вызова, а другой является использование vector<char> VS. vector<bool>. Вот некоторые результаты. Сначала с VC++ 2015:

ignore: 34568730 
Time using bool: 2623 
Time using char: 3108 

... то время, используя г ++ 5.1:

ignore: 34568730 
Time using bool: 2359 
Time using char: 3116 

Очевидно, что vector<bool> победы в обоих случаях - примерно на 15% с VC++, и более чем на 30% с gcc. Также обратите внимание, что в этом случае я выбрал размер, чтобы показать vector<char> в довольно благоприятном свете. Если, например, я уменьшаю number100000000 от до 10000000, то разница во времени становится гораздо больше:

ignore: 3987474 
Time using bool: 72 
Time using char: 249 

Хотя я не сделал много работы, чтобы подтвердить, что я думаю, что в этом случае , версия с использованием vector<bool> является сохранение достаточно мест, что массив соответствует полностью в кэше, в то время как vector<char> достаточно большая, чтобы переполнить кэш, и привлечь большое количество основного доступа к памяти.

Answer 2

Обычно вы избегаете std::vector<bool>, потому что это не стандартный контейнер. Это упакованная версия, поэтому она ломает некоторые ценные гарантии, обычно даваемые vector. Действительной альтернативой было бы использование std::vector<char>, что и рекомендует Герб Саттер.

Вы можете прочитать об этом в своем GotW on the subject.

Update:

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

Если вы решите использовать его, я сделаю это после измерения его с помощью vector<char> для вашего приложения. Даже тогда я бы рекомендовал использовать typedef, чтобы ссылаться на него с помощью имени, которое, похоже, не делает гарантий, которые оно не удерживает.

Answer 3

Похоже, что размер динамического битового набора не может быть изменен: «Класс dynamic_bitset почти идентичен классу std :: bitset. Разница заключается в том, что указан размер dynamic_bitset (количество бит) во время выполнения во время построения объекта dynamic_bitset, тогда как размер std :: bitset указан во время компиляции через параметр целочисленного шаблона. " (от http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html) Как таковой, он должен быть немного быстрее, так как он будет иметь немного меньше накладных расходов, чем вектор, но вы теряете возможность вставки элементов.

Answer 4

UPDATE: Я просто понимаю, что ОП спрашивал о vector<bool> против bitset, и мой ответ не дает ответа на вопрос, но я думаю, что я должен оставить его, если вы ищете C++ вектор BOOL медленно, вы в конечном здесь.

vector<bool> ужасно медленно. По крайней мере, на моей системе Arch Linux (возможно, вы можете получить лучшую реализацию или что-то еще ... но я был очень удивлен). Если у кого-то есть предложения, почему это так медленно, я все уши! (Извините за тупое начало, вот более профессиональная часть.)

Я написал две реализации SOE, а реализация «близко к металлу» C в 10 раз быстрее. sievec.c - реализация C, а sievestl.cpp - реализация на C++. Я просто скомпилирован с make (только неявные правила, без makefile): и результаты были 1.4 сек для версии C, и 12 сек для версии C++/STL:

sievecmp % make -B sievec && time ./sievec 27 
cc  sievec.c -o sievec 
aa 1056282 
./sievec 27 1.44s user 0.01s system 100% cpu 1.455 total 

и

sievecmp % make -B sievestl && time ./sievestl 27 
g++  sievestl.cpp -o sievestl 
1056282./sievestl 27 12.12s user 0.01s system 100% cpu 12.114 total 

sievec.c выглядит следующим образом:

#include <stdio.h> 
#include <stdlib.h> 

typedef unsigned long prime_t; 
typedef unsigned long word_t; 
#define LOG_WORD_SIZE 6 

#define INDEX(i) ((i)>>(LOG_WORD_SIZE)) 
#define MASK(i) ((word_t)(1) << ((i)&(((word_t)(1)<<LOG_WORD_SIZE)-1))) 
#define GET(p,i) (p[INDEX(i)]&MASK(i)) 
#define SET(p,i) (p[INDEX(i)]|=MASK(i)) 
#define RESET(p,i) (p[INDEX(i)]&=~MASK(i)) 
#define p2i(p) ((p)>>1) // (((p-2)>>1)) 
#define i2p(i) (((i)<<1)+1) // ((i)*2+3) 

unsigned long find_next_zero(unsigned long from, 
        unsigned long *v, 
        size_t N){ 
    size_t i; 
    for (i = from+1; i < N; i++) { 
    if(GET(v,i)==0) return i; 
    } 

    return -1; 
} 

int main(int argc, char *argv[]) 
{ 

    size_t N = atoi(argv[1]); 
    N = 1lu<<N; 
    // printf("%u\n",N); 
    unsigned long *v = malloc(N/8); 
    for(size_t i = 0; i < N/64; i++) v[i]=0; 

    unsigned long p = 3; 
    unsigned long pp = p2i(p * p); 

    while(pp <= N){ 

    for(unsigned long q = pp; q < N; q += p){ 
     SET(v,q); 
    } 
    p = p2i(p); 
    p = find_next_zero(p,v,N); 
    p = i2p(p); 
    pp = p2i(p * p); 
    } 

    unsigned long sum = 0; 
    for(unsigned long i = 0; i+2 < N; i++) 
    if(GET(v,i)==0 && GET(v,i+1)==0) { 
     unsigned long p = i2p(i); 
     // cout << p << ", " << p+2 << endl; 
     sum++; 
    } 
    printf("aa %lu\n",sum); 
    // free(v); 
    return 0; 
} 

sievestl.cpp как следует:

#include <iostream> 
#include <vector> 
#include <sstream> 

using namespace std; 

inline unsigned long i2p(unsigned long i){return (i<<1)+1; } 
inline unsigned long p2i(unsigned long p){return (p>>1); } 
inline unsigned long find_next_zero(unsigned long from, vector<bool> v){ 
    size_t N = v.size(); 
    for (size_t i = from+1; i < N; i++) { 
    if(v[i]==0) return i; 
    } 

    return -1; 
} 

int main(int argc, char *argv[]) 
{ 
    stringstream ss; 
    ss << argv[1]; 
    size_t N; 
    ss >> N; 
    N = 1lu<<N; 
    // cout << N << endl; 
    vector<bool> v(N); 

    unsigned long p = 3; 
    unsigned long pp = p2i(p * p); 

    while(pp <= N){ 

    for(unsigned long q = pp; q < N; q += p){ 
     v[q] = 1; 
    } 
    p = p2i(p); 
    p = find_next_zero(p,v); 
    p = i2p(p); 
    pp = p2i(p * p); 
    } 

    unsigned sum = 0; 
    for(unsigned long i = 0; i+2 < N; i++) 
    if(v[i]==0 and v[i+1]==0) { 
     unsigned long p = i2p(i); 
     // cout << p << ", " << p+2 << endl; 
     sum++; 
    } 
    cout << sum; 
    return 0; 
}