8 ms·
How often does Python allocate?
- zahlman 1y agoA 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 https://stackoverflow.com/questions/306313). It turns out (https://github.com/python/cpython/commit/7ce25edb8f41e527ed479bf61ef36dc9841b4ac5 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/pycore_runtime_structs.h#L109 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.)
- petters 1y ago> that make use of another garbage-collecting runtime, such as Jython I think that is mostly of historical interest. For example, it still does not support Python 3 and has not been updated in a very long time
- zahlman 1y agoAh, sorry to hear it. I'd lost track. It looks like IronPython is still active, but way behind. Or rather, maybe they have no interest in implementing Python 3 features beyond 3.4.
- cogman10 1y agoGraalpy [1] is where it's at if you want python on a JVM. [1] https://www.graalvm.org/python/ https://www.graalvm.org/python/
- sushibowl 1y agoWith respect to tagged pointers, there seems to be some recent movements on that front in CPython: https://github.com/python/cpython/issues/132509 https://github.com/python/cpython/issues/132509
- notatallshaw 1y agoUnfortunately that was posted 1 month before the Faster CPython project was disbanded by Microsoft, so I imagine things have slowed.
- nu11ptr 1y agoI 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.
- zbentley 1y agoYeah, spelunking around this is a great way to learn a language! That said, “is an object” is a bit of an overloaded term in this context. Most things in Python can be semantically addressed as objects (they have fields and methods, “dir” interrogates them, and so on), but not everything is necessarily backed by the same kind of heap-allocated memory object. Some builtins and bytecode-level optimizations, similar to (but not quite the same as) the ones discussed in TFA, result in things being less object-like (that is, PyObject*-ish structs with refcounting and/or pointer chasing on field access) in some cases. And that’s an important difference, not a nitpick! It means that performance-interested folks can’t always use the same intuition for allocation/access behavior that they do when determining what fields are available on a syntactic object. (And before the inevitable “if you want performance don’t write Python/use native libraries” folks pipe up: people still regularly have to care about making plain Python code fast. You might wish it weren’t so, but it is.)
- nu11ptr 1y agoYeah, I probably should have been careful there. Good call out that not every "object" is necessarily a heap allocated entity. I learned something, thx.
- winstonewert 1y ago> but not everything is necessarily backed by the same kind of heap-allocated memory object. Do you have an example, I thought literally everything in Python did trace to a PyObject*.
- godshatter 1y agoC 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.
- mgkuhn 1y agoThere 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-slides.pdf#page=5 https://www.cl.cam.ac.uk/teaching/2526/TeX+Julia/julia-slide... for an example.
- jakobnissen 1y agoThe function on that slide is dominated by the call to rand, which uses quite different implementations in Julia and Python, so may not be the best example. Julia is compiled and for simple code like that example code will have performance on par with C, Rust etc.
- Qem 1y agoI tested how PyPy performs on that. Just changing the implementation of Python drops the runtime from ~16.5s to ~3.5s in my computer, approximately a 5x speedup: 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 I changed the code to take advantage of some basic performance tips that are commonly given for CPython (taking advantage of stardard library - itertools, math; prefer comprehensions/generator expressions to loose for loops), and was able to get CPython numbers improve by ~1.3x. But then PyPy numbers took a hit: 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
- boothby 1y agoOnce 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.
- plant-ian 1y agoI guess the only downside might be if you need to push a bunch of things at once. But maybe just a loop is faster than calling extend on a list? This is cool.
- boothby 1y agoYep, that's the main exception when I said "many stack-based algorithms". It's worth mentioning that examining the stack while debugging is annoying because of the number of parens involved.
- Asooka 1y agoIf you can afford a function call, you can just borrow LISP's names for these functions, as these are literally LISP lists, e.g.: 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 May you write much LISP in Python.
- whilenot-dev 1y agoA 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?
- nemothekid 1y agoGiven that most string implementations have both a `len` and `cap` field (or eve just `len`), means that for every string data type, there is one more integer variables being used. So integer definitely gets used more than strings, and I'd argue way more than floats in most programs.
- zahlman 1y agoIn CPython, a string's length is stored internally as a machine integer (`Py_ssize_t`); when the `len` builtin is called, the corresponding integer object is created (or more likely, retrieved from cache) on the fly.
- ragnese 1y agoInts probably get a big boost in languages where the only built-in for-loop syntax involves incrementing an index variable, like C. And, speaking of C, specifically, even the non-int types are actually ints or isomorphic to ints: enums, bools, char, pointers, arrays (which are just pointers if you squint), etc... But, otherwise, I'd agree that strings probably win, globally.
- tialaramex 1y agoActually because of provenance the C pointers are their only type which isn't just basically the machine integers again. A char is just a machine integer with implementation specified signedness (crazy), bools are just machine integers which aren't supposed to have values other than 0 or 1, and the floating point types are just integers reinterpreted as binary fractions in a strange way. Addresses are just machine integers of course, but pointers have provenance which means that it matters why you have the pointer, whereas for the machine integers their value is entirely determined by the bits making them up.
- Joker_vD 1y agoShouldn'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?
- jonhohle 1y agoI’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?
- ragnese 1y ago> Are there any good resources on optimizing python performance while keeping idiomatic? At the risk of sounding snarky and/or unhelpful, in my experience, the answer is that you don't try to optimize Python code beyond fixing your algorithm to have better big-O properties, followed by calling out to external code that isn't written in Python (e.g., NumPy, etc). But, I'm a hater. I spent several years working with Python and hated almost every minute of it for various reasons. Very few languages repulse me the way Python does: I hate the syntax, the semantics, the difficulty of distribution, and the performance (memory and CPU, and is GIL disabled by default yet?!)...
- CraigJPerry 1y ago>> optimizing python performance while keeping idiomatic? That's impossible[1]. I think it is impossible because when i identify a slow function using cProfile then use dis.dis() on it to view the instructions executed, most of the overhead - by that i mean time spent doing something other than the calculation the code describes - is spent determining what each "thing" is. It's all trails of calls trying to determine "this thing can't be __add__() to that thing but maybe that thing can be __radd()__ to this thing instead. Long way to say most of the time wasting instructions i see can be attacked by providing ctypes or some other approach like that (mypyc, maybe cython, etc etc) - but at this point you're well beyond "idiomatic". [1] I'm really curious to know the answer to your question so i'll post a confident (but hopefully wrong) answer so that someone feels compelled to correct me :-)
- deleted 1y ago[deleted]
- weinzierl 1y agoNot 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.
- melenaboija 1y ago> 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.
- zozbot234 1y agoRust is a lot simpler than C++ and arguably Python itself, so it's not a huge surprise that it turns out to be viable as a first programming language. Especially since some parts of it can be taught as pretty much a pure functional language at the outset (actually this works quite well, right up until you really need interior mutability - which is not that often), which makes for a good intuition of what keeps the borrow checker happy.
- tialaramex 1y agoI believe Rust could work as a First language for CS students, but I don't expect it will ever make sense as the sole language we teach to non-CS students who need programmability as a potential skill, the same way they may need stats, or some of mathematics, or various other skills (I did Contract Law for example). The prominence of Python for those students makes sense to me, thirty years ago I'm sure a BASIC would have been fine too. It doesn't need to be elegant, or have good performance, it does matter that it's free, and that there's a lot of existing crap written in Python you can crib from.
- zozbot234 1y agoPython makes even less sense as a language for CS-naïve students. It has bonkers semantics, and the "intuitive" syntax only really helps when writing tiny, trivial programs.
- loeg 1y agoHistorically (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.)