Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk