{"id":2937,"date":"2025-04-08T07:02:36","date_gmt":"2025-04-08T07:02:36","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/04\/08\/how-to-optimize-your-python-program-for-slowness\/"},"modified":"2025-04-08T07:02:36","modified_gmt":"2025-04-08T07:02:36","slug":"how-to-optimize-your-python-program-for-slowness","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/04\/08\/how-to-optimize-your-python-program-for-slowness\/","title":{"rendered":"How to Optimize your Python Program for Slowness"},"content":{"rendered":"

How to Optimize your Python Program for Slowness
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

\n
\n

Also available: A Rust version of this article.<\/a><\/p>\n<\/blockquote>\n

Everyone<\/mdspan> talks about making Python programs faster [1<\/a>, 2<\/a>, 3<\/a>], but what if we pursue the opposite goal? Let\u2019s explore how to make them slower\u200a\u2014\u200aabsurdly slower<\/strong>. Along the way, we\u2019ll examine the nature of computation, the role of memory, and the scale of unimaginably large numbers.<\/p>\n

Our guiding challenge: write short Python programs that run for an extraordinarily long time.<\/strong><\/p>\n

To do this, we\u2019ll explore a sequence of rule sets\u200a\u2014\u200aeach one defining what kind of programs we\u2019re allowed to write, by placing constraints on halting, memory, and program state. This sequence isn\u2019t a progression, but a series of shifts in perspective. Each rule set helps reveal something different about how simple code can stretch time.<\/p>\n

Here are the rule sets we\u2019ll investigate:<\/strong><\/h4>\n
    \n
  1. \nAnything Goes<\/strong>\u200a\u2014\u200aInfinite Loop<\/li>\n
  2. \nMust Halt, Finite Memory<\/strong>\u200a\u2014\u200aNested, Fixed-Range Loops<\/li>\n
  3. \nInfinite, Zero-Initialized Memory<\/strong>\u200a\u2014\u200a5-State Turing Machine<\/li>\n
  4. \nInfinite, Zero-Initialized Memory<\/strong>\u200a\u2014\u200a6-State Turing Machine (>10\u2191\u219115 steps)<\/li>\n
  5. \nInfinite, Zero-Initialized Memory<\/strong>\u200a\u2014\u200aPlain Python (compute 10\u2191\u219115 without Turing machine emulation)<\/li>\n<\/ol>\n
    \n

    Aside: 10\u2191\u219115 is not a typo or a double exponent. It\u2019s a number so large that \u201cexponential\u201d and \u201castronomical\u201d don\u2019t describe it. We\u2019ll define it in Rule Set 4.<\/strong><\/p>\n<\/blockquote>\n

    We start with the most permissive rule set. From there, we\u2019ll change the rules step by step to see how different constraints shape what long-running programs look like\u200a\u2014\u200aand what they can teach us.<\/p>\n

    Rule Set 1: Anything Goes\u200a\u2014\u200aInfinite Loop<\/h2>\n

    We begin with the most permissive rules: the program doesn\u2019t need to halt, can use unlimited memory, and can contain arbitrary code.<\/p>\n

    If our only goal is to run forever, the solution is immediate:<\/p>\n

    while True:\n\u00a0 pass<\/code><\/pre>\n
    This program is short, uses negligible memory, and never finishes. It satisfies the challenge in the most literal way\u200a\u2014\u200aby doing nothing forever.<\/p>\n
    Of course, it\u2019s not interesting\u200a\u2014\u200ait does nothing. But it gives us a baseline: if we remove all constraints, infinite runtime is trivial. In the next rule set, we\u2019ll introduce our first constraint: the program must eventually halt.<\/strong> Let\u2019s see how far we can stretch the running time under that new requirement\u200a\u2014\u200ausing only finite memory<\/strong>.<\/p>\n
    Rule Set 2: Must Halt, Finite Memory\u200a\u2014\u200aNested, Fixed-Range Loops<\/h2>\n
    If we want a program that runs longer than the universe will survive and then halts<\/em>, it\u2019s easy. Just write two nested loops, each counting over a fixed range from 0 to 10\u00b9\u2070\u2070\u22121:<\/p>\n
    for a in range(10**100):\n  for b in range(10**100):\n      if b % 10_000_000 == 0:\n          print(f\"{a:,}, {b:,}\")<\/code><\/pre>\n
    You can see that this program halts after 10\u00b9\u2070\u2070 \u00d7 10\u00b9\u2070\u2070 steps. That\u2019s 10\u00b2\u2070\u2070. And\u200a\u2014\u200aignoring the print\u2014this program uses only a small amount of memory to hold its two integer loop variables\u2014just 144 bytes.<\/p>\n
    My desktop computer runs this program at about 14 million steps per second. But suppose it could run at Planck speed<\/a> (the smallest meaningful unit of time in physics). That would be about 10\u2075\u2070 steps per year\u200a\u2014\u200aso 10\u00b9\u2075\u2070 years to complete.<\/p>\n
    Current cosmological models estimate the heat death of the universe<\/a> in 10\u00b9\u2070\u2070 years, so our program will run about 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 times longer than the projected lifetime of the universe.<\/p>\n
    Aside: Practical concerns about running a program beyond the end of the universe are outside the scope of this article.<\/em><\/p>\n
    For an added margin, we can use more memory. Instead of 144 bytes for variables, let\u2019s use 64 gigabytes\u200a\u2014\u200aabout what you\u2019d find in a well-equipped personal computer. That\u2019s about 500 million times more memory, which gives us about one billion variables instead of 2. If each variable iterates over the full 10\u00b9\u2070\u2070 range, the total number of steps becomes roughly 10\u00b9\u2070\u2070^(10\u2079), or about 10^(100 billion) steps. At Planck speed\u200a\u2014\u200aroughly 10\u2075\u2070 steps per year\u200a\u2014\u200athat corresponds to 10^(100 billion \u2212 50) years of computation.<\/p>\n
    \n
    Can we do better? Well, if we allow an unrealistic but interesting rule change, we can do much, much better.<\/p>\n
    Rule Set 3: Infinite, Zero-Initialized Memory\u200a\u2014\u200a5-State Turing Machine<\/h2>\n
    What if we allow infinite memory\u200a\u2014\u200aso long as it starts out entirely zero?<\/p>\n
    \n
    Aside:<\/strong> Why don\u2019t we allow infinite, arbitrarily initialized memory? Because it trivializes the challenge. For example, you could mark a single byte far out in memory with a 0x01<\/code>\u2014say, at position 10\u00b9\u00b2\u2070\u2014and write a tiny program that just scans until it finds it. That program would take an absurdly long time to run\u200a\u2014\u200abut it wouldn\u2019t be interesting. The slowness is baked into the data, not the code. We\u2019re after something deeper: small programs that generate their own long runtimes from simple, uniform starting conditions.<\/p>\n<\/blockquote>\n
    My first idea was to use the memory to count upward in binary:<\/p>\n
    0\n1\n10\n11\n100\n101\n110\n111\n...<\/code><\/pre>\n
    We can do that\u200a\u2014\u200abut how do we know when to stop? If we don\u2019t stop, we\u2019re violating the \u201cmust halt\u201d rule. So, what else can we try?<\/p>\n
    Let\u2019s take inspiration from the father of Computer Science<\/a>, Alan Turing<\/strong><\/a>. We\u2019ll program a simple abstract machine\u200a\u2014\u200anow known as a Turing machine<\/strong>\u200a\u2014\u200aunder the following constraints:<\/p>\n