Repository navigation
Speculative Data Tables
Speculative. A proposal, not adopted.
Some collections are too large to generate on every use and too small to refuse: the unlabeled posets (183,231 classes at n = 9) and the unlabeled graphs (274,668 at n = 9, 12,005,168 at n = 10). A TypeScript fast kernel can generate the small sizes on first use, but the larger ones want a precomputed table. The repository has no mechanism for one (Posets §2, §9 answer 3; Unlabeled graphs §3): a family's tables is an Epsil expression hashed into the family, the build writes compiled code and small records, and nothing is loaded on demand. This page compares ways to add it, and recommends the smallest.
"Measured" means I ran it or read it directly from a file in the tree at origin/main (paths are repo-relative, path:line). "Estimated" means computed or run on a synthetic sample, not on the real tables. "Assumed" means reasoned, not run. The worktree has no node_modules, so nothing was built, compiled or tested here; sizes of build outputs are "not built here".
- Through n = 8 (posets and graphs), no table (option A). The kernel generates and keeps the classes per process, as Posets already plans. These are 16,999 and 12,346 codes.
-
n = 9 (and posets 10 if it is ever wanted): option B, one generated module per (collection, n), written by the package's
build, gitignored, holding the sorted codes as delta-varint bytes (about 0.5 MB for posets, 0.8 MB for graphs, estimated), loaded by dynamicimport()from a new asyncpreparestep that runs before evaluation. Until it has run, the kernel declines with a message that names the table. Node and the browser take the same path, so there is one code path and nofs/fetchsplit. -
Graphs at n = 10 do not ship in
@notatio/combinatorics. 12 M codes are about 36 to 42 MB (estimated), 50 times the whole existing committed data. If wanted, they are a separate data package under@enumeratio/*(option E), built from an external generator (nauty'sgeng), which also makes the table an independent check on our kernel. -
What would change this: a measured n = 8 generation under about a second in the browser worker keeps A to n = 8 (as Speculative-Posets says); the declare path turning out to have no per-head hook for
prepare(§3) puts the table in the library's own chunk, which costs every user of the library; a build-box measurement that table generation is slow (minutes) makes the table a committed snapshot (option D).
-
tablesis an expression.FamilyEpsil.tablesis "a list of integers over the params alone ... that the other definitions read as_tables", evaluated "once per distinct params" (packages/symbols/combinatorics/combinatorics/collections/src/families/epsil.ts:28-38; helperstables.ts:1-4). It is part of the family hash (epsil.ts:158-163), so editing it invalidates the compiled code. It is a completion-count table (DP rows), not a data table. -
FastKernelis plain JS over the params.count,unrank,rank,valid, each synchronous, any of which "may throw or answer undefined to leave the question to Epsil" (epsil.ts:40-52).fastis "a verified fast path: used while the fiber's count is a safe integer, ahead of Epsil", and is not part offamilyHash(epsil.ts:95-97). -
FAST_LIMITis a double bound, not a size bound.FAST_LIMIT = MAX_SAFE, 2^53 − 1 members, "the most a double counts exactly" (epsil.ts:173-176); the kernel uses a fast path only when the count is at most that (epsil.ts:566-576). A fast kernel that wants to decline at a size of its own (the posets plan: declining at n = 9) does it by returningundefined. The only decline the kernel itself raises today reads "past 2^53" or "its table doesn't fit in doubles" (epsil.ts:489-494). A "table not loaded" decline is a new reason. -
Kernel functions are synchronous.
NumberKernelcount/unrank/rank return values, not promises (collections/src/families/types.ts:120-125), and so does the kernelkernelOnbuilds (epsil.ts:305-330, return value at620). -
The fast path is held to the definition by a test.
tests/fast-kernels.test.ts:1-5: over a sampled grid of params the fast kernel and the Epsil-only kernel (epsilKernelOn,epsil.ts:763-765) agree on all four operations. The repo rule is the same (AGENTS.md, "A family's Epsil definition is its meaning"). -
Browser evaluation is in a worker and message-based. The site builds a session worker from
web/.vitepress/theme/session-worker-entry.tsvianew Worker(new URL(...))(web/.vitepress/theme/worker-factories.ts:44-47);Kernel.evaluatereturns aPromise(packages/symbols/evaluation/evaluation/src/kernel.ts:115-118). Inside the worker, compute-engine evaluates synchronously under a cooperative deadline (evaluation/src/cooperative-evaluate.ts:1-8). -
The one awaited step before evaluation is library declaration. The kernel does
await libraries.ensure(ce, input)before it evaluates (kernel.ts:189-193), and the site'scombinatoricslibrary is declared byawait import("@notatio/combinatorics")(web/.vitepress/theme/worker-catalogue.ts:38-40, header comment lines 1-6: "a worker loads a library's chunk when a call first needs it"). The granularity is the library, chosen from the names in the input. I did not read howensuremaps input to libraries, so whether a per-head hook exists is unknown. -
Node consumers.
@notatio/evaluation/noderuns isolated evaluation inworker_threads(evaluation/src/node.ts:1-6); tests callbareEngine()and the kernel directly (tests/fast-kernels.test.ts:55). I did not read the CLI's evaluation path; the kernel functions it reaches are the synchronous ones above. -
The service worker precaches library chunks. On install it caches "every library chunk the kernel loads" (
web/.vitepress/host/service-worker.js:2-5); the list is the closure of./name.jsand./name.cssstring literals from the worker entry (web/.vitepress/host/service-worker.ts:29,32-43,62-67). A table in a JS chunk is therefore precached for every visitor. A non-JS asset is not in that closure; the template says a hashed asset is answered from cache once fetched (service-worker.js:62, assumed to cover/assets/). -
What the build writes.
@notatio/combinatoricsgeneratessrc/statistics/naming-data.ts,src/maps-laws.generated.tsandsrc/compiled-maps.generated.js(combinatorics/package.json:93-97), plus*.generated.jssuch as the compiled families (.gitignoreof the package, line 3);scripts/build-generated.ts:1-3("everything the package generates from its own sources and the records, none of it committed").@notatio/referencelists six generated TS data files (packages/reference/package.json:85-92).buildends invp packwritingdist(combinatorics/package.json:40). All of these are small text; their sizes are not built here. -
The dist cache saves whatever git ignores. "What it saves is every gitignored file under its packages' directories, so generated data ... is picked up without being listed"; the key hashes tracked and untracked-not-ignored files, never outputs (
tools/ci/dist-cache.ts:9-17;outputsOf, line 202). A new generated table needs no cache edit. -
Committed data, measured. Among tracked
.tsv,.json,.bin,.gz,.csvfiles the largest are two kernel-answer snapshots,packages/symbols/arithmetic/residues/reference/PrimitiveRootList/examples.values.{wolfram,sage}.tsv(2,631,709 and 2,631,098 bytes), thencombinatorics/findstat/data/statistics.json(949,108 bytes),packages/bench/tests/bench.golden.json(830,593) andpackages/bench/catalogue/pinned.json(35,461). Largest tracked TS data file:packages/census/src/wolfram-frontier-data.ts(239,976). There are no tracked.bin,.gzor.wasmfiles. -
A committed external snapshot, and how it ships.
findstat/data/{statistics,maps}.jsonis written bypackages/reference/scripts/collect-findstat-data.ts:1-14from a crawl that is "too big to commit". It is in the package'sfiles(combinatorics/package.json:7-12) and exported as./findstat/data/*(line 36). Build-time readers load it withreadFileSync(findstat/tests/crosscheck-sweep.ts:84,src/statistics/generate-entries.ts:30,web/.vitepress/data/carrier-fields.ts:45); nothing inpackages/orweb/.vitepress/fetches a data file at run time (the onlyfetchin shipped code is the library host's,packages/manifest/src/libraries/host.ts:12). -
Tarballs.
tools/tarball-check/run.tspacks every package, installs only the.tgzfiles, and statically checks that every export target, everynew URL("../x", import.meta.url)file read (run.ts:232,327-337) and every import is in the tarball and declared (a dependency, peer or optional dependency,run.ts:296-301). Only a six-package core is published (tools/publish/prepare-core.ts:11;.github/workflows/publish-core.yml), and combinatorics is not in it. -
The
@enumeratio/*scope.AGENTS.md("Names") keeps it for data packages; none exists.packages/manifest/tests/hierarchy.test.tsrequires every package to sit in the layer hierarchy, and a library "may be in the tree or installed" (AGENTS.md, "Reference entries").
Counts are from Posets §2 (1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, measured through n = 9) and Unlabeled graphs §3 (measured through n = 8). A code has C(n,2) bits for both posets and graphs: 28 at n = 8, 36 at n = 9, 45 at n = 10; all fit a double. The estimates are from a script on a synthetic sample: that many uniformly random distinct-enough integers of that width, sorted, delta-encoded as LEB128 varints, gzip level 6 (stdlib only, one run, 31 s for the n = 10 case). Elias-Fano is the formula n·(2 + ⌈log2(2^bits / n)⌉) bits, not an encoder. Estimated on a synthetic sample. Real codes are not uniform, and the one real table measured is far smaller than its estimate: the 12,346 canonical ranks of the graphs on 8 vertices (Unlabeled graphs §2) are 12,901 bytes delta-varint, 1.04 bytes a rank, and 3,357 bytes after gzip, against 30 KB and 28 KB below. The ranks gather at the low end, because the least rank puts the edges on the low labels. The posets behave the same: the 183,231 canonical codes at n = 9 (Posets §11) are 201 KB delta-varint and 34 KB after gzip, against 543 KB and 520 KB below, and the 16,999 at n = 8 are 18 KB and 4.5 KB. So every row of the table is two to three times too large as varint and ten times or more too large after gzip, and gzip is worth having. The graphs at n = 9 and 10 are not generated; by the same ratio they are near 300 KB and 13 MB as varint (assumed).
| Table | Codes | Bits | Raw 64-bit | Packed bits | Delta-varint | + gzip | Elias-Fano |
|---|---|---|---|---|---|---|---|
| Posets n = 8 | 16,999 | 28 | 136 KB | 59 KB | 40 KB | 38 KB | 34 KB |
| Posets n = 9 | 183,231 | 36 | 1.47 MB | 825 KB | 543 KB | 520 KB | 481 KB |
| Graphs n = 8 | 12,346 | 28 | 99 KB | 43 KB | 30 KB | 28 KB | 26 KB |
| Graphs n = 9 | 274,668 | 36 | 2.20 MB | 1.24 MB | 806 KB | 759 KB | 687 KB |
| Graphs n = 10 | 12,005,168 | 45 | 96.0 MB | 67.5 MB | 41.8 MB | 39.1 MB | 36.0 MB |
Reading it:
- On the synthetic sample gzip over varint saves about 5%: random deltas have no redundancy left. On the real n = 8 graphs it saves three quarters. Elias-Fano is about 10% smaller than varint and can be searched without decoding; it is not worth its complexity below 1 MB.
- As a module: base64 of the varint bytes is 4/3 as long, about 0.72 MB (posets 9) and 1.08 MB (graphs 9) of source text (computed from the table).
- Decoding 183,231 varints into a
Float64Arrayis a single pass; I assume it takes milliseconds, not measured. A browser download of 0.5 MB is assumed sub-second on a normal connection. - The page's own n = 9 number: generation took 49 s in unoptimized single-thread Python (Speculative-Posets §1), 550,338 canonical-form calls. There is no measured time for the TypeScript kernel at any size.
- Graphs at n = 10 cost, at the module size above, about 56 MB of base64 source. Not viable as a module, and not worth shipping to a browser.
| A. No table | B. Generated module | C. Lazy binary asset | D. Committed snapshot | E. Data package | |
|---|---|---|---|---|---|
| File | none | gitignored *.generated.js in the package, built into dist
|
gitignored .bin under a shipped folder |
tracked findstat/data-style file |
@enumeratio/<name> package |
| Written by | kernel at run time | package build
|
package build
|
a collect-* script |
its own build or collect-*
|
| Dist cache | n/a | covered: ignored output (dist-cache.ts:16) |
covered, same | tracked file is in the key | its own unit; the library's key includes it only through reads
|
| Held to the kernel and Epsil by | the fast-kernel test | a test on the built file | same | a test; stale on a definition change unless it records a hash | same as B or D |
| From a tarball | works | works (inside dist) |
needs files entry and new URL(..., import.meta.url); tarball-check checks both |
needs files
|
a second tarball; optional dependency |
| Tarball cost | 0 | about +0.5 to 1.1 MB per table, text | about +0.5 to 0.8 MB, binary | same as C | zero in the library; the table in its own |
| First use | generate, per process |
import() plus decode |
fs read, or fetch plus decode |
same as C | same as B or C |
| Browser needs | nothing | async prepare | async prepare | async prepare | async prepare |
| Breaks | declines at n = 9 | async step; precache grows | two code paths; async step | repo rule if generation is cheap | scope, hierarchy, publishing |
A. No table. The kernel builds the classes of size n the first time it is asked and keeps them for the process (Speculative-Posets §2). It costs nothing to build, ship or cache, and needs no new mechanism; it breaks at the size where generation is too slow to do inside a worker's cooperative deadline (cooperative-evaluate.ts:1-8). Per-process caching means every browser tab and every new worker regenerates. The kernel's TypeScript generation time at n = 8 is not measured; the posets page asks for that measurement (answer 3). A holds through n = 8 if it is under about a second.
B. A generated module. A package script writes <name>.generated.js (ignored by the package's existing *.generated.js rule), exporting the varint bytes as a base64 string, or as a Uint8Array literal; vp pack puts it in dist, ideally as a chunk of its own. It follows the repo's rule exactly: derived from our own code, so built, gitignored and checked by a test, never committed (AGENTS.md, "Data derived from our own code is built, never committed"). The dist cache keys it by the package's sources and saves it as an ignored output with no change. From a tarball it works, since it is code inside dist (no files change, no new URL read for tarball-check to find). The costs are the source size (§1) and that the kernel needs the bytes before a synchronous call: Node can await import() only in an async function, and a browser worker likewise (§3). If the module is statically imported by the library, there is no async step, but every user of the library loads it, and the service worker precaches it for every visitor (service-worker.ts:29, 62-67). The test cannot be independent where the kernel built the table: the table equals the kernel's output by construction beyond what the Epsil definition reaches. What it can hold are independent facts: the count against A000112 (or A000088), sortedness, every code valid, and, in a deep run, the regenerated table. A Sage or nauty answer would be independent (see D).
C. A lazy binary asset. The same bytes as a .bin that is read on first use: readFileSync in Node, fetch in the browser. It saves the base64 overhead (25%) and keeps the bytes out of the JS chunk and the service worker's JS closure (service-worker.ts:29). It has two loaders, because fs does not exist in the worker and fetch does not exist as a sync call; the binary must be in files (combinatorics/package.json:7-12), referenced by a literal new URL("../data/x.bin", import.meta.url) that Vite recognizes (the same constraint as the worker URLs, web/.vitepress/theme/worker-factories.ts:1-30) and that tarball-check verifies (run.ts:232). Node is synchronous for free. The browser is not: kernel calls are synchronous, so there are three ways to bridge:
-
Preload on first mention. A declared async
preparethe kernel runs afterlibraries.ensureand before evaluating. The one place already awaited (kernel.ts:189-193) is the library declaration, and a per-head hook there is not known to exist (§3, open question 2). - Decline until loaded. The kernel returns "not loaded" and starts a fetch; the user re-evaluates. Never wrong, always poor. It is the fallback, not the design.
-
Synchronous
XMLHttpRequestin the worker. Workers allow it on the web platform (from memory, not checked here); it blocks the worker and the cooperative deadline does not interrupt it. Not recommended.
D. A committed snapshot. The repo commits a derived file only for "an external snapshot (a kernel's answers, a scrape, an expensive sweep)" written by its own collect-* script (AGENTS.md; the model is collect-findstat-data.ts). Is the sweep expensive? For posets n = 9 the Python run was 49 s; as a build step that is cheap beside the three-minute site build, and the dist cache skips it while the package is unchanged. So posets do not qualify on cost. Graphs n = 10 might: 12 M classes with our own TypeScript kernel is not measured and likely hours, assumed, from the 550,338 calls at n = 9. The stronger reason for D is independence: a table generated by geng (graphs) or Sage (posets; the repo has a Sage oracle lane) is a kernel's answers, so committing it is allowed by the rule, and it is an independent check on our kernel that B cannot be. The cost is that a committed file goes stale: a changed canonical code (the bit order of Speculative-Posets answer 2) silently invalidates it unless the file carries a hash of what it was made under (familyHash, epsil.ts:158) and a test refuses a mismatch. It enlarges the repository by the table size and adds an external tool to the collect script.
E. A separate data package. @enumeratio/<name>, in the scope the repo keeps for data packages, depending-on optionally from @notatio/combinatorics (optionalDependencies is accepted by tarball-check, run.ts:296-301). It keeps the library's tarball small, versions the data apart from the code, and is the only reasonable home for 36 to 42 MB. It breaks things: no data package exists, so the scope, the hierarchy rule (hierarchy.test.ts), publishing (only the six-package core is published, prepare-core.ts:11), the site (which resolves libraries from the catalogue, worker-catalogue.ts) and the dist-cache reads are each new. The library imports it dynamically inside try, and a missing package declines like an absent table. It is the right shape for graphs at n = 10 and the wrong first step for n = 9.
Names are placeholders. Nothing here exists.
/** A table the package built: the sorted codes of one fiber, delta-varint. */
export interface FamilyTable {
/** `posets-9`: the id the generated module is named for. */
readonly id: string;
/** The params whose fiber it holds, as the kernel reads them (`[9]`). */
readonly params: readonly number[];
/** Resolves to the table's bytes; Node and the browser both `import()` a module. */
readonly load: () => Promise<Uint8Array>;
/** Members it holds, and the `familyHash` of the definitions it was built under. */
readonly count: number;
readonly hash: string;
}
interface EpsilFamily {
// ...
/** Tables the fast kernel reads once `prepare` has loaded them; none is needed to be correct. */
readonly tables?: readonly FamilyTable[];
}
interface FastKernel {
// ...existing count / unrank / rank / valid ...
/** The decoded table for a fiber, or undefined: the kernel then declines (§ below). */
readonly stored?: (p: number[]) => Float64Array | undefined;
}
interface FamilyKernel {
// ...
/** Loads what a call at `p` will read; resolves at once when nothing is needed. */
readonly prepare?: (p: number[]) => Promise<void>;
}(tables as named on FamilyEpsil already means the DP-row expression, epsil.ts:34-37; the real name has to differ.)
-
Reads.
fast.unrankis an index into the decoded array;rankis a binary search;validis a binary search of the code after canonicalizing;countis the array length, or a constant held to it by the test. All four are synchronous oncepreparehas stored the array. -
Absent table.
stored(p)returnsundefined, sofast.*answersundefined(epsil.ts:44-47), the Epsil definition is tried, and where it cannot reach the fiber the kernel raises a decline whose message names the table (posets-9 is not loaded), as the existing decline does for 2^53 (epsil.ts:489-494). It never answers from a partial table, never rounds, never returns a guess. A table whosehashdiffers from the family's current hash is treated as absent. -
Who calls
prepare. The host, afterlibraries.ensureand beforeevaluate(kernel.ts:189-193), for the heads the input names. Node does the same in its own entry; a plaince.evaluatecall in a test calls it first, or the test uses the fast-kernel harness. Whetherensurecan pass head names to a family'sprepareis the first thing to read inpackages/manifest/src/libraries/(open question 2). -
Tests. (1) The built table's count equals the independent count (A000112 / A000088), codes ascending, each valid. (2) For fibers the Epsil definition reaches,
tests/fast-kernels.test.tsalready holds the fast kernel to it; add the table-backed path to its grid. (3) A deep test (DEEP_TESTS=1,AGENTS.md, "Long sweeps run nightly") regenerates the table with the kernel and compares. (4) A test that the kernel declines, with the message, when the table is removed.
-
Measure on a build box, not here: the TypeScript kernel's time to generate posets n = 8 and n = 9 and graphs n = 8 and n = 9 (the numbers every option turns on); the real delta-varint size of those tables (the synthetic sample is an upper bound only if real codes are more clustered); the decoded size in memory; and the size of the existing
dist/and the combinatorics chunk the site loads, so the added 0.5 to 1.1 MB has something to be compared to. - If n = 8 generation is under about a second, ship the posets collection through n = 8 with option A and stop (the posets plan, unchanged).
- Otherwise or for n = 9: add the build step that writes
posets-9.generated.jsinto the combinatorics package (one script besidescripts/build-generated.ts, listed under"generated",package.json:93-97), and the one new test (count 183,231, ascending, valid). Do not addprepareyet: let a Node-only consumer read it with a static import in a test, and prove the byte format and the cache. - Add
prepare, once step 1 has shown whether the declare path has a per-head hook. If it has none, move the table into a separate pack entry the library imports on demand and makepreparethe library declaration itself. - Run
node tools/tarball-check/run.tsand read the report for the added module; confirm the service-worker precache list (precacheList) and the page-weight test's thresholds (web/.vitepress/theme/page-weight.test.ts) move as predicted. - Graphs: repeat for n = 9 once the graph kernel exists. For n = 10 write the
geng-basedcollect-*script and put the result in a data package (E), or do nothing.
-
Is a table written by our own build allowed to be checked only by counts and by regeneration? Recommended: yes for B, with the counts coming from OEIS/Sage, and a deep regeneration test. The rule forbids committing derived data, and the independent check the table lacks is the external count; a committed
gengor Sage table (D) is optional, for graphs n = 10 only. -
Does the declare path have a per-head hook for
prepare? Recommended: readpackages/manifest/src/libraries/(ensure, the registry) before choosing between a per-head hook and a library-level load. If a library-level load is the only granularity, put each table in its own pack entry and haveprepareimport it, rather than paying every user for every table. -
Where does the table bit order come from? Recommended: the pair numbering of
LabeledGraphs(Speculative-Posets answer 2), settled before any table is built, because the table is a built artifact that changes with it and the posets page leaves it open. -
Do posets n = 9 and graphs n = 9 ship at all? Recommended: yes after step 1, because the crosscheck needs no collection (Speculative-Posets §5) but
Posets(9)as a catalogue entry does. If step 1 shows generation under a few seconds, defer. -
Binary assets (C) or modules (B)? Recommended: B. It costs 25% more bytes and a base64 decode, and it saves the
filesentry, thenew URLliteral, the Vite recognition constraint and thefs/fetchsplit. Revisit only if a table passes about 2 MB. -
Is a 36 to 42 MB graphs n = 10 table in scope? Recommended: no. Decline with a message at n = 10, as
IsIsomorphicGraphdeclines past 9 vertices today; build the data package (E) only if someone needs the collection. -
Name of the mechanism. Recommended: not
tables, which already means the DP-row expression (epsil.ts:34-37); something likestoredorsnapshot, with the word "table" kept for the old meaning.
Measured (read from the tree): tables, FastKernel, FAST_LIMIT and where the kernel declines; that kernel functions are synchronous; the worker and message structure; the awaited libraries.ensure and async combinatorics import; the service-worker precache closure; the build's generated lists and the .gitignore rule; the dist cache's "every ignored file" rule; the tarball-check rules; files and exports of the combinatorics package; the sizes of the committed data files above.
Estimated (synthetic sample): every delta-varint, gzip and Elias-Fano figure in §1 and the totals derived from them (base64 lengths; 56 MB for graphs n = 10 as a module). Raw and packed sizes are exact arithmetic on the counts and bit widths.
Assumed or unknown: generation time of the TypeScript kernel at every size; the real delta size of the graphs at n = 9 and 10; decode time and download time; that a hashed non-JS asset is cached by service-worker.js:62; whether libraries.ensure can carry a per-head prepare; the CLI's evaluation path; that synchronous XMLHttpRequest is allowed in a worker (from memory); that 12 M graphs from our own kernel takes hours; that geng and Sage can produce the tables (from memory); the size of any build output (not built here); whether optionalDependencies for an @enumeratio/* package passes the hierarchy test; class counts beyond those taken from Speculative-Posets.