Boost :: dynamic_bitset concat performance

Question

I want to combine a large bitset with a smaller one so as not to kill performance. Currently, my application spends 20% of the processor time only on the following code:

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; } 

I read this post , which proposes a solution, which, unfortunately, will not work for me, since the size difference between the destination destination bits and the original bitrate is very large.

Any ideas?

If this cannot be done with boost :: dynamic_bitset, then I am open to other suggestions.

Answer 1

I wrote my own class of bits. I appreciate any suggestions for improvement. I will try to look in SSE and see if there is anything useful there.

With my rough standard, I really got an 11-fold increase in performance, adding 6 bits at a time.

 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 2

This is because you continue to use push_back() , but in fact you already know the size in advance. This means a lot of redundant copying and redistribution. You must first resize it. In addition, you do not need push_back() each value - you must use some form of insert() (I really do not know its exact interface, but I think append() is the name) to insert the entire target vector at once, which should be much better.

In addition, you leave dynamic_bitset as an unsigned long, but as far as I can see, you only insert an unsigned char into it. A change that can make your life easier.

I am also curious what type of codes_ is - if it is map , you can replace it with vector or infact, since it is statically maximum size (256 entries is the maximum unsigned char ), a static array.

Answer 3

I tried to use boost-bit in performance code before and was disappointed. I delved into it a bit and came to the conclusion that I had better implement my own class of buffer buffers, although I forget that the details of what convinced me to upgrade would never be fast (I went to check the production assembly).

I still don’t know what is the fastest way to create bit buffers / bits / bit streams or something that you want to call them. A colleague is trying to find out this question, but at the time of writing he is still expecting a good answer.