russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
91 lines
3 KiB
Markdown
91 lines
3 KiB
Markdown
# 0003 — ModuleHashesBuilder$TopoSorter: O(N) Deque.contains() for cycle detection
|
||
|
||
**Status:** open
|
||
**Severity:** performance — medium
|
||
**Component:** `java.base / jdk.internal.module.ModuleHashesBuilder$TopoSorter`
|
||
**Module:** `java.base` — ships in every JDK and JRE
|
||
|
||
---
|
||
|
||
## Root Cause
|
||
|
||
`ModuleHashesBuilder.java` (inner class `TopoSorter.visit()`), bytecode instruction 57:
|
||
|
||
```
|
||
invokeinterface java/util/Deque.contains:(Ljava/lang/Object;)Z
|
||
```
|
||
|
||
The `visit()` method uses an `ArrayDeque` as a DFS stack and calls `Deque.contains()` to detect back edges (cycles in the module dependency graph). `ArrayDeque.contains()` is a linear scan — O(N).
|
||
|
||
This is the same structural defect as ticket 0001 (`GraphUtils.Tarjan`) in a different module and a different layer of the stack.
|
||
|
||
Source pattern (reconstructed from bytecode):
|
||
|
||
```java
|
||
private void visit(T node, Set<T> visited, Deque<T> stack) {
|
||
if (visited.contains(node)) {
|
||
if (stack.contains(node)) { // O(N) — THE DEFECT
|
||
throw new IllegalArgumentException("Cycle detected: " + node + " -> " + children(node));
|
||
}
|
||
return;
|
||
}
|
||
visited.add(node);
|
||
stack.push(node);
|
||
children(node).forEach(child -> visit(child, visited, stack));
|
||
stack.pop();
|
||
result.addLast(node);
|
||
}
|
||
```
|
||
|
||
**Fix — one boolean field per node, or a `HashSet<T> onStack`:**
|
||
|
||
```java
|
||
Set<T> onStack = new HashSet<>(); // O(1) contains
|
||
|
||
private void visit(T node, Set<T> visited, Deque<T> stack, Set<T> onStack) {
|
||
if (visited.contains(node)) {
|
||
if (onStack.contains(node)) { // O(1)
|
||
throw new IllegalArgumentException("Cycle: " + node);
|
||
}
|
||
return;
|
||
}
|
||
visited.add(node);
|
||
stack.push(node);
|
||
onStack.add(node); // O(1)
|
||
children(node).forEach(...);
|
||
stack.pop();
|
||
onStack.remove(node); // O(1)
|
||
result.addLast(node);
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## Where This Fires
|
||
|
||
`ModuleHashesBuilder` is called by `jlink` during custom runtime image creation:
|
||
|
||
```
|
||
jlink → ModuleHashesBuilder.computeHashes() → new TopoSorter(graph) → visit()
|
||
```
|
||
|
||
The module dependency graph fed to this sorter is the full transitive closure of the modules included in the image. For a typical server JDK image with 20–50 modules, this is manageable. For large multi-module applications using `jlink` with 100+ modules, the O(N²) degradation is measurable.
|
||
|
||
---
|
||
|
||
## Significance
|
||
|
||
This defect lives in `java.base` — the lowest-level module present in every JDK/JRE. The same pattern (`Deque.contains()` for on-stack check) replicated here independently of `GraphUtils.Tarjan` shows this is a **systemic pattern** in the JDK codebase, not an isolated incident.
|
||
|
||
---
|
||
|
||
## Complexity
|
||
|
||
| V (modules) | Defective contains() calls | Fixed contains() calls |
|
||
|---|---|---|
|
||
| 20 | ≤ 190 | ≤ 20 |
|
||
| 50 | ≤ 1,225 | ≤ 50 |
|
||
| 100 | ≤ 4,950 | ≤ 100 |
|
||
|
||
For small module graphs, impact is negligible. For large `jlink` builds or module graphs
|
||
with deep dependency chains, this compounds with other O(N²) patterns.
|