Pre-Allocated Lists in Python (rednafi.github.io)

This is interesting, and probably worth knowing, but I would like to see when it would be worth preallocating instead of a comprehension. Maybe there is a situation where the code is too complex for a comprehension directly, but putting it into a separate function for the comprehension to call would slow things down more than pre allocating the list.

EDIT:

I just tried it out and answered my own question.

  length = 10_000
  def func(i):
    """simplest function"""
    return i


  %%timeit
  #preallocating list
  pre = [None] * length
  for i in range(length):
      pre[i] = i

366 µs ± 2.03 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

  %%timeit
  #comprehension
  comp = [i for i in range(length)]

267 µs ± 2.75 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

  %%timeit
  #preallocating list with function
  pre_func = [None] * length
  for i in range(length):
      pre_func[i] = func(i)

1.04 ms ± 11.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

  %%timeit
  #comprehension with function
  comp_func = [func(i) for i in range(length)]

844 µs ± 8.61 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

So it looks like the act of calling a function in a comprehension is definitely slower than preallocating a list and running the code in-line. I thought it would take more than 10,000 iterations to be faster, but I was very wrong. It turns out that even with 1 iteration it is faster to preallocate a list and do the code in-line, then to do a comprehension while calling a function.

It's still fast enough that I doubt I'll be doing this. I prefer lots of smaller functions to keep things maintainable, but now I'll keep in mind the cost of calling a function for code that is moving too slow.

EDIT2: While working out a way to test this without using range I was about to do use enumerate, and instead I tested with enumerate and range to see what kind of an effect enumerate would add, and it turns out that it is even faster to just append the list than preallocate if you need to use enumerate, which you would likely need to do if your data doesn't already have it's own index.

  %%timeit
  #just appending
  append = []
  for i in range(length):
      append.append(i)

551 µs ± 5.18 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

  %%timeit
  #preallocating list with enumerate
  pre = [None] \* length
  for i, v  in enumerate(range(length)):
      pre[i] = v

625 µs ± 8.56 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

EDIT3: since we know the length we could avoid using enumerate with zip(range(length), iterable), and that seems to be an improvement

  %%timeit
  #preallocating list, avoiding enumerate
  pre = [None] * length
  for i, v  in zip(range(length), range(length)): #silly, but pretend the second one is actual data
      pre[i] = v

463 µs ± 5.55 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

EDIT4:(I really shouldn't have drank coffee so late)

  I just tried using map with list, and it was the fastest way to call a function, but still slower than all of the ways that didn't call a function.   Again, I'm surprised it was faster than a comprehension, I thought they were effectively the same thing. 

  %%timeit
  #map with range
  map_func = list(map(func, range(length)))

676 µs ± 15.8 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

FYI: I did these tests in jupyter with python 3.10.0, on macOS 11.6 intel. I ran them more than once, and the numbers varied, but the order remained the same.

I'm not going any farther down this rabbithole. I always optimize for readability over speed anyway. But I would be curious if someone else could get faster speeds, or could explain why my tests weren't valid.

  def pgen():
      with open('/etc/passwd') as f:
          for char in f.read():
              yield char

  def func(i):
      """simplest function"""
      return i

  length = len(list(pgen()))


  %%timeit
  #preallocating list without range
  pre = [None] * length
  for i, v  in enumerate(pgen()):
      pre[i] = v

  %%timeit
  #preallocating list from custom generator, and zipping from range to avoid enumerate
  pre = [None] * length
  for i,v in zip(range(length), pgen()):
      pre[i] = v

  %%timeit
  #comprehension without range
  comp = [v for v in pgen()]

  %%timeit
  #comprehension without range, and using enumerate to judge the difference fairly
  comp = [v for i, v in enumerate(pgen())]

For me the crossover point seems to be around 400k elements:

  >>> timeit.timeit('''a = [i for i in range(400000)]''', number=10); timeit.timeit('''
  l = [None] * 400000
  for i in range(len(l)):
      l[i] = i
  ''', number=10)
  0.17413130006752908
  0.1694186998065561

I was surprised to see that allocating with numpy is actually 2x slower than allocating a list:

  In [4]: length = 10000

  In [5]:   %%timeit
   ...:   #preallocating list
   ...:   pre = [None] \* length
   ...:   for i in range(length):
   ...:       pre[i] = i
   ...: 
  346 µs ± 10.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

  In [6]: %%timeit
   ...: pre = np.empty(length, dtype=int)
   ...: for i in range(length):
   ...:     pre[i] = i
   ...:

  688 µs ± 20.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

  In [1]: length = 10_000

  In [2]: %%timeit
     ...: pre = [None] * length
     ...: 
     ...: 
  38.7 µs ± 128 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
  
  In [3]: %%timeit
     ...: pre = np.empty(length, dtype=int)
     ...: 
     ...: 
  1.32 µs ± 6.59 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

  lst = [0]
  %timeit lst[0] = 1
  33.9 ns ± 0.0415 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
  
  arr = np.empty(1, dtype=int)  
  %timeit arr[0] = 1
  73.4 ns ± 0.306 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

  In [1]: import numpy as np
  
  In [2]: %timeit np.arange(10000, dtype=np.int64)
  3.03 µs ± 94.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  
  In [3]: import numba
  
  In [4]: @numba.jit
     ...: def alloc_np_jit(length):
     ...:     pre = np.empty(length, dtype=np.int64)
     ...:     for i in range(length):
     ...:         pre[i] = i
     ...:     return pre
     ...:
  
  In [5]: %timeit alloc_np_jit(10000)
  1.56 µs ± 12.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

The article is interesting, but there's really no point making little micro-optimisations like this in Python (yes a 35% increase in speed to one small part of your program is a micro-optimisation). If the code is really performance critical (by which I mean, the person running the program would notice a difference) then use a more suitable compiled language e.g. by calling into a C extension module like numpy. But, most of the time, making small performance tweaks will result in no noticable impact.

Some optimisations in pure Python are genuinely worth it, but they're usually by using a totally different data structure to change the asymptotic complexity e.g. if you repeatedly use `x in foo` in a loop then it's worth making sure foo is a set rather than a list.

    l = [None] * 10_000

How is this in Pypy, and why isn't it used more broadly?

This is an awesome view into the implementation details of python. Can anyone recommend other resources that go into the lower level python implementation?