Building a Development Environment for Monkey: Part 3 - Solving an Advent of Code problem

Intro

We are finally done with building the development environment for Monkey after Part 1 and Part 2 of our series, by adding syntax highlighting with Tree-sitter and building a Language Server for it from scratch in Go respectively. If you haven't already I suggest you check them out.

In the final entry of the series we will put Monkey to "real" work, solving an AoC problem (2024 - Day 1). Attempting to solve this problem will quickly reveal how limited Monkey is, how the Tree-sitter corpus and all the LSP unit tests missed some bugs and how we had to improve upon the language by going back to our previous two projects. Finally, we will also look closely at the solution's performance.

The following are some of the key findings:

• The LSP had a typed nil interface bug that broke all language features inside if blocks without an else block.
• Monkey's lexer didn't read escape characters correctly while reading/lexing string literals.
• Monkey is ~1000x slower than Go (2317 ms vs 2 ms).
• Monkey allocates ~2000x more memory than Go (232 MB vs 118 KB per op).
• ~83% of CPU time is inside the interpreter's Eval loop.
• ~39% of all allocations come from creating a new Environment per function call.

The AoC problem and solution

For brevity, I won't dump the interesting story behind the problem itself here since AoC problems tend to have rather long mythical stories.

The problem has two parts and they both have a similar input file: 1000 lines of two columns of numbers separated by three white-space characters. An example input:

3   4
4   3
2   5
1   3
3   9
3   3

Part one

The problem is stated as follows:

Pair up the smallest number in the left list with the smallest number in the right list, then the second-smallest left number with the second-smallest right number, and so on.

Within each pair, figure out how far apart the two numbers are; you'll need to add up all of those distances.

The naive algorithm of my solution is as follows:

1. Sort both columns in a non-decreasing order.
2. Iterate over the two columns simultaneously, and in the iteration we sum up the absolute difference between each column for each line.

Part two

The problem is stated as follows:

This time, you'll need to figure out exactly how often each number from the left list appears in the right list. Calculate a total similarity score by adding up each number in the left list after multiplying it by the number of times that number appears in the right list.

The algorithm to my naive solution: To find the similarity score, for each number in the first column, we count it in the second column and multiply that count with the number. The sum of all of these products will be the solution.

The efficient solution would be to build a frequency map the numbers in the right column first and then using it to find the counts of the numbers in the first column with a cheap hash map lookup.

We will stick to the naive O(n^2) solution to put Monkey to more work, which will help us observe its flaws far better than if we went with the efficient solution.

Monkey's limitations

First and foremost we need to read the input file and Monkey does not have a way to do that. We also need to do some string manipulations on the input text like splitting and trimming. Since the input is read as a string, we need a way to convert the string numbers into integers. As we saw in our solution for part one, we also need a way to sort an array of numbers. Other major issues include:

• no for loops - we have no keywords to iteratively run a code snippet or loop over iterable objects.
• no variable re-assignment (only declaration) - which makes Monkey a "type-safe" language (when it comes to variables). But funnily enough not just limited to types, it's also "value-safe" because you cannot assign another value to an already declared variable.

Solutions to language limitations

Some limitations can be worked around while some require changes to the interpreter itself. For example we can solve the following without any changes:

• Loops: We can use recursion to loop however we like. It only comes at the disadvantage of having O(n) space complexity. The bigger the loop, the deeper the recursion, the more stack memory used.
• Variable assignment: This can be solved by simply declaring new variables or, in our solutions, just passing them into functions as arguments to be updated through calls.

But when it comes to other limitations such as reading a file, string manipulations, ASCII to integer conversion or sorting, I resorted to just adding more built-in Monkey functions. In other words, doing them in Go, which may seem like cheating but implementing some of these things in Monkey is way more than what I'm currently willing to do!

Monkey updates: built-in functions and more

The following are the new Monkey built-in functions I had to add in order solve this AoC problem.

readFile

This function accepts the path to the file as a string and returns the full string content of the file. It uses Go's os.ReadFile function under the hood.

The main take away from implementing this and struggling with why it was reporting "file doesn't exist" is that a process's CWD is wherever the shell was when the program is launched. Running ./bin/monkey from the project root and relative paths resolve against the root; cd bin && ./run and they resolve against bin. The binary's location is irrelevant.

splitString

This function accepts a string as its first argument and the separator string as the second and it returns an array of strings. It uses Go's strings.Split function under the hood.

Unfortunately this wasn't the end of it, check out the following code: input.txt

1
2

main.monkey

let input = readFile("input.txt");
let lines = splitString(input, "\n");

puts(lines)
// Expected: ["1", "2"]
// Actual  : ["1/n2"]

When I tried to split a file into lines using splitString, the result was a single-element array containing the entire file.

Updating Monkey's Lexer to read escape sequences properly

The culprit turned out to be Monkey's Lexer, can you figure out what the issue is? lexer.go

// readChar() reads one character at a time from the input source code
func (l *Lexer) readString() string {
    position := l.position + 1 // advances the reader's position by one from the initial opening " of a string

    for {
        l.readChar()

        if l.ch == '"' || l.ch == 0 { // reached end of string or file
            break
        }
    }

    return l.input[position:l.position]
}

Our lexer did not handle escape sequences correctly, our second argument "\n" was lexed as two literal characters/bytes (\ and n) rather than the newline byte 0x0A (\n). This meant that splitString was searching for a two-character sequence that never appeared in the actual file content.

The fix was to rewrite readString in the lexer to decode escape sequences on the fly:

• \n becomes a real newline
• \t a tab
• \\ a backslash, and
• \" a quote
• Unknown escapes are kept literally so that no data is silently lost.

lexer.go (see source)

func (l *Lexer) readString() string {
    var sb strings.Builder

    for {
        l.readChar()

        // end of string or file
        if l.ch == '"' || l.ch == 0 {
            break
        }

        // normal case
        if l.ch != '\\' {
            sb.WriteByte(l.ch)
            continue
        }

        // different paths depending on the next char
        switch l.peekChar() {
        case 'n':
            l.readChar()
            sb.WriteByte('\n')
        case 't':
            l.readChar()
            sb.WriteByte('\t')
        case 'r':
            l.readChar()
            sb.WriteByte('\r')
        case '"':
            l.readChar()
            sb.WriteByte('"')
        case '\\':
            l.readChar()
            sb.WriteByte('\\')
        default:
            sb.WriteByte('\\') // just writes \ by default
        }
    }

    return sb.String()
}

NOTE: Not only did we fix readString, but we also added escaping quotes to Monkey's strings, which was not possible before.

Updating Monkey's Tree-sitter to handle escape sequences properly

Monkey strings can properly use escape sequences after updating our Lexer but our Tree-sitter grammar does not.

This is what a Monkey string with escaped quotes looked like before the fix, not so great:

Let's look at how our grammar describes strings: grammar.js

string: _ => token(seq('"', /[^"]*/, '"')), // no escapes

It handles any character except for quotes. Lets fix this by adding a new rule escape_sequence: grammar.js

string: $ => seq('"', repeat(choice(
    $.escape_sequence, // \n, \t, \\, \"
)), '"'),
escape_sequence: _ => /\\[ntr"\\]/,

That's it.

It also turns out that there's a specific Neovim capture @string.escape (check Neovim docs) to handle escaped characters specifically, lets use that in highlights.scm:

(escape_sequence) @string.escape

The result:

Bellissima!

atoi

atoi accepts a string as an argument and returns a number, it uses Go's strconv.Atoi function under the cover.

sortInts

sortInts accepts an array of integers and returns it sorted in a non-decreasing order, it uses Go's slices.Sort function.

trimSpace

trimSpace accepts a string and trims leading and trailing white space, returning the resulting string. It uses Go's strings.TrimSpace internally.

trimSuffix

trimSuffix accepts a string and returns it without the provided trailing suffix string. It uses Go's strings.TrimSuffix internally.

Updating Tree-sitter to include our new built-in functions

We should update highlights.scm to highlight our new functions as built-ins with the @function.builtin capture.

((call_expression
  function: (identifier) @function.builtin
  (#any-of? @function.builtin "len" "first" "last" "rest" "push" "puts"
    "readFile" "splitString" "atoi" "sortInts" "trimSpace" "trimSuffix"))
  (#set! priority 130))

Yet another typed nil interface bug

As I was implementing the solution, I encountered the most elusive bug I have faced in the series so far. Consider the following monkey code:

if(true){
    puts("hello")
}

All three language features stopped working inside and also after the if block, all triggering these features caused the server to panic.

After inspecting the stack trace, the cause turned out to be the function FindASTNode(state.go) in the Monkey Language Server. FindASTNode received an interface value whose data word was 0x0 yet somehow survived my if node == nil guard at the very start of the function.

IfExpression.Alternative is declared as *ast.BlockStatement, and an if expression without an else leaves it as a nil pointer.

Boxing a (*ast.BlockStatement)(nil) into the ast.Node interface produces a non-nil interface wrapping a nil pointer. node == nil is false because the type word is set, the type switch still matches *ast.BlockStatement, and the walker happily de-references the empty struct causing a panic.

This exact mistake is mentioned in the Go Mistakes and How to Avoid Them book under mistake #45, Returning a nil receiver. state.go

func FindASTNode(node ast.Node, line, character uint) ast.Node {
    // This fails
    if node == nil {
        return nil
    }

    switch node := node.(type) {
    case *ast.BlockStatement:
        // Panic happens in this function, dereferencing the nil node
        if !positionIsInRange(node, line, character) {
            return nil
        }
        for _, stmt := range node.Statements {
            if n := FindASTNode(stmt, line, character); n != nil {
                return n
            }
        }

    case *ast.IfExpression:
        if n := FindASTNode(node.Condition, line, character); n != nil {
            return n
        }
        if n := FindASTNode(node.Consequence, line, character); n != nil {
            return n
        }

        // The issue, node.Alternative is nil
        return FindASTNode(node.Alternative, line, character)
    }

    return nil
}

The following fix of changing the if expression case suffices (see source):

case *ast.IfExpression:
        if n := FindASTNode(node.Condition, line, character); n != nil {
            return n
        }
        if n := FindASTNode(node.Consequence, line, character); n != nil {
            return n
        }

        if node.Alternative != nil {
            return FindASTNode(node.Alternative, line, character)
        }

        return nil
    }

We can also update our guard to be more capable using reflection as follows:

func FindASTNode(node ast.Node, line, character uint) ast.Node {
    if isNilNode(node) {
        return nil
    }
    // ...
}

func isNilNode(node ast.Node) bool {
    if node == nil {
        return true
    }

    v := reflect.ValueOf(node)
    switch v.Kind() {
    case reflect.Pointer, reflect.Interface, reflect.Slice, reflect.Map:
        return v.IsNil()
    }
    return false
}

The Monkey solution

All issues are now fixed, let's finally solve the AoC problem.

reading the input

We read the input similarly for both problems.

let content = trimSuffix(readFile("input.txt"), "\n")
let lines = splitString(content, "\n")

let prep = fn(i) {
    if (i==len(lines)){
        return {
            "colOne": [],
            "colTwo": [],
        };
    }

    let res = prep(i+1);

    let splitLine = splitString(lines[i], "   ");
    return {
        "colOne": push(res["colOne"], atoi(splitLine[0])),
        "colTwo":push(res["colTwo"], atoi(splitLine[1])),
    };
}

let res = prep(0)

trimSuffix applied on the input because editors sometimes add \n to the input text. prep accepts an iteration index to recursively prepare two integer arrays from lines, an array of strings where each string is a line from the input. The base case is the end of the input, when the iterator is equal to the number of lines.

The result is a hash-map with two keys, they should be self-descriptive enough.

part one

part1.monkey

// read input

let colOne = sortInts(res["colOne"]);
let colTwo = sortInts(res["colTwo"]);

let dayOne = fn(i, j){
    if (i==len(lines)) {
        return 0
    }

    let sum = dayOne(i+1, j+1);

    let diff = colOne[i] - colTwo[j];
    return sum + if(diff<0){ -1*diff }else{ diff };
}

puts(dayOne(0, 0))

We start by sorting both columns (integer arrays) with sortInts. dayOne accepts two iteration indexes and recursively sums up the absolute differences of numbers on each line. The base case is the end of the input; we return 0. Then the recursion stack unwinds calculating and returning the new sum starting from the end of the arrays.

Running this on the main input returns: 2580760, which is the actual solution. It worked first try!

part two

part2.monkey

// read input

let colOne = res["colOne"];
let colTwo = sortInts(res["colTwo"]);

let countNumInArray = fn(num, arr, i) {
    if (i == len(arr)){
        return 0;
    }

    if (num < arr[i]){
        return 0;
    }

    let res = countNumInArray(num, arr, i+1);
    return if (num == arr[i]){ res + 1 } else { res };
}

let dayTwo = fn(i){
    if (i == len(colOne)){
        return 0;
    }

    let sol = dayTwo(i+1);

    let num = colOne[i]
    let numCount = countNumInArray(num, colTwo, 0);

    return sol + (num * numCount);
}

puts(dayTwo(0))

The solution to the second part is a bit more involved compared to the first as it is for most AoC problems.

We start by grabbing the two columns from the input and sorting the second one, this will help us prune our search by stopping the count when a candidate number in the second column becomes bigger than the number we are counting from the first.

countNumInArray accepts a number, an array and an iteration index and recursively counts the number in the given array. The base case is the end of the input and it also has an early return to stop the count to continue past bigger numbers than the one we are counting.

dayTwo accepts an iteration index as input and recursively iterates over the first column of integers and each time, it counts the number at that index in the second column and returns the product of the number and its count in the second column.

Running this on the main input again returns: 25358365, which is the correct answer!

Performance

Even though our solutions to each problem produced correct answers, their performances leave much to be desired. The poor performance is especially noticeable when testing the solutions with the main 1000-line input.

In the following sections we will do some benchmarking to compare our Monkey solutions to their equivalent Go solutions. Afterwards, we will explore and try to diagnose where all the CPU time is spent by performing CPU profiling.

The Go solution is as follows:

func Parse(path string) (col1, col2 []int) {
    fileBytes, err := os.ReadFile(path)
    if err != nil { panic(err) }

    fileBytes = bytes.TrimSuffix(fileBytes, []byte{'\n'})

    for line := range bytes.SplitSeq(fileBytes, []byte{'\n'}) {
        splitLine := bytes.Split(line, bytes.Repeat([]byte{' '}, 3))

        num1, _ := strconv.Atoi(string(splitLine[0]))
        num2, _ := strconv.Atoi(string(splitLine[1]))

        col1 = append(col1, num1)
        col2 = append(col2, num2)
    }

    return col1, col2
}

func Abs(num int) int {
    if num < 0 { return num * -1 }
    return num
}

func Part1(col1, col2 []int) int {
    slices.Sort(col1)
    slices.Sort(col2)
    soln := 0
    for i := range len(col1) { soln += Abs(col1[i] - col2[i]) }
    return soln
}

func Part2(col1, col2 []int) int {
    // Could've done this with a frequency map, again, but let's keep the solution as close as possible to the Monkey version.
    slices.Sort(col2)

    soln := 0
    for _, num1 := range col1 {
        count := 0
        for _, num2 := range col2 {
            if num1 < num2 { break }
            if num1 != num2 { continue }
            count++
        }
        soln += num1 * count
    }

    return soln
}

Notice that the Go solution doesn't compromise by avoiding for loops in favor of recursion to try and close the gap to the Monkey solution. The one adjustment I made is in Part2, where I sort col2 and do a linear scan instead of using a hash map - this keeps the algorithm closer to Monkey's approach.

Raw time comparison: Monkey vs Go solutions

You can check out the benchmark test file at bench_test.go.

Using the 1000-line input file, we use the following command to run our benchmark:

$ go test -bench=. -benchtime=10s

The -benchtime flag allows us to set the duration of the benchmark, how long each benchmark should run.

Output:

goos: linux
goarch: amd64
pkg: github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark
cpu: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
BenchmarkGoDay1Part1-8     12189     1032764 ns/op     121160 B/op     2029 allocs/op
BenchmarkGoDay1Part2-8      6582     1965238 ns/op     121160 B/op     2029 allocs/op
BenchmarkMonkeyDay1Part1-8   273     46781362 ns/op    19007745 B/op   55037 allocs/op
BenchmarkMonkeyDay1Part2-8     5     2317095265 ns/op  243211913 B/op  4325964 allocs/op
PASS
ok      github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark  49.902s

Reading the Benchmark Output

Before diving into the profiling data, let's establish a baseline. Below is the raw output from running the benchmarks. Each row represents one benchmark, and the columns break down the performance per operation:

• Benchmark Name & GOMAXPROCS: The name of the benchmark, followed by the number of CPUs available to the Go runtime (e.g., -8 means 8 logical CPUs).
• Iterations: The number of times the benchmark loop ran during the test duration.
• ns/op: The average execution time per operation in nanoseconds. This is the primary measure of speed.
• B/op: The average number of bytes allocated per operation. This measures memory pressure.
• allocs/op: The average number of distinct memory allocations per operation. This is the key metric for understanding GC pressure.

A quick look at the numbers and code complexity

The following is the comparison for bench time of 10 seconds. Part One:

What could be causing such a stark difference, especially in memory usage and allocations? Let's take a closer look at the Monkey solution and look for hints.

Let's start with prep function since it's common to both part one and two.

let content = trimSuffix(readFile("input.txt"), "\n");
let lines = splitString(content, "\n"); // array of strings

let prep = fn(i) {
    if (i==len(lines)){
        return {
            "colOne": [],
            "colTwo": [],
        };
    }

    let res = prep(i+1);

    let splitLine = splitString(lines[i], "   ");
    return {
        "colOne": push(res["colOne"], atoi(splitLine[0])),
        "colTwo":push(res["colTwo"], atoi(splitLine[1])),
    };
}

let res = prep(0);

The function is called with an argument of 0 and recursively calls itself until the base case is hit. At the base case we return a new hash literal and then the call stack unwinds, this is where all the work is done.

splitString creates a new array for each line, in our case 1000 times. The function then returns a new hash literal with two keys where for each key a push function is called, which is not cheap since it copies the array, time complexity of O(n). The push function makes our prep function have a time and space complexity of O(n^2), compared to O(n) time complexity of the Go version. This is also the main suspect for the high memory allocation because of the n (count of lines) number of new hash literal creations.

After getting the two columns we do sorting in both cases, which has the time complexity of O(nlog(n)) leaving prep with O(n^2) to still be our bottleneck.

Coming to the actual solutions, part one is a linear recursive function that only does math. The space complexity would also be linear because of the call stack. Part two on the other hand has O(n^2) time and space complexity.

We can get an idea of what the performance bottlenecks are from looking at the code alone and doing time and space complexity analysis. But we must do profiling to really know where all the CPU time is spent and what causes the massive memory allocations. Is our algorithm too slow and inefficient or is the Monkey interpreter itself too much of an overhead?

We do CPU and Memory profiling in the following section. Our goal is to only investigate, not optimize the solutions or the Interpreter.

CPU Profiling to know where Monkey is CHOKING

The benchmark function we use to profile our solution lives in at bench_test.go. We'll only benchmark the Monkey solution to part two since it's the most glaring when it comes to raw execution time and memory allocation numbers.

We will use the following command to produce a CPU profile file:

$ go test -bench=BenchmarkMonkeyDay1Part2 -benchtime=10s -cpuprofile /tmp/cpu.out

Outputs the following and creates a CPU profile file at /tmp/cpu.out:

goos: linux
goarch: amd64
pkg: github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark
cpu: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
BenchmarkMonkeyDay1Part2-8   5   2548156523 ns/op   243326184 B/op   4325995 allocs/op
PASS
ok      github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark      13.110s

We can use the following command to see the results in our browser:

$ go tool pprof -http=:8080 /tmp/cpu.out

This is what the Flame Graph looks like:

• X-axis: the total sample count (which represents CPU time). The width of a block is proportional to how much CPU time it consumed.
• Y-axis: the call stack (depth).

As expected most of our time is spent evaluating the source code:

• evaluator.Eval: 7.33 s, 51.4%
• evaluator.applyFunction: 2.54 s, 17.8%
• evaluator.evalBlockStatement: 2.03 s, 14.2%

But these only account for 83.4% of the time spent, where is the rest?

The rest of the time is when the GC runs in a separate goroutine, functions such as runtime.gcBgMarkWorker, runtime.bgsweep etc. We're using up so much memory that 20% of our program's run time is the GC doing work.

Note: The CPU profiler is a sampling tool that runs for the duration of the benchmark and captures all code that executes during that window, including setup. Our b.ResetTimer() only affects the ns/op and allocs/op numbers (as we'll see in the Heap Profiling), not the profile's sampling window.

Now let's take a look at the Flat views of the functions/nodes called.

1. The Flat View ("Where is the CPU?")

Flat% is the percentage of total CPU time spent directly inside the function itself.

Command:

# Show only the top 20 functions sorted by flat time
$ go tool pprof -top -flat -nodecount=20 /tmp/cpu.out

Output:

File: benchmark.test
Build ID: f8e079acc9de3bb17d615a24edff6fbc81f4736f
Type: cpu
Time: 2026-10-08 11:19:36 EAT
Duration: 12.75s, Total samples = 14270ms (111.93%)
Showing nodes accounting for 8460ms, 59.29% of 14270ms total
Dropped 201 nodes (cum <= 71.35ms)
Showing top 20 nodes out of 129
      flat  flat%   sum%        cum   cum%
    2090ms 14.65% 14.65%    11910ms 83.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
     870ms  6.10% 20.74%      870ms  6.10%  aeshashbody
     740ms  5.19% 25.93%     1810ms 12.68%  internal/runtime/maps.(*Map).getWithoutKeySmallFastStr
     450ms  3.15% 29.08%     2850ms 19.97%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Get
     450ms  3.15% 32.24%     2370ms 16.61%  runtime.mapaccess2_faststr
     360ms  2.52% 34.76%      360ms  2.52%  runtime.nextFreeFast (inline)
     330ms  2.31% 37.07%      360ms  2.52%  runtime.tryDeferToSpanScan
     310ms  2.17% 39.24%     1810ms 12.68%  runtime.mallocgcSmallScanNoHeader
     300ms  2.10% 41.35%    11900ms 83.39%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalBlockStatement
     290ms  2.03% 43.38%     2920ms 20.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalExpressions
     290ms  2.03% 45.41%     3310ms 23.20%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIdentifier
     280ms  1.96% 47.37%      280ms  1.96%  runtime.memclrNoHeapPointers
     230ms  1.61% 48.98%      550ms  3.85%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalInfixExpression
     230ms  1.61% 50.60%      230ms  1.61%  runtime.memmove
     220ms  1.54% 52.14%      220ms  1.54%  runtime.procyieldAsm
     210ms  1.47% 53.61%      390ms  2.73%  github.com/SegniAT/monkey-language-interpreter/evaluator.isError (inline)
     210ms  1.47% 55.08%      210ms  1.47%  memeqbody
     210ms  1.47% 56.55%      270ms  1.89%  runtime.(*mspan).writeHeapBitsSmall
     210ms  1.47% 58.02%     2850ms 19.97%  runtime.mallocgc
     180ms  1.26% 59.29%      290ms  2.03%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIntegerInfixExpression

Look at the top of the Flat output:

• 14.65% : github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
• 6.10% : aeshashbody
• 5.19% : internal/runtime/maps.(*Map).getWithoutKeySmallFastStr
• 3.15% : github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Get
• 3.15% : runtime.mapaccess2_faststr

The single biggest cost is the evaluator.Eval function itself, this is expected since we are bound to have a very high count of recursive calls to it and we spend considerable time inside that function even though it involves just a big switch statement.

But if we look closely at the next four entries, they are all related to map look-ups.

• aeshashbody is the CPU instruction Go uses to hash strings for map keys. It is eating 6.1% of our entire CPU time. The reason is the Monkey interpreter resolves variables by looking up strings (like i, lines, colOne) in a map[string]object.Object.
• Then, look at the memory functions: nextFreeFast, mallocgcSmallScanNoHeader, memclrNoHeapPointers, memmove. They collectively account for another ~7% of flat CPU time.

The CPU is spending a lot of time hashing strings for variable look-ups and frantically moving memory around for allocations.

2. The Cumulative View ("Why is it slow?")

Cum% is the percentage of total CPU time spent in the function plus all functions it called.

Command:

# Show only the top 20 functions sorted by cumulative time
$ go tool pprof -top -cum -nodecount=20 /tmp/cpu.out

Output:

File: benchmark.test
Build ID: f8e079acc9de3bb17d615a24edff6fbc81f4736f
Type: cpu
Time: 2026-10-08 11:19:36 EAT
Duration: 12.75s, Total samples = 14.27s (111.93%)
Showing nodes accounting for 5.84s, 40.93% of 14.27s total
Dropped 201 nodes (cum <= 0.07s)
Showing top 20 nodes out of 129
      flat  flat%   sum%        cum   cum%
     2.09s 14.65% 14.65%     11.91s 83.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
     0.09s  0.63% 15.28%     11.91
s 83.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.applyFunction
     0.30s  2.10% 17.38%     11.90s 83.39%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalBlockStatement
     0.14s  0.98% 18.36%      6.02s 42.19%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIfExpression
     0.29s  2.03% 20.39%      3.31s 23.20%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIdentifier
     0.29s  2.03% 22.42%      2.92s 20.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalExpressions
     0.45s  3.15% 25.58%      2.85s 19.97%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Get
     0.21s  1.47% 27.05%      2.85s 19.97%  runtime.mallocgc
         0     0% 27.05%      2.79s 19.55%  runtime.systemstack
     0.45s  3.15% 30.20%      2.37s 16.61%  runtime.mapaccess2_faststr
     0.11s  0.77% 30.97%      2.07s 14.51%  github.com/SegniAT/monkey-language-interpreter/evaluator.extendFunctionEnv (inline)
     0.74s  5.19% 36.16%      1.81s 12.68%  internal/runtime/maps.(*Map).getWithoutKeySmallFastStr
     0.31s  2.17% 38.33%      1.81s 12.68%  runtime.mallocgcSmallScanNoHeader
         0     0% 38.33%      1.75s 12.26%  runtime.gcBgMarkWorker
         0     0% 38.33%      1.67s 11.70%  runtime.gcBgMarkWorker.func2
     0.03s  0.21% 38.54%      1.67s 11.70%  runtime.gcDrain
     0.09s  0.63% 39.17%      1.49s 10.44%  runtime.newobject
     0.09s  0.63% 39.80%      1.47s 10.30%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Set (inline)
     0.16s  1.12% 40.93%      1.37s  9.60%  runtime.mapassign_faststr
         0     0% 40.93%      0.93s  6.52%  runtime.gcDrainMarkWorkerDedicated (inline)

Look at these three numbers:

• 83.46% - evaluator.Eval: This is expected since the entire program runs inside this recursive function.
• 42.19% - evaluator.evalIfExpression: This is pretty huge. Nearly half of your interpreter's total execution time is spent evaluating if expressions. In Monkey, if is used for base cases and control flow. Every recursive call (prep(i+1), partTwo(i+1), countNumInArray(...)) hits an if check. Millions of conditional jumps are being evaluated as AST nodes rather than machine instructions like in compiled languages such as Go.
• 23.20% - evaluator.evalIdentifier: Almost a quarter of all time is spent just finding variables. This calls Environment.Get 19.97%), which does a map lookup.

Look at runtime.mallocgc 19.97%) and runtime.gcBgMarkWorker 12.26%). GC background workers alone account for ~20%; adding the allocator brings total memory-management CPU to ~32%.

Where are all the allocations and garbage coming from?

• extendFunctionEnv 14.51%): Every function call creates a new enclosed environment.
• object.(*Environment).Set 10.30%): Every variable declaration or assignment updates a map.
• NewEnclosedEnvironment: Creating a map for every single recursive call.

The interpreter is spending 32% of its time cleaning up the memory it allocated. This is because every recursive call creates a brand new environment map.

Heap Profiling for confirmation

Just from CPU Profiling above we were able to figure out that the GC is doing a lot of work and we were able to deduce the exact reason there's so much garbage for the GC to collect: mainly creating a new environment on each function call. Now let's confirm this with Heap Profiling.

We use the -memprofile flag to create the Heap Profile file.

Command:

$ go test -bench=BenchmarkMonkeyDay1Part2 -benchtime=10s -memprofile /tmp/mem.out

Output:

goos: linux
goarch: amd64
pkg: github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark
cpu: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
BenchmarkMonkeyDay1Part2-8  4  2540705147 ns/op  243217254 B/op   4325988 allocs/op
PASS
ok      github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark      10.508s

We can use the following command to see the results in our browser:

$ go tool pprof -http=:8080 /tmp/mem.out

We can take a look at the Flame Graph with sampling set to alloc_objects under SAMPLE since the GC deals with objects.

• X-axis: the total allocated objects. The width of a block is proportional to how many objects are allocated.
• Y-axis: the call stack (depth).

The following are the functions that account for ~99% of the object allocations:

1. 84.4% - evaluator.Eval
2. 7.7% - evaluator.evalBlockStatement
3. 6.5% - evaluator.applyFunction

These are expected, let's scroll down and take a look at the rest of the graph:

The suspects from the CPU profile - NewEnclosedEnvironment and Environment.Set - are back at the top of the alloc list. Let's see their numbers more closely below.

1. The Flat View (The Smoking Guns)

Flat% tells us who is doing the allocating directly. This points the finger at the exact function and line of code. This is our "smoking gun."

Command:

$ go tool pprof -top -flat -sample_index=alloc_objects -nodecount=20 /tmp/mem.out

Output:

File: benchmark.test
Build ID: f8e079acc9de3bb17d615a24edff6fbc81f4736f
Type: alloc_objects
Time: 2026-10-08 14:27:14 EAT
Showing nodes accounting for 15357595, 99.41% of 15448453 total
Dropped 29 nodes (cum <= 77242)
      flat  flat%   sum%        cum   cum%
   4150735 26.87% 26.87%    4150735 26.87%  github.com/SegniAT/monkey-language-interpreter/object.NewEnvironment (inline)
   4104337 26.57% 53.44%    6267057 40.57%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalExpressions
   2981932 19.30% 72.74%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
   1922917 12.45% 85.19%    1922917 12.45%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Set (inline)
   1114129  7.21% 92.40%    1114129  7.21%  github.com/SegniAT/monkey-language-interpreter/evaluator.init.func1
   1081360  7.00% 99.40%    1081360  7.00%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIntegerInfixExpression
      2185 0.014% 99.41%     136747  0.89%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalHashLiteral
         0     0% 99.41%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.applyFunction
         0     0% 99.41%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalBlockStatement
         0     0% 99.41%    3309618 21.42%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIfExpression
         0     0% 99.41%    1081360  7.00%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalInfixExpression
         0     0% 99.41%    6073652 39.32%  github.com/SegniAT/monkey-language-interpreter/evaluator.extendFunctionEnv (inline)
         0     0% 99.41%    4150735 26.87%  github.com/SegniAT/monkey-language-interpreter/object.NewEnclosedEnvironment (inline)

Sorting by flat% shows the top functions physically calling mallocgc:

1. 26.87% - object.NewEnvironment: 4.15 million objects!
2. 26.57% - evalExpressions: 4.10 million objects!
3. 12.45% - Environment.Set: 1.92 million objects!
4. 7.21% - init.func1: 1.11 million objects!
5. 7.00% - evalIntegerInfixExpression: 1.08 million objects!

• NewEnvironment is creating a new map for every single recursive function call. Because Part 2 has an O(n^2) algorithm, it calls functions millions of times creating millions of maps.
• evalExpressions is allocating a slice every time it evaluates a list of arguments (like function arguments or array literal elements).
• Environment.Set is allocating an object every time a variable is declared (like let res = ...).
• init.func1 is a builtin function - almost certainly Monkey's push function allocating a new array on every single call. It's named func1 since it's an anonymous closure. It's under init since we defined builtins map globally.

2. The Cumulative View (The General Trend)

Cum% tells us the total cost of a subsystem. It shows you how individual allocations roll up into a massive total. This is the "macro trend."

Command:

$ go tool pprof -top -cum -sample_index=alloc_objects -nodecount=20 /tmp/mem.out

Output:

File: benchmark.test
Build ID: f8e079acc9de3bb17d615a24edff6fbc81f4736f
Type: alloc_objects
Time: 2026-10-08 14:27:14 EAT
Showing nodes accounting for 15357595, 99.41% of 15448453 total
Dropped 29 nodes (cum <= 77242)
      flat  flat%   sum%        cum   cum%
   2981932 19.30% 19.30%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
         0     0% 19.30%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.applyFunction
         0     0% 19.30%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalBlockStatement
   4104337 26.57% 45.87%    6267057 40.57%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalExpressions
         0     0% 45.87%    6073652 39.32%  github.com/SegniAT/monkey-language-interpreter/evaluator.extendFunctionEnv (inline)
         0     0% 45.87%    4150735 26.87%  github.com/SegniAT/monkey-language-interpreter/object.NewEnclosedEnvironment (inline)
   4150735 26.87% 72.74%    4150735 26.87%  github.com/SegniAT/monkey-language-interpreter/object.NewEnvironment (inline)
         0     0% 72.74%    3309618 21.42%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIfExpression
   1922917 12.45% 85.19%    1922917 12.45%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Set (inline)
   1114129  7.21% 92.40%    1114129  7.21%  github.com/SegniAT/monkey-language-interpreter/evaluator.init.func1
         0     0% 92.40%    1081360  7.00%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalInfixExpression
   1081360  7.00% 99.40%    1081360  7.00%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIntegerInfixExpression
      2185 0.014% 99.41%     136747  0.89%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalHashLiteral

Sorting by cum% shows the subsystems responsible:

• 40.57% - evalExpressions: 6.26 million objects!
• 39.32% - extendFunctionEnv: 6.07 million objects!
• 26.87% - NewEnclosedEnvironment: 4.15 million objects!
• 21.42% - evalIfExpression: 3.30 million objects!

Nearly 40% of all object allocations in the entire program come from one place: extendFunctionEnv. This is the function that sets up the environment for a new function call. Because our Part 2 algorithm is heavily recursive, this function is called millions of times and every call creates a new environment map.

Diagnosis: Interpreter Overhead vs. Language Design

Interpreter overhead: ~83% of time is spent in Eval + applyFunction + evalBlockStatement. That's the cost of the AST tree-walking nature of the interpreter itself.

Environment churn: ~39% of all allocations come from extendFunctionEnv. That's a design choice of the interpreter: creating a fresh Environment per call.

Language design: The lack of loops forces O(n) recursion depth, which means O(n) environments. The lack of mutable arrays turns push into O(n) copying.

Verdict: It's both. The CPU profile shows the interpreter's tree-walking overhead dominates execution time (~83% in Eval). But the memory gap is a different story - the 2000x difference is driven by the language's design (no loops, immutable arrays) being amplified by the O(n^2) algorithm. The interpreter overhead is the cost of running any Monkey program; the language design is what makes this specific program catastrophic.

Conclusion

Even though we had to make a few improvements to the interpreter, like adding builtin functions which could be considered cheating, and fixing tricky bugs we were able to achieve our goal of solving an AoC problem with Monkey. We were able to navigate Monkey's limitations such as missing loop primitives and variable re-assignments to solve the two-part problem.

We were able to accomplish our initial goal but there's a noticable performance problem we had discovered. Our Monkey solutions were 46x and 1,219x slower compared to their Go counterpart for part one and two of the AoC problem respectively.

To know the exact reason why there's such big contrast between the two languages, we had to do CPU and Heap profiling. The story these profiling results told were that there's a huge memory/heap overhead (lots of allocations) and the CPU spends a lot of time allocating and cleaning up all the garbage. Due to the nature of our interpreter (AST tree-walker) and lack of loop primitives forcing us to resort to recursive Monkey function calls, it led to deep call stacks and millions of new environment creations per function call.

Adding native builtins is how every production interpreter handles I/O and performance-critical paths - it's not cheating, it's the standard extension mechanism. But it does mean part of the answer comes from Go, not from Monkey.

Monkey is barely capable on its own even for simple AoC problems let alone real problems. Yet it was more capable than I thought when I began this series creating a Tree-sitter highlighting and a Language Server after that. Capability is one thing but programs running at a reasonable efficiency is another, and Monkey is far from efficient.

This shouldn't stop us from sitting back and appreciating what we have built. To conclude this 3-part series, I'll leave you with a quote from a wise king:

The end of a thing is better than its beginning; The patient in spirit is better than the proud in spirit. Ecclesiastes 7:8