switchcost_test.gno

  1package riscv
  2
  3import "testing"
  4
  5// Does the GnoVM dispatch a switch by jump table or by scanning the cases in
  6// order? The answer decides the interpreter's shape: predecoding an image into
  7// (op, rd, rs1, rs2, imm) arrays deletes the fetch and the field extraction,
  8// but it also flattens two small nested switches into one 48-case switch. If
  9// cases are scanned, that trade buys nothing and costs the deeper arms.
 10//
 11// The experiment: the same 48-case switch, driven to the first case and to the
 12// last. Equal cycles means a jump table. A large gap means a scan, and the
 13// switch has to stay shallow no matter what else changes.
 14
 15//go:noinline
 16func switch48(v uint32) uint32 {
 17	switch v {
 18	case 0:
 19		return 1
 20	case 1:
 21		return 2
 22	case 2:
 23		return 3
 24	case 3:
 25		return 4
 26	case 4:
 27		return 5
 28	case 5:
 29		return 6
 30	case 6:
 31		return 7
 32	case 7:
 33		return 8
 34	case 8:
 35		return 9
 36	case 9:
 37		return 10
 38	case 10:
 39		return 11
 40	case 11:
 41		return 12
 42	case 12:
 43		return 13
 44	case 13:
 45		return 14
 46	case 14:
 47		return 15
 48	case 15:
 49		return 16
 50	case 16:
 51		return 17
 52	case 17:
 53		return 18
 54	case 18:
 55		return 19
 56	case 19:
 57		return 20
 58	case 20:
 59		return 21
 60	case 21:
 61		return 22
 62	case 22:
 63		return 23
 64	case 23:
 65		return 24
 66	case 24:
 67		return 25
 68	case 25:
 69		return 26
 70	case 26:
 71		return 27
 72	case 27:
 73		return 28
 74	case 28:
 75		return 29
 76	case 29:
 77		return 30
 78	case 30:
 79		return 31
 80	case 31:
 81		return 32
 82	case 32:
 83		return 33
 84	case 33:
 85		return 34
 86	case 34:
 87		return 35
 88	case 35:
 89		return 36
 90	case 36:
 91		return 37
 92	case 37:
 93		return 38
 94	case 38:
 95		return 39
 96	case 39:
 97		return 40
 98	case 40:
 99		return 41
100	case 41:
101		return 42
102	case 42:
103		return 43
104	case 43:
105		return 44
106	case 44:
107		return 45
108	case 45:
109		return 46
110	case 46:
111		return 47
112	case 47:
113		return 48
114	}
115	return 0
116}
117
118const switchIters = 200000
119
120func TestSwitchCostFirstCase(t *testing.T) {
121	var acc uint32
122	for i := 0; i < switchIters; i++ {
123		acc += switch48(0)
124	}
125	if acc == 0 {
126		t.Fatal("unreachable")
127	}
128}
129
130func TestSwitchCostLastCase(t *testing.T) {
131	var acc uint32
132	for i := 0; i < switchIters; i++ {
133		acc += switch48(47)
134	}
135	if acc == 0 {
136		t.Fatal("unreachable")
137	}
138}
139
140// The control: the same loop with no switch at all, so the two above can be
141// read net of loop and call overhead.
142//
143//go:noinline
144func switchNone(v uint32) uint32 { return v + 1 }
145
146func TestSwitchCostNoSwitch(t *testing.T) {
147	var acc uint32
148	for i := 0; i < switchIters; i++ {
149		acc += switchNone(0)
150	}
151	if acc == 0 {
152		t.Fatal("unreachable")
153	}
154}
155
156// A scan means the question is no longer "how few cases" but "is there a
157// dispatch that does not scan at all". These three isolate the alternatives:
158// the bare loop, a direct call, and a call through a table indexed by opcode.
159
160//go:noinline
161func hADDI(v uint32) uint32 { return v + 1 }
162
163//go:noinline
164func hSUB(v uint32) uint32 { return v - 1 }
165
166//go:noinline
167func hXOR(v uint32) uint32 { return v ^ 1 }
168
169//go:noinline
170func hAND(v uint32) uint32 { return v & 1 }
171
172var dispatchTable = [4]func(uint32) uint32{hADDI, hSUB, hXOR, hAND}
173
174func TestDispatchLoopOnly(t *testing.T) {
175	var acc uint32
176	for i := 0; i < switchIters; i++ {
177		acc += uint32(i) & 1
178	}
179	if acc == 0 {
180		t.Fatal("unreachable")
181	}
182}
183
184func TestDispatchTableCall(t *testing.T) {
185	var acc uint32
186	for i := 0; i < switchIters; i++ {
187		acc += dispatchTable[3](1)
188	}
189	if acc == 0 {
190		t.Fatal("unreachable")
191	}
192}
193
194// What does memory cost? Predecode allocates five arrays per load and the
195// address space allocates a megabyte, so the answer decides whether the
196// predecode arrays should be built eagerly or only for words actually reached.
197
198func TestAllocBytes1000(t *testing.T) {
199	b := make([]byte, 4000)
200	if len(b) != 4000 {
201		t.Fatal("unreachable")
202	}
203}
204
205func TestAllocBytes4000(t *testing.T) {
206	b := make([]byte, 16000)
207	if len(b) != 16000 {
208		t.Fatal("unreachable")
209	}
210}
211
212// The five arrays predecode builds, at the same two sizes.
213func TestAllocArrays1000(t *testing.T) {
214	a, b, c := make([]uint8, 1000), make([]uint8, 1000), make([]uint8, 1000)
215	d, e := make([]uint8, 1000), make([]uint32, 1000)
216	if len(a)+len(b)+len(c)+len(d)+len(e) == 0 {
217		t.Fatal("unreachable")
218	}
219}
220
221func TestAllocArrays4000(t *testing.T) {
222	a, b, c := make([]uint8, 4000), make([]uint8, 4000), make([]uint8, 4000)
223	d, e := make([]uint8, 4000), make([]uint32, 4000)
224	if len(a)+len(b)+len(c)+len(d)+len(e) == 0 {
225		t.Fatal("unreachable")
226	}
227}