Pre-Allocated Lists in Python | Hacker News Reader

Pre-Allocated Lists in Python

rednafi.github.io

77 pointsEntICOnc31 comments

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)

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)

  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)

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)

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)

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

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/

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).

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.

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

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.

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

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

Sure, but if you can easily get that 10% improvement in your existing code, you probably should take advantage of the easy win. Even if you're eventually going to rewrite all or part of it in another language.

To me, it seems like there is potentially quite a good business case for writing

    l = [None] * 10_000

instead of rewriting parts of your application in C (possibly hiring new staff to do so).

Very short term maybe. Medium term you're just putting off work and building up technical debt.

That's a very naive statement. In machine learning, for example, there's a lot of scenarios where performance isn't critical but due to the huge quantities of data you may need to process (especially during feature engineering or selection), micro optimisations like this can result in huge improvements over millions of iterations.

Not to mention Python has Cython and numba's JIT which can provide great performance when needed.

I was actually waiting for this comment to pop up. Unfortunately, it's not so black and white as it seems. The service in question is deeply coupled with a Django monolith and rewriting that will be mostly a waste of time for a medium scale business like us.

However, micro-optimizations and effective refactoring quickly add up and for us, improving the service response by 100ms via micro-optimization is better than improving it by 200ms via rewriting the entire service.

200ms -> 100ms for a whole request (not just a tiny part of a request) is indeed worthwhile, I never meant to disagree with that. But for micro-optimisations, you'd be lucky to get a 10% speed increase in 10% of things you do, which would only give only a speed increase of 1% overall (obviously those are made up numbers to illustrate the idea). As I said in my first comment, usually the actual gains come from using a different data structures or making vectorised calls in to C libraries, and I assume that's what you mean by the effective refactorings in your case.

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.

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.

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.

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.

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)

Python does have a special optimization: when the iterable in a comprehension has len() defined, then Python preallocates the list. The comprehension is faster than manual preallocation+filling because the indexing happens in C instead of in Python.

Python does have a special optimization: when the iterable in a comprehension has len() defined, then Python preallocates the list.

ok, that makes sense then. So when I made a generator it didn't get the preallocation advantage, but range did because the range object has len.

The comprehension is faster than manual preallocation+filling because the indexing happens in C instead of in Python.

I learned this a long time ago, and have tried to use comprehensions since, To the point where I had to draw a line for readability because it was annoying co-workers. Though I never really took the time to understand what "In C" actually meant beyond it being an optimization over using a for loop with append.

Do you happen to know why list(map(func, iterable)) is faster than [func(_) for _ in iterable] ? I assume something about calling back to a python function from C, but my knowledge of the internals is obviously lacking at these levels.

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

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.

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.

Other languages have large ecosystems as well, though, and are often far easier to optimize for speed. For python, speed was pretty much a non-goal.

You could try to switch to Go or Nodejs - or do what Numpy/Scipy and TensorFlow did: write the performance-critical parts in C and only use python for the high-level control logic.

You fundamentally misunderstand my point. My point is that if a particular project has a particular rock-solid need for something that Python can't do, you shouldn't choose Python.

You can stick any language in there for that. You name the language, I'll name a disqualifying need for it. (A really simple one is "I want to work on $PLATFORM". There's hardly a language that's a great choice for iPhone, Android, desktop app, and server. There's some languages that can at least do all four but they aren't generally a great choice for all four.)

It is about matching the needs of a project to the implementation language, and neither blindly picking languages because they are "good", so they must be good at everything, nor blindly disqualifying languages because they are "bad", so they must be bad at everything.

If you need to go fast, you shouldn't have chosen Python. You don't always need to go fast. In fact, many people greatly overestimate their need to go fast! But if you did have that need to go fast, you shouldn't have chosen Python.

I observe that this bothers people, because they treat it as an emotional decision about who or what they are endorsing, or what team they are or are not part of. This is the wrong view. It is an engineering question, just like I would ask whether I use steel or plywood. There is no "team steel" and "team plywood", no "plywood is better at everything!" "no way dude, plywood rules, steel droolz!". Just tools that need to be analyzed.

Reply on news.ycombinator.com