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.