What costs what

One question

The program below empties a cell that holds 5. Press Play and count how often it asks “is this cell zero?”. Then open More controls, choose “flat loops as one step”, and count again:

Brainfuck has one way to look at a cell: a bracket asks “is this cell zero?”. It cannot ask “is it 5?” or “is it more than that one?”. So a program finds out how large a number is by counting it down to zero, and that takes time for every unit. Emptying a cell that holds 200 is 401 commands.

An interpreter that is allowed to look at the whole program first can skip some of that counting. Which loops can it skip?

What an optimising interpreter folds

Type a piece of brainfuck below and see what an optimising interpreter makes of it. The list has one line for each step it takes. Try [->+<], then [->+<.], then [>], then [+]:

A fast interpreter reads the program first and replaces three things by one step each:

• A run of the same command. +++++ is “add 5”.
• A move followed by something. >>>+ is “add 1 three cells to the right”.
• A flat loop: a loop that only adds and moves, comes back to where it started, and takes exactly 1 off its own cell each round. [->+++<] is “add 3 times this cell to the next one, and empty this cell”. One multiplication.

That is all. A flat loop costs one step whether its cell holds 2 or 2 billion. Every other loop still goes round, once per unit.

Look at [+] in the list. It empties a wrapping cell just as [-] does, but this interpreter does not fold it: its rule asks for “takes 1 off”. Other interpreters know other tricks. A pattern that needs a certain trick to be fast says so on its page.

Which of the patterns are flat, and which are not?

Cheap and expensive, measured

Eight patterns run below on 8-bit cells, for the x and y you choose. The ink bar counts plain steps and the hatched bar counts optimised steps; each row has its own scale. Move the sliders and watch which hatched bars stay still and which grow:

The first four rows are flat loops. Their optimised cost does not move. The last four hold a loop inside a loop, or a decision inside a loop. No interpreter can fold those without understanding what the program means, so their cost grows with the numbers.

What cannot be folded

• A loop with a loop inside. Multiplying two cells is “add y, x times”. The inner loop is one step; the outer one goes round x times.
• A loop with a decision inside. Less than, saturating subtract and divide, with remainder look at a cell every round.
• A loop that does not come back. A scan (find a zero cell or a marker) such as [>] ends on another cell than it started on. It costs one step per cell it passes.
• A loop that reads or prints. The outside world wants every letter one at a time.

All of these count in units: one round for every 1 in the number. That is fine for a letter code. It is hopeless for the sums of a chat model, which run into millions.

Is there a way to count something smaller than units?

The way out: count bits, not units

Below, X is divided by 128 and rounded in two ways on 32-bit cells: by counting down in units, and by the pattern shift, round and clamp. Both are run in your browser. Drag X and compare the two bars, then make X ten times larger:

A number below a million has a million units but only 20 bits. A program that can read a number bit by bit needs 20 rounds instead of a million.

On cells that wrap at a known width it can. Multiplying by 2 is a flat loop, and it pushes the top bit out of the cell. That turns “is this bit set?” into “is this cell zero?”: the bit peel.

This one idea carries the chat models of this site. Their division, their multiplication of two numbers from the tape and their table lookups are all “peel some bits, and do something for each set bit”: see the group Advanced: wrapping cells of a known width on the front page of the patterns, and How it works.

It has a price. The program text is made for one cell width and is wrong on any other. And it is only fast on an interpreter that folds flat loops: counted in plain steps the shifts are long loops.

Length is a cost too

A brainfuck program is a text. Every constant in it is written out, and a long text takes long to load and to read in. Several patterns exist only to make the text shorter. The table gives the length of the same result written two ways, for four jobs:

The four rows are these patterns: set a constant, print a constant string, write many numbers compactly as digits and one copy of code over many frames.

Rules of thumb

• Moving, copying, adding, subtracting and multiplying by a constant are flat. Use them freely.
• Anything that must look at a value on the way (compare, divide, stop at zero) costs a round per unit. Keep those numbers small, or put the smaller number in the loop.
• A walk costs a step per cell. Keep things that work together next to each other.
• When the numbers get large and the cells wrap at a known width, switch from units to bits.
• Say what you count. “Fast” on an optimising interpreter and “fast” in plain steps are different claims.