How to Optimize your Python Program for Slowness

Additionally out there: A Rust version of this article.

talks about making Python applications sooner [1, 2, 3], however what if we pursue the alternative objective? Let’s discover find out how to make them slower — absurdly slower. Alongside the way in which, we’ll study the character of computation, the function of reminiscence, and the size of unimaginably giant numbers.

Our guiding problem: write quick Python applications that run for a very very long time.

To do that, we’ll discover a sequence of rule units — each defining what sort of applications we’re allowed to put in writing, by putting constraints on halting, reminiscence, and program state. This sequence isn’t a development, however a collection of shifts in perspective. Every rule set helps reveal one thing completely different about how easy code can stretch time.

Listed here are the rule units we’ll examine:

1. Something Goes — Infinite Loop
2. Should Halt, Finite Reminiscence — Nested, Mounted-Vary Loops
3. Infinite, Zero-Initialized Reminiscence — 5-State Turing Machine
4. Infinite, Zero-Initialized Reminiscence — 6-State Turing Machine (>10↑↑15 steps)
5. Infinite, Zero-Initialized Reminiscence — Plain Python (compute 10↑↑15 with out Turing machine emulation)

Apart: 10↑↑15 will not be a typo or a double exponent. It’s a quantity so giant that “exponential” and “astronomical” don’t describe it. We’ll outline it in Rule Set 4.

We begin with essentially the most permissive rule set. From there, we’ll change the principles step-by-step to see how completely different constraints form what long-running applications appear to be — and what they’ll educate us.

Rule Set 1: Something Goes — Infinite Loop

We start with essentially the most permissive guidelines: this system doesn’t have to halt, can use limitless reminiscence, and might comprise arbitrary code.

If our solely objective is to run perpetually, the answer is quick:

whereas True:
  cross

This program is brief, makes use of negligible reminiscence, and by no means finishes. It satisfies the problem in essentially the most literal manner — by doing nothing perpetually.

After all, it’s not attention-grabbing — it does nothing. But it surely offers us a baseline: if we take away all constraints, infinite runtime is trivial. Within the subsequent rule set, we’ll introduce our first constraint: this system should finally halt. Let’s see how far we are able to stretch the operating time below that new requirement — utilizing solely finite reminiscence.

Rule Set 2: Should Halt, Finite Reminiscence — Nested, Mounted-Vary Loops

If we wish a program that runs longer than the universe will survive after which halts, it’s simple. Simply write two nested loops, every counting over a set vary from 0 to 10¹⁰⁰−1:

for a in vary(10**100):
  for b in vary(10**100):
      if b % 10_000_000 == 0:
          print(f"{a:,}, {b:,}")

You possibly can see that this program halts after 10¹⁰⁰ × 10¹⁰⁰ steps. That’s 10²⁰⁰. And — ignoring the print—this program makes use of solely a small quantity of reminiscence to carry its two integer loop variables—simply 144 bytes.

My desktop laptop runs this program at about 14 million steps per second. However suppose it might run at Planck speed (the smallest significant unit of time in physics). That might be about 10⁵⁰ steps per yr — so 10¹⁵⁰ years to finish.

Present cosmological fashions estimate the heat death of the universe in 10¹⁰⁰ years, so our program will run about 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 occasions longer than the projected lifetime of the universe.

Apart: Sensible considerations about operating a program past the tip of the universe are exterior the scope of this text.

For an added margin, we are able to use extra reminiscence. As a substitute of 144 bytes for variables, let’s use 64 gigabytes — about what you’d discover in a well-equipped private laptop. That’s about 500 million occasions extra reminiscence, which supplies us about one billion variables as a substitute of two. If every variable iterates over the complete 10¹⁰⁰ vary, the entire variety of steps turns into roughly 10¹⁰⁰^(10⁹), or about 10^(100 billion) steps. At Planck pace — roughly 10⁵⁰ steps per yr — that corresponds to 10^(100 billion − 50) years of computation.

Can we do higher? Nicely, if we enable an unrealistic however attention-grabbing rule change, we are able to do a lot, a lot better.

Rule Set 3: Infinite, Zero-Initialized Reminiscence — 5-State Turing Machine

What if we enable infinite reminiscence — as long as it begins out fully zero?

Apart: Why don’t we enable infinite, arbitrarily initialized reminiscence? As a result of it trivializes the problem. For instance, you would mark a single byte far out in reminiscence with a 0x01—say, at place 10¹²⁰—and write a tiny program that simply scans till it finds it. That program would take an absurdly very long time to run — but it surely wouldn’t be attention-grabbing. The slowness is baked into the information, not the code. We’re after one thing deeper: small applications that generate their very own lengthy runtimes from easy, uniform beginning situations.

My first concept was to make use of the reminiscence to rely upward in binary:

0
1
10
11
100
101
110
111
...

We are able to do this — however how do we all know when to cease? If we don’t cease, we’re violating the “should halt” rule. So, what else can we strive?

Let’s take inspiration from the daddy of Computer Science, Alan Turing. We’ll program a easy summary machine — now generally known as a Turing machine — below the next constraints:

• The machine has infinite reminiscence, laid out as a tape that extends endlessly in each instructions. Every cell on the tape holds a single bit: 0 or 1.
• A learn/write head strikes throughout the tape. On every step, it reads the present bit, writes a brand new bit (0 or 1), and strikes one cell left or proper.

• The machine additionally has an inside variable referred to as state, which may maintain certainly one of n values. For instance, with 5 states, we would title the potential values A, B, C, D, and E—plus a particular halting state H, which we don’t rely among the many 5. The machine at all times begins within the first state, A.

We are able to specific a full Turing machine program as a transition desk. Right here’s an instance we’ll stroll by way of step-by-step.

• Every row corresponds to the present tape worth (0 or 1).
• Every column corresponds to the present state (A by way of E).
• Every entry within the desk tells the machine what to do subsequent:
  • The first character is the bit to put in writing (0 or 1)
  • The second is the route to maneuver (L for left, R for proper)
  • The third is the subsequent state to enter (A, B, C, D, E, or H, the place H is the particular halting state).

Now that we’ve outlined the machine, let’s see the way it behaves over time.

We’ll refer to every second in time — the complete configuration of the machine and tape — as a step. This contains the present tape contents, the top place, and the machine’s inside state (like A, B, or H).

Under is Step 0. The pinnacle is pointing to a 0 on the tape, and the machine is in state A.

Taking a look at row 0, column A in this system desk, we discover the instruction 1RB. Which means:

• Write 1 to the present tape cell.
• Transfer the top Proper.
• Enter state B.

Step 0:

This places us in Step 1:

The machine is now in state B, pointing on the subsequent tape cell (once more 0).

What’s going to occur if we let this Turing machine hold operating? It’ll run for precisely 47,176,870 steps — after which halt. 

Apart: With a Google register, you’ll be able to run this your self by way of a Python notebook on Google Colab. Alternatively, you’ll be able to copy and run the pocket book domestically by yourself laptop by downloading it from GitHub.

That quantity 47,176,870 is astonishing by itself, however seeing the complete run makes it extra tangible. We are able to visualize the execution utilizing a space-time diagram, the place every row exhibits the tape at a single step, from prime (earliest) to backside (newest). Within the picture:

• The primary row is clean — it exhibits the all-zero tape earlier than the machine takes its first step.
• 1s are proven in orange.
• 0s are proven in white.
• Mild orange seems the place 0s and 1s are so shut collectively they mix.

In 2023, a web based group of newbie researchers organized by way of bbchallenge.org proved that that is the longest-running 5-state Turing machine that finally halts.

---

Need to see this Turing machine in movement? You possibly can watch the complete 47-million-step execution unfold on this pixel-perfect video:

Or work together with it instantly utilizing the Busy Beaver Blaze internet app.

The video generator and internet app are a part of busy-beaver-blaze, the open-source Python & Rust mission that accompanies this text.

---

It’s laborious to consider that such a small machine can run 47 million steps and nonetheless halt. But it surely will get much more astonishing: the staff at bbchallenge.org discovered a 6-state machine with a runtime so lengthy it may possibly’t even be written with abnormal exponents.

Rule Set 4: Infinite, Zero-Initialized Reminiscence — 6-State Turing Machine (>10↑↑15 steps)

As of this writing, the longest operating (however nonetheless halting) 6-state Turing machine recognized to humankind is:

A   B   C   D   E   F
0   1RB 1RC 1LC 0LE 1LF 0RC
1   0LD 0RF 1LA 1RH 0RB 0RE

Here’s a video exhibiting its first 10 trillion steps:

And right here you’ll be able to run it interactively via a web app.

So, if we’re affected person — comically affected person — how lengthy will this Turing machine run? Greater than 10↑↑15 the place “10 ↑↑ 15” means:

That is not the identical as 10¹⁵ (which is only a common exponent). As a substitute:

• 10¹ = 10
• 10¹⁰ = 10,000,000,000
• 10^10^10 is 10¹⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰, already unimaginably giant.
• 10↑↑4 is so giant that it vastly exceeds the variety of atoms within the observable universe.
• 10↑↑15 is so giant that writing it in exponent notation turns into annoying.

Pavel Kropitz introduced this 6-state machine on Might 30, 2022. Shawn Ligocki has a great write up explaining each his and Pavel’s discoveries. To show that these machines run so lengthy after which halt, researchers used a mixture of evaluation and automatic instruments. Reasonably than simulating each step, they recognized repeating buildings and patterns that may very well be confirmed — utilizing formal, machine-verified proofs — to finally result in halting.

Up up to now, we’ve been speaking about Turing machines — particularly, the longest-known 5- and 6-state machines that finally halt. We ran the 5-state champion to completion and watched visualizations to discover its habits. However the discovery that it’s the longest halting machine with 5 states — and the identification of the 6-state contender — got here from intensive analysis and formal proofs, not from operating them step-by-step.

That mentioned, the Turing machine interpreter I inbuilt Python can run for tens of millions of steps, and the visualizer written in Rust can deal with trillions (see GitHub). However even 10 trillion steps isn’t an atom in a drop of water within the ocean in comparison with the complete runtime of the 6-state machine. And operating it that far doesn’t get us any nearer to understanding why it runs so lengthy.

Apart: Python and Rust “interpreted” the Turing machines as much as some level — studying their transition tables and making use of the principles step-by-step. You may additionally say they “emulated” them, in that they reproduced their habits precisely. I keep away from the phrase “simulated”: a simulated elephant isn’t an elephant, however a simulated laptop is a pc.

Returning to our central problem: we need to perceive what makes a brief program run for a very long time. As a substitute of analyzing these Turing machines, let’s assemble a Python program whose 10↑↑15 runtime is clear by design.

Rule Set 5: Infinite, Zero-Initialized Reminiscence — Plain Python (compute 10↑↑15 with out Turing machine emulation)

Our problem is to put in writing a small Python program that runs for no less than 10↑↑15 steps, utilizing any quantity of zero-initialized reminiscence.

To attain this, we’ll compute the worth of 10↑↑15 in a manner that ensures this system takes no less than that many steps. The ↑↑ operator is named tetration—recall from Rule Set 4 that ↑↑ stacks exponents: for instance, 10↑↑3 means 10^(10^10). It’s an especially fast-growing operate. We are going to program it from the bottom up.

Reasonably than depend on built-in operators, we’ll outline tetration from first ideas:

• Tetration, carried out by the operate tetrate, as repeated exponentiation
• Exponentiation, by way of exponentiate, as repeated multiplication
• Multiplication, by way of multiply, as repeated addition
• Addition, by way of add, as repeated increment

Every layer builds on the one beneath it, utilizing solely zero-initialized reminiscence and in-place updates.

We’ll start on the basis — with the only operation of all: increment.

Increment

Right here’s our definition of increment and an instance of its use:

from gmpy2 import xmpz

def increment(acc_increment):
  assert is_valid_accumulator(acc_increment), "not a legitimate accumulator"
  acc_increment += 1

def is_valid_accumulator(acc):
  return isinstance(acc, xmpz) and acc >= 0  

b = xmpz(4)
print(f"++{b} = ", finish="")
increment(b)
print(b)
assert b == 5

Output:

++4 = 5

We’re utilizing xmpz, a mutable arbitrary-precision integer sort offered by the gmpy2 library. It behaves like Python’s built-in int when it comes to numeric vary—restricted solely by reminiscence—however not like int, it helps in-place updates.

To remain true to the spirit of a Turing machine and to maintain the logic minimal and observable, we limit ourselves to just some operations:

• Creating an integer with worth 0 (xmpz(0))
• In-place increment (+= 1) and decrement (-= 1)
• Evaluating with zero

All arithmetic is finished in-place, with no copies and no non permanent values. Every operate in our computation chain modifies an accumulator instantly. Most capabilities additionally take an enter worth a, however increment—being essentially the most fundamental—doesn’t. We use descriptive names like increment_acc, add_acc, and so forth to make the operation clear and to assist later capabilities the place a number of accumulators will seem collectively.

Apart: Why not use Python’s built-in int sort? It helps arbitrary precision and might develop as giant as your reminiscence permits. But it surely’s additionally immutable, that means any replace like += 1 creates a new integer object. Even if you happen to suppose you’re modifying a big quantity in place, Python is definitely copying all of its inside reminiscence—regardless of how massive it’s.
For instance:

x = 10**100
y = x
x += 1
assert x == 10**100 + 1 and y == 10**100

Despite the fact that x and y begin out similar, x += 1 creates a brand new object—leaving y unchanged. This habits is okay for small numbers, but it surely violates our guidelines about reminiscence use and in-place updates. That’s why we use gmpy2.xmpz, a mutable arbitrary-precision integer that really helps environment friendly, in-place adjustments.

Addition

With increment outlined, we subsequent outline addition as repeated incrementing.

def add(a, add_acc):
  assert is_valid_other(a), "not a legitimate different"
  assert is_valid_accumulator(add_acc), "not a legitimate accumulator"
  for _ in vary(a):
      add_acc += 1

def is_valid_other(a):
  return isinstance(a, int) and a >= 0      

a = 2
b = xmpz(4)
print(f"Earlier than: id(b) = {id(b)}")
print(f"{a} + {b} = ", finish="")
add(a, b)
print(b)
print(f"After:  id(b) = {id(b)}")  # ← examine object IDs
assert b == 6

Output:

Earlier than: id(b) = 2082778466064
2 + 4 = 6
After:  id(b) = 2082778466064

The operate provides a to add_acc by incrementing add_acc one step at a time, a occasions. The earlier than and after ids are the identical, exhibiting that no new object was created—add_acc was really up to date in place.

Apart: You may marvel why add doesn’t simply name our increment operate. We might write it that manner—however we’re intentionally inlining every stage by hand. This retains all loops seen, makes management circulation express, and helps us cause exactly about how a lot work every operate performs.

Despite the fact that gmpy2.xmpz helps direct addition, we don’t use it. We’re working on the most primitive stage potential—incrementing by 1—to maintain the logic easy, deliberately gradual, and to make the quantity of labor express.

As with increment_acc, we replace add_acc in place, with no copying or non permanent values. The one operation we use is += 1, repeated a occasions.

Subsequent, we outline multiplication.

Multiplication

With addition in place, we are able to now outline multiplication as repeated addition. Right here’s the operate and instance utilization. Not like add and increment, this one builds up a brand new xmpz worth from zero and returns it.

def multiply(a, multiply_acc):
  assert is_valid_other(a), "not a legitimate different"
  assert is_valid_accumulator(multiply_acc), "not a legitimate accumulator"

  add_acc = xmpz(0)
  for _ in count_down(multiply_acc):
      for _ in vary(a):
          add_acc += 1
  return add_acc

def count_down(acc):
  assert is_valid_accumulator(acc), "not a legitimate accumulator"
  whereas acc > 0:
      acc -= 1
      yield

a = 2
b = xmpz(4)
print(f"{a} * {b} = ", finish="")
c = multiply(a, b)
print(c)
assert c == 8
assert b == 0

Output:

2 * 4 = 8

This multiplies a by the worth of multiply_acc by including a to add_acc as soon as for each time multiply_acc will be decremented. The result’s returned after which assigned to c. The unique multiply_acc is decremented to zero and consumed within the course of.

You may marvel what this line does:

for _ in count_down(multiply_acc):

Whereas xmpz technically works with vary(), doing so converts it to an ordinary Python int, which is immutable. That triggers a full copy of its inside reminiscence—an costly operation for giant values. Worse, every decrement step would contain allocating a brand new integer and copying all earlier bits, so what needs to be a linear loop finally ends up doing quadratic complete work. Our customized count_down() avoids all that by decrementing in place, yielding management with out copying, and sustaining predictable reminiscence use.

We’ve constructed multiplication from repeated addition. Now it’s time to go a layer additional: exponentiation.

Exponentiation

We outline exponentiation as repeated multiplication. As earlier than, we carry out all work utilizing solely incrementing, decrementing, and in-place reminiscence. As with multiply, the ultimate result’s returned whereas the enter accumulator is consumed.

Right here’s the operate and instance utilization:

def exponentiate(a, exponentiate_acc):
  assert is_valid_other(a), "not a legitimate different"
  assert is_valid_accumulator(exponentiate_acc), "not a legitimate accumulator"
  assert a > 0 or exponentiate_acc != 0, "0^0 is undefined"

  multiply_acc = xmpz(0)
  multiply_acc += 1
  for _ in count_down(exponentiate_acc):
      add_acc = xmpz(0)
      for _ in count_down(multiply_acc):
          for _ in vary(a):
              add_acc += 1
      multiply_acc = add_acc
  return multiply_acc


a = 2
b = xmpz(4)
print(f"{a}^{b} = ", finish="")
c = exponentiate(a, b)
print(c)
assert c == 16
assert b == 0

Output:

2^4 = 16

This raises a to the facility of exponentiate_acc, utilizing solely incrementing, decrementing, and loop management. We initialize multiply_acc to 1 with a single increment—as a result of repeatedly multiplying from zero would get us nowhere. Then, for every time exponentiate_acc will be decremented, we multiply the present end result (multiply_acc) by a. As with the sooner layers, we inline the multiply logic instantly as a substitute of calling the multiply operate—so the management circulation and step rely keep totally seen.

Apart: And what number of occasions is += 1 referred to as? Clearly no less than 2⁴ occasions—as a result of our result’s 2⁴, and we attain it by incrementing from zero. Extra exactly, the variety of increments is:

• 1 increment — initializing multiply_acc to at least one

Then we loop 4 occasions, and in every loop, we multiply the present worth of multiply_acc by a = 2, utilizing repeated addition:

• 2 increments — for multiply_acc = 1, add 2 as soon as
• 4 increments — for multiply_acc = 2, add 2 twice
• 8 increments — for multiply_acc = 4, add 2 4 occasions
• 16 increments — for multiply_acc = 8, add 2 eight occasions

That’s a complete of 1 + 2 + 4 + 8 + 16 = 31 increments, which is 2⁵-1. Normally, the variety of calls to increment shall be exponential, however the quantity will not be the identical exponential that we’re computing.

With exponentiation outlined, we’re prepared for the highest of our tower: tetration.

Tetration

Right here’s the operate and instance utilization:

def tetrate(a, tetrate_acc):
  assert is_valid_other(a), "not a legitimate different"
  assert is_valid_accumulator(tetrate_acc), "not a legitimate accumulator"
  assert a > 0, "we do not outline 0↑↑b"

  exponentiate_acc = xmpz(0)
  exponentiate_acc += 1
  for _ in count_down(tetrate_acc):
      multiply_acc = xmpz(0)
      multiply_acc += 1
      for _ in count_down(exponentiate_acc):
          add_acc = xmpz(0)
          for _ in count_down(multiply_acc):
              for _ in vary(a):
                  add_acc += 1
          multiply_acc = add_acc
      exponentiate_acc = multiply_acc
  return exponentiate_acc


a = 2
b = xmpz(3)
print(f"{a}↑↑{b} = ", finish="")
c = tetrate(a, b)
print(c)
assert c == 16  # 2^(2^2)
assert b == 0   # Affirm tetrate_acc is consumed

Output:

2↑↑3 = 16

This computes a ↑↑ tetrate_acc, that means it exponentiates a by itself repeatedly, tetrate_acc occasions.

For every decrement of tetrate_acc, we exponentiate the present worth. We in-line the whole exponentiate and multiply logic once more, all the way in which right down to repeated increments.

As anticipated, this computes 2^(2^2) = 16. With a Google sign-in, you’ll be able to run this your self by way of a Python notebook on Google Colab. Alternatively, you’ll be able to copy the notebook from GitHub after which run it by yourself laptop.

We are able to additionally run tetrate on 10↑↑15. It’ll begin operating, but it surely gained’t cease throughout our lifetimes — and even the lifetime of the universe:

a = 10
b = xmpz(15)
print(f"{a}↑↑{b} = ", finish="")
c = tetrate(a, b)
print(c)

Let’s examine this tetrate operate to what we discovered within the earlier Rule Units.

Rule Set 1: Something Goes — Infinite Loop

Recall our first operate:

whereas True:
  cross

Not like this infinite loop, our tetrate operate finally halts — although not anytime quickly.

Rule Set 2: Should Halt, Finite Reminiscence — Nested, Mounted-Vary Loops

Recall our second operate:

for a in vary(10**100):
  for b in vary(10**100):
      if b % 10_000_000 == 0:
          print(f"{a:,}, {b:,}")

Each this operate and our tetrate operate comprise a set variety of nested loops. However tetrate differs in an essential manner: the variety of loop iterations grows with the enter worth. On this operate, in distinction, every loop runs from 0 to 10¹⁰⁰-1—a hardcoded certain. In distinction, tetrate’s loop bounds are dynamic — they develop explosively with every layer of computation.

Rule Units 3 & 4: Infinite, Zero-Initialized Reminiscence — 5- and 6-State Turing Machines

In comparison with the Turing machines, our tetrate operate has a transparent benefit: we are able to instantly see that it’ll name += 1 greater than 10↑↑15 occasions. Even higher, we are able to additionally see — by building — that it halts.

What the Turing machines provide as a substitute is an easier, extra common mannequin of computation — and maybe a extra principled definition of what counts as a “small program.”

Conclusion

So, there you’ve got it — a journey by way of writing absurdly gradual applications. Alongside the way in which, we explored the outer edges of computation, reminiscence, and efficiency, utilizing every part from deeply nested loops to Turing machines to a hand-inlined tetration operate.

Right here’s what stunned me:

• Nested loops are sufficient.
  If you happen to simply need a quick program that halts after outliving the universe, two nested loops with 144 bytes of reminiscence will do the job. I hadn’t realized it was that straightforward.
• Turing machines escalate quick.
  The leap from 5 to six states unleashes a dramatic leap in complexity and runtime. Additionally, the significance of beginning with zero-initialized reminiscence is apparent looking back — but it surely wasn’t one thing I’d thought-about earlier than.
• Python’s int sort can kill efficiency
  Sure, Python integers are arbitrary precision, which is nice. However they’re additionally immutable. Which means each time you do one thing like x += 1, Python silently allocates a brand-new integer object—copying all of the reminiscence of x, regardless of how massive it’s. It feels in-place, but it surely’s not. This habits turns efficient-looking code right into a efficiency entice when working with giant values. To get round this, we use the gmpy2.xmpz sort—a mutable, arbitrary-precision integer that enables true in-place updates.
• There’s one thing past exponentiation — and it’s referred to as tetration.
  I didn’t know this. I wasn’t accustomed to the ↑↑ notation or the concept that exponentiation might itself be iterated to kind one thing even faster-growing. It was shocking to find out how compactly it may possibly specific numbers which might be in any other case unthinkably giant.
  And since I do know you’re asking — sure, there’s one thing past tetration too. It’s referred to as pentation, then hexation, and so forth. These are half of an entire hierarchy generally known as hyperoperations. There’s even a metageneralization: programs just like the Ackermann operate and fast-growing hierarchies seize complete households of those capabilities and extra.
• Writing Tetration with Express Loops Was Eye-Opening
  I already knew that exponentiation is repeated multiplication, and so forth. I additionally knew this may very well be written recursively. What I hadn’t seen was how cleanly it may very well be written as nested loops, with out copying values and with strict in-place updates.

Thanks for becoming a member of me on this journey. I hope you now have a clearer understanding of how small Python applications can run for an astonishingly very long time — and what that reveals about computation, reminiscence, and minimal programs. We’ve seen applications that halt solely after the universe dies, and others that run even longer.

Please follow Carl on Towards Data Science and on @carlkadie.bsky.social. I write on scientific programming in Python and Rust, machine studying, and statistics. I have a tendency to put in writing about one article per 30 days.