title: boost::dynamic_bitset slower than std::bitset unless std::bitset is reset
body: <p>I recently came across the bitset templates and would really like to use them in my current project.  Reading on, I see that the <code>std::bitset</code> template must have a size determined at compile time.  Many suggest using the <code>boost::dynamic_bitset</code> to alleviate this requirement.</p>
  
  <p>To compare the two, I decided to do a speed comparison of <code>set</code>, <code>flip</code>, and <code>count</code> methods.</p>
  
  <p>The results are quite odd...and I'm wondering if someone can shed some light on it for me.</p>
  
  <p>The code is at the end of the post, but I'll explain what I'm doing here.  I have one <code>std::bitset</code> object (call it <code>bs</code>) and one <code>boost::dynamic_bitset</code> object (call it <code>dynbs</code>).  Each has <code>n=1000000</code> bits.  For a given method above, call the method on each of the <code>n</code> bits sequentially and repeat this <code>R=10000</code> times.</p>
  
  <p>Using the <code>std::chrono</code> library, here are the timings for each in nanoseconds:</p>
  
  <pre class="lang-none prettyprint-override"><code>set
          bitset:              267 nsecs
      dyn bitset:      18603174546 nsecs
  
  flip
          bitset:               73 nsecs
      dyn bitset:      18842352867 nsecs
  
  count
          bitset:               77 nsecs
      dyn bitset:               51 nsecs
  </code></pre>
  
  <p>The <code>boost::dynamic_bitset</code> seems to be much slower for <code>set</code> and <code>flip</code>.</p>
  
  <p>To make it more interesting, if the method <code>reset</code> is called on the two objects before running these tests, then the timings are comparable.  Here they are:</p>
  
  <pre class="lang-none prettyprint-override"><code>set
          bitset:      19397779399 nsecs
      dyn bitset:      18472863864 nsecs
  
  flip
          bitset:      18599248629 nsecs
      dyn bitset:      18376267939 nsecs
  
  count
          bitset:               68 nsecs
      dyn bitset:               61 nsecs
  </code></pre>
  
  <p>Now, both containers claim to initialize all bits to <code>0</code>, thus a call to <code>reset</code> shouldn't change any of the bits.  Dumping the output of <code>none</code> before and after <code>reset</code> does confirm this.</p>
  
  <p>So after all that, I have two questions:</p>
  
  <p>1)  Why is the <code>boost::dynamic_bitset</code> so much slower than the <code>std::bitset</code> when calling <code>set</code> and <code>flip</code>?</p>
  
  <p>2)  Why does calling <code>reset</code> have a huge negative effect on the speed of <code>std::bitset</code>?</p>
  
  <p>Here is my code:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>#include &lt;iostream&gt;
  #include &lt;iomanip&gt;
  #include &lt;bitset&gt;
  #include &lt;boost/dynamic_bitset.hpp&gt;
  #include &lt;vector&gt;
  #include &lt;chrono&gt;
  #include &lt;ctime&gt;
  
  using namespace std;
  using namespace chrono;
  using namespace boost;
  
  int main(){
    const unsigned int n=1000000;
    bitset&lt; n &gt; bs;
    dynamic_bitset&lt; &gt; dynbs(n);
    // bs.reset();
    // dynbs.reset();
  
    unsigned int i,r,R=10000;
    high_resolution_clock::time_point tick,tock;
  
  
    ////////////////////////////////////////////////////////////
    // Method: set
  
    std::cout &lt;&lt; "set" &lt;&lt; std::endl;
  
    tick=high_resolution_clock::now();
  
    for(r=0; r&lt;R; r++)
      for(i=0; i&lt;n; i++)
        bs.set(i);
  
    tock=high_resolution_clock::now();
    cout &lt;&lt; setw(16) &lt;&lt; "bitset: " 
         &lt;&lt; setw(16) &lt;&lt; duration_cast&lt;nanoseconds&gt;(tock-tick).count() &lt;&lt; " nsecs" 
         &lt;&lt; std::endl;
  
    tick=high_resolution_clock::now();
  
    for(r=0; r&lt;R; r++)
      for(i=0; i&lt;n; i++)
        dynbs.set(i);
  
    tock=high_resolution_clock::now();
    cout &lt;&lt; setw(16) &lt;&lt; "dyn bitset: " 
         &lt;&lt; setw(16) &lt;&lt; duration_cast&lt;nanoseconds&gt;(tock-tick).count() &lt;&lt; " nsecs"
         &lt;&lt; std::endl &lt;&lt; std::endl;
  
  
    ////////////////////////////////////////////////////////////
    // Method: flip
  
    std::cout &lt;&lt; "flip" &lt;&lt; std::endl;
  
    tick=high_resolution_clock::now();
  
    for(r=0; r&lt;R; r++)
      for(i=0; i&lt;n; i++)
        bs.flip(i);
  
    tock=high_resolution_clock::now();
    cout &lt;&lt; setw(16) &lt;&lt; "bitset: " 
         &lt;&lt; setw(16) &lt;&lt; duration_cast&lt;nanoseconds&gt;(tock-tick).count() &lt;&lt; " nsecs"
         &lt;&lt; std::endl;
  
    tick=high_resolution_clock::now();
  
    for(r=0; r&lt;R; r++)
      for(i=0; i&lt;n; i++)
        dynbs.flip(i);
  
    tock=high_resolution_clock::now();
    cout &lt;&lt; setw(16) &lt;&lt; "dyn bitset: " 
         &lt;&lt; setw(16) &lt;&lt; duration_cast&lt;nanoseconds&gt;(tock-tick).count() &lt;&lt; " nsecs"
         &lt;&lt; std::endl &lt;&lt; std::endl;
  
  
    ////////////////////////////////////////////////////////////
    // Method: count
  
    std::cout &lt;&lt; "count" &lt;&lt; std::endl;
  
    tick=high_resolution_clock::now();
  
    for(r=0; r&lt;R; r++)
      for(i=0; i&lt;n; i++)
        bs.count();
  
    tock=high_resolution_clock::now();
    cout &lt;&lt; setw(16) &lt;&lt; "bitset: " 
         &lt;&lt; setw(16) &lt;&lt; duration_cast&lt;nanoseconds&gt;(tock-tick).count() &lt;&lt; " nsecs"
         &lt;&lt; std::endl;
  
    tick=high_resolution_clock::now();
  
    for(r=0; r&lt;R; r++)
      for(i=0; i&lt;n; i++)
        dynbs.count();
  
    tock=high_resolution_clock::now();
    cout &lt;&lt; setw(16) &lt;&lt; "dyn bitset: " 
         &lt;&lt; setw(16) &lt;&lt; duration_cast&lt;nanoseconds&gt;(tock-tick).count() &lt;&lt; " nsecs"
         &lt;&lt; std::endl;
  
  
    return 0;
  }
  </code></pre>
  
  <p>I compiled it with</p>
  
  <pre class="lang-none prettyprint-override"><code>g++ -O3 -std=c++11 bitset.cpp -o bitset
  </code></pre>
  
  <p>where <code>bitset.cpp</code> is the code inserted above.</p>