diff options
Diffstat (limited to 'chapter32/README.md')
| -rw-r--r-- | chapter32/README.md | 485 |
1 files changed, 195 insertions, 290 deletions
diff --git a/chapter32/README.md b/chapter32/README.md index d7ca40db..467b1792 100644 --- a/chapter32/README.md +++ b/chapter32/README.md @@ -4,304 +4,209 @@ English | [日本語](README.ja.md) [Previous: Chapter 31 — Software Drawing, Time, and Graphical Games](../chapter31/README.md) -Chapter 31 completes the graphics, games, and library work. This chapter keeps -that language and those programs, then investigates the cost of compiling and -testing them. Larger programs have made repeated graph walks, unnecessary -worklist visits, and uneven test parallelism visible in the test runtime. - -The starting changes address four costs: test JVM scheduling, scratch-state -cleanup in type queries, expensive verification, and overly broad optimizer -notifications. Each change keeps the existing native and evaluator coverage. - -## Measure the work before changing it - -A test suite includes Java startup, JIT compilation, assertions, compiler -passes, native compiler/linker subprocesses, and execution of generated code. -Timing the suite alone does not identify which part is growing. Likewise, -adding the timings of parallel JVMs does not give elapsed time. - -The investigation used JFR and temporary counters around compiler phases, -`_iter.iterate()`, expensive checks, and native subprocesses. Counters separate -worklist peepholes from the extra peepholes performed by verification. A -separate sample records the first accepted enqueue and follows it until the -node is popped, relating a null result to the code that scheduled the visit. -Duplicate pushes while a node is already queued are coalesced by the worklist. - -Use identity maps for bookkeeping keyed by Nodes. `Node.hashCode()` participates -in GVN locking; an ordinary HashMap used by a profiler can change compiler state. -The investigation helpers stay outside the production compiler. - -## Give independent tests independent JVMs - -The older Makefile ran chapter cohorts in parallel, but put the remaining tests -into one JVM. That last process became the long tail of `make -j 8 tests`. -The [Makefile](Makefile) divides those tests into eight measured groups, keeping -each class and its fixtures together. New test classes join the last group -automatically, so the grouping cannot silently omit them. - -Each JVM defaults to `-XX:ActiveProcessorCount=2`. This sizes its JIT and GC -thread pools for a share of the machine instead of letting every concurrent -JVM size itself for all cores. The limit does not pin the process to CPUs. - -Native tests create objects and executables with common filenames. -[TestWorkspace](src/test/java/com/seaofnodes/simple/TestWorkspace.java) gives -each group a working directory under `build/tests`, refreshing its fixtures -and native libraries before the run. Classes and JARs are shared through an -absolute classpath. The groups can then run without overwriting each other's -generated programs. - -The exhaustive [lattice test](src/test/java/com/seaofnodes/simple/TypeTest.java) -partitions its outer type loop across four JVMs. Together they check every -pair and triple. Separate processes also isolate the mutable type interning -and traversal state. A direct JUnit or IDE invocation still runs the complete -lattice test in one JVM; part zero of the Make run also runs the other type tests. - -## Shallow type queries need no recursive scratch state - -[Type.isConstant and Type.isFinal](src/main/java/com/seaofnodes/simple/type/Type.java) -used to wrap their queries in `recurOpen`/`recurClose`. That made sense when -constant detection could follow pointers into cyclic structures. The current -rules stop at the pointer: constantness tests its identity, and finality tests -its access qualifier. Struct queries inspect their fields without following -pointer referents. - -These queries therefore do not need to clear the shared traversal map, mark -visited structs, or treat a repeated visit as success. Removing that bookkeeping -keeps the existing answers and avoids repeated scratch-state cleanup. Recursive -operations that actually traverse or construct cyclic types retain their own -recursion machinery. Type tests cover repeated fields, cyclic singleton -pointers, and finality qualifiers. - -## Sample expensive verification - -The optimizer checks a strong invariant: a live node is either on the worklist -or cannot make progress. Testing it walks the entire graph and tries peepholes -again. `schedulableUses` also walks the graph to check that inputs and uses admit -a legal schedule. Running such checks too often can dominate the transformation -being checked. - -[CodeGen](src/main/java/com/seaofnodes/simple/codegen/CodeGen.java) now defaults -`simple.assert.expensive` to log 10 rather than 8, sampling one eligible step in -1,024. [IterPeeps](src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java) -checks scheduling at the end of the completed fixed point instead of after -every intermediate inlining batch. Entry, periodic, and phase checks remain. -Ordinary assertions remain enabled in the test harness. - -The verification-only change left the measured worklist visits identical at -4,463,457. Assertion-only peepholes fell from 5,295,983 to 1,910,132, and measured -checking time inside `iterate()` fell from 12.36 to 4.08 seconds. - -## Wake nodes for changes they actually read - -`listener.addDep(source)` puts the listener on the source's dependency list. -Later, `source.moveDepsToWorklist()` schedules those listeners. Notifications -can follow type changes, edge edits, or use-count changes. An unnecessary -subscription can therefore cause many visits even if the source's type never -changes. - -### Outside state is needed only for opaque arguments - -[SummaryNode](src/main/java/com/seaofnodes/simple/node/SummaryNode.java) and -[CallNode](src/main/java/com/seaofnodes/simple/node/CallNode.java) requested -`Start.outside` unconditionally while computing exposed escapes. That request -registers a dependency on Start. Deleting constants changes Start's users and -can wake every registered summary. - -But `TypeMem.escapesFrom(argument, outside)` consults `outside` only for an -opaque argument. The callers now use that same condition before requesting -outside state. Dependencies on argument types remain: if an argument later -refines to an opaque type, it wakes the reader, which installs the needed Start -dependency. The return-state dependencies of external CallEnds remain intact. - -### Removing a constant argument should not wake unrelated callers - -[RegionNode.removeDeadPath](src/main/java/com/seaofnodes/simple/node/RegionNode.java) -used to schedule every user of each removed Phi input. During inlining, common -constants can be shared by parameters throughout the program. Removing one -argument caused a broadcast to many unrelated functions. - -For a constant input, the code now schedules the changed Phi. Nonconstant -inputs retain the broader notification, and the Phi's outputs still receive -their notification. - -Stronger verification exposed a dependency on the old broadcast: -`CallNode.unlink` removed parameter inputs without scheduling the edited Parms. -Those nodes need another visit even when their types stay unchanged, because -editing their inputs removes them from GVN. Unlink now queues the parameters it -actually edits. A focused regression checks this independently of later cloning. - -### Results and remaining work - -With verification held at the new setting, the two filters produced: - -| Worklist peepholes | Before | After | -|---|---:|---:| -| SummaryNode | 455,186 | 50,623 | -| ParmNode | 700,827 | 373,604 | -| All nodes | 4,463,457 | 3,695,609 | -| Null returns | 4,140,886 | 3,371,682 | -| Null percentage | 92.8% | 91.2% | - -That is 17.2% fewer live worklist visits. Measured `iterate()` wall time fell -from 14.24 to 11.97 seconds; the serial profiled suite fell from 98.53 to 93.37 -seconds. These are individual Windows/JDK 21 runs with JFR and enqueue sampling, -not portable performance guarantees. The baseline had 792 test methods; the -final run included two additional regressions. The parallel uninstrumented -Make run took 28.8 seconds and passed 797 executions, including the additional -lattice partitions. The full suite also passed at log 8, with focused tests -at log 1. These measurements were taken before creating the chapter snapshot. - -A null return does not always mean wasted work: `peepholeOpt` can reinsert an -unlocked node into GVN and still return null. Some null-returning nodes are then -killed as unused. Already-dead pops are counted separately from this table. - -Dependency notifications accounted for only 28% of sampled baseline null-return -visits. Most came from direct scheduling. The largest remaining candidates are -MemPhi input requeues during Lower and IfNode dominator dependencies. The latter -also wake on use-count changes. Any narrower filter must preserve the topology -and use-count changes that actually enable a rewrite; deleting subscriptions -just because a sample showed no progress is not enough. - -### MemPhi and IfNode follow-up - -The next trace records the notifying node as well as the enqueue stack. -BulkMemPhi splitting and MemMerge cleanup repeatedly queue precise memory Phis -as inputs of successful peepholes. Removing memory Phis also changes a Region's -users, waking IfNodes which subscribed while walking the dominator chain. -Unlinking callers produces similar notifications from CallNodes. - -Two small filters are retained. A type-only update of a user no longer queues -an already-used, stable MemPhi input. New or edited inputs and first-use Phis -remain eligible; replacement and edge-edit notifications retain their existing -behavior. `IfNode.idealize` searches dominators only when both branches remain -possible. Known branches already fold through CProj and need no new distant -subscriptions. - -On the same 794-method profiling sweep, MemPhi visits fell from 474,510 to -469,866, IfNode visits from 254,787 to 249,609, and total visits from 3,695,609 -to 3,661,560. The total reduction is 0.9%; whole-suite elapsed times of 91.88 -and 91.64 seconds do not establish a meaningful timing improvement. Existing -spill expectations still pass. One graph expectation loses a redundant integer -narrowing; both branches also have execution checks. - -A broader experiment separated dependency use-count notifications from type -and input-edge notifications, and filtered more MemPhi use-count revisits. -That version changed optimizer ordering enough to increase the Sieve spill -score from 216 to 343 and the forward-field example from 23 to 31. It is not -enabled: reducing compiler work is not a reason to silently raise code-quality -expectations. The broader filter also requires notifying a node's dependents -when `delDef` changes its inputs, rather than redundantly notifying the old -input's use-count listeners. - -In the 302-method non-chapter group, that isolated experiment reduced MemPhi -visits from 367,387 to 205,245 and IfNode visits from 144,652 to 59,185. Total -visits fell 9.7%, but elapsed time was essentially unchanged at 57.48 versus -57.75 seconds. Fewer visits alone do not demonstrate a runtime improvement. - -These measurements precede the verifier fixes below. - -### Every-step verifier fixes - -Checking every progress step exposed two bugs, both reproducible before the -MemPhi/IfNode filters: - -- `Chapter05Test.testMerge4` fails at iteration 38: replacing `Phi#44` with - `arg` changes `If#52`'s predicate and enables `Phi#75`'s guard-merge rewrite. - `matchingGuardMerge` had no dependency on that predicate comparison. It now - subscribes to the If for direct input edits and to its predicate for replacement - through `subsume`. Tests cover both notification paths. -- `Chapter15Test.testArrayLoadDominatingControl` fails at iteration 30, when a - bulk memory Phi splits into a MemMerge. The verifier treated the consuming - load's earlier range-check control as its execution block. A memory operation's - control is only a lower bound: its data inputs can force it later. The check - now includes those inputs, matching early scheduling. Regression tests accept - this legal placement and still reject a load used before its memory is ready. - -After these fixes, all 802 suite executions pass at log 8; 444 chapter tests and -34 focused worklist, scheduling, and memory tests pass at log 1. Existing spill -expectations are unchanged. - -### Dense MemMerge inputs - -`MemMergeNode` now keeps precise alias slices in a dense input list, with an -`IntHashMap` from alias to input index and a reverse array for iteration. -Alias order is preserved. Missing aliases use input 1, the bulk default. -Deletion compacts the list and rebuilds the small map; graph copies own their -maps. Bulk-Phi splitting and object loading use alias lookup rather than -assuming an alias is an input index. The existing sparse object encoding remains -compatible with the baseline compiler. - -This is deliberately a storage experiment. `_aliasLimit` retains the previous -sparse extent for encoding and fold eligibility. The old `allDefault` test -counts null holes as non-defaults; simply folding whenever the dense list is -empty introduces additional optimizations. That separate trial altered code -quality: graphical Tic-tac-toe's weighted spill score rose from 1085 to 1240 -with its rebuilt library. The retained version preserves the old folding -behavior and matches baseline peephole counts, code sizes, and spill counts on -all measured workloads. - -Against commit `8b80d94c`, the final interleaved comparison measured: - -| Workload | Compile time change | Compiler-thread allocation change | -| --- | ---: | ---: | -| sys library | -5.8% | -3.7% | -| Clock | -2.1% | -10.8% | -| Breakout | -2.9% | -6.4% | -| Graphical tic-tac-toe | -0.5% | -5.3% | -| HelloWorld | -0.6% | -4.5% | - -The timing improvement is modest; sub-percent differences are within noise. -The structural reduction is much larger. After Lower, sys's live MemMerge input -slots fall from 54,388 to 2,462, Clock's from 54,255 to 2,237, and Breakout's from -61,286 to 2,592. These are input-slot counts, not total heap measurements; the -maps and reverse arrays have their own cost. - -Measurements use Java 21, assertions at log10, two active processors, and a -256 MiB initial / 2 GiB maximum heap. The compiler runs through object export, -without gcc, linking, or execution. Isolated compiler class loaders alternate -in one JVM; six measured rounds follow three warmups for each workload. Games -read the same baseline sys objects. Time changes are medians of paired ratios; -allocation uses ThreadMXBean. Earlier separate-process runs drifted enough that -the interleaved comparison is the basis for the table. - -The full suite passes at log8; 444 chapter tests and 18 memory/import tests pass -with every-step verification. Raw measurements, saved compiler classes, and -reproduction commands are in `build/memmerge-dense/`; verification logs are in -`build/test-profile/dense-final-*.log`. - -## Build and test - -From `chapter32`, using the existing offline dependency caches: +The games and libraries from chapter 31 made both compiling and testing slow +enough to interrupt development. This chapter makes room for future work: +faster feedback for Simple's developers, and faster compilation for its users. + +| What improved | Result | +| --- | --- | +| Repeated compilation | 29–79% less compile time for the large workloads below | +| Development testing | Roughly 30 seconds for a full run → 8.8 seconds for sanity checks; the full suite now takes 22.8 seconds | +| IR stored in ELF files | 21.9% smaller across 26 objects | + +The compiler figures isolate the allocator-scratch fix in repeated compiles. +The testing gain includes a deliberate coverage tradeoff. The sections below +explain what changed and what each measurement covers. + +## Faster development of Simple + +### Measure the work and the wait + +A test run starts JVMs, compiles Java methods, runs the compiler, checks +assertions, links native programs, and executes them. In one serial profiling +run, compiler phases took 29.7 seconds and 153 GCC calls took another 29.8, +mostly linking. Compiler optimization could address only part of the cost. + +Parallel testing has the "tallest pole" problem: we wait for the last worker. +The [Makefile](Makefile) now splits the former catch-all JVM into balanced +groups, with private native outputs. Each JVM sizes its JIT and GC pools for +two processors. Eight Make jobs beat both four and sixteen on this host. + +| Command | Coverage | Warm elapsed time | +| --- | --- | ---: | +| `make -j8 sanity` | Full lattice, chapter/backend tests, saved fuzzer regressions, focused compiler tests | 8.8 s | +| `make -j8 tests` | All of the above, plus remaining library, application, and CLI integration | 22.8 s | + +These runs use Windows, Java 21, and a 10-core/20-thread i9-10900K, with builds +already up to date. They execute 680 and 819 tests respectively, including the +lattice partitions. Assertions stay enabled. Use the full suite before finishing +a change, especially when working on libraries or interfaces omitted by `sanity`. + +Routine savings came from cheaper fixtures: loop over the division/remainder +matrix instead of generating 200 conditional checks; share native programs +between formatting cases; compile two small modules for an assembly-dump test +instead of all of `sys`. The full suite's GCC calls fell from 153 to 141. + +### Keep the full lattice, with fewer repetitions + +The [lattice test](src/test/java/com/seaofnodes/simple/TypeTest.java) stays in +the sanity run. Compiler transformations depend on its laws, so we reduced +repetition rather than sampling fewer types. + +First, format assertion messages only on failure. Doing that inside the cubic +loop reduced the standalone run from 10.6 to 4.5 seconds. Next, cache pairwise +meets and joins, computing both operand orders before checking commutativity. + +Associativity formerly visited all `n^3` ordered triples. Now it visits +`i <= j <= k`, including repeated operands: `n(n+1)(n+2)/6` iterations. Each +visit compares all six results: -```sh -make -j 8 release -make -j 8 tests_nographics -make test CLASS=TypeTest ``` +(a & b) & c c & (a & b) +(a & c) & b b & (a & c) +(b & c) & a a & (b & c) +``` + +Once the original pairs commute, the six original associativity equalities +connect these results in a cycle. Comparing them to one common result checks +the same property. We must retain both operand orders involving intermediate +types: `a & b` may be outside the gathered set, so its commutativity has not +yet been established. -On a fresh checkout, run `make libs` once while online to populate the caches. -The ordinary builds and tests do not download dependencies or open windows. +All comparable-pair monotonicity checks remain. The complete unpartitioned +TypeTest now takes about 0.7 seconds. Make still partitions it across four +JVMs, each with private type-interning state. -Override JVM sizing with `TEST_JAVA_OPTS`. For example: +## Faster compilation for Simple users + +### Wake nodes when something relevant changes + +`listener.addDep(source)` asks to wake a node when the source changes. +Registering extra dependencies is easy; paying for them happens later. + +Tracing enqueues exposed two broad notifications. Calls and summaries read +`Start.outside` even when their arguments did not need it, subscribing them to +unrelated changes. They now read it only for opaque arguments. Removing a +constant Phi input also woke every user of that constant throughout the +program. It now queues the changed Phi. + +These filters cut worklist visits from 4.46 million to 3.70 million, or 17.2%. +Time inside `iterate()` fell from 14.24 to 11.97 seconds. Further MemPhi and +IfNode filters reduced visits slightly without a measurable timing gain. +Fewer visits alone are not proof of a faster compiler. + +Broad notifications can hide missing dependencies. Stronger verification found +nodes that had relied on accidental wakeups, including a Phi whose guard-merge +rewrite became possible after an If predicate changed. Checking every progress +step isolated the peephole that exposed the missing dependency. + +Normal runs sample expensive checks every 1,024 eligible steps, retaining entry +and completed-phase checks. Use `-Dsimple.assert.expensive=1` to check every +progress step while diagnosing a failure. Ordinary assertions remain enabled. + +### Give scratch data the lifetime of the work + +[RegAlloc](src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java) already +allocated one function at a time, but its interference-graph helper retained +basic-block keys from every previous allocation. Each `sys` compile added +another 2,558 keys to clear on later runs. + +Each function now owns its [IFG](src/main/java/com/seaofnodes/simple/codegen/IFG.java) +scratch maps. They survive spill retries, then become unreachable when allocation +finishes. Spill scoring also computes the function's area once per coloring +attempt instead of walking the blocks for each candidate. + +| Program | Before | After | +| --- | ---: | ---: | +| `sys` library | 1,290 ms | 913 ms | +| Clock | 537 ms | 279 ms | +| Breakout | 1,007 ms | 609 ms | +| Graphical tic-tac-toe | 1,362 ms | 292 ms | + +These medians isolate that change: six measured compiles after three warmups, +alternating baseline and changed compilers, with the same library and assertions +enabled. They include object export but exclude linking. The old compiler +accumulated keys during warmup too; this measures repeated compilation, not +fresh command-line startup. Machine-code bytes matched in all 26 objects checked. + +### Remove empty space and unnecessary allocation + +[MemMergeNode](src/main/java/com/seaofnodes/simple/node/MemMergeNode.java) +used alias numbers as input indices, leaving mostly null slots supplied by +the default memory value. A dense list plus an alias-to-input map cut `sys`'s +live MemMerge input slots from 54,388 to 2,462. That change alone reduced its +compile time by 5.8%, while preserving folding behavior and generated code. + +Other savings were straightforward: remove recursive scratch-state setup from +the shallow `isConstant` and `isFinal` queries; use node-ID BitSets for load-fold +visits; stop collecting a packed-value histogram left over from profiling. +The latter two changes reduced `sys` compiler-thread allocation from 119.6 to +69.4 MiB and median compile time from 1,017 to 942 ms. These are separate +comparisons, not cumulative chapter-wide timings. + +### Make saved compiler state smaller + +ELF's `.simple` section stores reloadable IR, declarations, and import metadata. +It occupied 79% of the measured `sys` objects. Three encoding changes removed +avoidable overhead: gradual growth for packed integers, explicit MemMerge +alias/input pairs instead of default holes, and a wider compact encoding for +singleton function IDs. Strings retain raw UTF-8 bytes. + +| `.simple` payload | Before | After | Reduction | +| --- | ---: | ---: | ---: | +| `sys`, all 22 modules | 469,881 bytes | 368,694 bytes | 21.5% | +| Clock | 43,854 bytes | 31,906 bytes | 27.2% | +| Breakout | 80,950 bytes | 62,139 bytes | 23.2% | +| Graphical tic-tac-toe | 44,353 bytes | 35,961 bytes | 18.9% | +| HelloWorld | 14,635 bytes | 11,523 bytes | 21.3% | + +Across these 26 objects, the payload shrank by 143,450 bytes, or 21.9%, with +identical machine code. Compile timings showed no consistent improvement; +the demonstrated gain is smaller saved compiler state. + +## Keep the generated code good + +Changing worklist order can change rewrites and register allocation. Some +broader notification filters increased register copies, so we did not keep +them. Judge a compiler speedup by compile time, memory use, and generated code +together. + +Correctness fixes uncovered here belong in their teaching chapters: +[Phi factoring after strength reduction in chapter 5](../chapter05/README.md#factoring-after-strength-reduction), +and shared class receivers in [chapter 28a](../chapter28a/README.md#globals-use-the-same-receiver-as-fields) +and [chapter 28b](../chapter28b/README.md). + +## Build and use this chapter + +From `chapter32`, populate the dependency cache once with `make libs` if needed. +Ordinary builds use that cache and do not download dependencies. ```sh -make -j 4 tests_nographics TEST_JAVA_OPTS=-XX:ActiveProcessorCount=4 -make test CLASS=EscapeFlowTest "TEST_JAVA_OPTS=-XX:ActiveProcessorCount=2 -Dsimple.assert.expensive=1" +make -j8 release +make -j8 sanity +make -j8 tests ``` -Log 1 checks every progress step; log 8 restores the preceding sampling rate; -log 0 disables these expensive checks while retaining ordinary assertions. +For a fully headless full run, use `make -j8 tests_nographics`. It disables the +optional MiniFB and miniaudio backends. The packed IR header changes from `C0DE` +to `C0D2`; the reader rejects the older format. Run `make clean` before +`make -j8 release` to rebuild old objects, and rebuild any separately maintained +Simple libraries too. -## Language, libraries, and examples - -The [grammar and parser map](docs/32-grammar.md) describes this snapshot. -Language and library additions are taught in [Chapter 31](../chapter31/README.md). -Their implementations and runnable examples are also present here: +Run one class, or enable every-step verification for a focused investigation: -- [Examples and launch commands](docs/examples/README.md), including Clock, - Breakout, and graphical tic-tac-toe. -- [Drawing](src/main/smp/sys/draw/README.md), [window/input](src/main/smp/sys/gfx.md), - [audio](src/main/smp/sys/audio.md), and [time](src/main/smp/sys/time/README.md). -- [Math and intrinsics](../chapter31/README.md#math-support-and-intrinsics). +```sh +make test CLASS=TypeTest +make test CLASS=WorklistTest "TEST_JAVA_OPTS=-XX:ActiveProcessorCount=2 -Dsimple.assert.expensive=1" +``` -Future compiler and language proposals remain in the [roadmap](../docs/roadmap.md). +The [grammar and parser map](docs/32-grammar.md) describes this snapshot. +[Chapter 31](../chapter31/README.md) teaches its language and library additions; +the [examples](docs/examples/README.md) include launch commands for the games. +Library references live with [drawing](src/main/smp/sys/draw/README.md), +[window/input](src/main/smp/sys/gfx.md), [audio](src/main/smp/sys/audio.md), and +[time](src/main/smp/sys/time/README.md). Further projects belong in the +[roadmap](../docs/roadmap.md). + +Use the fast checks while editing. Run the full suite before finishing, and +turn up verification when a failure needs a closer look. |
