Re: [Boost-users] optimizing use of dynamic_bitset

From: Zeljko Vrba (zvrba_at_[hidden])
Date: 2007-06-14 13:11:52

On Thu, Jun 14, 2007 at 10:36:18AM -0600, Dave Steffen wrote:
> 
> Profiling data now indicates that one of the more expensive operations
> is spending most of its time calling dynamic_bitset<>::test a
> bajillion times.  My question is this: is dynamic_bitset::test
> generally thought to be the fastest way to access a specific bit in a
> dynamic_bitset?  Are there other ways to determine if bit n is set?  
> 
In boost/dynamic_bitset/dynamic_bitset.hpp I find the following definition

template <typename Block, typename Allocator>
bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
{
    return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
}

This can be further optimized by using processor-specific instructions
(inline asm); eg. x86 CPUs have the BT (bit test) instruction which tests
a particular bit.  The nice thing about it is that it works over arbitrarily
long bit strings in memory.  Thus, a memory reference, AND and runtime
computation of bitmask (at least 3 instructions) can be boiled down to a single
instruction.  I doubt that compiler optimizers are smart enough to recognize
the above pattern and convert it automatically to CPU-specific code.  You
can always check by disassembling the generated code.