повышение :: concat производительности dynamic_bitset

Question

Я хочу объединить большой набор битов с меньшим, чтобы производительность не снижалась.В настоящее время мое приложение тратит 20% времени процессора только на следующий код:

boost::dynamic_bitset<> encode(const std::vector<char>& data)
{
    boost::dynamic_bitset<> result;

    std::for_each(data.begin(), data.end(), [&](unsigned char symbol)
    {
        for(size_t n = 0; n < codes_[symbol].size(); ++n)
            result.push_back(codes_[symbol][n]); // codes_[symbol][n].size() avarage ~5 bits
    });
    return result;
}

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

Есть идеи?

Если это невозможно сделать с помощью boost :: dynamic_bitset, тогда я открыт для другихпредложения.

Answer 1

Это потому, что вы продолжаете использовать push_back(), но на самом деле вы уже знаете размер заранее. Это означает много избыточного копирования и перераспределения. Вы должны изменить его размер в первую очередь. Кроме того, вам не нужно push_back() каждое значение - у вас должна быть возможность использовать некоторую форму insert() (на самом деле я не знаю точный интерфейс, но я думаю, что append() - это название) вставить весь вектор цели сразу, что должно быть значительно лучше.

Кроме того, вы оставляете dynamic_bitset как unsigned long, но, насколько я вижу, вы фактически только вставляете unsigned char в него. Изменение, которое может сделать вашу жизнь проще.

Мне также любопытно, что это за тип codes_ - если это map, вы можете заменить его на vector, или infact, поскольку он имеет максимальный статический размер (256 записей - максимум для unsigned char), статический массив.

Answer 2

Я написал свой собственный класс bitset.Я ценю любые предложения по улучшению.Я попытаюсь заглянуть в SSE и посмотреть, есть ли там что-нибудь полезное.

С моим очень грубым тестом я получил увеличение производительности в 11 раз при добавлении 6 бит за раз.

class fast_bitset
{
public:
    typedef unsigned long block_type;
    static const size_t bits_per_block = sizeof(block_type)*8;

    fast_bitset() 
        : is_open_(true)
        , blocks_(1)
        , space_(blocks_.size()*bits_per_block){}

    void append(const fast_bitset& other)
    {
        assert(!other.is_open_);

        for(size_t n = 0; n < other.blocks_.size()-1; ++n)
            append(other.blocks_[n], bits_per_block);
        append(other.blocks_.back() >> other.space_, bits_per_block - other.space_);
    }

    void append(block_type value, size_t n_bits)
    {
        assert(is_open_);
        assert(n_bits < bits_per_block);

        if(space_ < n_bits)
        {
            blocks_.back() = blocks_.back() << space_;
            blocks_.back() = blocks_.back() | (value >> (n_bits - space_));
            blocks_.push_back(value);
            space_ = bits_per_block - (n_bits - space_);
        }
        else
        {
            blocks_.back() = blocks_.back() << n_bits;
            blocks_.back() = blocks_.back() | value;
            space_ -= n_bits;
        }
    }

    void push_back(bool bit)
    {
        append(bit, 1);
    }

    bool operator[](size_t index) const
    {
        assert(!is_open_);

        static const size_t high_bit = 1 << (bits_per_block-1);
        const size_t block_index = index / bits_per_block;
        const size_t bit_index = index % bits_per_block;
        const size_t bit_mask = high_bit >> bit_index;
        return blocks_[block_index] & bit_mask;
    }

    void close()
    {
        blocks_.back() = blocks_.back() << space_;
        is_open_ = false;
    }

    size_t size() const
    {
        return blocks_.size()*bits_per_block-space_;
    }

    const std::vector<block_type>& blocks() const {return blocks_;}

    class reader
    {
    public:
        reader(const fast_bitset& bitset) 
            : bitset_(bitset)
            , index_(0)
            , size_(bitset.size()){}
        bool next_bit(){return bitset_[index_++];}
        bool eof() const{return index_ >= size_;}
    private:
        const fast_bitset& bitset_;
        size_t index_;
        size_t size_;
    };

private:
    bool is_open_;
    std::vector<block_type> blocks_;
    size_t space_;
};

Answer 3

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

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