russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
76 lines
2.7 KiB
Markdown
76 lines
2.7 KiB
Markdown
---
|
|
id: minecraft-0003
|
|
repo: Mojang/minecraft-java-edition
|
|
file: net/minecraft/world/level/redstone/ExperimentalRedstoneWireEvaluator.java (decompiled)
|
|
line: calculateCurrentChanges / enqueueNeighborWire methods (~141, 220, 224)
|
|
status: unpatched
|
|
severity: MEDIUM
|
|
complexity: O(N²) per redstone update — Deque.contains() for membership in BFS loop
|
|
pattern: ArrayDeque used as both queue AND membership test — Deque.contains() is O(N)
|
|
source: decompiled from ~/Downloads/server.jar (server-26.1)
|
|
created: 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:
|
|
|
|
```java
|
|
// 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
|