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.