micro_test.gno
5.78 Kb · 261 lines
1package bf
2
3import (
4 "testing"
5
6 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/vm/vmkit/v0"
7)
8
9// The microarchitecture matrix.
10//
11// The rungs in ladder_test.gno are the classic interpreter optimizations:
12// fewer instructions for the same program. These are the other axis, and on
13// the GnoVM they matter as much: the same instruction stream, executed by
14// loops that differ from each other by exactly one line.
15//
16// They are deliberately simplified (no host, no snapshot, no scan) so that
17// the one line is the only difference. They are comparable to each other and
18// not to the shipped machine, which does more. What the shipped machine took
19// from them is documented on [Machine.Step].
20
21type vm struct {
22 prog *Program
23 tape [TapeSize]byte
24 ptr int
25 pc int
26}
27
28// V0: cursors as struct fields. No meter, no bounds check, no defer.
29func (m *vm) runFields() int64 {
30 ops := m.prog.ops
31 var used int64
32 for {
33 used++
34 switch ops[m.pc].code {
35 case opAdd:
36 m.tape[m.ptr] += byte(ops[m.pc].arg)
37 case opMove:
38 m.ptr = wrap(m.ptr + ops[m.pc].arg)
39 case opSet:
40 m.tape[m.ptr] = byte(ops[m.pc].arg)
41 case opAddMul:
42 if v := m.tape[m.ptr]; v != 0 {
43 m.tape[wrap(m.ptr+ops[m.pc].off)] += v * byte(ops[m.pc].arg)
44 }
45 case opJmpZ:
46 if m.tape[m.ptr] == 0 {
47 m.pc = ops[m.pc].arg
48 }
49 case opJmpNZ:
50 if m.tape[m.ptr] != 0 {
51 m.pc = ops[m.pc].arg
52 }
53 case opHalt:
54 return used
55 }
56 m.pc++
57 }
58}
59
60// V1: V0 with the two cursors hoisted into locals. Only change.
61func (m *vm) runLocals() int64 {
62 ops := m.prog.ops
63 pc, ptr := m.pc, m.ptr
64 var used int64
65 for {
66 used++
67 switch ops[pc].code {
68 case opAdd:
69 m.tape[ptr] += byte(ops[pc].arg)
70 case opMove:
71 ptr = wrap(ptr + ops[pc].arg)
72 case opSet:
73 m.tape[ptr] = byte(ops[pc].arg)
74 case opAddMul:
75 if v := m.tape[ptr]; v != 0 {
76 m.tape[wrap(ptr+ops[pc].off)] += v * byte(ops[pc].arg)
77 }
78 case opJmpZ:
79 if m.tape[ptr] == 0 {
80 pc = ops[pc].arg
81 }
82 case opJmpNZ:
83 if m.tape[ptr] != 0 {
84 pc = ops[pc].arg
85 }
86 case opHalt:
87 m.pc, m.ptr = pc, ptr
88 return used
89 }
90 pc++
91 }
92}
93
94// V2: V1 plus a vmkit.Meter charged once per op. Only change.
95func (m *vm) runLocalsMeter(fuel int64) int64 {
96 ops := m.prog.ops
97 meter := vmkit.NewMeter(fuel)
98 pc, ptr := m.pc, m.ptr
99 for {
100 if !meter.Charge(1) {
101 m.pc, m.ptr = pc, ptr
102 return meter.Used()
103 }
104 switch ops[pc].code {
105 case opAdd:
106 m.tape[ptr] += byte(ops[pc].arg)
107 case opMove:
108 ptr = wrap(ptr + ops[pc].arg)
109 case opSet:
110 m.tape[ptr] = byte(ops[pc].arg)
111 case opAddMul:
112 if v := m.tape[ptr]; v != 0 {
113 m.tape[wrap(ptr+ops[pc].off)] += v * byte(ops[pc].arg)
114 }
115 case opJmpZ:
116 if m.tape[ptr] == 0 {
117 pc = ops[pc].arg
118 }
119 case opJmpNZ:
120 if m.tape[ptr] != 0 {
121 pc = ops[pc].arg
122 }
123 case opHalt:
124 m.pc, m.ptr = pc, ptr
125 return meter.Used()
126 }
127 pc++
128 }
129}
130
131// V3: V1 plus an inline fuel counter instead of the Meter object. Isolates
132// the cost of the method call from the cost of metering at all.
133func (m *vm) runLocalsInlineFuel(fuel int64) int64 {
134 ops := m.prog.ops
135 pc, ptr := m.pc, m.ptr
136 var used int64
137 for {
138 if used >= fuel {
139 m.pc, m.ptr = pc, ptr
140 return used
141 }
142 used++
143 switch ops[pc].code {
144 case opAdd:
145 m.tape[ptr] += byte(ops[pc].arg)
146 case opMove:
147 ptr = wrap(ptr + ops[pc].arg)
148 case opSet:
149 m.tape[ptr] = byte(ops[pc].arg)
150 case opAddMul:
151 if v := m.tape[ptr]; v != 0 {
152 m.tape[wrap(ptr+ops[pc].off)] += v * byte(ops[pc].arg)
153 }
154 case opJmpZ:
155 if m.tape[ptr] == 0 {
156 pc = ops[pc].arg
157 }
158 case opJmpNZ:
159 if m.tape[ptr] != 0 {
160 pc = ops[pc].arg
161 }
162 case opHalt:
163 m.pc, m.ptr = pc, ptr
164 return used
165 }
166 pc++
167 }
168}
169
170
171// V4: V3 with the tape as a local slice instead of an array field. Only
172// change, so this settles the "a fixed array removes a bounds check" claim.
173func (m *vm) runLocalsInlineFuelSliceTape(fuel int64) int64 {
174 ops := m.prog.ops
175 tape := make([]byte, TapeSize)
176 pc, ptr := m.pc, m.ptr
177 var used int64
178 for {
179 if used >= fuel {
180 m.pc, m.ptr = pc, ptr
181 return used
182 }
183 used++
184 switch ops[pc].code {
185 case opAdd:
186 tape[ptr] += byte(ops[pc].arg)
187 case opMove:
188 ptr = wrap(ptr + ops[pc].arg)
189 case opSet:
190 tape[ptr] = byte(ops[pc].arg)
191 case opAddMul:
192 if v := tape[ptr]; v != 0 {
193 tape[wrap(ptr+ops[pc].off)] += v * byte(ops[pc].arg)
194 }
195 case opJmpZ:
196 if tape[ptr] == 0 {
197 pc = ops[pc].arg
198 }
199 case opJmpNZ:
200 if tape[ptr] != 0 {
201 pc = ops[pc].arg
202 }
203 case opHalt:
204 m.pc, m.ptr = pc, ptr
205 return used
206 }
207 pc++
208 }
209}
210
211func microProg(lvl Level) *Program {
212 p, err := Compile(heavy, lvl)
213 if err != nil {
214 panic(err)
215 }
216 return p
217}
218
219// Rung 1's instruction stream, 121,202 ops, under each loop.
220
221func TestMicroJumpsCursorsAsFields(t *testing.T) {
222 (&vm{prog: microProg(LevelJumps)}).runFields()
223}
224
225func TestMicroJumpsCursorsInLocals(t *testing.T) {
226 (&vm{prog: microProg(LevelJumps)}).runLocals()
227}
228
229func TestMicroJumpsMeterPerOp(t *testing.T) {
230 (&vm{prog: microProg(LevelJumps)}).runLocalsMeter(vmkit.Unmetered)
231}
232
233func TestMicroJumpsInlineFuel(t *testing.T) {
234 (&vm{prog: microProg(LevelJumps)}).runLocalsInlineFuel(1 << 40)
235}
236
237// Rung 3's instruction stream, 1,203 ops, under the same loops.
238
239func TestMicroJumpsSliceTape(t *testing.T) {
240 (&vm{prog: microProg(LevelJumps)}).runLocalsInlineFuelSliceTape(1 << 40)
241}
242
243func TestMicroIdiomsCursorsAsFields(t *testing.T) {
244 (&vm{prog: microProg(LevelIdioms)}).runFields()
245}
246
247func TestMicroIdiomsCursorsInLocals(t *testing.T) {
248 (&vm{prog: microProg(LevelIdioms)}).runLocals()
249}
250
251func TestMicroIdiomsMeterPerOp(t *testing.T) {
252 (&vm{prog: microProg(LevelIdioms)}).runLocalsMeter(vmkit.Unmetered)
253}
254
255func TestMicroIdiomsInlineFuel(t *testing.T) {
256 (&vm{prog: microProg(LevelIdioms)}).runLocalsInlineFuel(1 << 40)
257}
258
259func TestMicroIdiomsSliceTape(t *testing.T) {
260 (&vm{prog: microProg(LevelIdioms)}).runLocalsInlineFuelSliceTape(1 << 40)
261}
