Across the grain

Here is the original — preserved in the tree as _int2bytes at the version-3.4 tag. It walks the number one byte at a time, prepending each to a list:

# _int2bytes — against the grain (rsa/transform.py @ version-3.4)
raw_bytes = []
while number > 0:
    raw_bytes.insert(0, byte(number & 0xFF))   # one byte; insert at the FRONT
    number >>= 8
return padding + b('').join(raw_bytes)

Everything here cuts across the grain. A 4096-bit key takes 512 turns of the loop. Each list.insert(0, …) shifts the entire list to make room, so the whole thing is quietly $O(n^2)$. Each turn boxes a fresh one-byte object. And the size arithmetic that fed it leaned on floating-point division — a continuous approximation doing an exact, discrete job. None of it is wrong; it's just sawing perpendicular to the way the wood wants to part.

Count the shifting yourself — it is the arithmetic the notation compresses:

With it

A machine word is the unit a processor — and struct.pack — handle in one go: not a single byte, but four or eight at once, depending on the platform's widest lane.

So the rewrite takes the number a word at a time — asking the platform for its widest packing lane — and hands the cut to C. The shipped code, from the same rsa/transform.py:

# int2bytes — along the grain (rsa/transform.py @ version-3.4)
num = number
word_bits, _, max_uint, pack_type = get_word_alignment(num)
pack_format = ">%s" % pack_type          # '>Q', '>I', '>H', or '>B'
while num > 0:
    raw_bytes = pack(pack_format, num & max_uint) + raw_bytes
    num >>= word_bits

A word per turn instead of a byte means a quarter (on 64-bit lanes, an eighth) of the passes, and struct.pack does the packing in C rather than in a Python loop boxing bytes by hand. One honest concession before admiring it: the rewrite keeps a quadratic of its own — each pack(…) + raw_bytes re-copies the accumulated byte string, so both functions are $O(n^2)$ in principle. The win is the constant factor: an eighth as many interpreter turns, each doing its byte work in C. At key sizes the constant factor is the whole game; the complexity-class fix comes later in this story. And none of this is the hardware moving memory differently — the win lives entirely in the layer above: a quarter as many trips through the Python interpreter, with the byte-work itself handed to C. I also re-implemented the byte_size and bit_size helpers with divmod, taking floating-point out of the hot path entirely — discrete math for a discrete problem. Same output, far less resistance: the new function and the old one still produce byte-for-byte identical results, which the benchmark checks before it times anything.

What it measures today

Both functions live side by side at the version-3.4 tag — int2bytes and its byte-at-a-time predecessor _int2bytes, kept precisely so the two could be raced — and that tag ships the harness, speed.sh. (On today's main you'll find neither: the story has a better ending, below.) I checked out the tag and ran the race on an Apple-silicon laptop and an x86-64 box:

Still worth its keep — $\sim 15\times$ at a standard 2048-bit key, $\sim 20\times$ for larger numbers, on both architectures. But not the $\sim 40\times$ I remember.

The grain holds; the margin doesn't

The honest caveat first: I haven't re-run the 2011 measurement. It was on Python 2.5–2.7 on hardware long gone — CPython 2.7 still compiles if you're determined, but the original machine and interpreter build don't exist to race. So I can't prove it was $40\times$. But the direction has a mechanism, and the mechanism is the whole point of this note.

A substrate has a grain too, and unlike a plank's, it changes. Look at where each function spends its time. The rewrite is dominated by struct.pack — a C routine whose cost barely moves between interpreter versions. The original is dominated by the interpreter itself: a long Python loop, a method call and an allocation every turn, an $O(n^2)$ insert. That is exactly the code modern CPython got dramatically better at running — the 3.11 "Faster CPython" work, the specializing interpreter, cheaper integers and bytes. So over fifteen years the two improved unequally: the C-bound rewrite stood still while the interpreter-bound original sped up. The ratio between them is the speedup, and it narrowed — not because my code got slower, but because the thing it was beating got faster. The interpreter's own grain had sharpened. (The comparison is confounded, and honesty says so: Python 2 → 3 rebuilt int and bytes wholesale, and my two 2026 machines run different interpreter versions. The mechanism, though, is not speculative: interpreter work speeds up interpreter-bound code and leaves C-bound code alone.)

And yet $\sim 15\times$ survived. That is the part worth keeping. A win that comes from working with the grain — fewer passes, word-aligned, the cut handed to C, no floating point in an integer routine — is structural. It doesn't depend on any one interpreter being slow; it depends on the shape of the machine, which doesn't change. Had the original speedup come from incidental cleverness — micro-tuning the Python loop, exploiting some quirk of CPython 2.6 — it would have evaporated the moment the quirk did. Instead it compressed and held. The margin is the runtime's to give and take; the alignment is mine to keep.

The grain won so hard it became a builtin

The story has a better ending than "my function survived." It didn't survive — it was retired, by the strongest possible vindication. Python 3.2 (2011, the same year as the rewrite) added int.to_bytes: one C call that converts directly from CPython's internal big-integer digits to bytes, no interpreter loop at all, and $O(n)$ — the complexity-class fix the word-packing loop never made. Upstream python-rsa eventually deleted both racers; int2bytes on today's main is a thin wrapper around number.to_bytes(…). The grain-following idea — do the byte-work word-wise, in C, below the interpreter — won so completely that it moved into the language, one layer deeper than I could reach in 2011. That's the trajectory of a with-the-grain optimization: it doesn't rot; it gets absorbed.

That is the rule I've trusted ever since, in code and out of it: work with the grain, and you fight less, splinter less, waste less.