title: Speed up bitstring/bit operations in Python?
body: <p>I wrote a prime number generator using <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noreferrer">Sieve of Eratosthenes</a> and Python 3.1. The code runs correctly and gracefully at 0.32 seconds on <a href="http://ideone.com/wCJm5" rel="noreferrer">ideone.com</a> to generate prime numbers up to 1,000,000.</p>
  
  <pre><code># from bitstring import BitString
  
  def prime_numbers(limit=1000000):
      '''Prime number generator. Yields the series
      2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...    
      using Sieve of Eratosthenes.
      '''
      yield 2
      sub_limit = int(limit**0.5) 
      flags = [False, False] + [True] * (limit - 2)   
  #     flags = BitString(limit)
      # Step through all the odd numbers
      for i in range(3, limit, 2):       
          if flags[i] is False:
  #        if flags[i] is True:
              continue
          yield i
          # Exclude further multiples of the current prime number
          if i &lt;= sub_limit:
              for j in range(i*3, limit, i&lt;&lt;1):
                  flags[j] = False
  #                flags[j] = True
  </code></pre>
  
  <p>The problem is, I run out of memory when I try to generate numbers up to 1,000,000,000.</p>
  
  <pre><code>    flags = [False, False] + [True] * (limit - 2)   
  MemoryError
  </code></pre>
  
  <p>As you can imagine, allocating 1 billion boolean values (<strike>1 byte</strike> 4 or 8 bytes (see comment) each in Python) is really not feasible, so I looked into <a href="http://code.google.com/p/python-bitstring/" rel="noreferrer">bitstring</a>. I figured, using 1 bit for each flag would be much more memory-efficient. However, the program's performance dropped drastically - 24 seconds runtime, for prime number up to 1,000,000. This is probably due to the internal implementation of bitstring.</p>
  
  <p>You can comment/uncomment the three lines to see what I changed to use BitString, as the code snippet above.</p>
  
  <p>My question is, <strong>is there a way to speed up my program, with or without bitstring?</strong></p>
  
  <p>Edit: Please test the code yourself before posting. I can't accept answers that run slower than my existing code, naturally.</p>
  
  <p><strong>Edit again:</strong></p>
  
  <p><a href="https://stackoverflow.com/questions/2897297/speed-up-bitstring-bit-operations-in-python/2903765#2903765">I've compiled a list of benchmarks on my machine.</a></p>