Code patterns Advanced: wrapping cells of a known widthOne copy of code over many frames

One copy of code over many frames

Runs one piece of program at many places on the tape, so the program text holds it once instead of many times.

Watch it run

The form “y = 3 × x in every frame” works on 19 cells; the named ones are “scratch”, “marker”, “x”, “y” and “tmp”. Press Play, drag the step slider forwards and back, or change frames and first x with the sliders:

The figure needs JavaScript. The program below is the result for the example values.

A program that is written out for 512 places is 512 times as long. Length is a real cost here: the chat program is a file you have to load.

Moves in brainfuck are relative, so a piece written for the first place works at every place. The tape is cut into equal stretches, frames, and a loop does the piece and then steps one frame on.

One flat loop first puts a marker in every frame. The walking loop takes the marker away as it goes and stops at the first frame without one. That costs 2 steps more per frame than writing the piece out.

The code

This is the program the figure ran, written by the generators for these values and this cell size. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:

+[->>+>>>>+>>>>+>>>>+<<<<<<<<<<<<<<]>>[->[->+++>+<<]>>[-<<+>>]<<<>>>>]

Open in the playground70 characters

What it needs

Frames of equal length; the piece may use only cells of its own frame, scratch cells included.
One marker cell per frame, zero outside the call, and a zero cell where the next frame would start. One scratch cell for laying the markers.
Any cell size: this pattern does not need wrapping.

Common mistakes

A piece that reaches into the next frame for scratch space.
Forgetting that results must leave the frame by being carried: see the form A running total that travels along of walk an array of records.

What it costs

A plain step is one command. An optimised step is one step of an interpreter that folds runs of the same command and flat loops. Choose the values and watch the two bars; What costs what explains how cost is counted:

The figure needs JavaScript. The table below has the measured steps.

Cost as a formula, and measured

**Table 1.** The cost as a function of the values. Exact formulas are checked on every case they run.
Form	Plain steps	Optimised steps
y = 3 × x in every frame	grows with the values	3 + 4 per frame
The naive way: written out per frame	grows with the values	2 per frame

**Table 2.** Measured when this page was written.
Form	Values	Bits	Characters	Plain steps	Optimised steps
y = 3 × x in every frame	frames = 4; first x = 2	8	70	333	19
y = 3 × x in every frame	frames = 8; first x = 2	8	106	935	35
y = 3 × x in every frame	frames = 64; first x = 2	8	610	37,923	259
The naive way: written out per frame	frames = 4; first x = 2	8	93	263	8
The naive way: written out per frame	frames = 8; first x = 2	8	185	797	16
The naive way: written out per frame	frames = 64; first x = 2	8	1,473	36,833	128

Against the naive way

The same job written out once per frame. The steps are nearly the same; look at the length of the text.

The numbers, row by row

this pattern, characters

610the naive way, characters

1,473

This pattern against the naive way, on 8-bit cells, measured when this page was written. The bars show the last row: the length of the two program texts.

Values	Optimised steps		Plain steps		Characters
Values	pattern	naive	pattern	naive	pattern	naive
frames = 8; first x = 2	35	16	935	797	106	185
frames = 64; first x = 2	259	128	37,923	36,833	610	1,473

Measured in the project: one clamped rounding step looped over 64 cells is one copy of the text (about 6,000 characters) and a few extra steps per cell, instead of 64 copies. measured in the project

Other forms

to measure against The naive way: written out per frame

The same piece, n times in the text.

>>>[->+++>+<<]>>[-<<+>>]>>[->+++>+<<]>>[-<<+>>]>>[->+++>+<<]>>[-<<+>>]>>[->+++>+<<]>>[-<<+>>]

Open in the playground93 characters

Run this form step by step

The form “The naive way: written out per frame” works on 18 cells; the named ones are “scratch”, “marker”, “x”, “y” and “tmp”. Press Play, drag the step slider forwards and back, or change frames and first x with the sliders:

The figure needs JavaScript. The program below is the result for the example values.

Where it is used

Build toward a chatbot, lesson 7, "No addresses", does one job at 512 places with it.
In the project: eachFrame in patterns.js. One rounding step is 5,000 to 13,000 characters; the model needs it at hundreds of places per layer.
Inside the program and the map show the frames on the real tape of the chat model.

Sources

Source: This project: emit.js and patterns.js: eachFrame.

Every program on this page was run on many inputs, in plain and in optimised mode, and compared with JavaScript. The explanations are written for this page.