Почему std :: vector <bool> быстрее?

Question

Как я применял Сито из Eratosthenes У меня возникла проблема с std::vector<bool>: нет доступа к исходным данным.

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

#ifndef LIB_BITS_T_H 
#define LIB_BITS_T_H 

#include <algorithm> 
template <typename B> 

class bits_t{ 

public: 

    typedef B block_t; 
    static const size_t block_size = sizeof(block_t) * 8; 

    block_t* data; 
    size_t size; 
    size_t blocks; 

    class bit_ref{ 
    public: 
     block_t* const block; 
     const block_t mask; 

     bit_ref(block_t& block, const block_t mask) noexcept : block(&block), mask(mask){} 

     inline void operator=(bool v) const noexcept{ 
      if(v) *block |= mask; 
      else *block &= ~mask; 
     } 

     inline operator bool() const noexcept{ 
      return (bool)(*block & mask); 
     } 
    }; 



    bits_t() noexcept : data(nullptr){} 

    void resize(const size_t n, const bool v) noexcept{ 
     block_t fill = v ? ~block_t(0) : block_t(0); 
     size = n; 
     blocks = (n + block_size - 1)/block_size; 
     data = new block_t[blocks]; 
     std::fill(data, data + blocks, fill); 
    } 

    inline block_t& block_at_index(const size_t i) const noexcept{ 
     return data[i/block_size]; 
    } 

    inline size_t index_in_block(const size_t i) const noexcept{ 
     return i % block_size; 
    } 

    inline bit_ref operator[](const size_t i) noexcept{ 
     return bit_ref(block_at_index(i), block_t(1) << index_in_block(i)); 
    } 

    ~bits_t(){ 
     delete[] data; 
    } 

}; 

#endif // LIB_BITS_T_H 

Код почти такой же, чем в /usr/include/c++/4.7/bits/stl_bvector.h, но медленнее.

Я попробовал оптимизацию,

#ifndef LIB_BITS_T_H 
#define LIB_BITS_T_H 

#include <algorithm> 
template <typename B> 

class bits_t{ 

const B mask[64] = { 
    0b0000000000000000000000000000000000000000000000000000000000000001, 
    0b0000000000000000000000000000000000000000000000000000000000000010, 
    0b0000000000000000000000000000000000000000000000000000000000000100, 
    0b0000000000000000000000000000000000000000000000000000000000001000, 
    0b0000000000000000000000000000000000000000000000000000000000010000, 
    0b0000000000000000000000000000000000000000000000000000000000100000, 
    0b0000000000000000000000000000000000000000000000000000000001000000, 
    0b0000000000000000000000000000000000000000000000000000000010000000, 
    0b0000000000000000000000000000000000000000000000000000000100000000, 
    0b0000000000000000000000000000000000000000000000000000001000000000, 
    0b0000000000000000000000000000000000000000000000000000010000000000, 
    0b0000000000000000000000000000000000000000000000000000100000000000, 
    0b0000000000000000000000000000000000000000000000000001000000000000, 
    0b0000000000000000000000000000000000000000000000000010000000000000, 
    0b0000000000000000000000000000000000000000000000000100000000000000, 
    0b0000000000000000000000000000000000000000000000001000000000000000, 
    0b0000000000000000000000000000000000000000000000010000000000000000, 
    0b0000000000000000000000000000000000000000000000100000000000000000, 
    0b0000000000000000000000000000000000000000000001000000000000000000, 
    0b0000000000000000000000000000000000000000000010000000000000000000, 
    0b0000000000000000000000000000000000000000000100000000000000000000, 
    0b0000000000000000000000000000000000000000001000000000000000000000, 
    0b0000000000000000000000000000000000000000010000000000000000000000, 
    0b0000000000000000000000000000000000000000100000000000000000000000, 
    0b0000000000000000000000000000000000000001000000000000000000000000, 
    0b0000000000000000000000000000000000000010000000000000000000000000, 
    0b0000000000000000000000000000000000000100000000000000000000000000, 
    0b0000000000000000000000000000000000001000000000000000000000000000, 
    0b0000000000000000000000000000000000010000000000000000000000000000, 
    0b0000000000000000000000000000000000100000000000000000000000000000, 
    0b0000000000000000000000000000000001000000000000000000000000000000, 
    0b0000000000000000000000000000000010000000000000000000000000000000, 
    0b0000000000000000000000000000000100000000000000000000000000000000, 
    0b0000000000000000000000000000001000000000000000000000000000000000, 
    0b0000000000000000000000000000010000000000000000000000000000000000, 
    0b0000000000000000000000000000100000000000000000000000000000000000, 
    0b0000000000000000000000000001000000000000000000000000000000000000, 
    0b0000000000000000000000000010000000000000000000000000000000000000, 
    0b0000000000000000000000000100000000000000000000000000000000000000, 
    0b0000000000000000000000001000000000000000000000000000000000000000, 
    0b0000000000000000000000010000000000000000000000000000000000000000, 
    0b0000000000000000000000100000000000000000000000000000000000000000, 
    0b0000000000000000000001000000000000000000000000000000000000000000, 
    0b0000000000000000000010000000000000000000000000000000000000000000, 
    0b0000000000000000000100000000000000000000000000000000000000000000, 
    0b0000000000000000001000000000000000000000000000000000000000000000, 
    0b0000000000000000010000000000000000000000000000000000000000000000, 
    0b0000000000000000100000000000000000000000000000000000000000000000, 
    0b0000000000000001000000000000000000000000000000000000000000000000, 
    0b0000000000000010000000000000000000000000000000000000000000000000, 
    0b0000000000000100000000000000000000000000000000000000000000000000, 
    0b0000000000001000000000000000000000000000000000000000000000000000, 
    0b0000000000010000000000000000000000000000000000000000000000000000, 
    0b0000000000100000000000000000000000000000000000000000000000000000, 
    0b0000000001000000000000000000000000000000000000000000000000000000, 
    0b0000000010000000000000000000000000000000000000000000000000000000, 
    0b0000000100000000000000000000000000000000000000000000000000000000, 
    0b0000001000000000000000000000000000000000000000000000000000000000, 
    0b0000010000000000000000000000000000000000000000000000000000000000, 
    0b0000100000000000000000000000000000000000000000000000000000000000, 
    0b0001000000000000000000000000000000000000000000000000000000000000, 
    0b0010000000000000000000000000000000000000000000000000000000000000, 
    0b0100000000000000000000000000000000000000000000000000000000000000, 
    0b1000000000000000000000000000000000000000000000000000000000000000 
}; 

public: 

    typedef B block_t; 
    static const size_t block_size = sizeof(block_t) * 8; 

    block_t* data; 
    size_t size; 
    size_t blocks; 

    class bit_ref{ 
    public: 
     block_t* const block; 
     const block_t mask; 

     bit_ref(block_t& block, const block_t mask) noexcept : block(&block), mask(mask){} 

     inline void operator=(bool v) const noexcept{ 
      if(v) *block |= mask; 
      else *block &= ~mask; 
     } 

     inline operator bool() const noexcept{ 
      return (bool)(*block & mask); 
     } 
    }; 



    bits_t() noexcept : data(nullptr){} 

    void resize(const size_t n, const bool v) noexcept{ 
     block_t fill = v ? ~block_t(0) : block_t(0); 
     size = n; 
     blocks = (n + block_size - 1)/block_size; 
     data = new block_t[blocks]; 
     std::fill(data, data + blocks, fill); 
    } 

    inline block_t& block_at_index(const size_t i) const noexcept{ 
     return data[i/block_size]; 
    } 

    inline size_t index_in_block(const size_t i) const noexcept{ 
     return i % block_size; 
    } 

    inline bit_ref operator[](const size_t i) noexcept{ 
     return bit_ref(block_at_index(i), mask[index_in_block(i)]); 
    } 

    ~bits_t(){ 
     delete[] data; 
    } 

}; 

#endif // LIB_BITS_T_H 

(Компиляция с г ++ 4,7 -O3)

Эратосфен алгоритм решета (33.333.333 бит)

std::vector<bool> 19.1s

bits_t<size_t> 19.9s

bits_t<size_t> (with lookup table) 19.7s

т е р + размер (33.333.333 бит) + dtor

std::vector<bool> 120 мс

bits_t<size_t> 150мс

ВОПРОС: Где замедление происходят из ?

Answer 1

По-видимому, обертывание i % block_size в функции был виновником

inline size_t index_in_block (const size_t i) const noexcept { 
    return i % block_size; 
} 

inline bit_ref operator[] (const size_t i) noexcept { 
    return bit_ref(block_at_index(i), block_t(1) << index_in_block(i)); 
} 

так заменяя выше код с

inline bit_ref operator[] (const size_t i) noexcept { 
    return bit_ref(block_at_index(i), block_t(1) << (i % block_size)); 
} 

решает эту проблему. Тем не менее, я до сих пор не знаю, почему это так. Мое лучшее предположение заключается в том, что я не получил подпись index_in_block вправо, и что оптимизатор, таким образом, не может встроить эту функцию аналогично руководству , введя в порядок.

Вот новый код.

#ifndef LIB_BITS_2_T_H 
#define LIB_BITS_2_T_H 

#include <algorithm> 

template <typename B> 

class bits_2_t { 

public: 

    typedef B block_t; 
    static const int block_size = sizeof(block_t) * __CHAR_BIT__; 


private: 

    block_t* _data; 
    size_t _size; 
    size_t _blocks; 


public: 

    class bit_ref { 

    public: 

     block_t* const block; 
     const block_t mask; 


     bit_ref (block_t& block, const block_t mask) noexcept 
     : block(&block), mask(mask) {} 


     inline bool operator= (const bool v) const noexcept { 

      if (v) *block |= mask; 
      else  *block &= ~mask; 

      return v; 

     } 

     inline operator bool() const noexcept { 
      return (bool)(*block & mask); 
     } 


    }; 


    bits_2_t() noexcept : _data(nullptr), _size(0), _blocks(0) {} 

    bits_2_t (const size_t n) noexcept : _data(nullptr), _size(n) { 

     _blocks = number_of_blocks_needed(n); 
     _data = new block_t[_blocks]; 

     const block_t fill(0); 
     std::fill(_data, _data + _blocks, fill); 

    } 

    bits_2_t (const size_t n, const bool v) noexcept : _data(nullptr), _size(n) { 

     _blocks = number_of_blocks_needed(n); 
     _data = new block_t[_blocks]; 

     const block_t fill = v ? ~block_t(0) : block_t(0); 
     std::fill(_data, _data + _blocks, fill); 

    } 

    void resize (const size_t n) noexcept { 
     resize(n, false); 
    } 

    void resize (const size_t n, const bool v) noexcept { 

     const size_t tmpblocks = number_of_blocks_needed(n); 
     const size_t copysize = std::min(_blocks, tmpblocks); 

     block_t* tmpdata = new block_t[tmpblocks]; 
     std::copy(_data, _data + copysize, tmpdata); 

     const block_t fill = v ? ~block_t(0) : block_t(0); 
     std::fill(tmpdata + copysize, tmpdata + tmpblocks, fill); 

     delete[] _data; 

     _data = tmpdata; 
     _blocks = tmpblocks; 
     _size = n; 

    } 

    inline size_t number_of_blocks_needed (const size_t n) const noexcept { 
     return (n + block_size - 1)/block_size; 
    } 

    inline block_t& block_at_index (const size_t i) const noexcept { 
     return _data[i/block_size]; 
    } 

    inline bit_ref operator[] (const size_t i) noexcept { 
     return bit_ref(block_at_index(i), block_t(1) << (i % block_size)); 
    } 

    inline bool operator[] (const size_t i) const noexcept { 
     return (bool)(block_at_index(i) & (block_t(1) << (i % block_size))); 
    } 

    inline block_t* data() { 
     return _data; 
    } 

    inline const block_t* data() const { 
     return _data; 
    } 

    inline size_t size() const { 
     return _size; 
    } 

    void clear() noexcept { 

     delete[] _data; 

     _size = 0; 
     _blocks = 0; 
     _data = nullptr; 

    } 

    ~bits_2_t() { 
     clear(); 
    } 


}; 

#endif // LIB_BITS_2_T_H 

Вот результаты этого нового кода на моем amd64 машина для простых чисел до 1.000.000.000 (лучше всего из 3-х серий, в режиме реального времени).

Сито Эратосфена с 1 единицей памяти на число (не пропускающее кратные 2).

< bits_t uint8_t >

реального 0m23.614s пользователя 0m23.493s SYS 0m0.092s

< bits_t uint16_t >

реального 0m24.399s пользователя 0m24.294s SYS 0m0.084s

bits_t <uint32_t>

реального 0m23.501s пользователя 0m23.372s SYS 0m0.108s< - лучший

< bits_t uint64_t >

реального 0m24.393s пользователя 0m24.304s SYS 0m0.068s

std :: vector <bool>

настоящий 0m24.362s пользователь 0m24.276s sys 0m0.056s

станд :: вектор <uint8_t>

реального 0m38.303s пользователя 0m37.570s SYS 0m0.683s

Вот код решета (где (...) должен быть заменен битовым массивом твой выбор).

#include <iostream> 

typedef (...) array_t; 

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

    if (argc != 2) { 
     std::cout << "#0 missing" << std::endl; 
     return 1; 
    } 

    const size_t count = std::stoull(argv[1]); 
    array_t prime(count, true); 
    prime[0] = prime[1] = false; 


    for (size_t k = 2 ; k * k < count ; ++k) { 

     if (prime[k]) { 

      for (size_t i = k * k ; i < count ; i += k) { 
       prime[i] = false; 
      } 

     } 

    } 

    return 0; 
} 

Answer 2

Вне всех проблем, о которых указывают некоторые другие пользователи, ваш размер выделяет больше памяти каждый раз, когда достигается текущий предел блока, чтобы добавить ОДИН блок. Std :: vector удваивает размер буфера (так что если у вас уже было 16 блоков, теперь у вас есть 32 блока). Другими словами, они будут делать меньше, чем вы.

Настоящая заявка не делает необходимой копию &, и это может иметь «положительное» воздействие в вашей версии ... («положительная» скорость удара мудрая, не положительно, что вы не удаляете старые данные, а также не копировать их в новом буфере.)

Кроме того, std :: vector будет правильно увеличивать буфер и, таким образом, копировать данные, которые, скорее всего, уже находятся в вашем кэше CPU. С вашей версией этот кеш теряется, поскольку вы просто игнорируете старый буфер на каждом изменении размера().

Также, когда класс обрабатывает буфер памяти, по каким-то причинам обычно реализуется оператор копирования и присваивания ... и вы могли бы изучить использование shared_ptr <>(). Удаления затем скрыт и класс представляет собой шаблон, так что очень быстро (это не добавляет код, который вы бы уже есть в вашей собственной версии.)

=== Обновление

Существует одна Другая вещь.Вы operator [] реализации:

inline bit_ref operator[](const size_t i) noexcept{ 
    return bit_ref(block_at_index(i), mask[index_in_block(i)]); 
} 

(примечание стороны: рядный не требуются, так как тот факт, что вы пишете код в классе уже означает, что вы выложите возможности встроенных уже.)

Вы только предложение неконвертная версия, которая «медленная», потому что она создает подкласс. Вы должны попробовать реализовать версию const, которая возвращает bool, и посмотреть, учитывает ли это 3% -ную разницу.

bool operator[](const size_t i) const noexcept 
{ 
    return (block_at_index(i) & mask[index_in_block(i)]) != 0; 
} 

Кроме того, использование массива mask[] также может замедлить работу. (1LL < < (индекс & 0x3F)) должен быть быстрее (2 инструкции CPU с 0 доступом к памяти).