Optimisations

The compiler improves a program after it has checked it and before it writes JavaScript. The part that does this is the optimiser, and every change it makes is a named pass. This page lists every pass under that name. --no-optimise turns the optimiser off, and --without-optimisation turns one pass off. A build that behaves differently with the optimiser off has hit a compiler bug, and turning passes off one at a time names the pass responsible. After the passes, the page lists the shapes the compiler emits and the improvements to the runtime, the support code every build includes. No flag turns those off.

implementation {
	constant secondsPerDay = 60::multiply(with 60)::multiply(with 24)

	Terminal.print(secondsPerDay) § 86400
}

Save it as Day.es and build it three ways:

essence build Day.es                                        # every pass on
essence build Day.es --without-optimisation fold-constants  # one pass off
essence build Day.es --no-optimise                          # no pass at all

The program prints 86400 every time. What changes is the JavaScript. With every pass on, fold-constants works the product out while compiling, and the program holds the result:

const $pool_0 = Integer.createInteger(86400);
…
const secondsPerDay = $pool_0;

With fold-constants off, the multiplication happens when the program runs. With --no-optimise, the JavaScript makes the two calls the source wrote:

const secondsPerDay = PositiveInteger.multiply(PositiveInteger.multiply(Integer.createInteger(60), Integer.createInteger(60)), Integer.createInteger(24));

A positive Integer literal is proven positive, so 60::multiply(with 60) calls PositiveInteger’s multiply, not Integer’s.

A minifier does not do this work. essence build Day.es --no-optimise --minify still multiplies at run time, because every Essence value is an object built by a runtime call, and a minifier cannot see into those calls.

To read the JavaScript on this page:

• Every Essence value other than a function is a JavaScript object with a tag, a hidden key under $type.typeKeySymbol that names its kind, such as "Integer" or "Optional#Value". An Integer, a String or a Boolean holds its JavaScript value in value.
• $type and $helpers are parts of the runtime: $type builds and tests types, and $helpers holds shared operations such as equality.
• $pool_0, $pool_1 and so on are constants the compiler built once (see pool-constants). _self is a method’s receiver or the value a match is testing. Names that start with $loop_ or $match_ are the compiler’s own.
• … stands for code left out of a sample.

How the two flags are used:

• build, run, watch and test all take both. Using the compiler walks through the commands themselves.
• --without-optimisation takes the exact name a pass is listed under on this page. It is repeatable, and every pass you do not name keeps running.
• A project can set the same for every build in essence.json. build.optimise set to false turns the optimiser off, and build.withoutOptimisations lists passes to turn off.

A name that is not a pass is refused before anything compiles, and the command exits with code 2. When a pass name is close, the refusal suggests it:

  ✖ There is no optimisation pass named "collapse-constructions".
  Did you mean "essence build --without-optimisation collapse-construction"?

  Usage: essence build <file...> [options]
  Help:  essence help build

When no name is close, the refusal lists every pass instead.

The contract

Four rules hold for every pass. Because of them, turning a pass off isolates a bug.

Any subset of the passes produces a correct program. No pass depends on another having run. The passes cooperate: one leaves a shape the next can do more with. But each is written against the program as it reaches the optimiser, and each is correct whether or not its neighbours ran.

A pass never changes what a program does. It does not change what the program prints, what it computes, or which errors and warnings the compiler reports. The optimiser runs after the compiler has checked the program, so a program that compiles compiles the same way with every pass off. A pass changes only how much work a run does. The one exception is instrument-coverage, which adds work: it counts what runs, and only when a coverage run asks for it.

The standard library is optimised with your program. The methods it writes in Essence are emitted beside the code that reaches them. The same passes run over them, under the same options. --no-optimise turns the optimiser off for the whole build.

The order is fixed. The passes run in the order this page lists them. Turning one off never reorders the rest.

Debugging

essence dap builds every debug session with the optimiser off, and that is not configurable. A debugger steps through statements, stops on bindings and reads their values, and several passes remove exactly those. eliminate-dead-code drops a constant nothing reads, prune-dead-match-arms drops an arm no value reaches, fold-constants replaces an operation with its result, and inline-loops writes a loop out where it was called. Debugging covers the sessions themselves.

To find the pass behind a wrong result, build with --no-optimise first. If the program then behaves, one of the passes is responsible. Turn them off one at a time with --without-optimisation until the wrong result goes away. Two passes give up a check that names a compiler bug: elide-final-match-test and compile-union-dispatch. When a match or a method call on a union returns the wrong thing, turning those two off puts the check back.

Passes

The passes run in the order below, and each heading is the name --without-optimisation takes. Most sections show the JavaScript with the pass off and on. Each says why the change is safe and what the pass leaves alone.

Where a section gives a timing, it was measured on an Apple M3 Pro with Bun 1.4.2 and Node 24.21.0. Each program was built with every pass on, and again without the pass named. Each build ran twenty-two times in fresh processes on each engine. A figure is the fastest run, less the fastest run of a program that prints one line. Each measured program does little besides the work its pass changes, so its ratio is the ratio for that work alone. A program that spends its time elsewhere gains less.

instrument-coverage

Counts what ran, for essence test --coverage.

A coverage run of essence test compiles the project with this pass on, and every other compile finds it does nothing. It writes a counter in front of every statement you wrote other than a declaration, and one into each branch of an if and its else. It writes one into each arm of a define, one into each match arm, and one around each case a program constructs. Beside the counters it writes a table of where each one stands and what it counts. The test runtime holds the counts, and the test runner reports them.

It runs first so that its counts describe your source. A counter written before lower-matches-to-statements stands in the arm you wrote. One written after it would stand in a statement the compiler made up.

A later pass may remove code a counter stands in. fold-constants can fold a conditional whose condition is known, and prune-dead-match-arms drops an arm no value can reach. The counter’s entry stays in the table with a count of zero, and the report lists it as never taken.

--no-optimise --coverage still counts. Turning the optimiser off asks the compiler not to improve the program, and a coverage run with no counters would report nothing. --without-optimisation instrument-coverage does turn counting off. The standard library is never instrumented.

compile-type-tests

Decides a match arm’s type test by reading the value’s tag.

Every value carries a tag, a hidden key that names its kind: "Integer", "List", "Optional#Value". With this pass off, an arm such as case #Value(value) on an Optional<Integer> builds a type descriptor at the test and hands it to the runtime, which walks it:

if ($type.isValueOfType(_self, {
		type: "Case",
		choice: "Optional",
		name: "Value",
		members: { item: { type: "Integer" } },
		typeArguments: [{ type: "Integer" }]
	})) {

With the pass on, the tag decides:

if (_self[$type.typeKeySymbol] === "Optional#Value") {

For a list the difference is one of complexity. A List<Integer> descriptor means a list whose every item is an Integer, so the runtime check reads every item. With the pass off, a case List over ten thousand items makes ten thousand checks, on every turn of a loop that reaches it.

The tag is used only where the compiler can prove it decides the test. The value’s static type says which member types can reach the match. The tag is compiled in only where exactly one of them carries the tag in question, and that member passes the matcher’s check outright. Where two members share a tag, the full check stays. List<Alpha> and List<Beta> are both "List", and Box<Integer>#Holding and Box<String>#Holding are both "Box#Holding". A type parameter among the members keeps the full check too, because a value of one can be anything.

Records. A record’s tag says only that the value is a record. That still decides the test where exactly one member of the union is a record and it passes the matcher. So case Point on a Point | String, where Point is { x: Integer, y: Integer }, compiles to one comparison:

if (_self[$type.typeKeySymbol] === "Record") {

Two records in one union both carry that tag, so their members decide. That is compile-record-members, further down.

A counted loop that does nothing but match a record against { x: Integer, y: Integer } | String | Integer ten million times runs over 20× faster with this pass, on both Bun and Node.

Literal matchers. A literal matcher such as case 0 or case "beta" has no type test to replace, because the comparison is its test. With the pass off it calls the runtime’s structural equality, $helpers.anyIs(_self, $pool_1). Where the matched value’s type and the literal are exactly one scalar kind, the pass writes the comparison instead:

if (_self.value === $pool_1.value) {         // case 0, on an Integer
if ($helpers.stringEquals(_self, $pool_4)) { // case "beta", on a String

$pool_1 and $pool_4 are the pooled literals 0 and "beta". Integer equality is === on the held value, because one Integer has exactly one representation (see hybrid-integers). Strings go through stringEquals, because two strings are equal when their normalised (NFC) forms are, whichever code points spell them. A value whose type is a union keeps anyIs, since a value of any member may arrive. So does every other literal kind: a case, a record or a list literal.

Guards and member literals are joined onto whichever test the matcher produced, so they keep their meaning.

lower-unit-case-equality

Compares a value with a payload-less case by reading its tag.

With this pass off, a::compare(to b)::is(#Less) calls the runtime’s choiceIs, which compares the two values structurally. With it on, the tag is read:

return Integer.compare(a, b)[$type.typeKeySymbol] === "Ordering#Less" ? Boolean.trueInstance : Boolean.falseInstance;

isNot asks !== instead of negating the result. Either side may be the case: #Less::is(ordering) compiles to the same comparison.

This is safe because a choice’s derived equality decides a case by its tag, and then compares payload members the way a record’s equality does. A case with no members has nothing more to compare, so the tag is the whole result. A generic choice compares through a descriptor that lists, for each tag, the payload members to compare. The pass reads that descriptor, and leaves the comparison to the runtime where it lists members for the tag.

Only equality a choice derives is lowered. A namespace that writes its own is is called as written.

The pass also runs inside the standard library, where it matters most. Comparable writes isLessThan as @::compare(to other)::is(Ordering#Less) and isGreaterThan the same way with #Greater, so those comparisons end in this shape.

lower-scalar-operations

Writes primitive operations out where they are called.

With this pass off, a::isLessThan(b) on two Integers calls a method, which calls Integer.compare and compares the result with #Less. The two values already hold what one < decides, so the pass writes that:

return a.value < b.value ? Boolean.trueInstance : Boolean.falseInstance;

These calls are lowered, and nothing else:

• Integer, where the receiver and the argument are both exactly Integer: isLessThan, isGreaterThan, isLessThanOrEqualTo, isGreaterThanOrEqualTo, is, isNot, add, subtract and multiply. The comparisons become JavaScript’s operators. The arithmetic becomes the guarded operation shown under hybrid-integers.
• NonZeroInteger: multiply, where both operands are exactly Integer. NonNegativeInteger and PositiveInteger: add and multiply, under the same condition. 1::add(2) and 2::multiply(with 3) reach these, as the first example showed. Each namespace re-exports Integer’s own arithmetic, and checked refinements are erased before the first pass runs, so the lowering is the one above. raise, divide, quotient, remainder, absolute, negate and squareRoot stay calls.
• Boolean: negate, and and or, which become !, && and || on the held values.
• String: is and isNot, which become one call to the runtime’s stringEquals. Two strings are equal when their NFC forms are, so é written as one code point equals e followed by a combining accent, where === would return false.

Mixed kinds stay calls. An Integer beside a Rational is a widening the covering Number namespace decides by cross-multiplying. An operand typed as a union or a type parameter is not known to be an Integer at all.

This is safe because the types are exact and the values are what the runtime built. Integer arithmetic in Essence is exact at any size and totally ordered. No Integer is unequal to itself the way NaN is, so !(a < b) can be asked as a >= b.

and and or keep eager evaluation. Essence evaluates every argument before the call. JavaScript’s && and || skip the right side when the left decides. The two agree only when the right side has no effect. So the pass lowers and and or only when nothing in the whole argument can print, assign, or call a function the compiler cannot name:

function both(a, b) {
	return Boolean.and(a, isSmall(b));
}
function plain(a, b) {
	return a.value && b.value < $pool_1.value ? Boolean.trueInstance : Boolean.falseInstance;
}

both is a::and(isSmall(b)), where isSmall is a function the program wrote that prints, so the call stays. plain is a::and(b::isLessThan(10)). Names, member reads, literals, values built from those, and a short list of Integer and Boolean methods qualify. A call to a function the program wrote, an interpolated string or a match does not. A namespace a program declares inside a block under the name Integer, Boolean or String replaces the built-in one there, so calls on it are never lowered.

The pass also runs inside the standard library, so Integer’s isLessThanOrEqualTo compiles to _self.value <= other.value there. A protocol’s provided bodies stay calls, because their receiver is Self, which is no kind in particular until a conformance says so.

A lowered Boolean used as a condition is not built and then read back. That collapse is unbox-conditions.

compile-union-dispatch

Decides which method a union receiver calls, where the call is written.

A method called on an Integer | Boolean is one of two methods, and the value decides which. With this pass off, the runtime chooses:

return $type.dispatchMethod(value, [], [
	[
		{ type: "Integer" },
		Integer.toString__overload$1,
		[]
	],
	[
		{ type: "Boolean" },
		$es_Boolean_toString,
		[]
	]
]);

That builds an array per call and a tuple and a type descriptor per case, and then searches them. The pass writes out the decision the search would make:

return value[$type.typeKeySymbol] === "Integer" ? Integer.toString__overload$1(value) : $es_Boolean_toString(value);

Each case’s test is the one compile-type-tests computes for a match arm. A case the tag decides becomes a comparison. Cases whose members share a tag keep isValueOfType, against a descriptor pool-constants builds once. Cases keep the order the compiler chose, most specific first. A case whose check accepts every value that can arrive ends the chain.

The receiver and the shared arguments are evaluated once, before any test. That is where building the search’s arrays evaluated them. Where a temporary is needed, the chain is the body of an arrow function called at once. Where the call is a statement’s value, lower-matches-to-statements turns that into a block of consts.

A branch’s own arguments are built only in that branch. The search built every branch’s arguments before choosing one. Those arguments are conformance witnesses, the method maps a protocol-bounded function is handed (see devirtualise-witnesses), and function literals, and building either has no effect, so the difference cannot be observed. The pass checks that per case, and leaves the call alone where it does not hold.

A chain whose every branch is the same call becomes that call. length on a List<Integer> | List<String> resolves to List.length for both members:

return List.length(mixed);

The measured program calls a function holding that call ten million times, in a counted loop that does nothing else. It takes about 30 ms on Bun with this pass and over 750 ms without it, and about 55 ms and 600 ms on Node. The bundle falls from 9,419 to 4,450 bytes, because nothing reaches dispatchMethod and the descriptor checks any more.

The last case is the else, where its test compares tags. The compiler emits a dispatch only where every member of the union has a case. A value that reaches the last case has nowhere else to go. The elision gives up $type.noDispatchCaseMatched(), a throw that names a compiler bug. It is reached only when a runtime check and a static type disagree. Where the last check needs a descriptor, its test and the throw stay. --without-optimisation compile-union-dispatch puts the search and its throw back.

devirtualise-witnesses

Calls the method a witness names, instead of reading it off the witness.

A conformance witness is a method map, such as { toString: Integer.toString__overload$1 }. A function bounded by a protocol is handed one, and reads the method it needs off it. Where a site reads exactly one method off a witness, right there, the compiler already knows which function that read finds. With this pass off, an interpolation hole reads the method off a pooled witness:

return String.createString("You have " + $pool_0.toString(count).value + " left.");

With the pass on, it calls the method:

return String.createString("You have " + Integer.toString__overload$1(count).value + " left.");

An interpolation hole is the only such site. Every other witness is passed as an argument, where the callee decides which method to read, so the object has to exist. pool-constants builds those once. The two passes never compete for a value: this one takes the witnesses used on the spot, and the pool takes the rest.

A conditional conformance is left alone. Its witness is built by boundConformance(…), which curries further witnesses onto every method, so the function behind toString is made by the call and has no name to write. A witness forwarded from the enclosing function’s own conformance argument is left alone too, because it is a different value on each call.

The pass saves bytes and one step of indirection, and little time: the hole already read one property off an object the pool built once. A program that interpolates and passes no witness anywhere stops building one at all.

lower-matches-to-statements

Writes a match where it stands, instead of inside a function called on the spot.

A match is an expression in Essence, and its arms hold statements. The only JavaScript expression that can hold statements is a function call, so with this pass off every match compiles to one:

function describe(count) {
	return function (_self) {
		if (_self[$type.typeKeySymbol] === "Optional#Value") {
			const value = _self.item;
			return String.createString("" + Integer.toString__overload$1(value).value + " left");
		} else {
			return $pool_0;
		}
	}(count);
}

That closure is built and called every time the match runs. Where the match is itself in a statement position, none of it is needed:

function describe(count) {
	{
		const _self = count;
		if (_self[$type.typeKeySymbol] === "Optional#Value") {
			const value = _self.item;
			return String.createString("" + Integer.toString__overload$1(value).value + " left");
		} else {
			return $pool_0;
		}
	}
}

Three positions qualify: a return statement, the value of a declaration or an assignment, and a match written for its effects. A match anywhere else, such as an argument, a record member or an interpolation hole, keeps its wrapper.

In return position the arms’ returns return from the enclosing function, which is what a return does anyway, so the arms are emitted as written. Everywhere else the result is written to where it goes, and an arm that returns before its end leaves the chain through a labelled break. Here constant answer = match count -> String { … } returns early from its #Value arm with <- "zero":

let answer;
$match_0: {
	const _self = count;
	if (_self[$type.typeKeySymbol] === "Optional#Value") {
		const value = _self.item;
		if ($es_Integer_isZero(value).value) {
			answer = $pool_1;
			break $match_0;
		}
		answer = String.createString("" + Integer.toString__overload$1(value).value + " left");
	} else {
		answer = $pool_0;
	}
}

_self still means the matched value. It was a parameter, which is bound outside the scope it declares, and a const is not. So match @ -> … binds nothing and reads the _self already there. A subject that only mentions _self, such as match @.item -> …, is read in a scope of its own before the block that shadows it.

An arm can shadow the name the result goes to. Say an arm declares its own answer, and the match is the value of constant answer. The result is then written to a name of the compiler’s own. answer is assigned from it once the block has closed.

A match written for its effects drops its arms’ final <- {}. The compiler gives every arm a return, and appends <- {} where the body has none. The pass removes that return, so no empty record is built only to be dropped. Only an arm’s last statement is considered, and a return that holds a call is kept and evaluated.

The pass also lifts a compiled union dispatch that holds operands. Where the dispatch is a statement’s value, its names become the consts of a block and the arrow function goes.

unbox-conditions

Tests a comparison directly, instead of the Boolean built around it.

Essence has no truthiness: a condition is a Boolean. An Essence Boolean is an object, and every object is truthy in JavaScript, so an if tests the value the object holds. Where the Boolean is one lower-scalar-operations built from a comparison, the two steps cancel. With this pass off:

if ((a.value < b.value ? Boolean.trueInstance : Boolean.falseInstance).value) {

With it on:

if (a.value < b.value) {

Each arm of a define holds a condition too, and gets the same treatment. define { as "A" if score::isGreaterThanOrEqualTo(90) as "B" otherwise } emits:

return score.value >= $pool_1.value ? $pool_2 : $pool_0;

Only that exact shape is collapsed. Any other condition, such as a method a namespace wrote, a name or a record member, is an Essence value, and JavaScript has to test its value. Reading .value off a raw JavaScript boolean would give undefined, which is falsy, so every such condition would quietly fail.

This is safe because it removes only a Boolean that is built and read back at once. With the pass off, the program asks the same questions and gets the same results, building and reading back one Boolean per condition.

inline-loops

Writes a loop out where it is called, instead of calling a driver that calls callbacks.

Essence has no loop statement. A loop is a call to a driver function with callbacks, such as loop(startingWith seed, while (n) { … }, (n) { … }). The driver calls them turn after turn. With this pass off, that is what the JavaScript does:

return $_.loop__overload$1(seed, function (n) {
	return n.value < $pool_0.value ? Boolean.trueInstance : Boolean.falseInstance;
}, function (n) {
	return …;
});

With the pass on, the walk, meaning the turns of the loop from its first to its last, is written out at the call. Each callback’s body stands where the call to it was:

let $loop_0_state = seed.value;
$loop_0:
	while (true) {
		{
			const n = $loop_0_state;
			if (!(n < $pool_0.value))
				break $loop_0;
		}
		{
			const n = $loop_0_state;
			$loop_0_state = …;
		}
	}
return Integer.createInteger($loop_0_state);

The seed.value and the final Integer.createInteger are the unboxed-loop-state shape, described below.

The pass inlines five loop entries and four List methods at the call. The loop entries are while, until, through, downTo and step. The List methods are map, everyItem(where:) and the two reduce entries. NonEmptyList declares a map of its own, which is List’s map re-exported, so a call on a proven non-empty list is inlined the same way.

The upTo entry and the three counted entries whose body returns a Step are not inlined at the call. Each is written in Essence on another entry, so the inlined walk sits inside its body in the standard library. loop(from 0, upTo count, …) compiles to a call.

A callback is inlined only where it is written at the call. A function-valued name holds whatever was bound to it, which the compiler cannot read. A call that passes one stays a call.

The parameters are bound, not renamed. Each callback body is emitted inside a block whose consts are its parameters, which is the scope the closure gave it. The names the walk binds itself start with $loop_ and a number unique in the program, which no Essence name can spell.

Evaluation order is the call’s. The seed, the bounds and the receiver are evaluated before the walk, in the order the call passes them. while and until check the predicate before each step, so a predicate decided on the seed returns the seed and the body never runs.

The counted loops skip their driver entirely. through and downTo are written in Essence on the while driver. They thread a { index, carried } record through it, which costs a record and an Integer per turn. Inlined, each becomes a for over the two bounds. This is loop(from 1, through count, startingWith 0, (index, total) { <- total::add(index) }):

const $loop_0_from = $pool_0.value;
const $loop_0_to = count.value;
let $loop_0_state = $pool_1.value;
const $loop_0_big = typeof $loop_0_from !== "number" || typeof $loop_0_to !== "number";
const $loop_0_delta = $loop_0_big ? 1n : 1;
for (let $loop_0_index = $loop_0_big ? BigInt($loop_0_from) : $loop_0_from; $loop_0_index <= $loop_0_to; $loop_0_index += $loop_0_delta) {
	{
		const $loop_0_held = $loop_0_big ? Integer.canonical($loop_0_index) : $loop_0_index;
		const total = $loop_0_state;
		$loop_0_state = …;
	}
}
return Integer.createInteger($loop_0_state);

The counter counts in numbers wherever both bounds are held as numbers, and in bigints past 2⁵³. The choice is made once, before the first turn. Where both bounds are written as Integer literals a double holds exactly, the choice is made while compiling, and the bigint half is not emitted:

const $loop_0_delta = 1;
for (let $loop_0_index = $loop_0_from; $loop_0_index <= $loop_0_to; $loop_0_index += $loop_0_delta) {

The body gets the raw counter where it only reads its value. A body that uses the counter only in arithmetic and comparisons reads the number directly. No Integer is built for it per turn. A body that passes the counter on, stores it or shadows its name gets an Integer. When a walk counts in bigints, Integer.canonical turns each counter back into a number where it fits. So a value inside the safe range, the integers a double holds exactly, keeps one representation (see hybrid-integers).

A Step is read where it is built. The step loop and reduce’s stopping entry decide by the case the body returns: #Done(x) stops with x, and #Continue(x) carries x on. Where the body’s result is such a case, the walk assigns and leaves, and the case is never built:

if (n > limit.value) {
	$loop_0_answer = Integer.createInteger(n);
	break $loop_0;
}
$loop_0_state = …;

Where the body returns a Step held under a name, or one a method returns, the tag is read at that one site.

Position decides whether there is a closure. A loop that is a statement’s value is written as statements. A loop anywhere else, such as an argument or an interpolation hole, is wrapped in an arrow function called at once, which is one closure for the whole walk.

List walks read the list’s items once. map, everyItem and reduce start with two consts: the items as one array, and their count, fixed before the first turn. list-tail-sharing explains why the count is fixed:

const $loop_0_items = List.materialise(prices);
const $loop_0_count = $loop_0_items.length;

A call that leaves out an argument is not inlined. The pass writes the callee’s body at the call, and reads the argument list the call wrote. A parameter’s default would have nowhere to go. None of the nine entries declares a default.

The standard library’s own walks are inlined inside their bodies. firstItem(where:), firstIndex(of:), count(where:) and removeEvery(where:) are written on reduce or everyItem with literal callbacks. A call to one of them stays a call, and what it calls is a for loop.

The pass costs text. A walk written at three sites is three walks, where it was three calls to one driver.

What it is worth depends on the driver. Three programs show the range:

• A counted sum over twenty million turns runs about 7× faster than the same build with only this pass off, on both engines. Against a build with every pass off it is about 31× faster on Bun and 20× on Node.
• A step loop threading a record over three million turns gains nothing measurable from this pass. It is still about 4.5× faster than with every pass off on Bun, and 4.8× on Node, and that gain comes from the other passes.
• An everyItem(where:) into a reduce over two million items gains between 1.1× and 1.3× on Bun, varying between runs, and nothing measurable on Node. Against every pass off it gains about 2.1× and 1.35×.

This pass removes the driver itself. After it there is no closure, no Step and no driver between a loop and the for you would have written in JavaScript.

build-lists-in-place

Pushes onto one array where a walk rebuilt a list every turn.

inline-loops writes the driver out, but the body still makes the call the program wrote. With this pass off, a counted walk that appends builds a new list every turn:

let $loop_0_state = {
	[$type.typeKeySymbol]: "List",
	value: [$pool_1]
};
…
for (let $loop_0_index = …; $loop_0_index <= $loop_0_to; $loop_0_index += $loop_0_delta) {
	{
		const index = Integer.createInteger($loop_0_index);
		const list = $loop_0_state;
		$loop_0_state = List.append__overload$1(list, index);
	}
}
return $loop_0_state;

With the pass on, it pushes onto one array and wraps it once at the end:

const $loop_0_built = [$pool_1];
…
for (let $loop_0_index = …; $loop_0_index <= $loop_0_to; $loop_0_index += $loop_0_delta) {
	{
		$loop_0_built.push(Integer.createInteger($loop_0_index));
	}
}
return List.createList($loop_0_built);

That is loop(from 1, through count, startingWith [0], (index, list) { <- list::append(index) }). It is what the compiler already emits for map and everyItem, applied to an accumulator the program wrote. The counted walks, the while and until walks, the step walk and both reduce entries can be rewritten this way.

The counter is not bound either, where the whole body is that one push: the Integer is built inside the push call, as above.

When it applies. Pushing onto an array is invisible only while nothing else can see the array, so the previous state has to be dead the moment it is rebuilt. The rule is strict. The accumulator’s name may appear only as the receiver at the root of the chain that rebuilds it. A branch that changes nothing may return it bare, and a #Done may carry it. Any other mention declines the walk, which then keeps the copying emission. That covers an argument, a member of something built, a name a closure captures, a nested walk over it, and even a read as harmless as length. So does prepend, which grows the end a build does not push onto. (index, list) { <- list::append(list::length()) } reads list as an argument, so it keeps List.append__overload$1(list, List.length(list)).

That rule costs the while, until and step walks most of their chances. Their predicate or body reads the state too, so they qualify only when they decide by something else. The counted walks and the two reduce entries are where the pass pays.

The seed decides one entry cost. A seed written as a list literal hands its array over, because nothing else has ever held it. So does a list added by append(contentsOf:) that is written as a literal: its items are pushed directly. Any other seed is copied once, on entry, into an array the walk owns, so a list the program held before the walk is never pushed onto. For a list that has never been prepended to, that copy is the same slice that append makes when it cannot push in place. Without the pass, the first append copies nothing where the held list still views its whole array (see list-tail-sharing).

What it is worth depends on what is appended:

• Five million appends of the counter run about 1.6× faster with this pass on Bun, and about 1.3× on Node.
• Five million appends of a constant run about 3.4× faster on Bun, and about 1.1× on Node.
• Four hundred thousand three-turn walks, each seeded with a list the program held, run about 1.2× faster on both.

One measured program is slower with this pass. It runs three hundred three-turn walks, each seeded with the same held list of a million items. With the pass it takes about 3.3 times as long on Bun, and about 1.2 times as long on Node. Both builds copy the million on nearly every walk, so the gap comes from how the engines run the pass’s copy, not from extra copies. Thirty such walks, or thirty thousand walks over ten thousand items, show no slowdown. A program of the slow shape runs faster with --without-optimisation build-lists-in-place.

A walk the pass declines is emitted as it was. So are map, everyItem and every walk that threads something other than a list.

fold-constants

Writes out the result of an operation whose operands are written out.

60::multiply(with 60)::multiply(with 24) becomes one Integer, as in the example at the top of this page. "a count: {7}" becomes one string instead of a witness and a toString call:

const $pool_0 = Integer.createInteger(86400);
const $pool_1 = String.createString("a count: 7");

What folds: Integer and Rational add, subtract, multiply, negate and absolute, and their comparison and equality methods. String append and prepend. An interpolation hole whose value is a literal and whose toString is the standard library’s. A written literal resolves to the narrowest refined namespace it proves. 60::multiply(with 60) is PositiveInteger’s product, and 1/2::multiply(with 2/3) is PositiveRational’s. Those fold too, as do NonZeroInteger’s and NonNegativeInteger’s. NonZeroRational.reciprocal stays a call. Where every hole of an interpolated string folds, the string becomes a literal, and pool-constants declares it once.

This is safe because the compiler works the result out the way the program would. Essence arithmetic is exact, and the fold runs on bigints, so there is no rounding to disagree about. Each fold carries out the body of the method it replaces. A folded Integer is written in its canonical representation, a number inside the safe range, so it is the literal you would have written by hand.

A Rational keeps the parts it was built with. It stores the numerator and denominator it was built from, and reduces only what it returns. 4/2 stores 4 and 2, Terminal.inspect shows it as 2/1, and its numerator() is 2. So 4/2 folds to Rational.createRational(4n, 2n). Arithmetic between two Rationals returns lowest terms, so 1/2::add(1/4) folds to Rational.createRational(3n, 4n), the value the unfolded program builds. The fold calls the same core functions the runtime does. An interpolation hole folds to what toString returns, so "{4/2}" folds to "2".

Only literals fold, never a name bound to a constant. A binding is a place a debugger stops and a name a reader looks for, and pool-constants already removes its allocation. Mixed-kind operands, such as an Integer beside a Rational, and operands that are calls stay as written.

Two things are not folded. String equality is not, because it compares normalised forms. The JavaScript engine running the compiler may have different Unicode tables from the one running the program. raise is not, because its result grows with its exponent’s value rather than its length. A folded number is also capped at 4,096 decimal digits.

prune-dead-match-arms

Drops a match arm that can never run.

implementation {
	function describe(_ value: Integer | String) -> String {
		<- match value -> String {
			case Integer { <- "an Integer" }
			case Boolean { <- "never" }
			case String  { <- "a String" }
		}
	}

	Terminal.print(describe(1)) § an Integer
	Terminal.print(describe("one")) § a String
}

value is an Integer | String, so no Boolean reaches the case Boolean arm. The validator reports it before the optimiser runs:

[unreachable-case]
Warning: This Case can never match
   ╭─┤ Describe.es:5:9 │
   │
 3 │        <- match value -> String {
   │                 ──┬──  
   │                   ╰──── this is an Integer | String
   │ 
 5 │          case Boolean { <- "never" }
   │               ───┬───  
   │                  ╰───── Boolean is not a member of the matched Union
───╯

A warning does not stop the build. With this pass off, the program still emits the arm and tests it on every call. With it on, the arm is gone:

if (_self[$type.typeKeySymbol] === "Integer") {
	return $pool_1;
} else {
	return $pool_0;
}

This is safe because a matcher is refuted only where its runtime check fails for every member of the subject’s type, which happens only where the tags differ. Two types that share a tag are never refuted, as compile-type-tests showed for List<Alpha> and List<Beta>: the empty list passes both.

The surviving arms keep their order. A match takes the first arm that matches, so the order decides the result.

The pass is narrower than the warning. unreachable-case also reports an arm that earlier arms already cover, such as case Integer written twice or anything below a case _. Deciding that needs the order as well as the types, and a kept arm costs only a test.

elide-final-match-test

Emits a match’s last arm as the else of the chain.

A match that compiles is exhaustive. The validator refuses one that leaves a member of its union unhandled, and an arm with a guard never counts toward that. So an unguarded last arm runs when every arm before it declined. Its test has one possible outcome, and the fall-through after it is unreachable. With this pass off:

const $self_tag = _self[$type.typeKeySymbol];
if ($self_tag === "Optional#Value") {
	…
} else if ($self_tag === "Optional#Empty") {
	return $pool_0;
} else {
	$type.noCaseMatched(_self);
}

With it on:

if (_self[$type.typeKeySymbol] === "Optional#Value") {
	…
} else {
	return $pool_0;
}

The version with the pass off binds $self_tag because it has two tag tests left, which is the tag-binding shape.

What is given up is $type.noCaseMatched. It is reached only when a matcher’s runtime check disagrees with the type the compiler gave the value, never through a program’s own fault. It throws, naming the value that fell through. With the last test elided, such a value takes the last arm instead. That trade is why this is a pass, and not the way every match is emitted. --without-optimisation elide-final-match-test puts every test and the throw back.

The test is elided only where the last arm’s check reduces to a tag comparison, or asks nothing, as case _ does. That limits what is lost. The only value the elided test would have caught is one whose tag disagrees with its type. A check that reads into the value keeps its test and the throw.

A last record arm is elided where one member of the union is a record. On a String | Point, a match that ends in case Point needs one tag comparison. Its fall-through cannot be reached:

if (_self[$type.typeKeySymbol] === "String") {
	return $pool_1;
} else {
	return $pool_0;
}

--without-optimisation compile-type-tests does not put that last test back; only this pass’s name does. Two records in one union keep both tests and the throw, even after compile-record-members rewrites them.

Some arms can decline for reasons exhaustiveness does not cover, and such an arm keeps its test. That is an arm with a guard, a literal matcher such as case 0, or member literals such as case { x = 0 }.

compile-record-members

Replaces a record matcher’s descriptor walk with a tree of member tests.

compile-type-tests reduces a record matcher to a tag only where one member of the union is a record. Where two are, their members tell them apart. With this pass off, each test calls the general check against a pooled descriptor, such as { type: "Record", members: { radius: { type: "Integer" } } }:

if ($type.isValueOfType(_self, $pool_1)) {
	…
} else if ($type.isValueOfType(_self, $pool_0)) {
	…
} else {
	$type.noCaseMatched(_self);
}

That call finds its record arm among the runtime’s kind tests, lists the descriptor’s members, and asks about each member’s type. With the pass on, the members are read instead. This is a match over Circle | Square, where Circle is { radius: Integer } and Square is { side: Integer }:

if (_self.radius?.[$type.typeKeySymbol] === "Integer") {
	…
} else if (_self.side?.[$type.typeKeySymbol] === "Integer") {
	…
} else {
	$type.noCaseMatched(_self);
}

Where the records share a member name and differ in its type, as { value: Integer } and { value: String } do, the member is read directly:

if (_self.value[$type.typeKeySymbol] === "Integer") {

Why it is safe. isValueOfType against a record descriptor is a conjunction of independent questions. The value’s tag is "Record", and for each member the matcher names, the member is present and its value passes that member’s type. A record matcher is open: it names some members, and the value may carry more. Each rule below drops one of those questions, or replaces it with one that gives the same result for every value that can arrive. Where a rule cannot be shown to hold, no tree is written and the descriptor walk stays.

• The tag is dropped where every member of the union is a record.
• Presence. Where every arriving record declares a member, the member is there and is read directly. Where one does not, nothing is known about it, and the read goes through ?.. An absent member reads undefined, which holds no tag. Only a requirement one tag comparison can decide is tested this way. One that would need a walk of a value that may not be there refuses the tree.
• Which members are tested. A member whose requirement the static type already settles is not tested.
• Type parameters. As a requirement, a type parameter accepts everything, so a member typed by one is not tested. As something that can arrive, it refuses the tree, because its tag cannot be named.
• Refinements. A refined member is tested as its base type.
• Nested records get the same argument one level down. A test is written only after every test on the path to it, so no member is read before its parent is known to be there.
• A matcher whose member types lead back into it is walked with a guard, because a type can be infinite where a value cannot.

The order is chosen by cost. Every test is a property read and a comparison, or a walk of the value. None can fail or observe anything, so their order does not change the result. Tag comparisons come first and walks last, because a walk over a list’s items costs a call per item. Among the comparisons, a shorter path comes before a longer one.

One rule serves three places: a match arm’s check, a case matcher’s payload requirement, and a compiled union dispatch’s case. compile-type-tests writes the first two and compile-union-dispatch builds the third, so turning either off still leaves the other’s.

The tree does not claim that a tag decides the matcher. So elide-final-match-test and compile-union-dispatch keep the last test and its throw.

A tree is written whole or not at all. Past eight tests the descriptor walk stays. That is a size rule: the walk is one call against one pooled descriptor, while a tree is written out at every site.

A match over five record shapes, run five million times, is about 15× faster with this pass on Bun and 10× on Node. A method called nine million times on a union of three record types is about 14× and 10× faster.

loop-self-tail-calls

Takes a function’s calls to itself in tail position back to the top of its own body, instead of making them.

Essence has no loop statement, so the walk the language teaches is recursion: take the head, answer with the walk of the tail.

implementation {
	function total(_ rest: List<Integer>, _ sum: Integer) -> Integer {
		<- match rest::firstItem() -> Integer {
			case #Empty       { <- sum }
			case #Value(head) { <- total(rest::removeFirst(), sum::add(head)) }
		}
	}
}

With this pass off, that is a self-recursive JavaScript function, and it costs a frame per item:

function total(rest, sum) {
	const _self = $es_List_firstItem__overload$1(rest);
	if (_self[$type.typeKeySymbol] === "Optional#Empty") {
		return sum;
	} else {
		const head = _self.item;
		return total($es_List_removeFirst__overload$1(rest), …);
	}
}

With the pass on, no call is made. The arguments are evaluated, the parameters are rebound, and the body runs again:

function total(rest, sum) {
	$tail_0: while (true) {
		const _self = $es_List_firstItem__overload$1(rest);
		if (_self[$type.typeKeySymbol] === "Optional#Empty") {
			return sum;
		} else {
			const head = _self.item;
			const $tail_0_t0 = $es_List_removeFirst__overload$1(rest);
			const $tail_0_t1 = …;
			rest = $tail_0_t0;
			sum = $tail_0_t1;
			continue $tail_0;
		}
	}
}

This is what makes the shape portable. JavaScriptCore has proper tail calls, so Bun ran the recursive version at any depth. V8 does not, so the same bundle threw RangeError: Maximum call stack size exceeded on Node and on Deno at about ten thousand items. With the pass on, one frame does any number of turns on every engine.

Tail position is the answer of the function, with nothing left to do with what the call gives back. It is the operand of the <- that answers, and, through that, the answer of every arm of a match, of an if/else, and of a define that itself stands there. It is not an argument of another call, not a receiver: <- total(rest, sum)::add(1) still has the addition to do, so it is an ordinary call. Non-tail calls to itself in the same body stay calls, so a function with one of each is looped for the one and still recurses for the other.

Why it is safe. A frame that does nothing but hand an answer straight on cannot be observed. What the pass has to preserve is that a turn is a call:

• The rebinding is simultaneous. Every argument is evaluated before any parameter is assigned, so <- swap(b, a) swaps. The arguments are held under names of the compiler’s own where one of them could read a parameter an earlier assignment already overwrote, and written straight where none can.
• Labels and order. Essence calls are labelled, and the compiler has already put the arguments in parameter order by the time the pass reads them — the receiver first, the hidden conformance witnesses last. So each argument is matched to its parameter by position, whatever order the call wrote them in.
• A default is taken again. A turn that leaves an argument out re-evaluates that parameter’s default, in that turn, reading the parameters before it as that turn bound them — which is what the language promises a default at every call.
• The whole body runs from the top, prologue included, so a pattern in a parameter binds again and a record default is merged again.
• A captured parameter gets a binding per turn. A JavaScript closure captures the variable, not its value, so a closure an earlier turn built would read the next turn’s parameter. Where a function literal in the body mentions a parameter the loop rebinds, that parameter is renamed to a slot and the name the body reads becomes a const of the turn.
• A shadowed parameter gets the same treatment. Inside a match arm, @ is the matched value, so a method’s receiver means something else there. Assigning it by name would land on the arm’s own binding, so it is rebound through a slot too.

A protocol’s provided method is looped too. Its call to itself is written on @, as <- @::walked(n::subtract(1), sum::add(n)), and goes through the conformance the method was handed. The conformance decides the body, once for every call through it: a conforming namespace that writes its own walked, or conforms to a protocol that extends this one and provides walked again, runs that body instead. A protocol that does not extend this one keeps its own walked, and a pick or a bound through it runs that one. So wherever the provided body runs, its call through @ reaches that same body again, and the turn hands the same conformance on.

What it declines. A Future-returning body, whose complete self(…) is an argument of the wait rather than the answer — such a body has no tail call to find, and taking a turn inside the current run would hand it that run’s cancellation scope rather than one of its own. A call to a different overload of the same name, which is a different function. A function literal bound to a constant cannot call itself at all — the compiler answers that the name is not declared inside its own initialiser.

And a function literal standing in a parameter’s default that reads a parameter a turn rebinds. A default is taken again every turn, but it is evaluated where the turn assigns — it is what the turn assigns — so the closure it builds would close over the loop’s own variable, and the per-turn binding that answers a capture in the body has nowhere to stand in front of it. Such a function is left recursive rather than looped a second way. A default that closes over nothing, = () -> Integer { <- 7 }, builds per turn exactly the closure a call builds per call, and is looped like any other.

Mutual recursion is out of scope. Two functions that answer with each other still use the host’s stack, and so does every non-tail call. On Node and Deno that is about ten thousand frames. Iteration covers what to reach for instead.

Debugging. essence dap builds every debug session with the optimiser off, so a session steps through the recursion as it was written, one frame per turn. In a build that carries a source map, a turn still points at the line the tail call was written on — stepping it stops on the assignments and then on the line that reads as the call, and steps back to the top of the body rather than into a new frame. The call stack shows one frame where the source shows recursion, so a crash inside a looped function names it once rather than ten thousand times.

A function that answers with a call to itself on every path is refused before this pass runs, by the infinite-recursion error. There is no base case to leave the loop through, and the compiler says so rather than emitting a while (true) that never ends.

What it costs and what it buys. The while and the assignments add between 120 and 390 bytes to a bundle per looped function. No fixture and no example in this repository writes a self tail call, so every one of them builds byte for byte what it built before — and no method of the standard library is looped either, because the library writes its walks on loop and reduce for exactly the reason this pass exists.

Five programs, each doing millions of turns and nothing else, measured with the pass on and off:

On Bun the frame was already free, so the figures are parity — the one real gain is the binary search, whose turns are short enough that the call was most of the work. The countdown is written as parity rather than as a number because it measured 0.98× in one sweep and 1.03× in another, on a machine with other work on it: that is measurement noise on either side of parity, and reading either figure as the answer would be reading the noise. On Node the frame was not free, and on Node the recursive build does not finish at all past about ten thousand turns: Tail_10000.es throws RangeError: Maximum call stack size exceeded with the pass off and prints 50005000 with it on. That is what the pass is for; the speed is a side effect.

eliminate-dead-code

Drops a constant nothing reads.

implementation {
	constant secondsPerHour = 60::multiply(with 60)

	Terminal.print("done") § done
}

Nothing reads secondsPerHour, so the build emits no const for it. Constants like this are rarely written on purpose. Earlier passes leave them behind when they fold an operation or inline a walk.

Two questions decide. Is the name read anywhere in the program? The check is by name across the whole program, not by scope, which errs toward keeping. Could the program tell the value is gone? That is the same effect check lower-scalar-operations uses for and and or, so a declaration whose value prints stays where it is.

Only constants are removed, because a variable can be assigned after it is declared. Everything a module exports is kept, whether or not this build can see who reads it.

An interpolated string is weighed like the calls it makes. Each hole calls a toString, so the same list of effect-free methods decides it. constant greeting = "you have {count}" with nothing reading greeting is dropped. A hole whose toString a program wrote, and which prints, keeps its declaration.

The pass reads the program once and does not repeat. Take constant width = 3 followed by constant doubled = width::multiply(with 2), with nothing reading doubled. doubled goes, and width stays, because doubled read it when the reads were counted.

A file that declares values and prints nothing bundles to nothing with this pass on. With it off, the bundle still builds those values.

collapse-construction

Builds a record, a list or a case in one allocation.

With this pass off, each literal calls a runtime constructor, which copies what it is given and adds the hidden tag:

return Record.createRecord({
	x: x,
	y: $pool_0
});
return List.createList([
	x,
	x
]);
return $type.createCase("Optional#Value", Record.createRecord({ item: x }));

With the pass on, the compiler writes the objects the constructors would have built:

return {
	[$type.typeKeySymbol]: "Record",
	x: x,
	y: $pool_0
};
return {
	[$type.typeKeySymbol]: "List",
	value: [
		x,
		x
	]
};
return {
	[$type.typeKeySymbol]: "Optional#Value",
	item: x
};

This is safe because the runtime’s constructors build exactly these objects: the same members, in the same order, under the same key, with every argument evaluated where it was. A case payload written as a literal is inlined into the case, which is sound because nothing else holds a fresh literal. Any other payload is spread, so a record the program still holds is copied, as the runtime copied it:

return {
	...article,
	[$type.typeKeySymbol]: "Route#Article"
};

A case with no payload keeps its constructor. createCase hands out one shared instance per tag, rather than a new object per construction.

collapse-combinations

Combines two records with a spread.

With every pass off, { base with x = 1 } builds an empty object and a record that is read once, and copies both into the empty object:

return Object.assign({}, base, Record.createRecord({ x: Integer.createInteger(1) }));

With this pass on, it is a spread:

return {
	...base,
	x: $pool_1
};

This is safe because the two do the same thing with Essence values. Object.assign copies own enumerable properties, symbol keys included, in order, and a later source overwrites an earlier one. Object spread copies the same set in the same order. Neither reads through a source’s prototype. A spread defines each property, while Object.assign assigns it, and an assignment can find a setter on the target’s prototype chain. Here the target is a fresh object literal in both forms, so there is no setter to find. The hidden tag rides along on the spread of base.

pool-constants

Builds each constant value once, instead of at every site.

With this pass off, a literal is built wherever it is written, every time that code runs. Sorting a List<Integer> builds its comparison witness at the call:

return $es_List_sort__overload$1(items, void 0, {
	compare: Integer.compare,
	isLessThan: $es_Integer_isLessThan__overload$1,
	isLessThanOrEqualTo: $es_Integer_isLessThanOrEqualTo__overload$1,
	isGreaterThan: $es_Integer_isGreaterThan__overload$1,
	isGreaterThanOrEqualTo: $es_Integer_isGreaterThanOrEqualTo__overload$1
});

With the pass on, each such value is built once, in a band of consts near the top of the module, and read by name:

const $pool_0 = Integer.createInteger(1);
const $pool_1 = {
	compare: Integer.compare,
	isLessThan: $es_Integer_isLessThan__overload$1,
	isLessThanOrEqualTo: $es_Integer_isLessThanOrEqualTo__overload$1,
	isGreaterThan: $es_Integer_isGreaterThan__overload$1,
	isGreaterThanOrEqualTo: $es_Integer_isGreaterThanOrEqualTo__overload$1
};

The band sits after the standard library’s function consts and before its static property values. A pooled witness reads the functions above it, and a property’s value may read a pooled constant. Each emitted module has its own band, because a name declared in one module is not in scope in another.

What is pooled: Integer, String and Rational literals, payload-less cases, and the type descriptors a match arm’s check still needs. Conformance witnesses are pooled too, including the boundConformance(…) a conditional one is built with. Two conditional witnesses are different constants when different witnesses are curried onto them.

This is safe because every Essence value is immutable, and the language has no operator that asks whether two values are the same object, only whether they are equal. One shared value cannot be told from twenty equal ones. One built before the first statement cannot be told from one built where it was written. None of these values can fail or observe anything while it is built.

Booleans are not pooled, because a running program already has exactly two Boolean objects.

A witness that names a namespace the program declares stays where it was. Such a namespace is emitted as a class, which is not hoisted, so a const above it would throw a ReferenceError when the module loads. A witness built from a conformance the enclosing function received stays too, because it differs on each call.

Emitted shapes

These are choices the compiler makes while writing JavaScript, not passes over the program, so no flag turns one off. None of them adds, removes or reorders anything the program does: the same values are read in the same order. They are listed here so that a reader tracing a line of emitted JavaScript finds them next to the passes.

Each holds under any set of passes. Each acts on a shape that a pass produces. Turn that pass off, or the whole optimiser, and there is nothing to act on.

tag-binding

Reads the matched value’s tag once when a chain asks about it more than once.

const $self_tag = _self[$type.typeKeySymbol];
if ($self_tag === "Integer") {
	return $pool_2;
} else if ($self_tag === "String") {
	return $pool_1;
} else {
	return $pool_0;
}

That is a match on an Integer | String | Boolean. Without the binding, each test would read _self[$type.typeKeySymbol] again.

It applies from two tests up. A two-member union compiles to one test and an else, and one read needs no name. Only the matched value’s own tag is bound, because a member test reads a different object each time. A match nested in an arm binds its own $self_tag in its own block.

Where the cases carry different fields, as a choice’s payloads do, each value has a shape of its own. The engine then cannot cache the property read. The binding costs one statement per chain.

unboxed-loop-state

Carries a walk’s Integer state as the number or bigint it holds, and builds the Integer once, where the walk ends.

The counted walk under inline-loops already shows it: let $loop_0_state = $pool_1.value; before the walk, and return Integer.createInteger($loop_0_state); after it. The line that section left out as … is the addition, written into the raw slot:

$loop_0_state = typeof total === "number" && typeof $loop_0_held === "number" && total + $loop_0_held >= -9007199254740991 && total + $loop_0_held <= 9007199254740991 ? total + $loop_0_held : Integer.sum(total, $loop_0_held).value;

That is loop(from 1, through count, startingWith 0, (index, total) { <- total::add(index) }). The state slot holds a number or a bigint. The guarded addition writes its raw result into it, and one Integer is built at the end.

The addition is read through both arms of its guard, which hybrid-integers names. The guarded arm writes the plain + into the slot without building an Integer. The escaped arm reads .value off the Integer that Integer.sum built. So no turn builds an Integer only for the slot to read it back.

The state is carried raw only where all of these hold:

1. The state’s type is exactly Integer in every body it reaches. A record, string or Rational state is untouched. A refinement of Integer is carried, because refinements are erased.
2. Every mention of the parameter a body reads the state under is a read of its value. Only the operations lower-scalar-operations writes out read the value: the arithmetic and the comparisons. A body that asks its accumulator isEven, passes it to a function, interpolates it, puts it in a list or shadows its name keeps the box. A member read of the same name anywhere in the body counts as a mention too. The escaped arm of an addition calls Integer.sum, so an accumulator named sum keeps its box, where the same walk with it named total does not.
3. A driver that hands one state to two bodies, as while and until do, carries it raw in both or in neither.
4. The parameter’s const is still bound each turn, now to the raw value, so a closure that reads it sees that turn’s value.
5. Every write of the state is unboxed: its seed, each assignment, and the state member of a Step the compiler could not see being built.
6. Every exit builds the Integer, through Integer.createInteger.
7. At every turn the slot holds what a canonical Integer holds: a number inside the safe range, a bigint outside it.
8. Two mentions beyond the value are admitted, and both write the state whole into a slot the walk owns. <- carried is unboxed with every other write. <- #Done(carried) is boxed where it stands, because a #Done leaves the walk.

Every driver that threads a state carries it raw: the while and until entries, the counted walk, the step walk and both reduce entries. map and everyItem thread none. A walk inside a walk carries both slots as one value: the inner walk writes straight into the enclosing slot, with no Integer built between them.

A walk whose every turn is outside the safe range takes the escaped arm on every turn, so a runtime call still builds an Integer each time.

unboxed-operand

Reads an Integer operation through both arms of its guard where the next operation needs only its value, so no Integer is built between them.

function blend(left, right) {
	return Integer.difference(Integer.sum(typeof left.value === "number" && typeof right.value === "number" && left.value + right.value >= -9007199254740991 && left.value + right.value <= 9007199254740991 ? left.value + right.value : Integer.sum(left.value, right.value).value, right.value).value, right.value);
}

That is left::add(right)::add(right)::subtract(right). lower-scalar-operations writes the first addition as a guard. The next addition reads only the first one’s value, so the guarded arm yields left.value + right.value directly, and the escaped arm reads .value off the Integer Integer.sum built. The outer two operations go to the runtime whole, because an operand that holds a call cannot be read twice (see hybrid-integers).

It is unboxed-loop-state’s other half, applied where that one does not reach, including programs with no loop at all. A site that takes the Integer itself, such as an argument, a list item or a method that was not lowered, keeps the box.

Runtime improvements

These change the runtime itself, not the code the compiler emits, so no pass turns them off. They rest on the same properties of the language as the passes. They are listed here so that a reader checking whether an optimisation is sound finds them in one place.

Each is invisible for the reason pool-constants is safe: every Essence value is immutable, and nothing asks whether two values are the same object. So nothing can tell a shared value from a fresh one, or a remembered result from a recomputed one.

interned-booleans

There are exactly two Boolean values, so there are exactly two Boolean objects, built once. Every comparison, every and and every loop predicate reuses them instead of allocating.

interned-unit-cases

A case with no payload carries only its tag, so every value of it holds the same thing. One instance per tag is built and reused, both for built-in choices and for the ones a program declares. The pool is bounded by how many distinct payload-less cases a program constructs, which depends on its text, not on how long it runs.

reflexive-equality-fast-path

Structural equality returns at once when a value is compared with itself. Equality is reflexive here: there is no NaN to be unequal to itself, and functions compare by identity anyway. The check earns its place because identical operands are common. Both Booleans, every payload-less case and every pooled literal are one shared object each.

grapheme-caching

Splitting a string into graphemes, the characters a reader sees, is the most expensive thing a string method does. The position methods ask for the same view of the same string again and again. The view and its count are remembered on the value, under symbol keys. Nothing that reads a value sees them: record equality, printing and the runtime’s type checks read with Object.keys, Object.entries and Object.hasOwn, which skip symbol keys. A string is immutable, so a remembered view cannot go stale.

Counting skips the segmenter for ASCII, where each code unit is a character of its own. The one exception is a carriage return, which joins a following line feed, so a string holding one is not treated as ASCII. Whether a string is ASCII is itself remembered.

The NFC form is remembered too, and it is what equality compares. is and compare decide over the normalised string, so an accent written as one code point equals the same accent written as two. Each string is normalised at most once, and an ASCII string not at all, since it is already its own normal form.

Joining two ASCII strings gives an ASCII string, and it is marked as one, so its character count is the two counts added. Building a string by appending while reading its length each turn is linear, not quadratic.

The segmenter is built on first use, so a program that never segments a string does not pay for loading one.

slice, character(at:) and the searches are natives that read the remembered view directly, rather than being written in Essence on top of characters(). repeat is native for the same reason — an Essence body would build a list of copies and join it — but it joins the text and never reads the view at all.

A join that is not two ASCII strings is marked as not ASCII, without a scan. A join holds every code unit of both sides, so a side the scan would refuse makes a join it would refuse. Without that mark the next method scanned the whole join to ask again, and an engine resolves the rope it built for a join the first time anything reads a unit of it — so a token built one non-ASCII character at a time re-flattened everything built so far, every turn. It is linear now, like the ASCII case beside it.

string-window-sharing

A slice of a string shares the character view it was cut from, rather than copying it. The view is the array of grapheme clusters grapheme-caching remembers; a window of it is that same array, an offset saying where the window’s first character stands in it, and a count saying how many are its own.

Its text is one slice of the text the clusters were cut from, between the two clusters’ code-unit offsets. A table of those offsets is built once per array, on its first cut, and shared with every window of it. The clusters partition that text, so the text between two of their offsets is exactly those clusters joined — which is the string the cut answered before there were windows, byte for byte. Everything downstream is handed the same text as before: is, compare, the normalised form, printing, and the key a dictionary files the string under.

This is what makes consuming a string from the front linear:

implementation {
	constant text = "café café café "

	constant consumed = loop(
		startingWith { rest = text, count = 0 },
		step (state) {
			if state.rest::isEmpty() {
				<- #Done(state.count)
			}

			<- #Continue({
				rest = state.rest::slice(from 1),
				count = state.count::add(1),
			})
		},
	)

	Terminal.print(consumed) § 15
}

Each turn used to copy the remaining clusters into a new array and join them back into a new text, which is O(n) per turn and O(n²) over the loop. A 40,000-character drain of "café " measured 2,245 ms, where the same program over "cafe " was flat at 19 ms, because ASCII is cut by the intrinsic and never builds a view at all. It measures 33 ms now, and stays flat to 640,000 characters.

Sharing follows the half rule, the one list-tail-sharing applies to a shared suffix: a cut shares only where it is at least half of what it would share, and is copied otherwise. What the rule bounds is retention — a window holds the whole array of clusters, the offset table and the whole text alive, and a six-character token cut out of a five-megabyte source must not pin the source for as long as the token is held.

The rule is asked in both units, because a window pins things counted two ways: the array and the offset table hold one entry per character, and the text holds one per code unit. Cluster widths are not uniform, so half the characters of a text can be a fraction of its units — a text of 20,000 one-unit clusters followed by 20,000 clusters 301 units wide is 12 MB, and a window over its narrow half is exactly half the characters and a three-hundredth of the text. So a cut shares only where its characters are at least half the array and its code units are at least half the text. Under both questions a window pins at most twice its own characters and at most twice its own text.

It costs nothing asymptotically: a drain shares every step down to half, copies once there, and shares down to half of that, so the copies over a whole drain add up to twice the characters rather than the square of them. Two questions rather than one do not change that — each copy halves the characters or halves the units of what the next window can share, and neither can halve more times than its own logarithm. On text whose clusters are all of a kind the two questions are one question, and every drain measured below copies exactly what it copied under the character rule alone. On the skewed text above, a 20,000-character drain copies 81,000 clusters rather than 40,000, in the same 32 ms.

A copy is exactly what a cut cost before. It copies the window’s clusters and joins them into a fresh text, rather than cutting the parent’s — because an engine’s sliced string keeps the string it was cut from alive, and a small window cut that way would pin the source. A tokenizer holding 250,000 six-character tokens of a five-megabyte source retains the same memory it did before this existed.

The readers a drain asks per turn never scan a window for ASCII-ness. The scan is O(n), and every turn of a drain is a new string, so asking it per turn was the same O(n²) from the other side. slice, character(at:), the prefix and suffix tests, the searches and the normalised form — which is, compare, every dictionary key, codePoints and the hasOnly predicates are decided over — all ask a question that takes the view into account instead. A window of a string the scan refused declines a fast path it might have passed; what that costs it is the view route, which is the route it is already on.

The methods that walk the whole receiver — uppercase, lowercase, repeat, words, split, separate and append — still ask outright. Each is O(n) per call anyway, so the scan beside the walk changes no complexity class, and answering “not ASCII” for a window that happens to be all ASCII would cost them the intrinsic route, which is tens of times faster than the walk. A drain calling one of those per turn is quadratic on either side of this change.

Every reader that must not walk the window reads it where it stands. length() answers from the count, so isEmpty() is O(1). character(at:), firstCharacter() and lastCharacter() read one cluster out of the shared array. starts(with:) and ends(with:) compare only as many characters as the part covers, and fold only those when the call folds the case — folding the whole receiver to compare a two-character prefix made a drain asking for one per turn quadratic, at 1,484 ms for 80,000 characters against 29 now. firstIndex(of:) and lastIndex(of:) cost the distance to the match however the comparison reads. A case-sensitive search hands the question to the engine, which stops where it finds. An #Insensitive one folds and searches a chunk at a time and folds the next only if the part was not in the last, doubling the chunk each time, so it folds about twice the distance to the match rather than the whole receiver: a drain asking for one per turn measured 117 ms over a 20,000-character receiver and 2,686 ms over 320,000, and is flat at 28 ms now. What the chunking costs is paid only by a search that must read the whole receiver anyway — one for a part that is not there — and it is up to 9% between 3,000 and 10,000 units, 3% beyond that, and nothing at all under 2,048 units, which are read in the single call they always were. The methods that read the whole receiver by nature — count(of:), everyIndex(of:), the replacements and split(on:) — fold it once per call rather than once per occurrence.

The readers that walk the whole receiver copy the window’s characters once. split, reverse, separate and characters() need an array they can index from zero, so the first of them copies the window’s clusters out and the window keeps the copy — which also lets the parent’s array, text and table go. The replacements walk the shared array where it stands and copy nothing, and words and codePoints read the text rather than the array, so none of those three materialises anything.

Measured on this machine, best of three, subprocess startup of about 20 ms included in every figure. Each program consumes a string of one é per five characters one character at a time, against an ASCII twin of the same length:

The same holds for texts of combining marks, joined emoji, regional-indicator flags and CRLF line breaks, and for a hand-written tokenizer over source with non-ASCII identifiers and string contents: 50,000 characters measured 4,608 ms and now 39 ms, 100,000 measured 18,218 ms and now 47 ms, and 200,000 measures 65 ms against its ASCII twin’s 42.

A string that has been through the view stays on it, and the one shape where that costs something is a string whose non-ASCII characters are all at the front: once they are consumed the remainder is pure ASCII, but it has a view and keeps taking the view route, where before this it was rescanned every turn and found its way back to the intrinsic. One é followed by pure ASCII, consumed one character at a time, measures 33 ms at 80,000 characters against the intrinsic’s 32, and 58 ms at 320,000 against 51 — linear either way, about 1.2 times the intrinsic. Buying the intrinsic back means rescanning per cut, which is the O(n²) this section exists to remove.

The design costs about four kilobytes in a bundle that reaches the cutting, and 75 bytes in one that only measures strings.

rational-reduction-caching

A Rational’s lowest-terms form is remembered on the value, under a symbol key. What the value stores does not change: 4/2 still holds 4 and 2, as fold-constants showed. Equality cross-multiplies those parts, which is why 4/2::is(2) is true. Every accessor and formatter returns lowest terms, and the cache means that reduction happens once instead of once per question.

add, subtract, multiply and divide between two Rationals are natives on the runtime’s bigint rational core. Each is one cross-multiplication and one reduction, and the result is built already holding its lowest-terms form. 1/2::add(1/2)::is(1) is true. fold-constants folds these four through the same core functions, so a folded result is the one the program builds.

hybrid-integers

An Integer holds a JavaScript number while its value fits a double exactly, which is |value| ≤ 2⁵³ − 1 (Number.MAX_SAFE_INTEGER), and a bigint beyond that. An ordinary Integer costs a double in a field, and a large one stays exact.

One value has one representation. A value inside the safe range is always a number, and a value outside it is always a bigint. Integer.createInteger enforces that for every value that arrives from elsewhere: a literal, a native, the client bridge, an escaped result. So equality is === on the held values, and a number never equals a bigint. Zero is inside the safe range, so it is always held as the number 0, never 0n.

Every emitted operation checks its result. An emitted +, - or * is a guard around the operation. This is a::add(b):

return typeof a.value === "number" && typeof b.value === "number" && a.value + b.value >= -9007199254740991 && a.value + b.value <= 9007199254740991 ? {
	[$type.typeKeySymbol]: "Integer",
	value: a.value + b.value
} : Integer.sum(a.value, b.value);

The guard has two arms. The guarded arm is the plain +, taken when both operands are numbers and the result is inside the safe range. The escaped arm is the runtime call, Integer.sum, taken otherwise. The operands are asked by kind with typeof, because JavaScript’s + throws on a number beside a bigint. The result is asked by range, and that check is exact. IEEE 754 addition, subtraction and multiplication are correctly rounded, rounding is monotone, and 2⁵³ is itself a double. So a true result of magnitude 2⁵³ or more can only round to a double at least that large, which fails the check. A true result inside the range rounds to itself. The check therefore passes exactly when the double is the true result. 94906265::multiply(with 94906265) fits and stays a number. 94906266::multiply(with 94906266) does not, and Integer.product returns 9007199326062756 exactly.

The escaped arm checks its own result only where that result can still be back inside the safe range, which is a sum or a difference with an escaped operand.

raise is not inlined, and stays in bigint. JavaScript’s ** on doubles is Math.pow, which the specification only requires to approximate, so its result cannot be checked afterwards.

An operand that holds a call goes to the runtime whole. The guard reads each operand twice. So Integer.sum, Integer.difference or Integer.product gets such an operand directly, and decides after evaluating it once.

The rest of the numeric tower does not see the two representations. Rational, Algebraic and Transcendental are written on pairs of bigints, and an Integer is converted at one boundary, so 1::is(1/1) is true.

Going out to a JavaScript host, an Integer is always a bigint, so a value in an embedding does not change type when it crosses 2⁵³. Coming in, a bigint is accepted, and so is a number that is a safe integer. 2 ** 53 as a number is refused, because the double has already lost its exactness.

The representation costs where a program’s values are all past 2⁵³, such as 64-bit hashes, ids or nanosecond timestamps. Each small operand then needs converting to a bigint, and each result a range test. The guard also costs text, since it is wider than the call it replaces.

list-tail-sharing

A list is two runs, arrays of items, and a view into each. The back run is stored forward in value, the front run is stored reversed in front, and a count beside each says how much of that run this list owns. A flat list, one that has never been prepended to, has no front at all, and is an array, its tag and a number. That is why collapse-construction can keep writing its literal: no counts means the view is the whole array.

The runs are shared between the lists of one chain. Appending asks one question: does the receiver view all of its back run? If so, it stands at the tip, the item is pushed onto that array, and the result views one more item of the same array. If not, another list has appended there already, so the result gets a run of its own: the receiver’s view is copied and the item pushed onto the copy. Prepending asks the same of the front run. A receiver that has never prepended starts a front of its own and keeps its back run. So a list grown at either end costs one push per item, and a list that branches at an end costs one copy at the branch.

The receiver’s count is written before the push. A list with no count views its whole array. So no list may ever have an item in its array that was pushed for another.

Everything that wants one array goes through materialise. It returns an array that is exactly the list’s view. That is the array itself for a flat list viewing all of it, a trimmed copy where it views less, and a combined array where there are two runs. In the last case the list keeps the combined array, so a list read twice combines once. reverse, sort, split and pair ask for one array. Methods that walk read the two runs in turn, and methods that index work out which run holds a position.

Every walk fixes its count before its first turn. A callback may append to the list being walked:

implementation {
	constant list = [1, 2, 3]

	constant doubled = list::reduce(startingWith list, (accumulated, item) {
		<- accumulated::append(item)
	})

	Terminal.print(doubled) § [1, 2, 3, 1, 2, 3]
}

The seed is the list being walked, so the first append finds it at its tip and pushes onto the very array the walk reads. A walk bounded by that array’s live length would walk the items it adds, and never end. It has to return what it would have returned if every append copied: the items the list held when the call began. A count taken on entry is what makes it do so.

createList takes ownership of the array it is given. It stores the array without copying it, and a later append may push onto it. So no caller may keep the array it passed. Every caller in the runtime and in emitted code builds a fresh one. build-lists-in-place relies on the same rule, which is why it copies a seed the program already held. A host of the client package builds lists through a second constructor that copies, so an array a host keeps is never one Essence pushes onto.

Edits share the runs they do not touch. A sub-list that still contains the seam, the point where the front run ends and the back run begins, can be returned without copying anything. Shrinking the front count drops leading items, and shrinking the back count drops trailing ones. A flat list keeps its seam at the start, so it can share only its prefixes. A slice at an end therefore costs a small object and no items, which makes removeLast() free, and removeFirst() free on a list that was prepended to. remove(at:) shares at either end the same way. replace(_:at:) writes its item into the run the position falls in, in place where it can — that is list-in-place-writes below. insert(_:at:) uses prepend and append at the ends. A window that misses the seam and keeps less than three quarters of the list is still a copy, made once from the two runs; one that keeps at least three quarters makes the list move its seam into the middle of the window instead, and is then shared like any other. That is what list-window-trimming below is about.

A shared window is copied when it is read and it is small enough to be worth copying. A read that copies copies the window’s items, never the whole parent array, and lets the parent go; a window keeping at least half of its parent keeps the array it has instead. The half rule described below is what decides between the two. length reads no items at all, so it leaves the window exactly as it found it.

One runtime change needed the emitted code to change too. The inlined map, everyItem and reduce walks read the items through List.materialise, as inline-loops showed. They fix the count before the seed is evaluated, because the seed may append to the receiver. With inline-loops off, the walk goes back through the native it was written from, which reads the same two runs.

This is safe because a list always returns exactly the items its view holds. Equality and ordering read both sides through their views, so [2, 3]::prepend(1)::is([1, 2, 3]) is true.

The design costs three things. A list viewing less than its run keeps the whole run alive until something reads it, and a read trims it only when the view is less than half the run. A positional read of a prepended-to list pays one comparison, to find the run that holds the position. A flat list pays a small view object on each item(at:) and length().

With every pass off, so that each call reaches the runtime, a million appends to one list take about 70 ms on Bun and 75 ms on Node. A million prepends take about 69 ms and 96 ms. That is one push per item, not a copy of the list.

list-window-trimming

A list that views less than the array it holds is keeping that whole array alive. Trimming it — copying out exactly the view and storing the shorter array back — is what lets the rest of it go. The half rule decides when. A run is trimmed only when the list views less than half of it. Above a half the list keeps the array it has.

The rule is what keeps a chain of shrinking lists linear. removeFirst() answers a window one item shorter, and the canonical functional walk reads each of those windows once:

implementation {
	function total(_ rest: List<Integer>, _ sum: Integer) -> Integer {
		<- match rest::firstItem() -> Integer {
			case #Empty       { <- sum }
			case #Value(head) { <- total(rest::removeFirst(), sum::add(head)) }
		}
	}

	Terminal.print(total(List.of(integersFrom 1, through 50_000), 0))
}

Trimming at every read copies what is left at every turn, so the walk moves half of n times n items and is quadratic. Under the half rule it trims at n/2, n/4, n/8 and so on, which is n items over the whole walk — one to three items moved per item of the list, whatever the shape of the walk. Fifty thousand items measured 634 ms before and 36 ms after, and the walk is flat from there: 100,000, 200,000 and 400,000 measure 33, 41 and 54 ms, of which about 20 ms is starting the process.

The rule is asked wherever a run changes hands, not only where one is read. Cutting a window out of a list is a use of that list, so the run it is cut from is trimmed exactly where reading it would have been. Otherwise the cost would depend on the order the two lines of a walk are written in — a turn that takes the tail before reading the head would find the untrimmed array every time, and that spelling still measured 220 ms against 35.

The rule is always asked about the list whose run it is. A window keeping two items of a list that views its whole array is cut without moving anything: the run is already as short as its owner can make it, and the window’s own smallness is settled the first time the window is read. Asking about the window’s size instead would copy a whole list to hand out two items.

A window holding neither end can be shared too. Only the windows containing a list’s seam can be shared, so a window of the middle used to be copied, which made a walk dropping an item from each end — a palindrome check — quadratic on its own, at 1203 ms for 50,000 items. Such a list now moves its seam into the middle of the window, once, and every window shrinking towards that middle from either side is shared afterwards. The same walk measures 32 ms. The move is made only when the window keeps at least three quarters of the list, and below that the plain copy is what happens. Three quarters rather than a half because the move rebuilds both runs, which is not free per item even done in bulk, and it is paid whether or not a second window ever follows to repay it. A drain that drops an item from each end asks for all but two of the items it has, so it qualifies at every turn and the walk above is windows from its first turn on; a one-shot slice of the middle, which nothing follows, takes the plain copy it can afford. At a half that one shot measured 6.7 ms for fifty middle windows of 50,000 items against 3.5 ms for the copy, and it is 3.5 ms again at three quarters.

This is invisible for the reason the rest of the representation is: a list always answers exactly the items its view holds, whichever array is behind it and however short that array has been made. Nothing in the language can ask whether two values are the same value, so swapping one array for a shorter one under a list cannot be observed.

What it costs is retention, bounded. A list may now hold an array up to twice the length of what it views, where trimming at every read held exactly what it viewed — and in exchange no walk pays for a trim it does not need. A window that is never read at all still holds its parent, which is what a deferred copy has always cost. Reading a ten-item window of a million-item list releases the parent under this rule exactly as it did before: measured as live heap after a collection, 0.0 MB held, against 38.2 MB if positional reads never trimmed at all. The head/tail walk over 200,000 items peaks at 60 MB under the rule and 176 MB when every read trims.

list-in-place-writes

Writing one cell of a list — replace(_:at:) — used to copy the run the position fell in. A push only ever extends an array, so the lists sharing it keep every position they have already answered for, but a write changes a position they view, and copying was the only honest answer to that. An accumulator written cell by cell therefore cost its own length every turn, which is quadratic. A sieve, a dynamic programming table, a binary heap, a board, a histogram and a grid are all that shape, and in JavaScript every one of them is xs[i] = i.

The newest list of a chain owns its array, and writes into it. Behind every written run is an undo log: the writer records what stood at the position, writes over it, and counts the log one version up. The answer views the new version and the receiver is left viewing the old one. Every list sharing that array says which version it views, so a list left behind can still say exactly what it holds — the first time anything reads it, it copies the array and undoes the writes made since it looked. That is the copy replace used to make, deferred to whoever actually reads, and never made at all for the receiver a loop throws away.

implementation {
	constant size  = 40_000
	constant zeros = List.repeat(0, times size)

	constant filled = loop(
		from 0,
		upTo size,
		startingWith zeros,
		(index, cells) { <- cells::replace(index, at index) },
	)

	Terminal.print(filled::lastItem())
}

Forty thousand cells measured 2,739 ms before and 26 ms after, and the fill is flat from there: 80,000, 160,000, 320,000 and 640,000 measure 31, 38, 47 and 65 ms, of which about 20 ms is starting the process. A sieve of Eratosthenes to 30,000 measured 2,425 ms and now measures 28 ms; a dynamic programming table of 20,000 cells, which reads the cell before it and writes the next, measured 684 ms and now measures 26 ms, with 100,000 cells at 33 ms; twenty thousand pushes onto a binary heap, two writes and a read per sift, measured 2,005 ms and now measure 30 ms.

A list with no log copies once, and the copy carries the log. Every list that has never met a positional write holds a bare array — a literal the optimiser wrote out, a fresh one a method built, one handed over by a host — and could never learn of a write into it. So the first write copies, exactly as before, and the log is attached to the array that write makes. The sieve pays one copy and then writes in place for good. A log is minted only where a fresh array is minted, and from there it travels with that array to every list the array is shared with.

A walk seals the run it is reading. A list’s items are read by handing a run array to the method walking it, and that method calls code the program wrote — a transform, a check, a comparison, an item’s own equality. That code can reach the list being walked:

implementation {
	§ One write mints the log. A literal carries none, so a list that has
	§ never been written takes the copying path and would show nothing about
	§ the seal — this write puts back the item already at that position.
	constant cells = [1, 2, 3, 4, 5]::replace(1, at 0)

	constant walked = cells::reduce(startingWith cells, (accumulated, item) {
		<- accumulated::replace(0, at 4)
	})

	Terminal.print(cells) § [1, 2, 3, 4, 5]
}

The fold is seeded with the very list it walks, so without a rule the first write would land in the array the walk is reading and the walk would visit an item nobody ever put there. The rule is that any reader handing a raw run to such code seals that run’s log, and a sealed log refuses writes in place for good: the next replace copies and starts a fresh log. A walk is linear work anyway, so the copy it may cause is paid for. The readers that look at one item — item(at:), firstItem(), lastItem() — hand no array to anybody and do not seal, which is what keeps “read the cell before, write this one” out of the copying path.

A list left behind pays for the writes made since it looked. Catching up replays every entry of the log from its current version down to the version that list views, so a list’s first read costs its own view and the whole of the log since it last looked — even where it views two items and the run is long. Many lists left behind over one heavily written run therefore pay that each: two thousand prefix windows of a 200,000-item run with a full log measure 206 ms of catching up, where reading two thousand windows of a list nothing has written is about 0.1 ms. No program has been built where that loses, because a log that long is filled by writes that each cost their whole list before this — a run of 50,000 with a thousand windows over it measures 3.30 s without in-place writes and 0.04 s with them. It is written down because it is a shape the rest of this section does not imply. The cheap bound for it, keeping the lowest position ever written beside the log and skipping the replay for any list viewing fewer items than that, is not bought by anything measured so far.

The log is bounded by the run it belongs to. Past that length the next write copies to a fresh array with a fresh log, so a chain holds at most its array and about as much again, and the copies amortise to constant work per write. The old array and its log are left exactly as they are, because whoever is behind on them still catches up through them.

This is invisible for the reason the rest of the representation is: a list always answers exactly the items its view holds, and nothing in the language can ask whether two values are the same value. What makes that a claim rather than a hope is that every reader reaches a list through one of the same few doors — the two views, materialise, and the three methods that grow a list — and each of them catches a list up before a single item of it is read. The two readers outside the runtime that walk a list’s runs directly, the client boundary and the debugger, undo the log into a copy of their own rather than repairing the value they are looking at.

What it does not fix is branching persistent use: keeping an old list and writing it again and again, as backtracking over a board does. Every write but the first finds its receiver behind, catches it up with a copy, and then writes — which is what every write cost before this, and it measures the same. A nine queens search over a board of nine squares measured 37 ms before and 32 ms after. insert(_:at:) and remove(at:) in the middle still move the items after the position, the way splice does in JavaScript; only the ends of a list are cheaper than that, and they are shared rather than moved.

What it costs is a field on every list that has met a positional write, the log itself, and one question — “have I been written past?” — at each of those doors. Measured against the same build without any of it: a grid read by position 36 ms against 35, map to filter to fold over 100,000 items twenty times 54 ms against 52, an append build of 400,000 items 38 ms against 35, a prepend build 37 against 35, a head/tail drain 33 against 32, and equality, sorting, printing and a string-keyed dictionary together 75 ms against 71. A bundle that reaches a list at all grows by about a kilobyte; one that never reaches one is unchanged.

canonical-key-encoding

A dictionary finds a key in one step where it can reduce that key to something a Map can be keyed by, and by comparing it against every live slot where it cannot. The same encoding is what the set-shaped list methods hold their seen keys in: removeDuplicates, hasDuplicates, contains(everyItemOf:), everyItem(alsoIn:), removeEvery(contentsOf:), mode and the groupings.

These key types are found in one step. String, Integer, Rational, Boolean, the covering Number, a record whose every declared member is one of these, a case of a choice whose equality the language derives and whose payload members are all one of these, an Optional or a Result or a generic choice of your own whose type arguments are all one of these, and a list whose every item is one of these, nested to any depth. A refinement counts as what it refines, so a NonEmptyString key and a NonEmptyList<NonEmptyString> key are found the same way as the types they refine.

These take the scan. Algebraic, Transcendental, a function, a dictionary, and anything holding one of those. A list of numbers is found in one step until an algebraic lands in it; that key alone then takes the scan, and the rest of the dictionary keeps its index.

A record or a case that asks a member takes the scan too, and it is the same rule. A record’s declared members decide its equality, so a record holding a Tag whose namespace writes an is of its own is compared by that is — and an encoding can not stand in for it. Such a key is found by asking every live slot, which is right for any is at all. A record whose every declared member is one of the encodable types above keeps the one-step lookup, so nothing that used to be found in one step stops being.

A key is reduced to a JavaScript primitive where one spells it exactly — a string’s NFC form, an integer’s number or bigint, a boolean — and to a text where no primitive does. A rational spells its reduced parts, a record its members in name order, a case its tag and then its payload, and a list how many items it holds and then each item’s own text. Every part is length-prefixed or terminated, so no two different keys spell one text: [1, 23] and [12, 3] differ by where the terminators fall, [[1], [2]] and [[1, 2]] by the counts in their heads, and a string holding l1:i1; is spelled by its own length-prefixed form rather than read as the list it imitates.

The encoding is used only where it is the equality the key is compared by. A namespace that writes an is of its own replaces the standard library’s, and its keys are then found by asking that is about every live slot:

implementation {
	function nameCount() -> Integer {
		namespace Loose for NonEmptyString is Equatable {
			is(_ other: NonEmptyString) -> Boolean {
				<- true
			}
		}

		constant ada: NonEmptyString = "Ada"
		constant bob: NonEmptyString = "bob"
		constant seen = Dictionary.of([
			{ key = [ada], value = 1 },
			{ key = [bob], value = 2 },
		])

		<- seen::length()
	}

	§ One entry, because the written `is` decides and not the text.
	Terminal.print(nameCount()) § 1
}

A list carries that answer up from its items. List<ItemType> is Equatable where ItemType is Equatable compares its items with the item type’s own is, so a list key is found in one step exactly when its items would be, and a written is anywhere inside it, at any depth, puts the whole key on the scan.

A generic choice carries it up from its type arguments, by the same rule. Optional<ItemType> compares two values by their case and then their payload with the item type’s own is, Result<ValueType, FailureType> does the same with two, and a choice you declare yourself compares each payload member that names a type parameter with that argument’s is — so Dictionary<Optional<Integer>, …> is found in one step, and Dictionary<Optional<NonEmptyString>, …> under the Loose namespace above takes the scan. Every type argument has to be found in one step, so a Result<Integer, NonEmptyString> key under that namespace takes the scan on the strength of its failure type alone.

A dictionary used as a key is the one composite that always takes the scan, whatever it holds. Its entries are organised by a store of its own, and spelling one would cost every program that merely removes duplicates from a list the whole of that store.

A list key’s text is remembered on the value, under a symbol key, as a string’s NFC form and a rational’s reduced form are. Spelling a key costs one pass over its items, and a lookup would otherwise spell it again every time. A list’s items never change, so a remembered text cannot go stale.

This is invisible from Essence. The same methods answer the same things either way, and only the time differs. A dictionary holds the key value that arrived first, so keys read back as they were written rather than as the text they share, and two spellings of one value — 3 and 3/1, an accent written as one code point or as two — land in one slot because the comparison calls them one value.

It costs the text, which a dictionary holds for as long as it holds the entry: about 17 characters for a two-integer list key, against 26 for the same pair written as a record, and about 3 MB for 100,000 remembered texts.

And it costs a pass over the key wherever the scan it replaced would have settled sooner. The text is spelled once per list value and remembered on it, so a lookup with a list that has been a key before is one Map probe and nothing else. A lookup with a list built fresh for that lookup pays for spelling it — the whole key, every item — before the dictionary can answer at all. The scan does not: it compares how many items two keys hold before it compares any of them, so a probe whose length differs from every live key, or whose first item does, is settled in one comparison against each. A dictionary of a few entries probed by long lists is therefore slower than it was, and by no bounded factor: three two-item keys probed a hundred times, each probe a fresh list that is never in the table, measure 30 ms against 101 at 20,000 items per probe, and 35 ms against 748 at 200,000. The trade is worth making because the shape it is slow on is a dictionary that stays small while its probes grow, and the shape it is fast on is a dictionary that grows — where the scan is quadratic in the entries and the encoding is not. Where a program really is the first shape, naming the probe and reusing it pays the spelling once.

Building a dictionary of 8,000 two-integer list keys took 808 ms and takes 25. It is flat to 64,000 keys, at 40 ms, against 43 ms for the same table keyed by a record. removeDuplicates() over 10,000 two-item lists took 1,711 ms and takes 1.6. hasDuplicates() over the same took 1,746 ms and takes 1.6. Grouping 10,000 items under 2,000 list keys took 335 ms and takes 1.6. One list of 10,000 integers looked up 10,000 times took 3,804 ms and takes 1.