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 other aim? Let’s discover learn how to make them slower — absurdly slower. Alongside the way in which, we’ll look at the character of computation, the function of reminiscence, and the dimensions 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 jot down, by inserting 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 below 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 seem like — and what they will train us.

Rule Set 1: Something Goes — Infinite Loop

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

If our solely aim is to run without end, the answer is fast:

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 means — by doing nothing without end.

After all, it’s not attention-grabbing — it does nothing. However it provides 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 will stretch the operating time beneath 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 straightforward. 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 may 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 pc runs this program at about 14 million steps per second. However suppose it may 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 instances longer than the projected lifetime of the universe.

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

For an added margin, we will 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 pc. That’s about 500 million instances extra reminiscence, which provides us about one billion variables as an alternative of two. If every variable iterates over the total 10¹⁰⁰ vary, the whole variety of steps turns into roughly 10¹⁰⁰^(10⁹), or about 10^(100 billion) steps. At Planck velocity — 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 will 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 totally zero?

Apart: Why don’t we enable infinite, arbitrarily initialized reminiscence? As a result of it trivializes the problem. For instance, you may 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 circumstances.

My first thought was to make use of the reminiscence to depend upward in binary:

0
1
10
11
100
101
110
111
...

We are able to try 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 — beneath 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 might maintain one in every of n values. For instance, with 5 states, we would title the doable values A, B, C, D, and E—plus a particular halting state H, which we don’t depend 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 via step-by-step.

• Every row corresponds to the present tape worth (0 or 1).
• Every column corresponds to the present state (A via E).
• Every entry within the desk tells the machine what to do subsequent:
  • The first character is the bit to jot down (0 or 1)
  • The second is the path 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 total 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).

Beneath 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. Meaning:

• 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 maintain operating? It’s going to run for precisely 47,176,870 steps — after which halt. 

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

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

• The primary row is clean — it reveals 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 novice researchers organized via bbchallenge.org proved that that is the longest-running 5-state Turing machine that finally halts.

---

Wish to see this Turing machine in movement? You may watch the total 47-million-step execution unfold on this pixel-perfect video:

Or work together with it immediately utilizing the Busy Beaver Blaze net app.

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

---

It’s onerous to imagine that such a small machine can run 47 million steps and nonetheless halt. However it will get much more astonishing: the group at bbchallenge.org discovered a 6-state machine with a runtime so lengthy it could’t even be written with extraordinary 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 identified 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 may 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 Could 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. Quite than simulating each step, they recognized repeating constructions and patterns that may very well be confirmed — utilizing formal, machine-verified proofs — to finally result in halting.

Up so far, 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 conduct. 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 thousands and thousands 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 total 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 possibly can additionally say they “emulated” them, in that they reproduced their conduct precisely. I keep away from the phrase “simulated”: a simulated elephant isn’t an elephant, however a simulated pc is a pc.

Returning to our central problem: we wish 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 jot down a small Python program that runs for at the very least 10↑↑15 steps, utilizing any quantity of zero-initialized reminiscence.

To attain this, we’ll compute the worth of 10↑↑15 in a means that ensures this system takes at the very least that many steps. The ↑↑ operator known as tetration—recall from Rule Set 4 that ↑↑ stacks exponents: for instance, 10↑↑3 means 10^(10^10). It’s a particularly fast-growing operate. We’ll program it from the bottom up.

Quite 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 under it, utilizing solely zero-initialized reminiscence and in-place updates.

We’ll start on the basis — with the best 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 sound 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 supplied by the gmpy2 library. It behaves like Python’s built-in int when it comes to numeric vary—restricted solely by reminiscence—however in contrast to 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 prohibit 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 completed in-place, with no copies and no momentary values. Every operate in our computation chain modifies an accumulator immediately. Most capabilities additionally take an enter worth a, however increment—being essentially the most primary—doesn’t. We use descriptive names like increment_acc, add_acc, and so forth to make the operation clear and to help 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. However it’s additionally immutable, that means any replace like += 1 creates a new integer object. Even should you assume you’re modifying a big quantity in place, Python is definitely copying all of its inside reminiscence—irrespective of how large it’s.
For instance:

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

Though x and y begin out an identical, x += 1 creates a brand new object—leaving y unchanged. This conduct 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 actually 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 sound different"
  assert is_valid_accumulator(add_acc), "not a sound 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 instances. The earlier than and after ids are the identical, exhibiting that no new object was created—add_acc was actually up to date in place.

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

Though gmpy2.xmpz helps direct addition, we don’t use it. We’re working on the most primitive degree doable—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 momentary values. The one operation we use is += 1, repeated a instances.

Subsequent, we outline multiplication.

Multiplication

With addition in place, we will now outline multiplication as repeated addition. Right here’s the operate and instance utilization. In contrast to 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 sound different"
  assert is_valid_accumulator(multiply_acc), "not a sound 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 sound 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 would possibly surprise 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 ought to be a linear loop finally ends up doing quadratic whole 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 sound different"
  assert is_valid_accumulator(exponentiate_acc), "not a sound 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 ability 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 immediately as an alternative of calling the multiply operate—so the management move and step depend keep absolutely seen.

Apart: And what number of instances is += 1 referred to as? Clearly at the very least 2⁴ instances—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 1

Then we loop 4 instances, 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 instances
• 16 increments — for multiply_acc = 8, add 2 eight instances

That’s a complete of 1 + 2 + 4 + 8 + 16 = 31 increments, which is 2⁵-1. On the whole, the variety of calls to increment will likely 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 sound different"
  assert is_valid_accumulator(tetrate_acc), "not a sound 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 instances.

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

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

We are able to additionally run tetrate on 10↑↑15. It’s going to begin operating, but it surely received’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

In contrast to 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 necessary means: 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 sure. 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 will immediately see that it’s going to name += 1 greater than 10↑↑15 instances. Even higher, we will additionally see — by building — that it halts.

What the Turing machines provide as an alternative is a less complicated, 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 via writing absurdly gradual applications. Alongside the way in which, we explored the outer edges of computation, reminiscence, and efficiency, utilizing the whole lot from deeply nested loops to Turing machines to a hand-inlined tetration operate.

Right here’s what shocked me:

• Nested loops are sufficient.
  Should you simply desire 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 bounce from 5 to six states unleashes a dramatic leap in complexity and runtime. Additionally, the significance of beginning with zero-initialized reminiscence is clear on reflection — but it surely wasn’t one thing I’d thought of earlier than.
• Python’s int sort can kill efficiency
  Sure, Python integers are arbitrary precision, which is nice. However they’re additionally immutable. Meaning each time you do one thing like x += 1, Python silently allocates a brand-new integer object—copying all of the reminiscence of x, irrespective of how large it’s. It feels in-place, but it surely’s not. This conduct turns efficient-looking code right into a efficiency lure when working with giant values. To get round this, we use the gmpy2.xmpz sort—a mutable, arbitrary-precision integer that permits 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 conversant in the ↑↑ notation or the concept exponentiation may itself be iterated to kind one thing even faster-growing. It was stunning to find out how compactly it could specific numbers which can 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 a complete hierarchy generally known as hyperoperations. There’s even a metageneralization: methods just like the Ackermann operate and fast-growing hierarchies seize total households of those capabilities and extra.
• Writing Tetration with Specific 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 methods. 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 jot down about one article monthly.