Epsil Kernel Performance

Epsil kernel performance

Why compiled Epsil kernels run about 10× slower than the hand-written TS kernels, and what closes the gap. Measured on compute-engine 0.142, Node 24.21, Apple Silicon (10 cores), load average 6–8 throughout (other lanes running), each figure the median of 9 timed runs after 3 warmups; runs repeat to within about 10%. The TS kernels stay as the baseline.

Method

The generated code (compiled-families.generated.js, statistics.compiled.generated.js) is copied and rewritten in a scratch harness, one cost at a time, by source transforms. Each variant is checked to give the same answer for every rank before it is timed:

transform	removes
range	Array.from({length: _SYS.rangeCount(…)}, fn): a Range built by a counted loop instead
fuse	the array itself, for a Range consumed at once by .map / .reduce
at	_SYS.atNumeric(a, i, type): a plain a[i - 1]
bcast	the Array.isArray(x) ? _SYS.bcastFn(f, x) : f(x) wrapper around every lambda, and the fold adaptor
nan	x === x self-tests and typeof x === "number" guards
fact	_SYS.factorial from a table, _SYS.pow(-1, i) by parity

Beside them: the Epsil rewritten (compiled the same way), the same Epsil algorithm transcribed by hand to plain JS, and the TS kernel.

Measurements

Derangements, unrank then rank back. At n = 8 that is every 7th rank (2,119 round trips), and at n = 16 it is 2,030 ranks spread evenly.

variant	n = 8 (ms)	speedup	n = 16 (ms)	speedup
generated, as is	89.0	1×	317	1×
only −range	39.8	2.2×	155	2.0×
only −at	81.5	1.09×	272	1.17×
only −bcast	88.2	1.01×	299	1.06×
only −nan, only −fact	≈ 89–97	≈ 1×	≈ 305–310	≈ 1.03×
−range −fuse	39.6	2.2×	137	2.3×
… −at	30.2	2.9×	102	3.1×
… −bcast	25.2	3.5×	82	3.9×
… −nan −fact (all codegen)	22.5	4.0×	80	4.0×
Epsil with a subfactorial table	81.8	1.09×	247	1.29×
… and all codegen	20.1	4.4×	67	4.7×
plain JS transcription, state rebuilt each step	8.4	10.6×	24–28	12×
plain JS transcription, state updated in place	1.2	73×	5.1	63×
TS kernel	9.0	9.9×	25.4	12.5×

Involutions, n = 8, every rank (764 round trips): generated 14.3 ms, −range 7.1, all codegen 4.3, telephone table 11.7, table and all codegen 3.6. The TS kernel takes 1.3 ms (11×).

LongestIncreasingSubsequence, n = 1000, per random permutation (n = 100 in brackets):

variant	ms
generated, as is	10.7 (0.134)
generated, all codegen	10.2
Epsil: the target pile bound once per step	2.61
Epsil: bound once, and Map over the piles instead of a Fold of Joins	0.65 (0.045)
plain JS, patience with a linear scan (the test helper)	0.23 (0.016)
plain JS, patience with a binary search	0.018 (0.003)

kernelOn adds 11–14% to Derangements and 35% to Involutions over calling the generated code directly, because rank runs valid first and each call spreads a fresh variables object.

Where the gap is

The families: mostly compute-engine's codegen. All the codegen transforms together take Derangements and Involutions from 10–12× the TS kernel to 2.5–3.4×. About half of the original time is Array.from with a map function, which costs about 40× a counted loop on V8 (720 ns against 19 ns for 17 elements). The scalar guards (at, bcast, nan) are 1.6–1.8× of what is left once ranges are loops. fact hardly registers.

The state rebuild is not the gap. The TS kernels rebuild state too (filter, slice, a copied Map per step), and a plain JS transcription of the Epsil algorithm, which also rebuilds its state every step, runs at TS speed. In-place update would make it about 7× faster than TS. That is worth having (compute-engine#386), but it is a further gain, not the cause of the 10×.

The statistic: ours. LongestIncreasingSubsequence as defined does O(L²) work per element: the inner fold re-counts the target pile for every pile it copies, and copies with a Join per pile. Codegen is only 5% of its time. Rewriting the Epsil is 16× faster. What remains against the linear patience loop (2.8×) is the per-step copy of the piles, which is the #386 case.

Residual, unattributed. After every transform, compiled Derangements is still about 2.5× its plain-JS transcription. The cost is closures made per element: three-valued And/Or and If conditions lowered as nested IIFEs, the lazy-hoisting closure around each inner fold, and one closure per Apply∘Function binding. In a microbenchmark a let as Apply∘Function costs 3.4× the same let as Block(Declare, Assign) (8.6 µs against 2.5 µs, a fold over 1..1000). Rewriting the Derangements lets as Blocks gains nothing, though. The generated code changes shape in other ways too (the shared Range goes), so that rewrite doesn't isolate the cost of a let.

Ours: fixable in definitions

• LongestIncreasingSubsequence (and LongestDecreasingSubsequence, the same piles): bind the target once per step, and replace the inner Fold/Join with Map(e ↦ If(e = a[k], b, e), a). This is 16× at n = 1000. A Map over Range(1, Length(a)) in that place makes the compiler decline (Count: operand is not an indexed collection), so map over a itself.
• Subfactorial and telephone counts as a table: build [X(−1), X(0), …, X(n)] once by the recurrence (Fold of Append) and read it with At, instead of the factorial sum per step. This is 1.1–1.3× on Derangements and 1.2× on Involutions. It is small, because n ≤ 18 keeps the O(n³) cheap, and it compiles as is.
• kernelOn's rank validates on every call. Skipping that where the caller already knows the element is valid (a round trip, an enumeration) saves 11–35%.

compute-engine's: upstream candidates

1. A Range is built with Array.from({length}, fn). A counted loop is 18× faster for a short range, and fusing a Range into the .map/.reduce that consumes it is another 2–3×. This is half the family gap, and the predicate cases already lower to loops since the fix for #373.
2. Per-call guards on statically typed scalars. The broadcast dispatch around every lambda, atNumeric on a list<integer>, and NaN self-tests on integers cost 1.6–1.8× of what is left once ranges are loops, and 2× on a one-slot Map rewrite.
3. A let compiles to closures. Apply(Function(body, Typed(x, T)), v) allocates a broadcast-wrapped closure per evaluation. A const would do: 3.4× on the microbenchmark under Residual.

The drafts with repros and numbers wait for sign-off before anything is posted.

Structural

• In-place update (compute-engine#386, 0.143; re-measured on 0.146, Node 24.21, load average about 2). A compiled Fold updates its list in place only when the step returns the accumulator or a ReplaceAt chain on it and reads it only through At, Length or an aggregate of it (Sum, Max, Count). Probe, 20,000 slots, one fill: a step reading the accumulator through At takes 3.5 ms; the same read inside a let body or a Map lambda takes 570–650 ms, copying. A let around the step, and Filter, Take or Join of the accumulator, copy too.

  • In place: the telephone table (already), every rowTable row (the Stirling, Entringer and Eulerian tables, and the lattice-path and set-partition tables), the running free-value count of the pattern-avoiding families, and the position table rank builds.
  • Copying: the unrank state, because the completion counts fold over the prefix inside lambdas; and the pile list of LongestIncreasing/DecreasingSubsequence, because the target pile is found by a Filter of it. Forcing the unrank step in place by hand in the generated code (Derangements, n = 16) made no measurable difference, 167 against 169 µs per unrank: at the sizes compiled code serves (n ≤ 18) the copy is not what costs.

• Restriction folds, 0.146, round trip (unrank then rank back; every rank at n = 8, except CyclicPermutations, an even 3,000 of 5,040; an even sample at n = 16; median of 3 runs, each the median of 5 timed runs after a warmup, runs within about 1% of one another). TS has no kernel for KCycle or KDescent.

  family	round trips	main (ms)	in place (ms)	speedup	TS kernel (ms)
  Involutions n = 8	764	24.9	19.7	1.26×	1.6
  Involutions n = 16	2,000	297	188	1.58×	6.1
  Derangements n = 8	14,833	658	573	1.15×	57.7
  Derangements n = 16	2,000	726	597	1.22×	23.6
  KCyclePermutations n = 8, k = 3	13,132	4,353	2,306	1.89×
  KCyclePermutations n = 16, k = 4	500	1,637	823	1.99×
  KDescentPermutations n = 8, k = 3	15,619	6,783	5,182	1.31×
  KDescentPermutations n = 16, k = 7	200	1,224	646	1.89×
  CyclicPermutations n = 8	3,000	1,639	552	2.97×

  On compute-engine 0.142 the round trip at n = 8 was 36 ms for Involutions and 756 ms for Derangements; the 0.143–0.146 codegen alone brought them to 25 and 658 (main, above). What moved the rest:

  • prefix by ReplaceAt. The completion count's prefix was rebuilt by a Map over n slots on each of the O(n²) calls per operation; it is now a native copy of the state with one slot set. The unrank state carries a flag per value, so a value's use is read, not searched.
  • Cycle walks bound once. CyclicPermutations and KCyclePermutations read the result of the same n-step walk two or three times in one expression, and the compiled code walks each time. Bound once, Cyclic runs 3× faster (n = 8); this is most of the KCycle gain.
  • Table rows filled in place. KDescent at n = 16 builds a 16 × 289 table on every operation (about 2 ms of the 2.2 ms an unrank took on main, 1 ms of 1.2 ms now); its rows were appended a cell at a time and are now filled in place.
  • Remaining against TS (n = 16): Involutions 31×, Derangements 25×; the per-call cost is mostly the closures compute-engine's codegen makes per element (see Residual), not the state.

• LongestIncreasingSubsequence (and Decreasing), compiled, per random permutation: replacing the Map over the piles by ReplaceAt takes n = 100 from 28 to 7.7 µs and n = 1000 from 556 to 129 µs (4.3×). A plain linear patience loop takes 1.3 and 21 µs.

• Doubles only: compiled code answers while the count is a safe integer. Past that, the interpreter answers. No BigInt path appears in the generated code.

Families against their TS kernels, CE 0.146 (BL-70 re-time, 2026-10-02)

Round trip (unrank then rank back) through kernelOn with the generated code, against the TS kernel's own round trip; every rank when the fiber has under 2,000, else 2,000 ranks spread evenly. Each cell is the median of 3 runs, each run the median of 5 timed runs after 2 warmups. Node 24.21, 10 cores, load average 7–10 at the starts of the runs and up to 30 at the end of the third (other lanes running): runs agree to within about 10% for the permutation families and vary more (up to 2×) for the fast ones, where a sample is a few ms. All 188 family operations compile; none falls back to interpreted. The harness is .scratch/bench/families.ts (not committed). Involutions and Derangements are timed against TS kernels that order differently; the rest are checked element for element against TS first. On 0.142 (above) Involutions n = 8 took 36 ms against 19 ms now, and Derangements n = 8 756 ms against 102 ms for this sample (a different sample, 2,000 ranks of 14,833; not comparable per rank).

family	params	round trips	compiled (ms)	TS (ms)	compiled / TS
SymmetricGroup	8	2000	13.0	3.1	4.2×
SymmetricGroup	16	2000	54.2	5.8	9.3×
KPermutations	16, 8	2000	19.2	4.4	4.4×
SignedPermutations	12	2000	32.4	5.3	6.1×
ColoredPermutations	10, 3	2000	29.8	5.5	5.4×
Involutions	16	2000	255	6.2	41×
Derangements	16	2000	813	24.1	34×
DyckPaths	16	2000	105	5.1	21×
MotzkinPaths	16	2000	107	4.1	26×
SchroederPaths	12	2000	205	7.9	26×
DyckPathsByHeight	16, 6	2000	288	9.6	30×
SetPartitions	12	2000	81	3.4	24×
SetPartitionsIntoKBlocks	12, 4	2000	48	7.7	6.3×
Surjections	10, 4	2000	41	6.8	6.1×
CompositionsIntoKParts	24, 6	2000	1,197	1.4	855×
WeakCompositions	16, 6	2000	1,011	1.5	674×
PartitionsInBox	10, 10	2000	2,169	4.2	516×

With no TS kernel (compiled only, n = 16 unless noted; ms for 2,000 round trips): CyclicPermutations 3,265; KCyclePermutations (16, 4) 3,551; KDescentPermutations (16, 7) 8,514; AlternatingPermutations (14) 936; ConnectedPermutations (14) 685; GrassmannianPermutations (14) 287; PermutationsAvoiding132 (14) 1,577.

Reading it: the closed-form permutation families sit at 3–9× TS. The completion-count families (Involutions, Derangements, the DP lattice-path and set-partition families) are 20–40×. The three that stand out, CompositionsIntoKParts, WeakCompositions and PartitionsInBox (500–850×), have O(1) or tiny TS kernels (binomial arithmetic, one small table) against Epsil that rebuilds a table per call: the per-params table caching under "Restrictions: what's left" applies to them too, not only to KDescent/KCycle.

After #600: per-params tables and the lattice-path families (2026-10-03)

FamilyEpsil.tables builds a family's table once per params and caches it per kernel (a small LRU, exact values past 2^53); unrank, rank and valid read it as _tables. Round trip, compiled, against the TS kernel, n = 16 unless noted; each cell the median of 3 runs on a loaded machine (load 3–13), "before" being main at the time (a TS kernel where the family was still TS):

family	before (ms)	after (ms)	after / TS
CompositionsIntoKParts (24, 6)	703–1,221	10	6–7×
WeakCompositions (16, 6)	1,004	10	6×
PartitionsInBox (10, 10)	2,190	11	2.4×
KDescentPermutations (16, 7)	7,424	587	no TS kernel
AlternatingPermutations (14)	687	285	no TS kernel
KCyclePermutations (16, 4)	3,409	3,273	no TS kernel
MotzkinPaths / SchroederPaths (12)	84 / 146	32 / 36	8× / 5×
DyckPathsByHeight (16, 6)	197	60	6×
SetPartitions (12)	81	27	9×
RestrictedGrowthStrings (12)	66	15	15×
NonCrossingPartitions (14)	362	84	19×
PermutationsAsCycles (8)	119	54	67×
LatticePaths	TS 9.5	35	4×
MotzkinPathsByPeaks (20, 5)	TS 12	84	8×
DelannoyPaths (12)	TS 1.0	36	46×
LukasiewiczPaths	TS 8	189	24×

• The tables were not always the cost. CompositionsIntoKParts, WeakCompositions and PartitionsInBox spent their time in a colex digit search that re-ran a nested search for every slot (about k²n/2 Binomial calls per unrank); a table alone gave 2–3×, and a one-pass search reading a Pascal table gave the rest.
• KCyclePermutations barely moved: its table was cheap; the cost is the per-prefix completion count, which is the state-carrying prefix change (Roadmap, "Restrictions: what's left").
• Per-step list state is the floor. DelannoyPaths with its table is still 46× TS, DyckPaths (no table) 20×: compiled code copies a list per step. Closing that is compute-engine's, not ours.
• Past 2^53 the exact interpreter is far too slow for some tables: the tail-partition families (NonCrossingPartitions(32) did not finish a round trip in minutes) and MotzkinPathsByPeaks(60, 8) (200 s) keep declinePastDoubles; the TS kernel answered instantly there, inexactly.
• Direction since 2026-10-04: hand-written kernels stay as cross-verified fast paths the host prefers, so these ratios are what a family costs without one.

After #634: taken and prefix state for the restriction families (2026-10-04)

completions can read a taken list (per value, 0 or the slot holding it), so "is this value used" is one At instead of a fold over the prefix, and an opt-in prefix state (init, step(state, slot, value)) updated once per placed value. CyclicPermutations and KCyclePermutations keep head/tail maps and a closed-cycle count in place of the n-step walk each completions call made. Round trip, compiled, median of 3, load 16–19 (small gains are rough):

family	n	before (ms)	after (ms)	speedup
CyclicPermutations	16	3,684	185	20×
KCyclePermutations	16, k = 4	3,857	197	20×
KDescentPermutations	16, k = 7	697	471	1.5×
PermutationsAvoiding132	14	1,796	961	1.9×
Derangements	16	699	424	1.65×
GrassmannianPermutations	14	234	153	1.5×
AlternatingPermutations	14	365	255	1.4×
ConnectedPermutations, Involutions	14, 16	unchanged

• A state for KDescent ([descents, last]) measured 1.19× at n = 16 and 0.84× at n = 8, against 1.3–1.6× from taken alone, so it is not in.
• What is left per call (KDescent n = 16: about 0.9 µs per completions, about 544,000 calls per 2,000 round trips) is the per-call list copies and the O(n) free-value counts.
• Past 2^53 the interpreter answers exactly: CyclicPermutations at n = 20 took 2.9 s before and 1.5 s after; Derangements 3.4 s and 2.1 s.

Fast paths (#622) and the words and trees areas (#622, #637)

EpsilFamily.fast is an optional hand-written kernel the host prefers while the fiber has at most 2^31 members; tests/fast-kernels.test.ts holds it to the Epsil definition. Below that limit a fast family is within 1.1–1.8× of the raw TS kernel and 2–300× faster than its Epsil alone (DyckPaths (16) 95 to 6 ms, Multisets (10, 8) 829 to 2.8 ms, SetPartitions (12) 26 to 5.6 ms). The limit is 2^31 because the check found the TS kernels wrong above it while their counts were still safe integers (SymmetricGroup(18), Tuples(3, 33), Surjections(53, 2), GrayCodeSubsets(51), PhylogeneticTreeUnrank near 2^52). A TS kernel that orders differently from its Epsil (Involutions, Derangements, Cyclic, Subsets, KSubsets, IntegerCompositions) gets none.

Words, round trip against TS (n as listed, median of 3, loaded machine): BinaryWordsByWeight (24, 12) 17×, StirlingPermutations (12) 10×, FibStrings (20) and LucasStrings (20) about 100× faster than the TS kernel (uncached exponential), NonDecreasingParkingFunctions (16) 10× faster. Trees: LabeledTrees (12) 9.5×, RootedForests (12) 3.4×, BinaryTreeParentArrays (16) 7×, NonCrossingTrees (12) 5.8×, PhylogeneticTrees (14) 10× faster.