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