title: Optimizing bit array accesses
body: <p>I'm using Dipperstein's bitarray.cpp class to work on bi-level (black and white) images where the image data is natively stored as simply as one pixel one bit.</p>
  
  <p>I need to iterate through each and every bit, on the order of 4--9 megapixels per image, over hundreds of images, using a for loop, something like:</p>
  
  <pre><code>for( int i = 0; i &lt; imgLength; i++) {
      if( myBitArray[i] == 1 ) {
           //  ... do stuff ...
      }
  }
  </code></pre>
  
  <p>Performance is usable, but not amazing.  I run the program through gprof and find out there is significant time and millions of calls to <code>std::vector</code> methods like iterator and begin.  Here's the top-sampled functions:</p>
  
  <pre><code>Flat profile:
  
  Each sample counts as 0.01 seconds.
    %   cumulative   self              self     total           
   time   seconds   seconds    calls   s/call   s/call  name    
   37.91      0.80     0.80        2     0.40     1.01  findPattern(bit_array_c*, bool*, int, int, int)
   12.32      1.06     0.26 98375762     0.00     0.00  __gnu_cxx::__normal_iterator&lt;unsigned char const*, std::vector&lt;unsigned char, std::allocator&lt;unsigned char&gt; &gt; &gt;::__normal_iterator(unsigned char const* const&amp;)
   11.85      1.31     0.25 48183659     0.00     0.00  __gnu_cxx::__normal_iterator&lt;unsigned char const*, std::vector&lt;unsigned char, std::allocator&lt;unsigned char&gt; &gt; &gt;::operator+(int const&amp;) const
   11.37      1.55     0.24 49187881     0.00     0.00  std::vector&lt;unsigned char, std::allocator&lt;unsigned char&gt; &gt;::begin() const
    9.24      1.75     0.20 48183659     0.00     0.00  bit_array_c::operator[](unsigned int) const
    8.06      1.92     0.17 48183659     0.00     0.00  std::vector&lt;unsigned char, std::allocator&lt;unsigned char&gt; &gt;::operator[](unsigned int) const
    5.21      2.02     0.11 48183659     0.00     0.00  __gnu_cxx::__normal_iterator&lt;unsigned char const*, std::vector&lt;unsigned char, std::allocator&lt;unsigned char&gt; &gt; &gt;::operator*() const
    0.95      2.04     0.02                             bit_array_c::operator()(unsigned int)
    0.47      2.06     0.01  6025316     0.00     0.00  __gnu_cxx::__normal_iterator&lt;unsigned char*, std::vector&lt;unsigned char, std::allocator&lt;unsigned char&gt; &gt; &gt;::__normal_iterator(unsigned char* const&amp;)
    0.47      2.06     0.01  3012657     0.00     0.00  __gnu_cxx::__normal_iterator&lt;unsigned char*, std::vector&lt;unsigned char, std::allocator&lt;unsigned char&gt; &gt; &gt;::operator*() const
    0.47      2.08     0.01  1004222     0.00     0.00  std::vector&lt;unsigned char, std::allocator&lt;unsigned char&gt; &gt;::end() const
  ... remainder omitted ...
  </code></pre>
  
  <p>I'm not really familiar with C++'s STL, but can anyone shed light on why, for instance, std::vector::begin() is being called a few million times?  And, of course, whether there's something I can be doing to speed it up?</p>
  
  <p><strong>Edit:</strong> I just gave up and optimized the search function (the loop) instead.</p>