title: Python deque performance for small iterables
body: <p>I was playing around with Python's collection.deque and wrote the following benchmark:</p>
  
  <pre><code>#!/usr/bin/python
  
  import timeit
  
  if __name__=='__main__':
      number = 1000000
      for r in (1,10,100,1000,5000,10000,100000):
          print r
          print timeit.timeit("while x: x.pop(0);",
                              "x = list(range("+str(r)+"))",
                              number=number)
          print timeit.timeit("while x: x.popleft();",
                              "from collections import deque; x = deque(range("+str(r)+"))",
                               number=number)
  </code></pre>
  
  <p>This will pop(0)/popleft() from a list/deque with various sizes. The results are:</p>
  
  <pre><code>1
  0.0801048278809
  0.0822219848633
  10
  0.081041097641
  0.080836057663
  100
  0.0806250572205
  0.0807700157166
  1000
  0.081248998642
  0.082062959671
  5000
  0.0976719856262
  0.0825741291046
  10000
  0.157499074936
  0.0825819969177
  100000
  16.0247170925
  0.097559928894
  </code></pre>
  
  <p>My question is: Why is the performance for small deques and lists (~1000 elements) almost the same?</p>