How often does Python allocate? (zackoverflow.dev)

A caveat applies to the entire analysis that CPython may be the reference implementation, but it's still just one implementation. This sort of thing may work totally differently in PyPy, and especially in implementations that make use of another garbage-collecting runtime, such as Jython.

> Let’s take out the print statement and see if it’s just the addition:

Just FWIW: the assignment is not required to prevent optimizing out the useless addition. It isn't doing any static analysis, so it doesn't know that `range` is the builtin, and thus doesn't know that `i` is an integer, and thus doesn't know that `+` will be side-effect-free.

> Nope, it seems there is a pre-allocated list of objects for integers in the range of -5 -> 1025. This would account for 1025 iterations of our loop but not for the rest.

1024 iterations, because the check is for numbers strictly less than `_PY_NSMALLPOSINTS` and the value computed is `i + 1` (so, `1` on the first iteration).

Interesting. I knew of them only ranging up to 256 (https://stackoverflow.com/questions/306313).

It turns out (https://github.com/python/cpython/commit/7ce25edb8f41e527ed4...) that the change is barely a month old in the repository; so it's not in 3.14 (https://github.com/python/cpython/blob/3.14/Include/internal...) and won't show up until 3.15.

> Our script appears to actually be reusing most of the PyLongObject objects!

The interesting part is that it can somehow do this even though the values are increasing throughout the loop (i.e., to values not seen on previous iterations), and it also doesn't need to allocate for the value of `i` retrieved from the `range`.

> But realistically the majority of integers in a program are going to be less than 2^30 so why not introduce a fast path which skips this complicated code entirely?

This is the sort of thing where PRs to CPython are always welcome, to my understanding. It probably isn't a priority, or something that other devs have thought of, because that allocation presumably isn't a big deal compared to the time taken for the actual conversion, which in turn is normally happening because of some kind of I/O request. (Also, real programs probably do simple arithmetic on small numbers much more often than they string-format them.)

With respect to tagged pointers, there seems to be some recent movements on that front in CPython: https://github.com/python/cpython/issues/132509

I admit it may just be because I'm a PL nerd, but I thought it was general knowledge that pretty much EVERYTHING in Python is an object, and an object in Python is always heap allocated AFAIK. This goes deeper than just integers. Things most think of as declarative (like classes, modules, etc.) are also objects, etc. etc. It is both the best thing (for dynamism and fun/tinkering) and worst thing (performance optimization) about Python.

If you've never done it, I recommend using the `dir` function in a REPL, finding interesting things inside your objects, do `dir` on those, and keep the recursion going. It is a very eye opening experience as to just how deep the objects in Python go.

C gets a lot of crap, sometimes for good reason, but one thing I like about it is that the question of whether C is allocating something is easy to answer, at least for your own code.

There are reasons why the same program in Julia can be 60x faster than in Python, see e.g. slide 5 in https://www.cl.cam.ac.uk/teaching/2526/TeX+Julia/julia-slide... for an example.

  xxxx@xxxx:~
  $ python3 -VV
  Python 3.11.2 (main, Apr 28 2025, 14:11:48) [GCC 12.2.0]
  xxxx@xxxx:~
  $ pypy3 -VV
  Python 3.9.16 (7.3.11+dfsg-2+deb12u3, Dec 30 2024, 22:36:23)
  [PyPy 7.3.11 with GCC 12.2.0]
  xxxx@xxxx:~
  $ cat original_benchmark.py
  #-------------------------------------------
  import random
  import time
  
  def monte_carlo_pi(n):
      inside = 0
      for i in range(n):
          x = random.random()
          y = random.random()
          if x**2 + y**2 <= 1.0:
              inside += 1
      return 4.0 * inside / n
  
  # Benchmark
  start = time.time()
  result = monte_carlo_pi(100_000_000)
  elapsed = time.time() - start
  
  print(f"Time: {elapsed:.3f} seconds")
  print(f"Estimated pi: {result}")
  #-------------------------------------------
  xxxx@xxxx:~
  $ python3 original_benchmark.py
  Time: 16.487 seconds
  Estimated pi: 3.14177012
  xxxx@xxxx:~
  $ pypy3 original_benchmark.py
  Time: 3.357 seconds
  Estimated pi: 3.14166756
  xxxx@xxxx:~
  $ python3 -c "print(round(16.487/3.357, 1))"
  4.9

  xxxx@xxxx:~
  $ cat mod_benchmark.py
  #-------------------------------------------
  from itertools import repeat
  from math import hypot
  from random import random
  import time
  
  def monte_carlo_pi(n):
      inside = sum(hypot(random(), random()) <= 1.0 for i in repeat(None, n))
      return 4.0 * inside / n
  
  # Benchmark
  start = time.time()
  result = monte_carlo_pi(100_000_000)
  elapsed = time.time() - start
  
  print(f"Time: {elapsed:.3f} seconds")
  print(f"Estimated pi: {result}")
  #-------------------------------------------
  xxxx@xxxx:~
  $ python3 mod_benchmark.py
  Time: 12.998 seconds
  Estimated pi: 3.14149268
  xxxx@xxxx:~
  $ pypy3 mod_benchmark.py
  Time: 12.684 seconds
  Estimated pi: 3.14160844
  xxxx@xxxx:~
  $ python3 -c "print(round(16.487/12.684, 1))"
  1.3

Once upon a time, I wanted to back a stack with a linked list in Python. I had been reading a lot of compiled bytecode, and had recently learned that CPython is a stack-based language capable of unrolling and popping tuples as singular bytecode instructions. I also learned about the freelist.

I ended up with the notation

  Initialization:
    head = ()
  Push:
    head = data, head
  Safe Pop:
    if head:
       data, head = head
  Safe Top:
    head[0] if head else None

And for many stack-based algorithms, I've found this to be quite optimal in part because the length-2 tuples get recycled (also due to a lack of function calls, member accesses, etc). But I'm rather embarrassed to put it into a codebase due to others' expectations that Python should be beautiful and this seems weird.

    def cons(head, tail=()):
        return (head, tail)

    def snoc(pair):
        '''
        Decompose (kind of) pair, transforming () to None, ().
        So you can write slightly clearer code:
        pair = cons(head, tail)
        head, tail = snoc(pair)
        '''
        if pair: return pair
        else: return (None, ())

    def car(pair):
        return pair[0] if pair else None

    def cdr(pair):
        return pair[1] if pair else ()

    def cons_iter(stack):
        '''
        Iterate stack, e.g.
        for item in cons_iter(stack): ...
        '''
        while stack:
            head, stack = stack
            yield head

A bit beside the point, but this caught my eye:

> Integers are likely the most used data type of any program, that means a lot of heap allocations.

I would guess strings come first, then floats, then booleans, and then integers. Are there any data available on that?

Shouldn't having a freelist and pushing and popping blocks of memory to and from it for re-use count as a form of memory allocation?

I’ve tried optimizing some python that’s in the hot path of a build system and a few dozen operations out of over 2K nodes in the ninja graph account for 25-30% of the total build time.

I’ve found python optimization to be nearly intractable. I’ve spent a significant amount of time over the past two decades optimizing C, Java, Swift, Ruby, SQL and I’m sure more. The techniques are largely the same. In Python, however, everything seems expensive. Field lookup on an object, dynamic dispatch, string/array concatenation. After optimization, the code is no longer “pythonic” (which has come to mean slow, in my vernacular).

Are there any good resources on optimizing python performance while keeping idiomatic?

Not sure how well-known this is, but you can run Python with a different allocator by LD_PRELOADing it. We had good results using jemalloc this way.

> I will never forget Rust for...

Fuck, this made me feel old. It blows my mind that the learning path Rust then Python even exists.

When I started school in 2000, it was C, then C++, and then Java. Oh, and then compilers. It’s impossible for me not to think about allocation when doing anything, it’s just rooted in my mind.

Historically (Python 2.x) it had a bunch of caches in front of actual system malloc. And that was (is?) reasonable with glibc default malloc being the very bad dlmalloc.

(This plays hell on things like Valgrind or ASAN.)