Code patternsDataStore and fetch by index
Store and fetch by index
Reads or writes item number i of an array, when i is a value on the tape.
Watch it run
The form “Fetch, carrying the value home” works on 21 cells; the named ones are “zero”, “index”, “out”, “count”, “item 0”, “carry”, “item 1”, “item 2”, “item 3”, “item 4” and “item 5”. Press Play, drag the step slider forwards and back, or change index i with the slider and edit the array:
The figure needs JavaScript. The program below is the result for the example values.
There are no addresses. The program cannot say "go to cell i". It can only walk, and count the walk down: the index travels along with the pointer and loses 1 at every item.
In our form each item is three cells: a counter slot, the item, and a carry slot. Walking out, the counter is moved one item on and a 1 is left behind as a trail. At the item, the value is copied into the carry slot.
Walking back, the trail says "not home yet": each step clears one trail mark and moves the carry one item to the left. A zero cell before the array ends the walk.
The wiki form uses two cells per item and lays the whole trail first. Its fetch walks the trail once for every unit of the value, so its cost grows with index × value. Ours grows with the index only.
The code
This is the program the figure ran. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
>[->>+<<]>>[-[->>>+<<<]+>>>]>[->+<<+>]<[->+<]<<<[->>>>>[-<<<+>>>]<<<<<<<<]>>>>>[-<<<+>>>]<<<<<
What it needs
- Our form: a zero cell, the index, one more cell, then the array at three cells per item. The index is used up.
- Wiki form: index, value or out, a temp, then head, two temps and the array at two cells per item.
- The index must be inside the array. Any cell size.
Common mistakes
- An index past the end: the walk goes on into whatever follows the array.
- Forgetting that the walk costs time. Item 1000 is 1000 hops away, every time. The project cuts this to a few dozen with long hops: see Build toward a chatbot, lesson 7, "No addresses".
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
| Form | Plain steps | Optimised steps |
|---|---|---|
| Fetch, carrying the value home | grows with the index, and with the value times the index | 7 + 7 per hop |
| Store | grows with the index, and with the value times the index | 6 + 7 per hop |
| Fetch, the form from the wiki | grows with index × value | grows with index × value |
| Store, the form from the wiki | grows with index × value | grows with index × value |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| Fetch, carrying the value home | the array = 7, 3, 9, 4, 6, 2; index i = 0 | 8 | 94 | 178 | 7 |
| Fetch, carrying the value home | the array = 7, 3, 9, 4, 6, 2; index i = 5 | 8 | 94 | 398 | 42 |
| Fetch, carrying the value home | the array = 7, 3, 99, 4, 6, 2; index i = 2 | 8 | 94 | 4,053 | 21 |
| Store | the array = 7, 3, 9, 4, 6, 2; index i = 2; value = 50 | 8 | 74 | 1,691 | 20 |
| Fetch, the form from the wiki | the array = 7, 3, 9, 4, 6, 2; index i = 0 | 8 | 114 | 298 | 121 |
| Fetch, the form from the wiki | the array = 7, 3, 9, 4, 6, 2; index i = 5 | 8 | 114 | 563 | 171 |
| Fetch, the form from the wiki | the array = 7, 3, 99, 4, 6, 2; index i = 2 | 8 | 114 | 6,192 | 2,321 |
| Store, the form from the wiki | the array = 7, 3, 9, 4, 6, 2; index i = 2; value = 50 | 8 | 107 | 2,265 | 596 |
Other forms
Store
Item i becomes the value. The layout of the main form (Fetch, carrying the value home, the first figure), with the value in the third cell.
>[->>+<<]>[->>>+<<<]>[-[->>>+<<<]>>[->>>+<<<]<<+>>>]>[-]>[-<+>]<<<<<[-<<<]
Run this form step by step
The form “Store” works on 21 cells; the named ones are “zero”, “index”, “value”, “count”, “item 0”, “carry”, “item 1”, “item 2”, “item 3”, “item 4” and “item 5”. Press Play, drag the step slider forwards and back, or change index i and value with the sliders and edit the array:
The figure needs JavaScript. The program below is the result for the example values.
Fetch, the form from the wiki
out gets item i; the index is kept. Two cells per item. The walk is repeated for every unit of the value.
[->>>>>+<+<<<<]>>>>[-<<<<+>>>>]<>>[[>>]+[<<]>>-]+[>>]<[<[<<]>+<<<+>>>>[>>]<-]<[<<]>[>[>>]<+<[<<]>-]>[>>]<<[-<<]<<<
Run this form step by step
The form “Fetch, the form from the wiki” works on 18 cells; the named ones are “index”, “out”, “head”, “temp”, “trail”, “item 0”, “item 1”, “item 2”, “item 3”, “item 4” and “item 5”. Press Play, drag the step slider forwards and back, or change index i with the slider and edit the array:
The figure needs JavaScript. The program below is the result for the example values.
Store, the form from the wiki
Item i becomes the value; index and value are kept.
[->>>>>+<<<+<<]>>[-<<+>>]<[->>>+<<+<]>[-<+>]>>>[[>>]+[<<]>>-]+[>>]<[-]<[<<]>[>[>>]<+<[<<]>-]>[>>]<<[-<<]<<<
Run this form step by step
The form “Store, the form from the wiki” works on 18 cells; the named ones are “index”, “value”, “head”, “temp”, “trail”, “item 0”, “item 1”, “item 2”, “item 3”, “item 4” and “item 5”. Press Play, drag the step slider forwards and back, or change index i and value with the sliders and edit the array:
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", fetches from a table of 64 records with long and short hops.
- The chat program avoids indexing where it can: a table whose index is known to be small becomes a decision tree in the program text (see table lookup as a decision tree).
Sources
- Source: Esolang wiki: Brainfuck algorithms: sections "x(y) = z" and "x = y(z)" (1-d array, 2 cells per element; Jeffry Johnston). The three-cell forms are our own..
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.