Bettering programming language efficiency | xnacly

I began creating the sophia programming language in july 2023 to study all
about lexical evaluation, parsing and analysis in an actual world setting. Thus i
selected the (in)well-known lisp S-expressions. A really early stage of the undertaking
will be seen
here.

At the moment the syntax is as follows:

 1;; energy of n
 2(enjoyable sq. (_ n)
 3    (* n n))
 4
 5(let n 12)
 6(let res
 7    (sq. a))
 8(put '{n}*{n} is {res}') ;; 12*12 is 144
 9
10;; fizzbuzz 0-15
11(for (_ i) 15
12    (let mod3 (eq 0 (% i 3)))
13    (let mod5 (eq 0 (% i 5)))
14    (match
15        (if (and mod3 mod5) (put "FizzBuzz"))
16        (if mod3 (put "Fizz"))
17        (if mod5 (put "Buzz"))
18        (put i)))
19
20;; environment friendly binomial computation
21(enjoyable bin (_ n ok)
22    (if (gt ok n)
23        (return -1))
24    (if (and (eq ok n) (eq ok 0))
25        (return 1))
26
27    ;; Because of the symmetry of the binomial coefficient with regard to ok and n −
28	;; ok, calculation could also be optimised by setting the higher restrict of the
29	;; product above to the smaller of ok and n − ok, see
30	;; https://en.wikipedia.org/wiki/Binomial_coefficient#Computing_the_value_of_binomial_coefficients
31    (let kn (- n ok))
32    (if (lt kn ok)
33        (let ok kn))
34
35    ;; see https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
36    (let r 1)
37    (for (_ i) ok
38        (let r
39            (/ (* r (- n i)) (+ i 1)))
40        )
41    r)
42
43(put (bin 1 1)) ;; 1
44(put (bin 6 3)) ;; 20
45(put (bin 49 6)) ;; 20
46(put (bin 20 15)) ;; 15504

Lets Speak Structure ##

The interpreter follows the identical rudimentary levels of interpretation most interpreters make use of:

1. Lexical evaluation: character stream to token stream
2. Parsing: token stream to summary syntax tree
3. Evalulation: summary syntax tree to values (Tree stroll interpreter)

I didn’t develop the interpreter with efficiency in thoughts.

Tip

Each the lexer and the parser do not likely try this a lot, thus i concentrate on the
analysis stage of the interpreter on this weblog submit.

AST and Eval ###

The analysis is probably the most fascinating a part of the interpreter, I selected the
Interpreter pattern –
just because it was the primary time I used to be implementing an interpreter.

The AST in sophia consists of Node’s that may comprise little one Node’s. The
analysis course of begins on the root of the AST and dispatches a
Node.Eval() name. The foundation node dispatches this name to its kids and its
kids to their kids, thus strolling the tree and shifting the work to the
Node’s:

 1// expr/node.go
 2kind Node interface {
 3    // [...]
 4    Eval() any
 5}
 6
 7// expr.String statisfies expr.Node
 8kind String struct {
 9    Token token.Token
10}
11
12func (s *String) Eval() any {
13    return s.Token.Uncooked
14}
15
16// expr.Put dispatches a .Eval name
17// to every of its little one nodes
18kind Put struct {
19    Token    token.Token
20    Youngsters []Node
21}

Because of the interpreter holding all token, all ast nodes and probably strolling
and calling Eval() on most of them a number of instances, the reminiscence and cpu
footprint is giant for a minimal language like this. This may be mitigated
with transforming the analysis right into a byte code compiler and vm.

Benchmarking ##

The true drawback is that programmers have spent far an excessive amount of time worrying
about effectivity within the flawed locations and on the flawed instances; untimely
optimization is the basis of all evil (or no less than most of it) in programming.

Donald E. Knuth, Turing Award Lecture (1974)

Step one within the technique of optimisation is to know the place to look. I
didn’t have any earlier expertise with benchmarks and interpreter efficiency –
subsequently I did the one accountable factor and fired up a profiler.

Instance benchmark ###

Earlier than we try this we wish to shortly hack up a script utilizing a large enough set of
the directions of our programming language that takes lengthy sufficient for us to
acquire an perception on whats happening contained in the interpreter. I selected a leetcode
drawback and wish to execute it round 500k instances – this could actually give us a
large enough of a pattern.

 1;; leetcode 327 Most Rely of optimistic integer and detrimental integer
 2(let example1
 3    (not 2) ;; negated: (not 2) -> -2
 4    (not 1)
 5    (not 1) 1 2 3)
 6(let example2 (not 3) (not 2) (not 1) 0 0 1 2)
 7(let example3 5 20 66 1314)
 8
 9;; returns a if larger than b, in any other case b
10;; max: float, float -> float
11(enjoyable max (_ a b)
12    (let max a) ;; created as nil
13    (if (lt a b) (let max b))
14    max) ;; return with out further assertion
15
16;; counts detrimental and positve numbers in arr, returns the upper quantity
17(enjoyable clear up (_ arr)
18    (let pos 0)
19    (let neg 0)
20    (for (_ i) arr
21        (match
22            (if (lt i 0) (let pos (+ pos 1)))
23            (let neg (+ neg 1))))
24    (max neg pos))
25
26
27(for (_ i) 500_000
28    (clear up example1) ;; 3
29    (clear up example3) ;; 4
30    (clear up example2) ;; 4
31)

Naive first estimates ###

Executing this on my machine with none optimizations utilized takes a whooping
6.5s:

Anyway, lets begin organising the profiler.

Mission and Profiler setup ###

Tip

That is considerably of a information to organising a go undertaking and operating a profiler
with the appliance. You’ll be able to observe alongside in case your need :^).

Lets first clone the repo and transfer again in git historical past untill we’re earlier than the optimizations came about:

1git clone https://github.com/xnacly/sophia oldsophia
2cd oldsophia
3git reset --hard 024c69d

Lets modify our utility to gather runtime metrics through the
runtime/pprof package deal:

 1// oldsophia/predominant.go
 2package deal predominant
 3
 4import (
 5	"os"
 6	"runtime/pprof"
 7	"sophia/core/run"
 8)
 9
10func predominant() {
11	f, err := os.Create("cpu.pprof")
12	if err != nil {
13		panic(err)
14	}
15	pprof.StartCPUProfile(f)
16	defer pprof.StopCPUProfile()
17
18	run.Begin()
19}

The following step is to compile, run and begin the profile of our utility with
the instance benchmark script we created earlier than:

1$ go construct.
2$ ./sophia leetcode.phia
3$ go device pprof -http=":8080" ./sophia ./cpu.pprof

We aren’t within the graph view, so lets swap to Prime.

Essentially the most fascinating for us on this new view are the Flat and Flat% columns:

Archiving Simple Efficiency Positive aspects ##

Doing much less is extra (efficiency) ###

Particularly in scorching paths, equivalent to nodes which can be accessed or evaluated quite a bit,
lowering the quantity of directions or operations is essential to bettering
efficiency.

Fixed parsing ####

Beforehand each expr.Boolean & expr.Float did heavy operations on every
Eval() name:

 1func (f *Float) Eval() any {
 2	float, err := strconv.ParseFloat(f.Token.Uncooked, 64)
 3	if err != nil {
 4		serror.Add(&f.Token, "Float parse error", "Didn't parse float %q: %q", f.Token.Uncooked, err)
 5		serror.Panic()
 6	}
 7	return float
 8}
 9
10func (b *Boolean) Eval() any {
11	return b.Token.Uncooked == "true"
12}

Each these features can and can be executed a number of instances all through operating
a script, thus computing these values at parse time improves efficiency be
lowering operations in scorching paths.

 1// core/parser/parser.go:
 2func (p *Parser) parseArguments() expr.Node {
 3    // [...]
 4	} else if p.peekIs(token.FLOAT) {
 5		t := p.peek()
 6		worth, err := strconv.ParseFloat(t.Uncooked, 64)
 7		if err != nil {
 8			serror.Add(&t, "Didn't parse quantity", "%q not a sound floating level integer", t.Uncooked)
 9			worth = 0
10		}
11		little one = &expr.Float{
12			Token: t,
13			Worth: worth,
14		}
15        //[...]
16	} else if p.peekIs(token.BOOL) {
17		little one = &expr.Boolean{
18			Token: p.peek(),
19			// fastpath for simple boolean entry, skipping a examine for every eval
20			Worth: p.peek().Uncooked == "true",
21		}
22	}
23    // [...]
24}
25
26// core/expr/float.go:
27kind Float struct {
28	Token token.Token
29	Worth float64
30}
31
32func (f *Float) Eval() any {
33	return f.Worth
34}
35
36// core/expr/bool.go:
37kind Boolean struct {
38	Token token.Token
39	Worth bool
40}
41
42func (b *Boolean) Eval() any {
43	return b.Worth
44}

Sort casts!? ####

A outstanding operate within the profiler output is core/expr.castPanicIfNotType,
which is a generic operate and on this case current for float64:

The implementation for castPanicIfNotType is as follows:

1func castPanicIfNotType[T any](in any, t token.Token) T {
2	val, okay := in.(T)
3	if !okay {
4		var e T
5		serror.Add(&t, "Sort error", "Incompatiable varieties %T and %T", in, e)
6		serror.Panic()
7	}
8	return val
9}

This operate will increase the load on the rubbish collector as a result of val is
virtually at all times escaping to the heap. I attempted mitigate the necessity for a generic
operate by implementing two helper features for casting to bool and to
float64, each features make use of kind switches and proved to be quicker /
being not represented within the prime 15 of the profiler:

 1// fastpath for casting bool, reduces reminiscence allocation by skipping allocation
 2func castBoolPanic(in any, t token.Token) bool {
 3	swap v := in.(kind) {
 4	case bool:
 5		return v
 6	default:
 7		serror.Add(&t, "Sort error", "Incompatiable varieties %T and bool", in)
 8		serror.Panic()
 9	}
10	// technically unreachable
11	return false
12}
13
14// fastpath for casting float64, reduces reminiscence allocation by skipping allocation
15func castFloatPanic(in any, t token.Token) float64 {
16	swap v := in.(kind) {
17	case float64:
18		return v
19	default:
20		serror.Add(&t, "Sort error", "Incompatiable varieties %T and float64", in)
21		serror.Panic()
22	}
23	// technically unreachable
24	return 0
25}

Ensuing benchmark and pprof ###

Placing these optimisation collectively, rebuilding and rerunning the app +
profiler leads to our new prime 15 features we will use for optimising the
interpreter additional:

We lowered the time castPanicIfNotType took from 0.24s to 0.16s, moreover
we lowered expr.(*Lt).Eval from 0.37s to 0.27s. Our large challenge with rubbish
assortment (pink sq. on the prime proper) nonetheless stays.

We began of with a hyperfine naive benchmark for whole time taken to run the
script, thus I’ll proceed evaluating through the profiler and hyperfine:

Our straightforward to implement modifications already decreased the runtime by ~750ms from
6.553s to five.803s compared to the not optimised state.

Much less Simple Efficiency Positive aspects ##

Much less allocations, much less frees ###

Essentially the most eye-catching operate is unquestionably the runtime.mallocgc operate.
Our program spends 0.76s of its complete execution allocating reminiscence – Keep in mind we
are writing an interpreter, the lexical evaluation and the parser are making a
lot of reminiscence.

At the moment every AST node shops a duplicate of its token, this might be a possible
trigger for enormous allocation actions, merely as a result of the truth that we now have a
lot of tokens and AST nodes.

1kind Float struct {
2    // copied by the parser, primarily duplicating GC load
3	Token token.Token
4	Worth float64
5}

Our first optimization is subsequently to cease copying tokens into AST nodes and
as a substitute preserve references to them. Theoretically we should always scale back the quantity of
reminiscence for the rubbish collector to allocate and free from n^2 to n, the place
n is the quantity of tokens * the scale of a token:

1kind Float struct {
2	Token *token.Token
3	Worth float64
4}

This optimization took a while to implement, I needed to rewrite elements of the
parser and all expression definitions.

Quick paths ###

The sophia language accommodates an entire lot of directions that settle for two or
extra directions, equivalent to:

• addition
• subtraction
• division
• multiplication
• modulus
• and
• or
• equal

expr.Add and the opposite above expressions had been applied by merely iterating
the youngsters of the node and making use of the operation to them:

 1func (a *Add) Eval() any {
 2	if len(a.Youngsters) == 0 {
 3		return 0.0
 4	}
 5	res := 0.0
 6	for i, c := vary a.Youngsters {
 7		if i == 0 {
 8			res = castFloatPanic(c.Eval(), a.Token)
 9		} else {
10			res += castFloatPanic(c.Eval(), a.Token)
11		}
12	}
13	return res
14}

The brand new and improved manner consists of checking if there are two kids, thus
having the ability to apply the operation for the 2 kids instantly:

 1func (a *Add) Eval() any {
 2	if len(a.Youngsters) == 2 {
 3		// fastpath for 2 kids
 4		f := a.Youngsters[0]
 5		s := a.Youngsters[1]
 6		return castFloatPanic(f.Eval(), f.GetToken()) + castFloatPanic(s.Eval(), s.GetToken())
 7	}
 8
 9	res := 0.0
10	for i, c := vary a.Youngsters {
11		if i == 0 {
12			res = castFloatPanic(c.Eval(), c.GetToken())
13		} else {
14			res += castFloatPanic(c.Eval(), c.GetToken())
15		}
16	}
17	return res
18}

Reinvent the wheel (generally) ###

That is an optimization that i couldn’t precisely measure, however I knew having to
parse a format string for every put instruction is just too heavy of an operation:

 1func (p *Put) Eval() any {
 2	b := strings.Builder{}
 3	for i, c := vary p.Youngsters {
 4		if i != 0 {
 5			b.WriteRune(' ')
 6		}
 7		b.WriteString(fmt.Dash(c.Eval()))
 8	}
 9	fmt.Printf("%sn", b.String())
10	return nil
11}

Thus I not solely eliminated the fmt.Printf name but additionally wrapped it for widespread prints:

 1func (p *Put) Eval() any {
 2	buffer.Reset()
 3	formatHelper(buffer, p.Youngsters, ' ')
 4	buffer.WriteRune('n')
 5	buffer.WriteTo(os.Stdout)
 6	return nil
 7}
 8
 9// core/expr/util.go
10func formatHelper(buffer *bytes.Buffer, kids []Node, sep rune) {
11	for i, c := vary kids {
12		if i != 0 && sep != 0 {
13			buffer.WriteRune(sep)
14		}
15		v := c.Eval()
16		swap v := v.(kind) {
17		case string:
18			buffer.WriteString(v)
19		case float64:
20			buffer.WriteString(strconv.FormatFloat(v, 'g', 12, 64))
21		case bool:
22			if v {
23				buffer.WriteString("true")
24			} else {
25				buffer.WriteString("false")
26			}
27		default:
28			fmt.Fprint(buffer, v)
29		}
30	}
31}

This new operate omits the necessity for parsing format strings, calling to the
runtime to make use of reflection for easy circumstances equivalent to strings, float64 and
booleans. The identical formatHelper operate is reused for format strings.

Ensuing benchmark and pprof ###

Once more we restart the profiler and examine our prime 15 features:

See Also

Biking Doping Fallacies · The New Leaf Journal

We moved runtime.mallocgc and runtime.nextFreeFast down by an entire lot, the
first from 0.74s of the appliance run time to 0.12s, the second from 0.28s to
0.05s.

Our barely much less straightforward to implement modifications decreased the runtime by 3.795s
from 5.803s to 2.009s compared to the not optimised state – that’s actually
good, actually actually good, we’re speaking a 65.38% runtime lower.

A story of hash desk key efficiency ##

Our final optimization requires an introduction. The sophia programming language
shops all consumer outlined variables in a map referred to as consts.SYMBOL_TABLE and all
consumer outlined features in consts.FUNC_TABLE. Each are maps utilizing strings as
keys.

1var FUNC_TABLE = make(map[string]any, 16)
2var SYMBOL_TABLE = make(map[string]any, 64)

Map key hashing is so costly this system spends 0.23s/12.5% of its whole
runtime on assigning keys to a map (runtime.mapassign_faststr), 0.23s/12.5%
on hashing strings (runtime.aeshashbody) and 0.16s/8.7% on accessing maps
(runtime.mapaccess2_faststr). Cumulated these add as much as 0.62s or 33.7% of the
utility runtime, thus positively value investigating.

Hashing strings with for instance
FNV-1a
is as costly because the string is lengthy, as a result of the hash has to take each
character under consideration. Integers are inherently simpler to hash and subsequently
require much less computational effort. This prompted me to check if the maps would
carry out higher with uint32 as keys.

Changing this was laborious, as a result of I needed to discover a manner of protecting observe of distinctive
variables and features whereas assigning them an identifier (this after all had
to be extra environment friendly than strings as keys for maps).

I solved this by creating the
sophia/core/alloc
package deal and hooking it as much as the parser. This package deal retains observe of variables,
features and their distinctive id whereas parsing. Whereas evaluating, the map entry
for identifiers is finished with their new fields referred to as Key the parser fills
with the assistance of the alloc package deal:

 1// core/expr/ident.go
 2kind Ident struct {
 3	Token *token.Token
 4	Key   uint32
 5	Identify  string
 6}
 7
 8func (i *Ident) Eval() any {
 9	val, okay := consts.SYMBOL_TABLE[i.Key]
10	if !okay {
11		serror.Add(i.Token, "Undefined variable", "Variable %q will not be outlined.", i.Identify)
12		serror.Panic()
13	}
14	return val
15}
16
17// core/parser/parser.go
18func (p *Parser) parseStatement() expr.Node {
19    // [...]
20    case token.LET:
21		if len(childs) == 0 {
22			serror.Add(op, "Not sufficient arguments", "Anticipated no less than one argument for variable declaration, acquired %d.", len(childs))
23			return nil
24		}
25		ident, okay := childs[0].(*expr.Ident)
26		if !okay {
27			serror.Add(childs[0].GetToken(), "Flawed parameter", "Anticipated identifier, acquired %T.", childs[0])
28			return nil
29		}
30		if _, okay := alloc.Default.Variables[ident.Name]; !okay {
31			ident.Key = alloc.NewVar(ident.Identify)
32		}
33		stmt = &expr.Var{
34			Token: op,
35			Ident: ident,
36			Worth: childs[1:],
37		}
38}

Ensuing benchmark and pprof ###

So lets benchmark this drastic change and have a look what occurred compared to the earlier change:

We changed the costly map entry through string keys and changed them with
their respective 32 variants. This modified the cumulated quantity of
utility runtime for map entry from beforehand 0.62s or 33.7% to 0.66s or
40%, nevertheless our hyperfine benchmark tells us we decreased the whole runtime by
~400ms from beforehand 2s to 1.6s:

Ultimate benchmarks ##

Lets examine the earlier stage with the optimised stage of the undertaking through hyperfine:

This after all being my beefy machine, if I run the identical benchmark on my
macbook from 2012, I primarily develop on whereas in college (and that i first ran the
benchmark on), the delta is much more spectacular:

In comparison with a ~4x enchancment a ~7x enchancment is much more spectacular.