ladder_test.gno

  1package bf
  2
  3import (
  4	"testing"
  5
  6	"gno.land/p/moul/x/vm/vmkit/v0"
  7	"gno.land/p/nt/uassert/v0"
  8)
  9
 10// heavy is the benchmark program: 200 increments, then an outer loop that on
 11// each of its 200 iterations moves right, adds 200, clears that cell with the
 12// "[-]" idiom, and moves back.
 13//
 14// It writes nothing, so a measurement of it is a measurement of the dispatch
 15// loop and not of the output path.
 16var heavy = rep("+", 200) + "[" + "-" + ">" + rep("+", 200) + "[-]" + "<" + "]"
 17
 18// GuestOps and NaiveDispatches are the two counts for [heavy], and the
 19// difference between them is the reason the ladder needs both named.
 20//
 21// A guest instruction is one operator the language executes, counted the way
 22// any jump-table interpreter counts it. The naive interpreter dispatches more
 23// often than that for the same program: its "]" handler scans back to the
 24// matching "[" and lands on it, so "[" is re-evaluated on every iteration of
 25// every loop. On heavy that is 1.33 dispatches per guest instruction.
 26//
 27// Rung 1 removes exactly that excess, so a ladder that used the naive
 28// dispatch count as its denominator would be crediting rung 1 twice. Both
 29// numbers come from an independent simulator, not from this package, so the
 30// denominator is not derived from the thing being measured.
 31const (
 32	GuestOps        = 121201
 33	NaiveDispatches = 161200
 34)
 35
 36func rep(s string, n int) string {
 37	out := ""
 38	for i := 0; i < n; i++ {
 39		out += s
 40	}
 41	return out
 42}
 43
 44// nullHost is a Host that costs as close to nothing as a Host can, so the
 45// ladder measures the dispatch loop rather than the storage or output path.
 46type nullHost struct{}
 47
 48func (nullHost) Caller() address                     { return address("") }
 49func (nullHost) Origin() address                     { return address("") }
 50func (nullHost) Now() int64                          { return 0 }
 51func (nullHost) Height() int64                       { return 0 }
 52func (nullHost) Get(key []byte) []byte               { return nil }
 53func (nullHost) Set(key, val []byte)                 {}
 54func (nullHost) Input() []byte                       { return nil }
 55func (nullHost) Output(p []byte)                     {}
 56func (nullHost) Emit(typ string, kv ...string)       {}
 57func (nullHost) Send(to address, amount int64) error { return vmkit.ErrNotGranted }
 58func (nullHost) Log(msg string)                      {}
 59
 60// runHeavy compiles heavy at lvl and runs it on the shipped machine,
 61// returning how many machine ops it executed. The count is the fuel the
 62// machine charged itself, so the ladder's "machine ops" column is measured by
 63// the machine and not counted by hand.
 64func runHeavy(t *testing.T, lvl Level) int64 {
 65	t.Helper()
 66	prog, err := Compile(heavy, lvl)
 67	uassert.NoError(t, err)
 68	if prog == nil {
 69		return 0
 70	}
 71	m := NewMachine(prog)
 72	used, status := m.Step(nullHost{}, vmkit.Unmetered)
 73	uassert.Equal(t, "halted", status.String())
 74	return used
 75}
 76
 77// The rungs. One test each, so `gno test -print-runtime-metrics` prints one
 78// cycle count per rung and the README's table is a transcription rather than
 79// an estimate. They assert that the run completed and how many machine ops it
 80// took: what is being recorded is the metric line.
 81
 82func TestRung0Naive(t *testing.T) {
 83	uassert.Equal(t, "", Execute(heavy))
 84}
 85
 86func TestRung0Naive4x(t *testing.T) {
 87	for i := 0; i < 4; i++ {
 88		Execute(heavy)
 89	}
 90}
 91
 92func TestRung1Jumps(t *testing.T) {
 93	uassert.Equal(t, int64(GuestOps+1), runHeavy(t, LevelJumps))
 94}
 95
 96func TestRung2Fuse(t *testing.T) {
 97	uassert.True(t, runHeavy(t, LevelFuse) < GuestOps)
 98}
 99
100func TestRung3Idioms(t *testing.T) {
101	uassert.True(t, runHeavy(t, LevelIdioms) < GuestOps)
102}
103
104func TestRung3Idioms4x(t *testing.T) {
105	for i := 0; i < 4; i++ {
106		runHeavy(t, LevelIdioms)
107	}
108}
109
110func TestRung5Metered(t *testing.T) {
111	// Same program, same rung, but every op goes through the fuel meter's
112	// budget branch instead of its unmetered one. The delta against
113	// TestRung3Idioms is the price of being a machine that can be stopped.
114	prog, err := Compile(heavy, LevelIdioms)
115	uassert.NoError(t, err)
116	m := NewMachine(prog)
117	_, status := m.Step(nullHost{}, 1<<40)
118	uassert.Equal(t, "halted", status.String())
119}
120
121// TestLadderOpCounts records the compile-time half of the ladder: how many
122// machine ops each rung executes for the same 121,201 guest instructions.
123// These are the numbers the README's table quotes, asserted here so the table
124// cannot silently go stale.
125func TestLadderOpCounts(t *testing.T) {
126	jumps := runHeavy(t, LevelJumps)
127	fuse := runHeavy(t, LevelFuse)
128	idioms := runHeavy(t, LevelIdioms)
129
130	// Rung 1 executes exactly one machine op per guest instruction, plus
131	// the halt: the independent simulator and this machine agree to the op.
132	uassert.Equal(t, int64(121202), jumps)
133	// Fusing runs of + and > collapses the two 200-long runs.
134	uassert.Equal(t, int64(81203), fuse)
135	// Recognizing "[-]" turns the inner clear loop into a single op.
136	uassert.Equal(t, int64(1203), idioms)
137
138	uassert.True(t, fuse < jumps)
139	uassert.True(t, idioms < fuse)
140}