[boost] dynamic_bitset

From: Alkis Evlogimenos (alkis_at_[hidden])
Date: 2002-10-19 21:27:44

Hi,

dynamic_bitset<>::resize() always allocates a new block when called even if 
the number of blocks needed is the same. This causes a performance bottleneck 
for appliations that use resize() frequently. IMO it would be best to change 
the semantics of resize() to be the same as std::vector::resize() and at the 
same time provide a reserve() function. Shinking a dynamic_bitset<> can still 
be achieved using the swap idiom but any resize() calls will not reallocate 
if the current block is big enough.

What do you guys think?

Here's a patch against Version_1_29_0:

Index: dynamic_bitset.hpp
===================================================================
RCS file: /n/cvsrep/src/boost/boost/dynamic_bitset.hpp,v
retrieving revision 1.1.1.1
diff -r1.1.1.1 dynamic_bitset.hpp
235a236
>     void reserve(size_type num_bits);
510a512
>
512,517c514,515
<   Block* d = this->m_alloc.allocate(new_nblocks, static_cast<void const 
*>(0));
<   if (num_bits < size()) { // shrink
<     std::copy(this->m_bits, this->m_bits + new_nblocks, d);
<     std::swap(d, this->m_bits);
<     this->m_alloc.deallocate(d, this->m_num_blocks);
<   } else { // grow
---
>   if (this->m_num_blocks < new_nblocks) { // reallocate
>     Block* d = this->m_alloc.allocate(new_nblocks, static_cast<void const 
*>(0));
522,524d519
<     for (std::size_t i = this->m_num_bits;
<          i < this->m_num_blocks * bits_per_block; ++i)
<       set_(i, value);
526a522
>     this->m_num_blocks = new_nblocks;
527a524,527
>   for (std::size_t i = this->m_num_bits;
>        i < this->m_num_blocks * bits_per_block; ++i)
>     set_(i, value);
>
529c529,544
<   this->m_num_blocks = this->calc_num_blocks(num_bits);
---
>   m_zero_unused_bits();
> }
>
> template <typename Block, typename Allocator>
> void dynamic_bitset<Block, Allocator>::
> reserve(size_type num_bits)
> {
>   size_type new_nblocks = this->calc_num_blocks(num_bits);
>   if (this->m_num_blocks >= new_nblocks)
>     return;
>   Block* d = this->m_alloc.allocate(new_nblocks, static_cast<void const 
*>(0));
>   std::copy(this->m_bits, this->m_bits + this->m_num_blocks, d);
>   std::swap(d, this->m_bits);
>   if (d != 0)
>     this->m_alloc.deallocate(d, this->m_num_blocks);
>   this->m_num_blocks = new_nblocks;
1395c1410
<     assert (this->m_num_blocks == this->calc_num_blocks(this->m_num_bits));
---
>     assert (this->m_num_blocks >= this->calc_num_blocks(this->m_num_bits));
-- 
Alkis