russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
259 lines
6.8 KiB
ReStructuredText
259 lines
6.8 KiB
ReStructuredText
Benchmark Methodology and Results
|
||
===================================
|
||
|
||
.. contents:: :local:
|
||
|
||
Methodology
|
||
-----------
|
||
|
||
Benchmarks are conducted at two levels:
|
||
|
||
**Unit level (operation count):** Each unit test instruments the defective and fixed
|
||
implementations with a comparison counter. The test measures exact operation counts for
|
||
specific input topologies, not wall-clock time. This eliminates JIT warm-up, GC pauses, and
|
||
system load as variables. The operation count is deterministic and verifiable by formula.
|
||
|
||
**Integration level (wall-clock timing):** Integration tests measure real execution time
|
||
against the actual shipped tool (``javac``, etc.) using ``--patch-module`` or equivalent
|
||
mechanisms to swap the patched implementation against the installed binary. These tests use
|
||
worst-case input topologies at multiple values of V to measure growth curves.
|
||
|
||
The growth curve test is the key measurement: if the before/after ratio grows with V, the
|
||
defective implementation is super-linear; if it is constant, it is linear. For javac-0001,
|
||
the ratio grows from 8x at V=200 to 23x at V=800 — consistent with O(V²) vs O(V).
|
||
|
||
Test Infrastructure
|
||
-------------------
|
||
|
||
All benchmark infrastructure is in ``tests/`` relative to the repository root:
|
||
|
||
- ``tests/unit/`` — 6 suites, one per javac defect, operation counts
|
||
- ``tests/integration/InferenceGraphScalingTest.java`` — real GraphUtils.tarjan() timing
|
||
- ``tests/functional/CompilerBenchmarkTest.java`` — real javac compilation
|
||
- ``tests/bench/AllDefectsBenchmark.java`` — consolidated before/after table (reference impls)
|
||
- ``tests/bench/benchmark-real.sh`` — before/after using ``--patch-module`` against installed JDK
|
||
- ``tests/Makefile`` — ``make all``, ``make bench-all``, ``make bench-real``
|
||
|
||
To reproduce:
|
||
|
||
.. code-block:: bash
|
||
|
||
cd tests/
|
||
make bench-real
|
||
|
||
javac Benchmark Results (Confirmed)
|
||
-------------------------------------
|
||
|
||
These are the only benchmarked defects as of 2026-03-23. All five javac patches have unit-test
|
||
proof. javac-0001 has full integration and end-to-end benchmarks. javac-0002a/b are source-only
|
||
patches (API drift blocks JDK 21 recompilation); javac-0004 and javac-0005 are compiled but
|
||
not yet integration-benchmarked.
|
||
|
||
javac-0001 (GraphUtils.java Tarjan SCC)
|
||
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
||
|
||
**Topology:** ``starWithBackEdges(V)`` — one hub node connected to V spokes, each spoke with
|
||
a back-edge to the hub. This is the worst-case topology for Tarjan SCC with the defective
|
||
stack membership implementation.
|
||
|
||
**Operation counts (unit test):**
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
|
||
* - V (nodes)
|
||
- Before (comparisons)
|
||
- After (comparisons)
|
||
- Formula before
|
||
- Formula after
|
||
* - 10
|
||
- 54
|
||
- 9
|
||
- V*(V+1)/2 - 1 = 54
|
||
- V - 1 = 9
|
||
* - 100
|
||
- 5,049
|
||
- 99
|
||
- 5,049
|
||
- 99
|
||
* - 200
|
||
- 20,099
|
||
- 199
|
||
- 20,099
|
||
- 199
|
||
* - 800
|
||
- 320,399
|
||
- 799
|
||
- 320,399
|
||
- 799
|
||
|
||
**Wall-clock timing (integration test, JDK 21 --patch-module):**
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
|
||
* - V (nodes)
|
||
- Before (ns)
|
||
- After (ns)
|
||
- Speedup
|
||
- Growth ratio (before)
|
||
- Growth ratio (after)
|
||
* - 200
|
||
- 60,040
|
||
- 7,428
|
||
- 8x
|
||
- —
|
||
- —
|
||
* - 800
|
||
- 703,732
|
||
- 30,736
|
||
- 23x
|
||
- 3.89x (200→800)
|
||
- 1.98x (200→800)
|
||
|
||
**Interpretation:** Growth ratio 3.89x over a 4x increase in V is consistent with O(V²)
|
||
(expected ratio: 4² / 4 = 4). Growth ratio 1.98x is consistent with O(V) (expected: ~2).
|
||
The speedup increases with V — the defect worsens quadratically.
|
||
|
||
javac-0002a Operation Count (QueryAll)
|
||
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
|
||
* - N (type vars)
|
||
- Before (comparisons)
|
||
- After (comparisons)
|
||
* - 10
|
||
- 55
|
||
- 10
|
||
* - 100
|
||
- 5,050
|
||
- 100
|
||
* - 500
|
||
- 125,250
|
||
- 500
|
||
|
||
Formula: before = ``N*(N+1)/2``, after = ``N``.
|
||
|
||
javac-0002b Operation Count (Closure)
|
||
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
|
||
* - V (nodes), K (calls)
|
||
- Before (comparisons)
|
||
- After (comparisons)
|
||
* - V=100, K=10
|
||
- 1,000
|
||
- 109
|
||
* - V=500, K=10
|
||
- 5,000
|
||
- 509
|
||
* - V=100, K=50
|
||
- 5,000
|
||
- 149
|
||
|
||
Formula: before = ``K*V``, after = ``V + (K-1)``.
|
||
|
||
javac-0004 Operation Count (AddUnique)
|
||
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
|
||
* - M (dependencies)
|
||
- Before (comparisons)
|
||
- After (comparisons)
|
||
* - 10
|
||
- 45
|
||
- 10
|
||
* - 100
|
||
- 4,950
|
||
- 100
|
||
* - 500
|
||
- 124,750
|
||
- 500
|
||
|
||
Formula: before = ``M*(M-1)/2``, after = ``M``.
|
||
|
||
javac-0005 Operation Count (IsEquiv)
|
||
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
|
||
* - B (type bounds)
|
||
- Before (comparisons)
|
||
- After (comparisons)
|
||
* - 10
|
||
- 110
|
||
- 10
|
||
* - 50
|
||
- 2,550
|
||
- 50
|
||
* - 200
|
||
- 40,200
|
||
- 200
|
||
|
||
Formula: before = ``B*(B+1)``, after = ``B``.
|
||
|
||
End-to-End Compiler Benchmark (javac)
|
||
---------------------------------------
|
||
|
||
The end-to-end benchmark compiles real Java source with type-inference-heavy expressions
|
||
(multiple overloaded generic methods, chained lambda expressions) using the patched javac.
|
||
|
||
**Result:** Noise-level improvement. Typical type-inference call sites in real Java source
|
||
have V = 4–6 type variables per expression. At V=5 the savings is
|
||
(5*(5+1)/2 - 1) - (5-1) = 14 - 4 = 10 comparisons per Tarjan call — tens of nanoseconds,
|
||
buried under parser and codegen cost.
|
||
|
||
**Interpretation:** The algorithm is now correct O(V+E). The impact at typical call sites is
|
||
small in absolute terms. The defect becomes significant at scale: code with many generic
|
||
parameters (deeply nested generic types, complex overload chains, high-arity tuples) will
|
||
show measurable regression in compile time with the defective implementation.
|
||
|
||
Pending Benchmarks
|
||
-------------------
|
||
|
||
The following defects have patches but no integration benchmarks yet:
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
|
||
* - Defect
|
||
- Ecosystem
|
||
- Blocker
|
||
* - javac-0002a, javac-0002b
|
||
- OpenJDK
|
||
- API drift vs JDK 21 — requires full JDK build
|
||
* - ghc-0001 through ghc-0004
|
||
- GHC
|
||
- Patch not yet written
|
||
* - ts-0001, ts-0002, ts-0003
|
||
- TypeScript
|
||
- Patch not yet written
|
||
* - scala3-0001
|
||
- Scala 3
|
||
- Patch not yet written; CRITICAL priority
|
||
* - All others
|
||
- Various
|
||
- Patch not yet written
|
||
|
||
Benchmark Replication
|
||
----------------------
|
||
|
||
To replicate the javac benchmarks on a machine with JDK 21 installed:
|
||
|
||
.. code-block:: bash
|
||
|
||
cd /home/fox/git/java-topology/tests/
|
||
make bench-real
|
||
|
||
This runs ``benchmark-real.sh``, which:
|
||
|
||
1. Compiles both before (reference) and after (patched) implementations
|
||
2. Runs ``InferenceGraphScalingTest`` with ``--patch-module`` for V = 200 and V = 800
|
||
3. Prints before/after timing and speedup ratio
|