Pre-Allocated Lists in Python

https://rednafi.github.io/reflections/pre-allocated-lists-in-python.html

by EntICOnc • 4 years ago

77 31 4 years ago

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.

chrsig• 4 years ago

when you know the number of elements you'll be putting in the list, you can save on resizing and copying. A comprehension doesn't always know how many elements it will require.

dec0dedab0de4• 4 years ago

I think the article, and my test just showed that the comprehension is faster than preallocating. So if it's something that works well in a comprehension, you should do it that way. The preallocation is only an improvement when the code you're doing per loop is too complex to be done in a comprehension. My initial thought was that a function in a comprehension would be better than preallocation with code in the loop, but I was wrong.

Unless you're suggesting that Python has a special optimization for the range generator in comprehensions, which is plausible, let me think of a way to test for that.

EDIT: I changed it to iterate over the characters in my shadow file, and comprehensions were still faster. I'm not sure if that is enough to fake out possible optimizations, but it definitely rules out range.

  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

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

  %%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

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

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

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

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

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

dataflow• 4 years ago

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

martopix• 4 years ago

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)

sharikous• 4 years ago

You are measuring two things together: allocation and an initialization inside a loop.

I would try to separate them (I.e. measure [None]*length and np.empty(length)

knappa• 4 years ago

  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)

erdewit• 4 years ago

It's that the array access of numpy is surprisingly slow compared to a Python list:

  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)

w-m• 4 years ago

Here was a weird one for me, why is numba jitted initialization twice as fast as np.arange, which presumably has a C implementation?

  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)

quietbritishjim3• 4 years ago

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.

gpvos• 4 years ago

It all depends on context. They did write "[...] the 10% performance improvement was significant for the service that I was working on."

IshKebab2• 4 years ago

Yes but his point is that if a 10% performance improvement is significant then you shouldn't be using Python!

quietbritishjim3• 4 years ago

I knew my comment would be a bit spicy for HN :-)

Frankly, I'm skeptical that it actually was significant for them. IMO people grossly overestimate the utility of a 10% or even 20% increase in speed. (A 90% increase is probably worth the effort, while 50% is borderline.)

If a user clicks on a button and it feels slow (e.g. 500ms), then it's still going to feel slow if you speed it up but it's still the same order of magnitude (e.g. 400ms). Roughly the same is true at all different levels e.g. if you speed things up from 5 hours to 4 hours then it's still long enough that it shapes your day. A similar point applies to hardware costs. And it's even more true if there's some absolute ceiling e.g. if you speed up your service by 20% so it doesn't overflow then you'll still be close to danger if conditions perturb slightly.

And all the above is not even relevant to the article. It's talking about how to preallocate a list. There's no point doing that unless you then populate the list! In most situations that's going to dwarf the time to create the list object, and at the very least is likely to match it. So you're likely to be talking about a tiny fraction of an overall runtime.

rednafi3• 4 years ago

Yep. Our entire stack is primarily based on Python. Rewriting microservices in a faster language seems tempting in theory but in practise there are so many hurdles that sometimes, in medium term, micro-optimizations really pay off.

amelius2• 4 years ago

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

jerf2• 4 years ago

I mean this seriously, dispassionately, and without insult to Python, but this isn't used more broadly because if you're in a "counting microseconds", you shouldn't have chosen Python in the first place, and you ought to be seriously considering getting whatever you're having this sort of performance issue with out of Python entirely. Python qua Python is so slow already that while a quick profile and some low-fruit plucking can be a quick win if you've never done it before, if you need something to go fast you need to get out of Python. The time you save with this technique is almost instantly eaten by all the other slow thing in Python.

Precisely because that's such a great need, there's a lot of ways to do it, beyond the obvious "use another language directly". There's Ye Olde write a C extension. There's Cython, and a family of techniques there. There's trying to use PyPy. There's a whole array of more exotic things, if you do some searching around on the web, which may work for you. If you are in a "counting microseconds" situation, all of these are going to pay off much better than trying to squeeze Python.

I include the first few words of my post here because I do not mean this as an "insult" or a slag on Python. It is simply something that people need to understand when they choose solutions to their problem. Everything has advantages and disadvantages. Python has many advantages, but one of its most noticeable disadvantages is that if you just naively and simply program Python, you end up working in the slowest class of languages. You can also slow down your code much more than you may realize if you pile the abstractions on too heavily. This isn't something you should process through a "rah rah! / booo!" "my team" filter, this is engineering facts on the ground.

amelius2• 4 years ago

Like you said, Python has many advantages and disadvantages. Choosing one of the disadvantages and disqualifying Python based on it doesn't seem fair. It is also not very useful. Python has the largest ecosystem on the planet. Lack of X, Y of Z could disqualify a platform, yet Python has them all. If, by increasing performance even 10% you can put the Python ecosystem to better use, that's already a huge win.

iams• 4 years ago

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

rednafi3• 4 years ago

I'd suggest following Bret Cannon's Syntactic Sugar series. It's an awesome overview of what goes behind different Python data structures.

https://snarky.ca/tag/syntactic-sugar/

neoncontrails• 4 years ago

I highly recommend Victor Skvortsov's exhaustive, 12-part series, "Python Behind the Scenes," a deep dive into the implementation details of just about every Python language feature one could possibly take for granted. There isn't a single one I haven't learned something from, but some of my personal favorites include:

* Part 2, How the CPython compiler works: https://tenthousandmeters.com/blog/python-behind-the-scenes-...

* Part 6, How Python's object system works: https://tenthousandmeters.com/blog/python-behind-the-scenes-...

* Part 10, How Python dictionaries work: https://tenthousandmeters.com/blog/python-behind-the-scenes-...

* Part 13: The GIL and its effects on Python multithreading: https://tenthousandmeters.com/blog/python-behind-the-scenes-...

The whole series can be found here: https://tenthousandmeters.com/tag/python-behind-the-scenes/

For a slightly higher-level (i.e., no macabre, low-level C code), but still incredibly enlightening dive into the "dark side" of Python, in particular various abuses and hexes for manipulating control flow, have a look at David Beazley's smorgasboard of keynote presentations like "Generators: The Final Frontier" (https://www.dabeaz.com/finalgenerator/), "Python Concurrency From The Ground Up" (https://www.youtube.com/watch?v=MCs5OvhV9S4), and "Build Your Own Async" (https://www.youtube.com/watch?v=Y4Gt3Xjd7G8&t=2045s).

AndrewOMartin• 4 years ago

https://www.youtube.com/watch?v=p33CVV29OG8

Modern Dictionaries by Raymond Hettinger

The official description of this talk is below, but personally, I'd watch any video with "Raymond Hettinger" in the title.

Python's dictionaries are stunningly good. Over the years, many great ideas have combined together to produce the modern implementation in Python 3.6. This fun talk is given by Raymond Hettinger, the Python core developer responsible for the set implementation and who designed the compact-and-ordered dict implemented in CPython for Python 3.6 and in PyPy for Python 2.7. He will use pictures and little bits of pure python code to explain all of the key ideas and how they evolved over time. He will also include newer features such as key-sharing, compaction, and versioning. This talk is important because it is the only public discussion of the state of the art as of Python 3.6. Even experienced Python users are unlikely to know the most recent innovations.

Pre-Allocated Lists in Python

Related Stories