Volume 3 Python, from the metal up · algorithms in the wild · 1

wild·1The algorithms in your pocket

You have just finished a volume on how algorithms are analysed, and a whole course on how Python actually works underneath. Here is the other half of that education: four famous algorithms you have already used today without being introduced to them. One of them fixed a word you mistyped. One of them decided which app the phone was allowed to forget. One of them shrank the file you attached. And one of them is the reason your upload came back after the tunnel, instead of joining a stampede that kept the server down. We will start each one where you already are — in the product, in the moment you noticed something happen — and only then open the lid. Every number on this page came out of a real run on Python 3.12.7, including the ones that make the simple story wrong. Those are the interesting ones.

iolinked · in the wild · 1 — the checkpoints4 steps

$ algorithms covered in the algorithms in your pocket —

›01Edit distance — the word you meant

›02The LRU cache — what the phone forgets

›03Huffman coding — why the file got smaller

›04Exponential backoff — the polite retry

01How your phone knows you meant ‘the’

★ IN YOUR POCKET · edit-distancethe word you meant, before you finished being wrong

You are typing fast and your thumb lands a beat early: teh. Before you have even registered the mistake, the strip above the keyboard has put the in the middle slot, and you tap it without breaking stride. Now notice what did not happen. Nothing compared your word to the dictionary letter by letter from the start — if it had, t-e-h and t-h-e would have disagreed in the second position and the match would have been thrown out. Something asked a stranger, more forgiving question instead: what is the cheapest way to turn what you typed into this word? One edit? Two? The candidate with the smallest answer floats to the front of the strip.

the word your thumb actually produced→a = "teh"

one candidate out of a dictionary of thousands→b = "the" — every candidate scored the same way

“how wrong is this, exactly?”→edit_distance(a, b) — insert, delete, replace

the suggestion strip, best guess in the middle→sorted(vocab, key=lambda w: distance(typed, w))

two fingers that landed out of order→the Damerau twist — a swap counts as one edit

pin it: A search box that forgives you is not being clever about English. It is counting the cheapest way to turn what you typed into something that exists.

Start with the question the strip has to answer, because it is smaller than it looks. It does not need to understand English. It needs a number: given the letters you actually produced and a word the dictionary knows, how far apart are they? And “far apart” has to mean something a machine can count. So we fix a tiny alphabet of moves — insert a character, delete a character, replace one character with another — and define the distance as the smallest number of those moves that turns one string into the other. That is edit distance, also called Levenshtein distance after Vladimir Levenshtein, who wrote it down in 1965. kitten to sitting is 3: replace the k, replace the e, add a g.

Now the part that has to be solved rather than defined. There are infinitely many edit sequences between two words, and we want the cheapest one, so searching them all is hopeless — the number of ways to interleave insertions and deletions explodes with length. The escape is the move you met in Chapter 40: stop asking about the whole words and start asking about their prefixes. Build a table where cell (i, j) holds the true distance between the first i letters of one word and the first j letters of the other. The corner you actually want — both words in full — is the bottom right. Everything else is scaffolding you will need on the way there.

Two edges of the table are free. Turning nothing into the first j letters of a word costs exactly j insertions, so the top row counts up. Turning the first i letters into nothing costs i deletions, so the left column counts down. Every other cell is decided by exactly three neighbours and nothing else. The cell above means “I had the answer without this letter of the left word, so delete it”, and costs one. The cell to the left means “insert the next letter of the right word”, and costs one. The diagonal steps back one letter in both words at once, which is precisely what a replacement does — and if those two letters happen to be equal, the same move is free. Take the minimum of the three. That is the whole algorithm, and it costs len(a) × len(b) constant-time cells.

Which is why the strip is instant. Scoring one candidate against a five-letter typo is twenty-five additions; scoring a thousand candidates is still nothing on a phone. The same table, under other names, is doing the work when git diff lines up two versions of a file, when a package manager says did you mean, when a search box tolerates your spelling, and when Python's own difflib.get_close_matches picks the nearest key you probably meant. Step the table filling itself, and watch where the typo actually gets fixed.

Run it and the first surprise arrives immediately. distance("teh", "the") is 2, not 1 — because with only insert, delete and replace, moving the e past the h takes two moves: delete it, then insert it again on the other side. And that is not a rounding error, it is a ranking failure. Score the dictionary against teh with classic distance and the top of the list is tea(1), ten(1) — the word you actually wanted is sitting further down at 2. A strip built on this alone would suggest the wrong thing.

RUN · edit_distance, and the ranking it gets wrongthe table, the classic demo, and the honest failure

you type
$ python edit_distance.py

def edit_distance(a, b, show=False):
    prev = list(range(len(b) + 1))                     # turning "" into b[:j]
    if show:
        print("      " + "".join("%4s" % c for c in "_" + b))
        print("   _  " + "".join("%4d" % v for v in prev))
    for i, ca in enumerate(a, start=1):
        cur = [i] + [0] * len(b)                       # turning a[:i] into ""
        for j, cb in enumerate(b, start=1):
            cur[j] = min(prev[j] + 1,                  # delete ca
                         cur[j - 1] + 1,               # insert cb
                         prev[j - 1] + (ca != cb))     # keep it, or replace it
        if show:
            print("   %s  " % ca + "".join("%4d" % v for v in cur))
        prev = cur
    return prev[-1]


print("teh -> the")
print("distance =", edit_distance("teh", "the", show=True))
print()
print("kitten -> sitting")
print("distance =", edit_distance("kitten", "sitting", show=True))


def damerau(a, b):
    d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        d[i][0] = i
    for j in range(len(b) + 1):
        d[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1,
                          d[i - 1][j - 1] + (a[i - 1] != b[j - 1]))
            if i > 1 and j > 1 and a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]:
                d[i][j] = min(d[i][j], d[i - 2][j - 2] + 1)   # ONE transposition
    return d[len(a)][len(b)]


print()
for a, b in [("teh", "the"), ("adn", "and"), ("recieve", "receive")]:
    print("%-8s -> %-8s classic %d   damerau %d"
          % (a, b, edit_distance(a, b), damerau(a, b)))

typed = "teh"
vocab = ["the", "ten", "tea", "then", "them", "tell", "test", "there"]
print()
print("ranking the dictionary against", repr(typed))
for name, score in (("classic", edit_distance), ("damerau", damerau)):
    best = sorted(vocab, key=lambda w: (score(typed, w), w))[:4]
    print("  %-8s %s" % (name, ", ".join("%s(%d)" % (w, score(typed, w)) for w in best)))

you see
teh -> the
         _   t   h   e
   _     0   1   2   3
   t     1   0   1   2
   e     2   1   1   1
   h     3   2   1   2
distance = 2

kitten -> sitting
         _   s   i   t   t   i   n   g
   _     0   1   2   3   4   5   6   7
   k     1   1   2   3   4   5   6   7
   i     2   2   1   2   3   4   5   6
   t     3   3   2   1   2   3   4   5
   t     4   4   3   2   1   2   3   4
   e     5   5   4   3   2   2   3   4
   n     6   6   5   4   3   3   2   3
distance = 3

teh      -> the      classic 2   damerau 1
adn      -> and      classic 2   damerau 1
recieve  -> receive  classic 2   damerau 1

ranking the dictionary against 'teh'
  classic  tea(1), ten(1), tell(2), test(2)
  damerau  tea(1), ten(1), the(1), tell(2)

what the run is telling you

The table for teh against the reads 2 in the bottom-right corner, and the diagonal of the last cell shows why: all three moves cost the same there, a genuine three-way tie.
kitten to sitting is the textbook demo and comes out at 3, exactly as advertised. Classic Levenshtein is not broken.
It is the wrong model for fingers. Typing errors are overwhelmingly transpositions — teh, adn, recieve — and classic distance charges 2 for every one of them.
Add a fourth move (swap two adjacent characters, cost 1) and you have Damerau-Levenshtein. All three transposition typos drop to 1, and the ranking repairs itself: the climbs into the top three.
Note what the fix did not do: the is now tied at 1 with tea and ten, not clearly ahead. Real systems break that tie with word frequency, with the physical distance between keys, and with what you have typed before. Distance narrows the field; it does not finish the job on its own.

Where the simple story ends

It is fair to say that fuzzy matching ranks candidates by edit distance — that is true of search boxes, spell checkers and “did you mean” prompts generally. It is not fair to say any particular keyboard runs this exact function. What you can say from this run is narrower and more useful: a scorer that ignores transpositions will mis-rank the most common kind of typo there is, so any serious implementation either allows the swap or compensates for it somewhere else.

reach for it when

Two sequences differ and you need the cheapest set of edits between them — scoring how wrong a word is, lining up two versions of a file, or matching records that were typed by humans.

Distance told us which answer to give. The next one decides which answers are worth keeping →

02The shelf your phone keeps by the door

★ IN YOUR POCKET · lru-cachethe four apps you actually switch between

Swipe up and hold, and there they are: the things you were just doing, newest first. Scroll far enough back and the old ones are simply gone — you never closed them, they were quietly dropped. The phone has a fixed amount of fast memory and an unfixed number of things you might want, so something has to choose what to forget. And look at what it chose. Not the app you use least often. Not the oldest one. It let go of the one you have not reached for in the longest time, which is why the app you opened once this morning and abandoned is gone, while the one you keep flicking back to all day is still sitting there, warm, exactly where you left it.

the row of recent apps, newest first→OrderedDict — coldest on the left, hottest on the right

flicking back to something you left open→get(key), and then move_to_end(key)

the app that quietly disappeared→popitem(last=False) — the coldest entry, no search

how much the device is willing to keep→capacity — the only knob there is

the browser tab that reloads when you return to it→the same eviction, one layer up the stack

pin it: Recency is not a property you measure. It is an order you maintain, one touch at a time — and once you maintain it, eviction is free.

A cache is a bet. You keep a small number of expensive answers close by, and you are betting that the next question will be one you have already answered. What makes that bet pay is a real property of how programs and people behave, and it has a name: locality of reference. What you touched recently, you are unusually likely to touch again soon. Not certainly — unusually. So when the shelf is full and something must go, the cheapest good guess is to drop whatever has gone untouched the longest. That policy is least recently used, and it is the default in so many systems that LRU reads as a word rather than an initialism.

Now the engineering, because the policy is easy and the implementation is where people quietly lose. Every operation has to be fast, or the cache costs more than the thing it was protecting. There are two questions to answer on every request. Where is this entry? — and searching for it defeats the purpose, so we need a hash map, which finds it without looking. And what is the coldest thing here? — and scanning to find out defeats the purpose too, so we keep the entries strung together in a doubly-linked order, coldest at one end, hottest at the other. A hit unhooks its entry from wherever it sits and re-attaches it at the hot end: a handful of pointer writes, no matter how large the cache. An eviction takes whatever is at the cold end. Nothing ever scans.

That pairing — a dict for finding, a linked order for ranking — is exactly what Python's OrderedDict already is, which is why the honest implementation is about fifteen lines rather than a hundred. move_to_end(key) is the promotion; popitem(last=False) is the eviction. Watch the shelf re-order itself on every touch, and pay attention to what happens on the get: a read is not a passive act here. Reading something changes the order, and that is the entire policy.

In practice you often do not write the class at all. functools.lru_cache wraps any function whose answers depend only on its arguments, and turns repeated calls into dictionary lookups. Below, the function being wrapped is the edit-distance scorer from the last section, hit with twenty thousand lookups drawn from a small pool of words — which is a fair model of a real spell-check workload, where the same handful of confusions come back over and over. Same code, same answers, one added line.

RUN · the shelf, hand-builtnine operations, and the order after each one

you type
$ python lru.py

from collections import OrderedDict


class LRU:
    def __init__(self, capacity):
        self.cap = capacity
        self.box = OrderedDict()              # left = coldest, right = hottest

    def get(self, key):
        if key not in self.box:
            return None
        self.box.move_to_end(key)             # touching it makes it the newest
        return self.box[key]

    def put(self, key, value):
        if key in self.box:
            self.box.move_to_end(key)
        self.box[key] = value
        if len(self.box) > self.cap:
            evicted, _ = self.box.popitem(last=False)    # drop the coldest
            return evicted
        return None


cache = LRU(4)
for op, key in [("put", "A"), ("put", "B"), ("put", "C"), ("put", "D"),
                ("get", "A"), ("put", "E"), ("get", "B"), ("get", "C"),
                ("put", "F")]:
    if op == "put":
        gone = cache.put(key, key.lower())
        note = "evicted " + gone if gone else ""
    else:
        note = "hit" if cache.get(key) else "MISS"
    print("%s %s   %-10s coldest..hottest: %s"
          % (op, key, note, " ".join(cache.box)))

you see
put A              coldest..hottest: A
put B              coldest..hottest: A B
put C              coldest..hottest: A B C
put D              coldest..hottest: A B C D
get A   hit        coldest..hottest: B C D A
put E   evicted B  coldest..hottest: C D A E
get B   MISS       coldest..hottest: C D A E
get C   hit        coldest..hottest: D A E C
put F   evicted D  coldest..hottest: A E C F

read the order, not the values

get A is the whole idea in one line. A was the oldest arrival and about to be evicted; one read moved it to the far end and B took its place at the front of the queue for deletion.
The eviction of B is why LRU is not FIFO. A first-in-first-out cache would have dropped A here — the entry we had just proved we still wanted.
get B misses, one step after we threw B away. Every eviction is a bet, and the miss column is where you find out how the bets are going.

RUN · functools.lru_cacheone decorator, a measured speedup, and the trap that bites first

you type
$ python lru_cache_timing.py

import functools
import random
import time


def edit_distance(a, b):
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, start=1):
        cur = [i] + [0] * len(b)
        for j, cb in enumerate(b, start=1):
            cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (ca != cb))
        prev = cur
    return prev[-1]


cached = functools.lru_cache(maxsize=256)(edit_distance)      # the whole change

words = ["accommodation", "accomodation", "recieve", "receive", "definately",
         "definitely", "seperate", "separate", "occurrence", "occurence"]
random.seed(7)
stream = [(random.choice(words), random.choice(words)) for _ in range(20000)]

t0 = time.perf_counter()
for a, b in stream:
    edit_distance(a, b)
plain = time.perf_counter() - t0

t0 = time.perf_counter()
for a, b in stream:
    cached(a, b)
warm = time.perf_counter() - t0

print("%d lookups over %d distinct pairs" % (len(stream), len(set(stream))))
print("no cache : %.3f s" % plain)
print("lru_cache: %.3f s" % warm)
print("speedup  : %.0fx" % (plain / warm))
print(cached.cache_info())

print()


@functools.lru_cache(maxsize=None)
def biggest(seq):
    return max(seq)


print("biggest((3, 1, 4, 1, 5)) =", biggest((3, 1, 4, 1, 5)))
try:
    biggest([3, 1, 4, 1, 5])
except TypeError as err:
    print("biggest([3, 1, 4, 1, 5]) -> TypeError:", err)

you see
20000 lookups over 100 distinct pairs
no cache : 0.430 s
lru_cache: 0.005 s
speedup  : 94x
CacheInfo(hits=19900, misses=100, maxsize=256, currsize=100)

biggest((3, 1, 4, 1, 5)) = 5
biggest([3, 1, 4, 1, 5]) -> TypeError: unhashable type: 'list'

where this bites

19,900 hits against 100 misses is not a lucky benchmark, it is arithmetic: the workload only contains 100 distinct pairs, so once each has been computed once, nothing is ever computed again. The 94× is a measurement on one machine and one run — repeating it landed between 86× and 94× — but the hit and miss counts are exact and reproducible.
The speedup is a property of the workload, not of the decorator. Feed the same cache 20,000 distinct pairs and you get 20,000 misses, the original runtime, plus the overhead of a dictionary you never read from.
Arguments must be hashable, because they become dictionary keys. A list argument raises TypeError: unhashable type: 'list' on the very first call. The fix is to take a tuple (or a frozenset) at the boundary and convert once.
maxsize is the shelf length, and it is doing LRU eviction underneath exactly as above. maxsize=None never evicts, which is a memory leak wearing a bow tie if the key space is unbounded.
The deeper caveat: LRU is a heuristic, not a law. One pass over a large collection touches every entry once, evicts everything useful, and leaves the cache full of things nobody will ask for again. That failure has a name — cache pollution by a scan — and it is why real systems sometimes reach for policies that also count how often something was used, not only how recently.

reach for it when

The same expensive answers keep being asked for and recency predicts the next ask — and you can afford to be wrong occasionally, because a miss costs time rather than correctness.

We have kept the useful answers close. Now let us make the answers themselves smaller →

03Why the zip file is smaller than your essay

★ IN YOUR POCKET · huffmanthe letters you use most, priced least

You attach a document and watch the number shrink. Forty kilobytes of writing becomes fourteen, and nothing is lost — open it at the other end and every comma is exactly where you left it. Here is the part worth being surprised by. Your text was stored at eight bits a character, and every character got the same eight, whether it was an e or a q. But you did not use them equally. You typed hundreds of e's and possibly two q's. Charging the same for both is a postal service that charges the same for a postcard and a piano. Somebody noticed — a graduate student, in 1952 — and worked out how to hand the common letters short codes and the rare ones long ones, in a way that provably cannot be beaten.

the letters you actually typed, tallied→Counter(text) — the only input the algorithm has

pairing off the two rarest symbols first→heappop twice, then heappush the pair

‘e’ costs one bit, ‘q’ costs seven→depth in the tree is the code length

no separators between codes in the file→every symbol at a leaf — no code prefixes another

the .zip you actually send→DEFLATE — LZ77 first, then this

pin it: Huffman does not compress your words. It re-prices your alphabet — and the bill comes out smaller because you were never spending evenly in the first place.

The fixed-width assumption is the thing to attack. Eight bits per character is a wonderfully simple rule and a quietly expensive one, because it charges by the slot rather than by the demand. So let the codes be variable-length: short bit patterns for frequent symbols, long ones for rare symbols. Immediately there is a problem, and it is the one that makes this interesting. If codes have different lengths and the file has no separators, how does a reader know where one code ends? The answer is a constraint called a prefix-free code: no symbol's code may be the beginning of any other symbol's code. Get that, and the bitstream parses itself with no lookahead and no ambiguity at all.

David Huffman's insight was that you can build such a code from the bottom up, greedily, and that the greedy answer is provably optimal — no other prefix-free code assigns fewer total bits to that set of counts. The construction: put every symbol on a min-heap keyed by its count. Repeatedly take the two lightest things, fuse them into one node whose weight is their sum, and push that node back. A fused node competes on exactly the same terms as a plain symbol, which is what lets two lines of code run all the way to the root. When one thing remains, it is the root of a binary tree with every symbol at a leaf. Label every left branch 0 and every right branch 1, and a symbol's code is the path down to it. Leaves cannot be on the way to anywhere else, so prefix-freedom comes for free from the shape.

You have met both halves of this before. Chapter 39 stepped the greedy fuse itself and argued why taking the two lightest can never paint you into a corner. Chapter 58 built the heap that makes each “give me the lightest” cost log k instead of a scan. This section owns the whole pipeline end to end: count, fuse, read the codes off the tree, encode, and measure the saving in real bits. Watch the meter labelled bits as the tree assembles, because it is doing something quietly beautiful: each fuse buries a whole subtree one level deeper and so adds exactly one bit to every character underneath it — and the weight of the node you just created counts exactly how many characters that is. The running total of fused weights is the final size of the message.

RUN · count, fuse, encode, measurethe full pipeline on a real sentence, with the round trip checked

you type
$ python huffman.py

import heapq
from collections import Counter

TEXT = "banana bandana"


def leaves(node):
    return [node] if isinstance(node, str) else leaves(node[0]) + leaves(node[1])


def show(node):
    return "".join(sorted(leaves(node))).replace(" ", "_")


def huffman(text, trace=False):
    counts = Counter(text)
    heap = [[w, i, ch] for i, (ch, w) in enumerate(sorted(counts.items()))]
    heapq.heapify(heap)                       # a min-heap ordered by weight
    tag = len(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)              # the two lightest, always
        hi = heapq.heappop(heap)
        if trace:
            print("  fuse %-5s (%d) + %-5s (%d)  -> new node (%d)"
                  % (show(lo[2]), lo[0], show(hi[2]), hi[0], lo[0] + hi[0]))
        heapq.heappush(heap, [lo[0] + hi[0], tag, [lo[2], hi[2]]])
        tag += 1
    return heap[0][2], counts


def codes(node, prefix="", table=None):
    table = {} if table is None else table
    if isinstance(node, str):
        table[node] = prefix or "0"
    else:
        codes(node[0], prefix + "0", table)   # left  = 0
        codes(node[1], prefix + "1", table)   # right = 1
    return table


print("text  :", repr(TEXT), "-", len(TEXT), "characters")
print("counts:", dict(sorted(Counter(TEXT).items(), key=lambda kv: -kv[1])))
tree, counts = huffman(TEXT, trace=True)

table = codes(tree)
print()
for ch, code in sorted(table.items(), key=lambda kv: len(kv[1])):
    print("  %-4s appears %d times   code %-5s (%d bits)"
          % (repr(ch), counts[ch], code, len(code)))

bits = "".join(table[c] for c in TEXT)
print()
print("encoded :", bits)
print("huffman : %d bits" % len(bits))
print("baseline: %d bits (14 characters at 8 bits each)" % (8 * len(TEXT)))
print("saving  : %.1f%%" % (100 * (1 - len(bits) / (8 * len(TEXT)))))
print("fuse weights 2 + 4 + 8 + 14 =", 2 + 4 + 8 + 14, "= the bit count, exactly")

out, node = [], tree                          # decode by walking the tree
for bit in bits:
    node = node[0] if bit == "0" else node[1]
    if isinstance(node, str):
        out.append(node)
        node = tree
print("decoded :", repr("".join(out)), "- round trip ok:", "".join(out) == TEXT)

ESSAY = ("the quick brown fox jumps over the lazy dog. "
         "the dog barks, the fox runs, and the quick brown fox jumps again.") * 6
t2, c2 = huffman(ESSAY)
tab2 = codes(t2)
huff_bits = sum(c2[ch] * len(tab2[ch]) for ch in c2)
print()
print("a 660-character paragraph")
print("  baseline: %d bits" % (8 * len(ESSAY)))
print("  huffman : %d bits  (%.1f%% saved)"
      % (huff_bits, 100 * (1 - huff_bits / (8 * len(ESSAY)))))

import zlib
print("  zlib    : %d bits  (DEFLATE = LZ77 then Huffman)"
      % (len(zlib.compress(ESSAY.encode(), 9)) * 8))

you see
text  : 'banana bandana' - 14 characters
counts: {'a': 6, 'n': 4, 'b': 2, ' ': 1, 'd': 1}
  fuse _     (1) + d     (1)  -> new node (2)
  fuse b     (2) + _d    (2)  -> new node (4)
  fuse n     (4) + _bd   (4)  -> new node (8)
  fuse a     (6) + _bdn  (8)  -> new node (14)

  'a'  appears 6 times   code 0     (1 bits)
  'n'  appears 4 times   code 10    (2 bits)
  'b'  appears 2 times   code 110   (3 bits)
  ' '  appears 1 times   code 1110  (4 bits)
  'd'  appears 1 times   code 1111  (4 bits)

encoded : 1100100100111011001011110100
huffman : 28 bits
baseline: 112 bits (14 characters at 8 bits each)
saving  : 75.0%
fuse weights 2 + 4 + 8 + 14 = 28 = the bit count, exactly
decoded : 'banana bandana' - round trip ok: True

a 660-character paragraph
  baseline: 5280 bits
  huffman : 2952 bits  (44.1% saved)
  zlib    : 728 bits  (DEFLATE = LZ77 then Huffman)

three numbers to argue with

75% on the toy sentence is real but flattering: five symbols with very lopsided counts is the best case Huffman ever sees. On the 660-character paragraph the same code manages 44.1%, which is much closer to what English prose actually gives up.
The fuse weights 2 + 4 + 8 + 14 sum to 28, and the encoded message is 28 bits. That is not a coincidence to be memorised, it is the invariant: each fuse charges one bit to every character beneath it, and its weight counts them.
The honest asterisk. A real .zip is not Huffman — it is DEFLATE, which runs LZ77 first (replace repeated strings with back-references) and only then Huffman-codes what LZ77 emitted. Look at the last line: zlib got the paragraph down to 728 bits against Huffman's 2,952, because that paragraph repeats whole phrases six times over and LZ77 eats repetition that a per-symbol code cannot see. Huffman is the second half of the pipeline, and it is genuinely doing work there — but it is not the half that produced that number.
The tree has to travel with the data, or the decoder cannot rebuild it. On 14 characters that overhead would swamp the saving completely; on a real file it is noise. Compression ratios quoted without the table are quoted optimistically.

reach for it when

Symbols repeat unevenly and you pay per bit — and you need the original back exactly, byte for byte, not merely something that looks like it.

Three algorithms that make one machine cleverer. The last one is about what happens when a million machines are clever at the same instant →

04Why the app waits 1, 2, 4, 8 seconds

★ IN YOUR POCKET · backoff + jitterthe pause that feels like the app giving up

The train goes into a tunnel and your upload stalls. Out the other side, it does not resume instantly — there is a pause, a retry, a longer pause, and then the bar moves again. That pause irritates you, and it is close to the most considerate thing the app does all day. Everyone else in that carriage came out of the tunnel at the same moment. If every phone retried immediately, and then again every second, the server that just came back would take the entire carriage at once and go straight back down — and then be knocked down again by the retries from the retries. So each client waits, and doubles its wait, and — the part almost everyone leaves out — picks its wait at random.

the pause before the app tries again→time.sleep(window)

each pause about twice the last→window = BASE * 2 ** attempt

the pause that stops growing→min(CAP, ...) — so it never waits an hour

everyone leaving the tunnel together→the thundering herd — doubling alone will not break it

the randomness inside the pause→random.uniform(0, window) — full jitter

pin it: Backoff decides how often one client knocks. Only jitter decides whether all of them knock at the same time — and it is the sameness that keeps the door shut.

Take the naive retry first, because it is what everybody writes on the first try: if the call fails, sleep a second and call again. One client doing that is harmless. Now imagine the failure was not yours. A server restarted, a network partition healed, a deploy rolled — and every client failed at the same instant. They all sleep one second. They all wake one second later. They all call. The server, which was halfway through warming its caches and refilling its connection pool, gets the entire population at once, falls over again, and hands every client another failure to retry. That is a thundering herd, and the ugly part is that the retries are what keep the outage alive. The system has organised itself into a loop that prevents its own recovery.

The standard fix is exponential backoff: double the wait after each failure — 1, 2, 4, 8, 16 seconds — with a ceiling so it does not eventually wait an hour, and usually a cap on attempts so it eventually gives up honestly rather than pretending. Doubling is exactly right for the pressure one client applies: it drops the request rate against a struggling service by orders of magnitude within a few rounds. But look carefully at what it does not fix. Every client doubles by the same factor from the same starting instant, so the herd stays a herd — just a herd that arrives less often. Bursts of 500 requests every 32 seconds is not meaningfully better than bursts of 500 every second, if 500 at once is what breaks you.

So add the piece that actually breaks the synchronisation: instead of sleeping the whole window, sleep a random amount somewhere inside it. random.uniform(0, window) — the variant usually called full jitter. Now two clients that failed in the same microsecond wake at different times, and every subsequent round pushes them further apart. The counter-intuitive bonus, which the run below measures: because a uniform draw from 0..window averages window/2, the jittered client also waits less on average. It is gentler on the server and faster for the user. That is a rare shape for an engineering trade-off, and it is why every serious client library does this. Step the two policies side by side — same eight clients, same doubling, one line different.

RUN · the herd, measuredwhere retries land, how long recovery takes, and the loop itself

you type
$ python backoff.py

import random

BASE, CAP, CAPACITY = 2.0, 32.0, 3          # seconds, seconds, requests per second


def retry_slots(n_clients, attempts, jitter, seed, slots=16):
    """Which second does each client's k-th retry land in?"""
    rng = random.Random(seed)
    hist = [0] * slots
    for _ in range(n_clients):
        t = 0.0
        for k in range(attempts):
            window = min(CAP, BASE * 2 ** k)
            t += rng.uniform(0, window) if jitter else window
            if int(t) < slots:
                hist[int(t)] += 1
    return hist


def shed(hist):
    return sum(max(0, c - CAPACITY) for c in hist)


print("8 clients, 3 retries each, a server that serves %d a second" % CAPACITY)
for jitter in (False, True):
    h = retry_slots(8, 3, jitter, seed=11)
    print("  %-10s %s" % ("jitter" if jitter else "no jitter", h))
    print("  %-10s %d requests, busiest second %d, %d refused"
          % ("", sum(h), max(h), shed(h)))


def recover(n_clients, jitter, seed):
    """Everyone retries until served. How much work, and how long?"""
    rng = random.Random(seed)
    pending = [(0.0, 0) for _ in range(n_clients)]        # (arrival time, attempt)
    used, requests, done_at = {}, 0, 0.0
    while pending:
        pending.sort()
        t, k = pending.pop(0)
        requests += 1
        second = int(t)
        if used.get(second, 0) < CAPACITY:
            used[second] = used.get(second, 0) + 1        # served
            done_at = max(done_at, t)
        else:
            window = min(CAP, 1.0 * 2 ** k)               # refused -> back off
            pending.append((t + (rng.uniform(0, window) if jitter else window), k + 1))
    return requests, done_at


print()
print("50 clients against the same server, everyone retrying until served")
for jitter in (False, True):
    r, t = recover(50, jitter, seed=5)
    print("  %-10s %d requests total, last client served at t = %.1fs"
          % ("jitter" if jitter else "no jitter", r, t))

print()
print("the retry loop itself, on a flaky endpoint (virtual clock, seed 12)")
rng = random.Random(12)
clock, base, cap = 0.0, 0.5, 20.0
for attempt in range(6):
    ok = rng.random() < 0.25
    print("  t = %5.2fs  attempt %d -> %s" % (clock, attempt, "200 OK" if ok else "503"))
    if ok:
        break
    window = min(cap, base * 2 ** attempt)     # double, but never past the ceiling
    wait = rng.uniform(0, window)              # full jitter: anywhere in [0, window)
    clock += wait
    print("              back off: window 0..%.2fs, slept %.2fs" % (window, wait))

you see
8 clients, 3 retries each, a server that serves 3 a second
  no jitter  [0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 8, 0]
             24 requests, busiest second 8, 15 refused
  jitter     [6, 3, 4, 3, 2, 1, 0, 2, 1, 0, 1, 1, 0, 0, 0, 0]
             24 requests, busiest second 6, 4 refused

50 clients against the same server, everyone retrying until served
  no jitter  442 requests total, last client served at t = 383.0s
  jitter     236 requests total, last client served at t = 24.8s

the retry loop itself, on a flaky endpoint (virtual clock, seed 12)
  t =  0.00s  attempt 0 -> 503
              back off: window 0..0.50s, slept 0.33s
  t =  0.33s  attempt 1 -> 503
              back off: window 0..1.00s, slept 0.14s
  t =  0.47s  attempt 2 -> 200 OK

the numbers that settle the argument

The histogram is the herd made visible. Without jitter the 24 requests arrive as three towers of eight and the server sits idle for thirteen of the sixteen seconds. Refusals: 15 of 24.
With jitter, on the same eight clients and the same doubling, refusals fall to 4. Not zero — six still land in the first second, which is honest: jitter flattens the spike, it does not abolish collisions.
The recovery run is the one worth remembering. Fifty clients, a server serving three a second: lockstep retries need 442 requests and 383 seconds to clear; jittered retries clear in 236 requests and 24.8 seconds. Nearly half the work and about a fifteenth of the outage — from one call to uniform.
Why the jittered clients also finish sooner: the synchronised ones keep leaving capacity unused between their bursts. Spreading arrivals means finding the idle seconds the herd was stepping over.
These are simulations with fixed seeds, not production telemetry — the model is a server with a hard per-second limit and clients that never give up. The ordering of the results is robust to the seed; the exact figures are not.
Do not retry everything. Backoff is for failures that might pass on their own — timeouts, 429s, 503s, connection resets. Retrying a 400 or a 401 just applies the same load to a request that will never succeed. And a retry is only safe when the operation is idempotent, or when you are carrying a key that lets the server recognise the duplicate.

reach for it when

Many independent clients retry against one recovering resource — and remember that the doubling is the easy half; the randomness is the half that actually keeps the herd apart.

Look back at the four and notice what they share, because it is not the subject matter. Edit distance turned “how wrong is this word?” into a number a table could compute, by asking about prefixes instead of whole words. The LRU cache turned “what should I forget?” into a number by maintaining an order instead of measuring one. Huffman turned “how small can this get?” into a number by re-pricing the alphabet against counts it actually measured. Backoff turned “when should I try again?” into a number by admitting that the real problem was never one client's timing but the whole population's agreement. In each case the algorithm is short; the work was finding the quantity worth computing. That is the move to carry forward, and it is the one that separates people who know algorithms from people who use them: before reaching for a technique, get precise about what number would settle the question.

Four algorithms that live inside one device. Next: the ones that run between them — routing, ranking, and finding a path through a graph the size of a country →

end of in the wild · 1 · four algorithms

iolinked

designed & developed by Ajai Raj

Python, from the metal up · a product of iolinked