Почему std:: вектор быстрее?

Когда я реализовывалсито Эратосфена , я столкнулся с проблемой 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

(компиляция с g++4.7-O3)

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

std::vector<bool> 19.1 s

bits_t<size_t> 19.9 s

bits_t<size_t> (with lookup table) 19.7 s

Ctor + resize (33.333.333 бит) + dtor

std::vector<bool> 120 мс

bits_t<size_t> 150 мс

Вопрос : откуда берется замедление?

2 5
c++ performance stdvector

2 ответа:

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

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

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

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

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

Есть еще одна вещь. Вы 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

3

По-видимому, обертывание 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 и что оптимизатор, таким образом, не может встроить эту функцию аналогично ручному способу inlining.

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

#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

Настоящий 0m23.Пользователь 614s 0m23.493s представление sys 0m0.092s

Bits_t

Настоящий 0m24.Пользователь 399s 0m24.294s представление sys 0m0.084s

Bits_t

Реальные 0m23.Пользователь 501s 0m23.372s представление sys 0m0.108s

Bits_t

Настоящий 0m24.Пользователь 393s 0m24.304с представление sys 0m0.068s

Std:: vector

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

Std:: vector

Настоящий 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;
}
0