`std :: bitset` с и без пограничных проверок

Question

И снова о STL std::bitset - в его документации говорится, что функции set/reset/test выполняют пограничные проверки, а operator[] - нет. Мои эксперименты по времени показывают, что функции set/test обычно выполняют на 2-3% быстрее, чем operator[]. Код, с которым я работаю:

typedef unsigned long long U64; 
const U64 MAX = 800000000ULL; 

struct Bitmap1 
{ 
    void insert(U64 N) {this->s[N % MAX] = 1;} 
    bool find(U64 N) const {return this->s[N % MAX];} 
private: 
    std::bitset<MAX> s; // <---- takes MAX/8 memory (in bytes) 
}; 

struct Bitmap2 
{ 
    void insert(U64 N) {this->s.set(N % MAX);} 
    bool find(U64 N) const {return this->s.test(N % MAX);} 
private: 
    std::bitset<MAX> s; // <---- takes MAX/8 memory (in bytes) 
}; 

int main() 
{ 
    Bitmap2* s = new Bitmap2(); 
    // --------------------------- storing 
    const size_t t0 = time(0); 
    for (unsigned k = 0; k < LOOPS; ++k) 
    { 
    for (U64 i = 0; i < MAX; ++i) s->insert(i); 
    } 
    cout << "storing: " << time(0) - t0 << endl; 
    // -------------------------------------- search 
    const size_t t1 = time(0); 
    U64 count = 0; 
    for (unsigned k = 0; k < LOOPS; ++k) 
    { 
    for (U64 i = 0; i < MAX; ++i) if (s->find(i)) ++count; 
    } 
    cout << "search: " << time(0) - t1 << endl; 
    cout << count << endl; 
} 

Как это объяснить? Отсутствие пограничных проверок должно сэкономить нам несколько циклов, верно?

Compiler: g++ 4.8.1 (options -g -O4) 
VMware VM: Ubuntu 3.11.0-15 
Host: MacBook Pro 

Answer 1

Когда я удалить rand, деление, выход и кэш памяти из тайминги:

bool bracket_test() { 
    std::bitset<MAX> s; 
    for(int j=0; j<num_iterations; ++j) { 
     for(int i=0; i<MAX; ++i) 
      s[i] = !s[MAX-1-i]; 
    } 
    return s[0]; 
} 
bool set_test() { 
    std::bitset<MAX> s; 
    for(int j=0; j<num_iterations; ++j) { 
     for(int i=0; i<MAX; ++i) 
      s.set(i, !s.test(MAX-1-i)); 
    } 
    return s.test(0); 
} 
bool no_test() { 
    bool s = false; 
    for(int j=0; j<num_iterations; ++j) { 
     for(int i=0; i<MAX; ++i) 
      s = !s; 
    } 
    return s; 
} 

я получить эти результаты с Clang на http://coliru.stacked-crooked.com/a/cdc832bfcc7e32be. (Я 10000 итераций, в 20 раз, и измерить самое низкое время, смягчающий ошибки синхронизации.)

clang++ -std=c++11 -O0 -Wall -Wextra -pedantic -pthread main.cpp && ./a.out 
bracket_test took 178663845 ticks to find result 1 
set_test  took 117336632 ticks to find result 1 
no_test  took 9214297 ticks to find result 0 
clang++ -std=c++11 -O1 -Wall -Wextra -pedantic -pthread main.cpp && ./a.out 
bracket_test took 798184780 ticks to find result 1 
set_test  took 565999680 ticks to find result 1 
no_test  took 41693575 ticks to find result 0 
clang++ -std=c++11 -O2 -Wall -Wextra -pedantic -pthread main.cpp && ./a.out 
bracket_test took 81240369 ticks to find result 1 
set_test  took 72172912 ticks to find result 1 
no_test  took 41907685 ticks to find result 0 
clang++ -std=c++11 -O3 -Wall -Wextra -pedantic -pthread main.cpp && ./a.out 
bracket_test took 77688054 ticks to find result 1 
set_test  took 72433185 ticks to find result 1 
no_test  took 41433010 ticks to find result 0 

Предыдущие версии этого теста установлено, что скобки немного быстрее было, но теперь, когда я улучшил точность тайминги, похоже, что моя погрешность для синхронизации составляет около 3%. На O1 Set на 35-54% быстрее, при O2 - на 13-49% быстрее, а у O3 - на 2-34% быстрее. Для меня это выглядит довольно убедительно, если не смотреть на сборку.

Так вот сборка (в GCC -O) с помощью http://assembly.ynh.io/:

std::bitset<MAX> s 
s[1000000] = true; 
return s; 

0000 4889F8   movq %rdi, %rax 
0003 4889FA   movq %rdi, %rdx 
0006 488D8F00  leaq 100000000(%rdi), %rcx 
    E1F505 
000d 48C70200  movq $0, (%rdx) 
    000000 
0014 4883C208  addq $8, %rdx 
0018 4839CA   cmpq %rcx, %rdx 
001b 75F0   jne .L2 
001d 48838848  orq $1, 125000(%rax) 
    E8010001 
0025 C3    ret 

и

std::bitset<MAX> s; 
s.set(1000000); 
return s; 

0026 4889F8   movq %rdi, %rax 
0029 4889FA   movq %rdi, %rdx 
002c 488D8F00  leaq 100000000(%rdi), %rcx 
    E1F505 
0033 48C70200  movq $0, (%rdx) 
    000000 
003a 4883C208  addq $8, %rdx 
003e 4839CA   cmpq %rcx, %rdx 
0041 75F0   jne .L6 
0043 48838848  orq $1, 125000(%rax) 
    E8010001 
004b C3    ret 

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

Что касается ПРИЧИНЫ, то, что Set быстрее, это то, что operator[] должен сделать TON работы для ссылочного прокси, что Set не требуется. Причина, по которой Set медленнее, заключается в том, что прокси-сервер тривиально инкрустирован, и в этом случае единственная разница заключается в том, что Set должен выполнить граничную проверку. С другой стороны, Set должен выполнить только граничную проверку, если компилятор не может доказать, что индексы всегда находятся в зоне действия. Так что это зависит от окружающего кода, много. Ваши результаты могут отличаться.

http://en.cppreference.com/w/cpp/utility/bitset/set говорит:

Устанавливает бит в позиции поз до значения величины.
Выбрасывает std :: out_of_range, если pos не соответствует действительной позиции внутри битового набора.

http://en.cppreference.com/w/cpp/utility/bitset/operator_at говорит:

Обращается бит в позиции поз. Возвращает объект типа std :: bitset :: reference, который позволяет изменять значение.
В отличие от test(), не генерирует исключений: поведение не определено, если pos вне пределов.

и http://en.cppreference.com/w/cpp/utility/bitset/reference говорят:

БППП :: BitSet класс включает зЬй :: BITSET :: ссылку в качестве общедоступного вложенного класса. Этот класс используется как прокси-объект, чтобы позволить пользователям взаимодействовать с отдельными битами битового набора, поскольку стандартные типы C++ (например, ссылки и указатели) не построены с достаточной точностью для указания отдельных битов. Основное использование std :: bitset :: reference - это предоставление l-значения, которое может быть возвращено оператором []. Любой считывает или записывает в биты, которые происходят через std :: bitset :: reference, потенциально читаемые или записываемые во весь базовый набор бит.

Должно быть ясно, что у operator[] фактически есть намного больше, чем интуитивно.