how a four-line change made a compiler check 137x faster
contents
I first heard about Bend while scrolling through Twitter, where I came across poteto hyping it up for its core idea of making AI verify its own work. After building many, many applications with AI and getting back code that was lowkey straight trash, the idea immediately resonated with me. I wanted to be able to describe what I wanted to build and trust that the result actually matched my intentions, without having to manually verify every little thing myself. That's what got me interested in Bend.
As I started exploring the codebase, I became curious about the systems that make this kind of verification possible. I had no idea where to start, but performance optimization was something that excited me. I liked the idea of taking an existing system, figuring out what was slowing it down, and seeing how much faster I could make it.
That's what led me to an issue in Bend's type checker, where a seemingly small implementation detail was causing a surprising amount of unnecessary work.
The Problem
While looking through Bend's open issues I came across a performance problem in its type checker.
A type checker is responsible for making sure a program follows a language's rules. In a typical programming language design this might mean catching mistakes like assigning a string to a variable that expects a number, or passing the wrong type of argument to a function.
Bend takes this a step further with a more expressive type system that can represent and check mathematical properties of programs. Meaning rather than checking whether a value is a number, its type system can express constraints on what the value must satisfy.
To perform these checks, the compiler needs to compare types and determine whether they're compatible. Some of these comparisons involve recursively breaking complex expressions into smaller pieces.
This is where the performance problem I encountered came from.
Understanding Quantity Comparisons
Before I could understand what was slowing down the type checker, I needed to understand what it was actually comparing.
Bend has a quantity system that describes how values can be used within a program. These constraints are part of the rules that allow Bend to express and verify mathematical properties of programs.
One of the operators in this system is called a meet, represented by the <&> operator.
For example, consider two quantities, q and r:
q <&> r
A meet combines larger quantities into a larger expression. What's important is how the type checker compares these expressions.
Suppose we want to check whether:
(q <&> r) fits (r <&> q)
The type checker needs to determine whether the quantities on the left satisfy the quantities on the right.
Rather than comparing the expression at once, the checker breaks it into small comparisons.
There are two important rules:
When a meet appears on the left, both branches must satisfy the comparison
(q <&> r) fits x
= (q fits x) AND (r fits x)
When a meet appears on the right, at least one of the branches must satisfy the comparison
q fits (r <&> q)
= (q fits r) OR (q fits q)
These rules are implemented recursively. Whenever the checker encounters a meet, it calls the same comparison function again with smaller pieces of the expression.
Eventually, it reaches expressions simple enough to compare directly.
Let's go back to the second example:
q fits (r <&> q)
The checker first asks if q fits r. If that fails, it then moves on to see if q fits q, which succeeds.
At this point we know now that the overall comparison succeeds and there's no reason to check anything else.
But now what happens if the matching quantity appears in the beginning of a much larger expression?
q fits (q <&> r <&> s <&> t)
The natural idea to assume is that if the checker finds a match, it should stop immediately.
The problem was that the original implementation didn't always do that, even after finding a match it would continue evaluating other branches of the recursive comparison.
This might not seem as expensive with only a handful of quantities, but as expressions grew larger, those unnecessary recursive calls began to add up. This was the source of the performance issue I wanted to investigate.
Finding the Bottleneck
Now that I had a better understanding of how Bend compared quantities, I wanted to figure out why they took so long.
The relevant logic lived in a recursive function called compare_go, which the type checker uses to determine whether two expressions satisfy a particular comparison.
When the function encounters a meet (<&>), it breaks the expression down into smaller pieces and calls itself to compare them.
Here's a simplified version:
if (g.$ === "Min") {
const fa = compare_go("LE", book, Typ(g.a), b, dep);
const fb = compare_go("LE", book, Typ(g.b), b, dep);
return fa && fb;
}
if (h.$ === "Min") {
const fa = compare_go("LE", book, a, Typ(h.a), dep);
const fb = compare_go("LE", book, a, Typ(h.b), dep);
return fa || fb;
}
Nothing looks crazy out of place from this block of code. It represents what we covered earlier where if the meet is on the left, both branches must succeed and when it's on the right, at least one of them needs to succeed.
But if we look closer we can see the problem. Both recursive calls are executed before the function checks whether their results are needed. If we look back at the second condition:
if (h.$ === "Min") {
const fa = compare_go("LE", book, a, Typ(h.a), dep);
const fb = compare_go("LE", book, a, Typ(h.b), dep);
return fa || fb;
}
Since fa and fb are assigned separately, both of these functions are evaluated before reaching the return statement.
Going back to our first example:
q fits (q <&> r)
The checker first compares q with q and finds a match. Since the comparison uses OR, that's already enough to stop and determine that the comparison succeeds.
However the original implementation still compares q with r even after it was established that the match was found, and the compiler performs it anyway.
The same problem exists with AND comparisons. If the first branch returns false, the overall comparison must be false, regardless of what the second branch returns. Yet the original implementation still evaluates both.
This may seem minor, but each recursive call can trigger even more recursive calls.
For a large meet expression, checking one unnecessary branch might involve going down a whole other subtree of additional comparisons. So the more quantities involved, the more unneeded work that the checker would perform.
There was also another source of cost. Before comparing certain expressions, the checker uses a function called term_wnf to evaluate them just enough to reveal their structure.
For example, an expression might refer to another definition and the checker needs to evaluate that reference to discover that it represents a meet.
So each additional recursive comparison can also involve not only more comparisons but also evaluation work. This helps explain why the performance problem became so significant as the number of quantities increased.
The issue wasn't that the compiler was applying the wrong comparison rules. It was doing more work than those rules required.
The Fix: Short-Circuiting Recursive Comparisons
Once I figured out where the unnecessary work was coming from the fix was surprisingly small.
The problem wasn't with the comparison rules themselves. The type checker was correctly using AND and OR to combine the results of the recursive comparisons. The issue was that it did the extra work of evaluating both branches before checking whether or not the second result was needed.
Thankfully, JavaScript already provides a way to avoid this through short-circuit evaluation.
When using && (AND), JavaScript immediately stops evaluating as soon as it encounters false, since the entire expression must be false.
Similarly when using || (OR), JavaScript again stops evaluating as soon as it encounters true since the entire expression must be true.
Instead of assigning both recursive results to variables, I changed the code to return the comparisons directly.
if (g.$ === "Min") {
return compare_go("LE", book, Typ(g.a), b, dep)
&& compare_go("LE", book, Typ(g.b), b, dep);
}
if (h.$ === "Min") {
return compare_go("LE", book, a, Typ(h.a), dep)
|| compare_go("LE", book, a, Typ(h.b), dep);
}
That's literally the entire optimization which is kind of crazy given how much it was able to run much more efficiently.
Now, when the first branch of an AND comparison returns false, the checker skips the second branch. When the first branch of an OR comparison returns true, it does the same.
Going back to our first example:
q fits (q <&> r)
Previously the checker evaluated both comparisons:
q fits q → true
q fits r → false
true OR false → true
After the change it only needs the first:
q fits q → true
Result: true
The second comparison is now never executed.
This becomes particularly valuable when the skipped branch contains additional meet expressions. Avoiding one recursive call can also eliminate all the recursive comparisons and evaluations that would have happened beneath it.
Preserving Correctness
Before considering the optimization safe I needed to think about if skipping this recursive comparison changes anything else besides the amount of work performed.
In a simple boolean expression, the change obviously seemed safe. However in a compiler functions can do much more than return true or false. For example, a comparison function might update internal state, report errors, or resolve constraints that other parts of the type checker depend on.
If the second recursive call performed any important work like that, skipping it could introduce a whole wave of bugs.
So it was important to understand what happened inside both the comparison function and the evaluator when it is called.
I discovered that the skipped comparisons did not need to execute to produce diagnostics or solve constraints. The relevant state changes were related to caching, rather than required results of the comparison.
This means the checker could safely avoid evaluating branches once their results could no longer affect the outcome.
The comparison rules remained unchanged. The type checker still accepted and rejected the same expressions, but it no longer performed unnecessary recursive work to reach those decisions.
And although the code change was only a few lines, the performance improvement was much larger than I initially expected.
Measuring the Improvement
With the optimization in place, I wanted to understand just how much unnecessary work the type checker had been doing.
To measure this, I compared the original implementation against the optimized version using increasingly large quantity expressions.
Rather than testing a single input, I looked at how the number of recursive comparisons changed as the number of quantities increased.
The results were pretty surprising.
Counting Recursive Comparisons
| Number of quantities | Before | After |
|---|---|---|
| 8 | 228 | 80 |
| 16 | 836 | 156 |
| 32 | 3,204 | 308 |
| 64 | 12,548 | 612 |
It was pretty crazy to see how differently the two implementations scaled.
Before optimization, doubling the number of quantities caused the comparison count to grow by roughly four times.
After the optimization doubling the number of quantities caused the comparison count to grow by roughly two times.
This is the difference between linear and quadratic growth.
Understanding the Time Complexity
In computer science, we use Big O notation to describe how the amount of work an algorithm performs grows as its input becomes larger.
For example:
- O(n), or linear growth, means doubling the input roughly doubles the work.
- O(n²), or quadratic growth, means doubling the input roughly quadruples the work.
- O(n³), or cubic growth, means doubling the input can increase the work by roughly eight times.
In the benchmark I was investigating, the original implementation exhibited quadratic growth in recursive comparisons.
The reason was that the checker could search through an entire meet expression for each quantity being compared, even after finding a match.
If there were n quantities on the left and n on the right, this could result in roughly n × n comparisons.
After introducing short-circuiting, the checker could stop searching as soon as it found a match.
For the tested input family, this reduced the comparison count from O(n²) to O(n).
It's important to distinguish this from the worst-case complexity. If a match appears at the very end of every search, the checker may still need to examine every branch. The optimization improves cases where the result can be determined early; it doesn't eliminate every possible expensive comparison.
The Cost of Evaluation
There was another important detail I hadn't initially considered.
The checker wasn't just performing recursive comparisons. It was also evaluating expressions to understand their structure.
Bend uses a function called term_wnf, which evaluates an expression into a weak normal form. In simpler terms, it evaluates an expression just enough for the compiler to determine what kind of expression it's looking at.
For example, if an expression refers to another definition, the checker may need to evaluate that reference before discovering that it contains a meet.
This matters because each recursive comparison can trigger additional evaluation work.
In the original implementation, repeatedly traversing meet expressions meant the checker could also repeatedly evaluate portions of those expressions.
For the benchmarked input family, the combination of recursive comparisons and evaluation resulted in O(n³) evaluator work.
After the optimization, unnecessary recursive branches were skipped, reducing that work to O(n²).
The checker still needed to evaluate expressions, but it was no longer evaluating branches whose results couldn't change the answer.
Measuring Execution Time
The reduction in recursive work translated into a substantial improvement in actual execution time.
For a benchmark containing 1,024 quantity variables, the results were:
| Implementation | Execution time |
|---|---|
| Before optimization | 16.5 seconds |
| After optimization | 0.12 seconds |
That's approximately a 137× speedup, or a 99.3% reduction in execution time for that particular benchmark.
What I found especially interesting was that the optimization didn't require a new algorithm, a cache, or a major rewrite of the type checker.
It came down to recognizing that the existing algorithm was continuing to perform work after it already knew the answer.
By allowing the recursive comparisons to stop early, the compiler avoided entire branches of unnecessary computation.
The improvement also reinforced something important for me: performance problems aren't always caused by complicated algorithms. Sometimes they're caused by simple implementation decisions whose costs multiply as the input grows.
What I Learned
Going into this contribution, I didn't know much about Bend's type checker, let alone how its quantity comparisons worked.
One of my biggest takeaways was that correct code isn't necessarily efficient code.
The original implementation wasn't producing incorrect results. It was following the comparison rules exactly as intended. The problem was that it continued doing work even when that work could no longer change the outcome.
Understanding that distinction changed how I thought about optimization. Rather than immediately looking for faster algorithms or more sophisticated techniques, I started thinking about a simpler question: Is all of this work actually necessary?
I also learned how important it is to measure a problem instead of relying on intuition.
Looking at the original implementation, I wouldn't have expected literally four lines to make such a significant difference. But by examining how the number of comparisons grew with the input size, I could see how the unnecessary work accumulated.
The benchmarks helped connect what I was seeing in the code to the actual performance of the compiler.
Another important lesson was that an optimization is only useful if it preserves correctness.
Short-circuiting the comparisons seemed straightforward, but skipping a function call in a compiler isn't necessarily harmless. I needed to understand whether those calls performed other important work, such as updating state, reporting errors, or resolving constraints.
That investigation helped me appreciate why understanding the surrounding system matters just as much as understanding the code you're changing.