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
bool dynamic_bitset::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.
