russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
1.3 KiB
1.3 KiB
| id | repo | severity | status | created | patched | patch |
|---|---|---|---|---|---|---|
| javac-0003 | openjdk | MEDIUM | PATCHED | 2026-03-23 | 2026-03-23 | defects/javac/patch/javac-0003-modulehasher-stackset.patch |
Defect
File: src/jdk.compiler/.../javac/comp/ModuleHashesBuilder.java
Pattern: Deque.contains() in module dependency traversal
Complexity: O(M²)
Language: Java
Description
ModuleHashesBuilder traverses the module dependency graph to compute hashes for modules. During traversal, it uses Deque.contains() to check whether a module has already been visited. Deque.contains() performs a linear scan of all elements in the deque. With M modules, each requiring a membership check against up to M already-visited modules, the total traversal cost is O(M²).
Fix
Replace: visited.contains(module)
With: visitedSet.contains(module)
Data structure change: Deque<ModuleSymbol> visited → HashSet<ModuleSymbol> visitedSet + Deque<ModuleSymbol> visitedQueue
Work required
- Patch in
defects/javac/patch/ - Unit test — asserts exact operation counts before/after (in
defects/javac/unit/) - Integration test (in
defects/javac/integration/) - Benchmark — before/after on V=100,200,400,800 (in
defects/javac/bench/) - White paper section