commit ed31b64ea0479f9fcf59a55b7e404998f238352d
parent d4706460bc780d61852e0538f569c4d081ff2c16
Author: david cochran <about.trout@gmail.com>
Date: Thu, 23 Jul 2026 20:03:54 -0700
replace sparse loop jump map with dense array.
profiling showed we spent a lot of time computing hash lookups.
we can trade some memory for a big improvement on Eval performance,
at least for all of our benchmark programs!
> 70% reduction (333% improvement) on BenchmarkLong.
> 49% reduction (196%) on BenchmarkMandelbrot.
> 33% reduction (142%) on BenchmarkFactor.
```
$ go test -bench=.
goos: darwin
goarch: arm64
pkg: github.com/abtrout/gbfy
cpu: Apple M3
BenchmarkLong-8 1 10378019125 ns/op
BenchmarkMandelbrot-8 1 11992853958 ns/op
BenchmarkFactor-8 1 1297234500 ns/op
PASS
ok github.com/abtrout/gbfy 24.032s
```
also cleaned up partial eval logic. now the interpreter can Eval
multiple valid Brainfuck expressions.
Diffstat:
| M | bf.go | | | 88 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------------- |
| M | bf_test.go | | | 111 | +++++++++++++++++++++++++++++++++++++++++++++---------------------------------- |
| M | cmd/gbfy/main.go | | | 6 | +++--- |
3 files changed, 126 insertions(+), 79 deletions(-)
diff --git a/bf.go b/bf.go
@@ -1,49 +1,46 @@
package gbfy
import (
- "errors"
"fmt"
"io"
)
type Brainfuck struct {
- cells [3e4]byte
- cmds []byte
- i, d int // instruction and data pointer
- in io.Reader // for reading with ,
- out io.Writer // for writing with .
- loops map[int]int // stores index for matching [ or ]
- parLoops []int // indices for not-yet-complete loops
+ cells [3e4]byte
+ cmds []byte
+ i, d int // instruction and data pointer
+ in io.Reader // for reading with ,
+ out io.Writer // for writing with .
+ loops []int // stores index for matching [ or ]
}
// New returns a new Brainfuck interpreter.
func New(in io.Reader, out io.Writer) *Brainfuck {
- return &Brainfuck{in: in, out: out, loops: map[int]int{}}
+ return &Brainfuck{in: in, out: out, loops: []int{}}
}
-// Eval a single Brainfuck command.
-func (bf *Brainfuck) Eval(cmd byte) error {
- switch cmd {
- case '>', '<', '+', '-', '.', ',', '[', ']':
- bf.cmds = append(bf.cmds, cmd)
- default:
- return nil
+// Eval evaluates a valid Brainfuck program.
+func (bf *Brainfuck) Eval(src string) error {
+ cmds, loops, err := parseProgram(src)
+ if err != nil {
+ return fmt.Errorf("failed to parse program: %v", err)
}
- // Handle loops before calling internal eval.
- if cmd == '[' {
- bf.parLoops = append(bf.parLoops, len(bf.cmds)-1)
- } else if cmd == ']' {
- if len(bf.parLoops) == 0 {
- return errors.New("invalid loop close")
+ // update loop pairs.
+ off := len(bf.cmds)
+ for i := 1; i < len(loops); i++ { // skip first element; see below!
+ if loops[i] > 0 {
+ loops[i] += off
}
- i, j := len(bf.cmds)-1, bf.parLoops[len(bf.parLoops)-1]
- bf.loops[i] = j
- bf.loops[j] = i
- bf.parLoops = bf.parLoops[:len(bf.parLoops)-1]
}
- if len(bf.parLoops) > 0 {
- return nil // delay eval if there are partial loops.
+ // ... and handle special case where program begins with loop.
+ if loops[0] > 0 {
+ loops[loops[0]] += off
+ loops[0] += off
}
+ // update interpreter state
+ bf.cmds = append(bf.cmds, cmds...)
+ bf.loops = append(bf.loops, loops...)
+
return bf.eval()
}
@@ -96,3 +93,38 @@ func (bf *Brainfuck) eval() error {
func (bf *Brainfuck) Dump() (int, []byte, int, []byte) {
return bf.d, bf.cells[:], bf.i, bf.cmds
}
+
+func parseProgram(src string) ([]byte, []int, error) {
+ // collect valid Brainfuck commands.
+ var cmds []byte
+ for _, b := range []byte(src) {
+ switch b {
+ case '[', ']', '<', '>', '+', '-', ',', '.':
+ cmds = append(cmds, b)
+ }
+ }
+ // scan program and remember indices of loop pairs.
+ loops := make([]int, len(cmds))
+ var opens []int
+ for i, cmd := range cmds {
+ switch cmd {
+ case '[':
+ opens = append(opens, i)
+ case ']':
+ if len(opens) == 0 {
+ return nil, nil, fmt.Errorf("mismatched [ at index %d", i)
+ }
+ // pop
+ j := opens[len(opens)-1]
+ opens = opens[:len(opens)-1]
+ // swap
+ loops[i] = j
+ loops[j] = i
+ }
+ }
+ if len(opens) > 0 {
+ return nil, nil, fmt.Errorf("mismatched ] at index %d", opens[0])
+ }
+
+ return cmds, loops, nil
+}
diff --git a/bf_test.go b/bf_test.go
@@ -12,8 +12,8 @@ import (
func TestEval(t *testing.T) {
tests := []struct {
- // Command to evaluate.
- cmd byte
+ // Program to evaluate.
+ cmds string
// Expected value of instruction and Data pointer.
i, d int
// Expected values of *specific* cells; mapping between cell
@@ -21,51 +21,47 @@ func TestEval(t *testing.T) {
// large (3e4) and sparse (0 by default) only specific cells
// are checked.
cells map[int]byte
+ // Similar as above, but for the internal loop jump lookup array.
+ // Internally this is a dense array (len(loops) == len(cmds)) with
+ // nonzero elements corresponding to the ['s or ]'s index in bf.cmds
+ loops map[int]int
// Expected output data bytes.
out []byte
}{
// Check < and > move data pointer around circular cell region.
- {'<', 1, 29999, nil, nil},
- {'>', 2, 0, nil, nil},
+ {"<", 1, 29999, nil, nil, nil},
+ {">", 2, 0, nil, nil, nil},
// Check that + and - modify cell values.
- {'+', 3, 0, map[int]byte{0: 1}, nil},
- {'-', 4, 0, map[int]byte{0: 0}, nil},
+ {"+", 3, 0, map[int]byte{0: 1}, nil, nil},
+ {"-", 4, 0, map[int]byte{0: 0}, nil, nil},
// Check that , and . read input and write output bytes.
- {',', 5, 0, map[int]byte{0: 4}, nil},
- {'>', 6, 1, map[int]byte{0: 4}, nil},
- {',', 7, 1, map[int]byte{0: 4, 1: 8}, nil},
- {',', 8, 1, map[int]byte{0: 4, 1: 15}, nil},
- {'>', 9, 2, map[int]byte{0: 4, 1: 15}, nil},
- {',', 10, 2, map[int]byte{0: 4, 1: 15, 2: 16}, nil},
- {'.', 11, 2, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16}},
- {'<', 12, 1, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16}},
- {'.', 13, 1, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15}},
- {'<', 14, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15}},
- {'.', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
- // Check that [ and ] are handled correctly by adding two adjacent cells.
- // Evaluation is delayed in the presence of partial loops, so all internal
- // state remain the same until the final ] is Eval'd.
- {'[', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
- {'-', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
- {'>', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
- {'+', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
- {'<', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
- {']', 21, 0, map[int]byte{0: 0, 1: 19, 2: 16}, []byte{16, 15, 4}},
- {'>', 22, 1, map[int]byte{0: 0, 1: 19, 2: 16}, []byte{16, 15, 4}},
- {'.', 23, 1, map[int]byte{0: 0, 1: 19, 2: 16}, []byte{16, 15, 4, 19}},
+ {",", 5, 0, map[int]byte{0: 4}, nil, nil},
+ {">", 6, 1, map[int]byte{0: 4}, nil, nil},
+ {",", 7, 1, map[int]byte{0: 4, 1: 8}, nil, nil},
+ {",", 8, 1, map[int]byte{0: 4, 1: 15}, nil, nil},
+ {">", 9, 2, map[int]byte{0: 4, 1: 15}, nil, nil},
+ {",", 10, 2, map[int]byte{0: 4, 1: 15, 2: 16}, nil, nil},
+ {".", 11, 2, map[int]byte{0: 4, 1: 15, 2: 16}, nil, []byte{16}},
+ {"<", 12, 1, map[int]byte{0: 4, 1: 15, 2: 16}, nil, []byte{16}},
+ {".", 13, 1, map[int]byte{0: 4, 1: 15, 2: 16}, nil, []byte{16, 15}},
+ {"<", 14, 0, map[int]byte{0: 4, 1: 15, 2: 16}, nil, []byte{16, 15}},
+ {".", 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, nil, []byte{16, 15, 4}},
+ {"[->+<]", 21, 0, map[int]byte{0: 0, 1: 19, 2: 16}, map[int]int{15: 20, 20: 15}, []byte{16, 15, 4}},
+ {">", 22, 1, map[int]byte{0: 0, 1: 19, 2: 16}, map[int]int{15: 20, 20: 15}, []byte{16, 15, 4}},
+ {".", 23, 1, map[int]byte{0: 0, 1: 19, 2: 16}, map[int]int{15: 20, 20: 15}, []byte{16, 15, 4, 19}},
}
var out bytes.Buffer
bf := New(bytes.NewBuffer([]byte{4, 8, 15, 16, 23, 41}), &out)
- if err := checkInterpreter(bf, 0, 0, nil); err != nil {
+ if err := checkInterpreter(bf, 0, 0, nil, nil); err != nil {
t.Fatalf("[0] Unexpected interpreter state: %v", err)
}
for i, test := range tests {
- if err := bf.Eval(test.cmd); err != nil {
- t.Fatalf("[%d] Eval(%q) failed with error: %v", i, test.cmd, err)
+ if err := bf.Eval(test.cmds); err != nil {
+ t.Fatalf("[%d] Eval(%q) failed with error: %v", i, test.cmds, err)
}
- if err := checkInterpreter(bf, test.i, test.d, test.cells); err != nil {
+ if err := checkInterpreter(bf, test.i, test.d, test.cells, test.loops); err != nil {
t.Fatalf("[%d] Unexpected interpreter state: %v", i, err)
}
if diff := cmp.Diff(test.out, out.Bytes()); diff != "" {
@@ -74,23 +70,42 @@ func TestEval(t *testing.T) {
}
}
-func checkInterpreter(bf *Brainfuck, i, d int, cells map[int]byte) error {
+func checkInterpreter(bf *Brainfuck, i, d int, cells map[int]byte, loops map[int]int) error {
if bf.i != i {
return fmt.Errorf("instruction pointer; got %d, want %d", bf.i, i)
}
if bf.d != d {
return fmt.Errorf("data pointer; got %d, want %d", bf.d, d)
}
+ // bf.cells \subseteq cells.
for idx, got := range bf.cells {
if want := cells[idx]; got != want {
return fmt.Errorf("cell value at index %d; got %d, want %d", idx, got, want)
}
}
+ // cells \subseteq bf.cells.
+ for idx, want := range cells {
+ if got := bf.cells[idx]; got != want {
+ return fmt.Errorf("cell value at index %d; got %d, want %d", idx, got, want)
+ }
+ }
+ // bf.loops \subseteq loops.
+ for idx, got := range bf.loops {
+ if want := loops[idx]; got != want {
+ return fmt.Errorf("loop value at index %d; got %d, want %d", idx, got, want)
+ }
+ }
+ // loops \subseteq bf.loops.
+ for idx, want := range loops {
+ if got := bf.loops[idx]; got != want {
+ return fmt.Errorf("loop value at index %d; got %d, want %d", idx, got, want)
+ }
+ }
return nil
}
func TestInvalidLoopHandling(t *testing.T) {
- tests := []string{"]", "[]]", "[][]]"}
+ tests := []string{"[", "]", "[]]", "[][", "[][]]"}
for _, test := range tests {
if _, err := Run([]byte(test), nil); err == nil {
t.Errorf("Parsed invalid program %q; expected error", test)
@@ -126,24 +141,24 @@ func TestCellWrapping(t *testing.T) {
bf := New(nil, nil)
// Move to the right .... 3e4 - 1 times.
for i := 0; i < len(bf.cells)-1; i++ {
- if err := bf.Eval('>'); err != nil {
+ if err := bf.Eval(">"); err != nil {
t.Fatalf("Eval(>) failed with error %v", err)
}
}
- if err := checkInterpreter(bf, 29999, 29999, nil); err != nil {
+ if err := checkInterpreter(bf, 29999, 29999, nil, nil); err != nil {
t.Fatalf("Unexpected interpreter state: %v", err)
}
// Move to the right once more -- should wrap!
- if err := bf.Eval('>'); err != nil {
+ if err := bf.Eval(">"); err != nil {
t.Fatalf("Eval(>) failed with error %v", err)
- } else if err := checkInterpreter(bf, 30000, 0, nil); err != nil {
+ } else if err := checkInterpreter(bf, 30000, 0, nil, nil); err != nil {
t.Fatalf("Unexpected interpreter state: %v", err)
}
// Move to the left -- should wrap!
- if err := bf.Eval('<'); err != nil {
+ if err := bf.Eval("<"); err != nil {
t.Fatalf("Eval(<) failed with error %v", err)
}
- if err := checkInterpreter(bf, 30001, 29999, nil); err != nil {
+ if err := checkInterpreter(bf, 30001, 29999, nil, nil); err != nil {
t.Fatalf("Unexpected interpreter state: %v", err)
}
}
@@ -151,20 +166,20 @@ func TestCellWrapping(t *testing.T) {
func Run(cmds []byte, in io.Reader) ([]byte, error) {
var out bytes.Buffer
bf := New(in, &out)
- for _, cmd := range cmds {
- if err := bf.Eval(cmd); err != nil {
- return nil, err
- }
+ if err := bf.Eval(string(cmds)); err != nil {
+ return nil, err
}
return out.Bytes(), nil
}
// Find your own source files!
-func BenchmarkLong(b *testing.B) { runBenchmark(b, "long.bf", nil) }
-func BenchmarkMandelbrot(b *testing.B) { runBenchmark(b, "mandelbrot.bf", nil) }
-func BenchmarkFactor(b *testing.B) { runBenchmark(b, "factor.bf", bytes.NewReader([]byte("418151632\n"))) }
+func BenchmarkLong(b *testing.B) { runBenchmark(b, "long.bf", nil) }
+func BenchmarkMandelbrot(b *testing.B) { runBenchmark(b, "mandelbrot.bf", nil) }
+func BenchmarkFactor(b *testing.B) {
+ runBenchmark(b, "factor.bf", bytes.NewReader([]byte("418151632\n")))
+}
-func runBenchmark(b *testing.B, path string, in io.Reader) {
+func runBenchmark(b *testing.B, path string, in io.Reader) {
b.Helper()
src, err := os.ReadFile(path)
if err != nil {
diff --git a/cmd/gbfy/main.go b/cmd/gbfy/main.go
@@ -122,14 +122,14 @@ func runPiped(bf *gbfy.Brainfuck) error {
func runCommands(bf *gbfy.Brainfuck, r *bufio.Reader) error {
for {
- cmd, err := r.ReadByte()
+ cmds, err := r.ReadString('\n')
if err == io.EOF {
break
} else if err != nil {
return fmt.Errorf("failed to ReadByte: %v", err)
}
- if err := bf.Eval(cmd); err != nil {
- return fmt.Errorf("failed to Eval %q: %v", cmd, err)
+ if err := bf.Eval(cmds); err != nil {
+ return fmt.Errorf("failed to Eval %q: %v", cmds, err)
}
}
return nil
