russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
79 lines
3.6 KiB
Text
79 lines
3.6 KiB
Text
// Diagram: buildStuckGraph() complexity cascade (ticket 0002)
|
||
// Shows how three compounding inefficiencies in DeferredAttr+Infer
|
||
// produce O(N³) total work where O(N²) should be the floor.
|
||
//
|
||
// Render: dot -Tsvg 0002-buildstuckgraph-cascade.dot -o 0002-buildstuckgraph-cascade.svg
|
||
|
||
digraph buildstuck_cascade {
|
||
graph [
|
||
label="buildStuckGraph() complexity cascade (DeferredAttr.java:685 + Infer.java:1850)"
|
||
labelloc=t fontsize=13 fontname="monospace" bgcolor="#f8f8f8" pad=0.6
|
||
rankdir=TB
|
||
]
|
||
node [fontname="monospace" fontsize=10]
|
||
edge [fontname="monospace" fontsize=9]
|
||
|
||
// ── Entry point ──────────────────────────────────────────────────────────
|
||
bsg [
|
||
label="buildStuckGraph()\nDeferredAttr.java:685\nN stuck nodes"
|
||
shape=box style="filled,rounded" fillcolor="#dde8ff" penwidth=2
|
||
]
|
||
|
||
// ── Outer N² loop ────────────────────────────────────────────────────────
|
||
loop [
|
||
label="for sn1 in nodes:\n for sn2 in nodes:\n canInfluence(sn2, sn1)\n\nO(N²) calls"
|
||
shape=box style=filled fillcolor="#fff0cc" penwidth=2
|
||
]
|
||
|
||
// ── canInfluence internals ────────────────────────────────────────────────
|
||
ci [
|
||
label="canInfluence()\nDeferredAttr.java:700"
|
||
shape=box style="filled,rounded" fillcolor="#ffe8cc"
|
||
]
|
||
|
||
fn [
|
||
label="findNode(inputVar)\nInfer.java:1850\nO(N) ArrayList scan\n← DEFECT 0002a"
|
||
shape=box style=filled fillcolor="#ffcccc" penwidth=2
|
||
]
|
||
|
||
cl [
|
||
label="inputNode.closure()\nInfer.java:1747\nO(V+E) DFS\nNOT CACHED ← DEFECT 0002b"
|
||
shape=box style=filled fillcolor="#ffcccc" penwidth=2
|
||
]
|
||
|
||
fn2 [
|
||
label="outputVars.map(findNode)\nInfer.java:1850\nO(S·N) per call\n← DEFECT 0002a (again)"
|
||
shape=box style=filled fillcolor="#ffcccc" penwidth=2
|
||
]
|
||
|
||
// ── Tarjan (already in 0001) ──────────────────────────────────────────────
|
||
tarjan [
|
||
label="GraphUtils.tarjan(stuckGraph)\nDeferredAttr.java:675\n← DEFECT 0001 (separate)"
|
||
shape=box style=filled fillcolor="#ffeebb" penwidth=2
|
||
]
|
||
|
||
// ── Total complexity ─────────────────────────────────────────────────────
|
||
total_defective [
|
||
label="DEFECTIVE TOTAL\nO(N²) × O(S·N) × O(V+E)\n= O(N³·S·(V+E))"
|
||
shape=rect style="filled,rounded" fillcolor="#ff8888" fontcolor=white penwidth=3
|
||
]
|
||
total_fixed [
|
||
label="FIXED TOTAL (with HashMap + closure cache)\nO(N²) × O(S) × O(1) [amortized]\n= O(N²·S)"
|
||
shape=rect style="filled,rounded" fillcolor="#88cc88" penwidth=3
|
||
]
|
||
|
||
bsg -> loop
|
||
loop -> ci [label="N² calls"]
|
||
ci -> fn [label="per stuckVar"]
|
||
ci -> cl [label="per inputNode"]
|
||
ci -> fn2 [label="per outputVar"]
|
||
loop -> tarjan [label="after loop\n(once)"]
|
||
|
||
fn -> total_defective [style=dashed color="#cc0000"]
|
||
cl -> total_defective [style=dashed color="#cc0000"]
|
||
fn2 -> total_defective [style=dashed color="#cc0000"]
|
||
|
||
fn -> total_fixed [style=dashed color="#006600" label="HashMap O(1)"]
|
||
cl -> total_fixed [style=dashed color="#006600" label="cached"]
|
||
fn2 -> total_fixed [style=dashed color="#006600"]
|
||
}
|