russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
2.7 KiB
| id | repo | file | line | status | severity | complexity | pattern | source | created |
|---|---|---|---|---|---|---|---|---|---|
| minecraft-0003 | Mojang/minecraft-java-edition | net/minecraft/world/level/redstone/ExperimentalRedstoneWireEvaluator.java (decompiled) | calculateCurrentChanges / enqueueNeighborWire methods (~141, 220, 224) | unpatched | MEDIUM | O(N²) per redstone update — Deque.contains() for membership in BFS loop | ArrayDeque used as both queue AND membership test — Deque.contains() is O(N) | decompiled from ~/Downloads/server.jar (server-26.1) | 2026-03-24 |
Defect
File: net/minecraft/world/level/redstone/ExperimentalRedstoneWireEvaluator (decompiled)
Methods: calculateCurrentChanges(), enqueueNeighborWire()
Pattern: Deque<BlockPos>.contains() inside BFS while-loops
Trigger: Redstone wire placement/removal when experimental feature flag is enabled
Description
ExperimentalRedstoneWireEvaluator implements an improved redstone wire evaluation
algorithm. It uses a Deque<BlockPos> as both a BFS frontier queue AND a membership
set — testing deque.contains(pos) to avoid re-queuing already-queued positions.
ArrayDeque.contains() is O(N) — it scans linearly. For a redstone wire network of
N blocks, each enqueue check costs O(N), making the BFS O(N²) total.
Severity constraint
This defect is behind an experimental feature flag — it is not active in default survival mode. Players must explicitly enable the experimental redstone evaluator. However, when enabled:
- Wire networks can span entire loaded chunks (unbounded N)
- Large redstone computers and circuits in technical Minecraft servers would hit this
- The experimental evaluator is presumably the intended replacement for the legacy one
Comparison — DefaultRedstoneWireEvaluator
The non-experimental version (DefaultRedstoneWireEvaluator) correctly separates
the queue from the visited set:
- Queue:
Deque<BlockPos>for ordering - Visited:
HashSet<BlockPos>or equivalent for O(1) membership
The experimental evaluator was written without applying the same pattern.
Fix
Add a companion Set<BlockPos> for O(1) membership checks:
// Before
Deque<BlockPos> frontier = new ArrayDeque<>();
// ...
if (!frontier.contains(pos)) { // O(N)
frontier.add(pos);
}
// After
Deque<BlockPos> frontier = new ArrayDeque<>();
Set<BlockPos> inFrontier = new HashSet<>();
// ...
if (inFrontier.add(pos)) { // O(1)
frontier.add(pos);
}
Same pattern as javac-0001 (Tarjan stack → parallel HashSet).
Work items
- Confirm method signatures with second decompile pass (Procyon)
- Verify feature flag name and activation path
- Report to Mojang bug tracker — note experimental flag context
- Benchmark: wire network N=100, 500, 1000 with experimental flag on