title: Relative performance of large and small lists and bytearrays of boolean values
body: <p>I was writing a simple <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Sieve of Eratosthenes</a> in which one produces a list of all of primes up to some number N without performing any division or modular arithmetic. Abstractly, my implementation uses an array of N boolean values which all start out False and are eventually flipped to True over the course of the algorithm.</p>
  
  <p>I wanted to know if this would be faster and/or use less memory if I implemented it as a <code>list</code> of <code>0</code> and <code>1</code>, a <code>list</code> of <code>True</code> and <code>False</code>, or a <code>bytearray</code> of <code>0</code> and <code>1</code>.</p>
  
  <h3>Timing (python 2.7)</h3>
  
  <p>Using python 2.7, I found the following when using N = 10k and N = 30M:</p>
  
  <pre><code>$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list(3000000)'
  10 loops, best of 3: 1.42 sec per loop
  $ python -m timeit -s 'import sieve' -n 10 'sieve.soe_byte(3000000)'
  10 loops, best of 3: 1.23 sec per loop
  $ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list2(3000000)'
  10 loops, best of 3: 1.65 sec per loop
  
  $ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list(10000)'
  500 loops, best of 3: 3.59 msec per loop
  $ python -m timeit -s 'import sieve' -n 500 'sieve.soe_byte(10000)'
  500 loops, best of 3: 4.12 msec per loop
  $ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list2(10000)'
  500 loops, best of 3: 4.25 msec per loop
  
              10k       3M
  byte (01)   4.12 ms   1.23 s
  list (01)   3.59 ms   1.42 s
  list (TF)   4.25 ms   1.65 s
  </code></pre>
  
  <p>What surprises me is that for small values of N, the <code>list</code> of integers was the best, and for large values of N, the <code>bytearray</code> was the best. The <code>list</code> of True and False was always slower.</p>
  
  <h3>Timing (python 3.3)</h3>
  
  <p>I also repeated the test in python 3.3:</p>
  
  <pre><code>$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list(3000000)'
  10 loops, best of 3: 2.05 sec per loop
  $ python -m timeit -s 'import sieve' -n 10 'sieve.soe_byte(3000000)' 
  10 loops, best of 3: 1.76 sec per loop
  $ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list2(3000000)'
  10 loops, best of 3: 2.02 sec per loop
  
  $ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list(10000)'
  500 loops, best of 3: 5.19 msec per loop
  $ python -m timeit -s 'import sieve' -n 500 'sieve.soe_byte(10000)'
  500 loops, best of 3: 5.34 msec per loop
  $ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list2(10000)'
  500 loops, best of 3: 5.16 msec per loop
  
              10k       3M
  byte (01)   5.34 ms   1.76 s
  list (01)   5.19 ms   2.05 s
  list (TF)   5.16 ms   2.02 s
  </code></pre>
  
  <p>Here there was the same ordering with the <code>list</code> being better for small N, and the <code>bytearray</code> for large N, but the <code>list</code> with <code>True</code> and <code>False</code> was not significantly different than the <code>list</code> with <code>1</code> and <code>0</code>.</p>
  
  <h3>Memory Use</h3>
  
  <p>The memory use was exactly the same in python 2.7 and 3.3. I used <code>sys.getsizeof</code> on the <code>list</code> or <code>bytearray</code>, which was the same size at the beginning and end of the algorithm.</p>
  
  <pre><code>&gt;&gt;&gt; import sieve
  &gt;&gt;&gt; sieve.verbose = True
  &gt;&gt;&gt; x = sieve.soe_list(10000)
  soe_list, 10000 numbers, size = 83120
  &gt;&gt;&gt; x = sieve.soe_byte(10000)
  soe_byte, 10000 numbers, size = 10993
  &gt;&gt;&gt; x = sieve.soe_list2(10000)
  soe_list2, 10000 numbers, size = 83120
  &gt;&gt;&gt; x = sieve.soe_list(3000000)
  soe_list, 3000000 numbers, size = 26791776
  &gt;&gt;&gt; x = sieve.soe_byte(3000000)
  soe_byte, 3000000 numbers, size = 3138289
  &gt;&gt;&gt; x = sieve.soe_list2(3000000)
  soe_list2, 3000000 numbers, size = 26791776
  
              10k       3M
  byte (01)   ~11k      ~3.1M
  list (01)   ~83k      ~27M
  list (TF)   ~83k      ~27M
  </code></pre>
  
  <p><strike>I was a bit surprised~ that the large <code>bytearray</code> used more memory than the large <code>list</code> given that the large <code>bytearray</code> was faster.</strike></p>
  
  <p>EDIT: Oops, as pointed out in the comments, I read my own values wrong and interpreted 27M as 2.7M. The list is really much bigger.</p>
  
  <h3>The Question</h3>
  
  <p>Can anyone explain why this algorithm runs faster using a <code>list</code> for small N, and faster using a <code>bytearray</code> for large N?</p>
  
  <h3>Test code for reference</h3>
  
  <p>sieve.py:</p>
  
  <pre><code>import sys
  
  if sys.version_info.major == 3:
      xrange = range
  
  verbose = False
  
  def soe_byte(upper):
      numbers = bytearray(0 for _ in xrange(0,upper+1))
      if verbose:
          print("soe_byte, {} numbers, size = {}".format(upper, sys.getsizeof(numbers)))
      primes = []
      cur = 2
      while cur &lt;= upper:
          if numbers[cur] == 1:
              cur += 1
              continue
          primes.append(cur)
          for i in xrange(cur,upper+1,cur):
               numbers[i] = 1
      return primes
  
  def soe_list(upper):
      numbers = list(0 for _ in xrange(0,upper+1))
      if verbose:
          print("soe_list, {} numbers, size = {}".format(upper, sys.getsizeof(numbers)))
      primes = []
      cur = 2
      while cur &lt;= upper:
          if numbers[cur] == 1:
              cur += 1
              continue
          primes.append(cur)
          for i in xrange(cur,upper+1,cur):
               numbers[i] = 1
      return primes
  
  def soe_list2(upper):
      numbers = list(False for _ in xrange(0,upper+1))
      if verbose:
          print("soe_list2, {} numbers, size = {}".format(upper, sys.getsizeof(numbers)))
      primes = []
      cur = 2
      while cur &lt;= upper:
          if numbers[cur] == True:
              cur += 1
              continue
          primes.append(cur)
          for i in xrange(cur,upper+1,cur):
               numbers[i] = True
      return primes 
  </code></pre>