Chunk generation order goes stale as the player moves

[soloturn]

AI-assisted issue. Filed by agent driven by @soloturn via GDD.

Context

Found while reviewing #4879 and its base branch feat/chunk-ordering-reactor to decide whether either was still worth reviving. Filing this so the underlying problem is tracked independently of the PRs that tried to fix it — it has now outlived two of them.

This is not a newly discovered bug. It has a documented history, is still reproducible on develop, and the last serious attempt (#4822) is still open and was never rejected on technical grounds — it was reviewed favourably and simply stalled.

Problem / Current State

Chunk generation order goes stale as the player moves. The canonical description is @naalit's, from #4773:

You'll probably notice that chunks near you often generate after chunks far away from you, especially if you're moving. Right now, the ChunkProcessingPipeline orders chunks by storing them in a priority queue indexed by their distance to a player. The problem is, when the player moves the priority queue has cached some priorities, and so a chunk that used to be far away and is now close will still have a low priority.

In extreme cases, if you move to right next to a chunk that used to be at the edge of your view distance, all of the chunks that are now in range that didn't used to be will generate before the one right next to you.

Still accurate on current develop. The mechanism:

1. RelevanceSystem eagerly calls chunkProvider.createOrLoadChunk(pos) for every position entering a relevance region (RelevanceSystem.java:137, :189).
2. Each becomes a PositionFuture in ChunkProcessingPipeline's PriorityBlockingQueue(800, comparator), ordered by ChunkTaskRelevanceComparator (distance from region centres).
3. That heap is ordered at insertion time. PriorityBlockingQueue only re-compares during sift operations, so entries already placed keep positions derived from scores computed when the player was somewhere else.

Related smell in the same file, untouched since 2021:

.sorted(new PositionRelevanceComparator()) //<-- this is n^2 cost. not sure why this needs to be sorted like this.

(RelevanceSystem.java:182)

Prior art — read this before starting

Three attempts, none merged:

#4773	closed	feat: order chunks on demand. Original fix. Replaced the priority queue with a re-sorted list plus a new InitialChunkProvider that generator threads pull from. Closed in favour of the Reactor rewrite.
#4822	OPEN	feat: rework chunk ordering using Reactor. Rewrite of #4773 using Reactor, per #4798. Reviewed by @keturn, @skaldarnar, @pollend, @DarkWeird; @skaldarnar recorded before/after comparison videos; @pollend asked "anything else blocking this?" — and it stopped there. Now conflicting.
#4879	draft	Late light merging, stacked on #4822's branch. Separate idea, being pursued separately.

Umbrella context: #4798 (Refactor usage of concurrency with reactor) is still open with unchecked boxes; this work is part of it.

The design question that actually blocked #4822 is still unanswered. @keturn proposed the shape you would expect:

Flux<Chunk> fullChunks = locations.parallel().map(chunkProvider);
fullChunks.subscribe(cacheChunk);

@naalit's objection — "when there are no more chunks to generate right now and execution pauses, there's no way to wake it up again from the main thread" — is what the implemented version works around with notifyRelevanceChanged() (called on relevance-region update, i.e. roughly every player move). @keturn: "This is the part I keep getting stuck on when trying to think about this design."

Any new attempt should answer that explicitly rather than rediscover it.

Acceptance Criteria

• Chunk generation order is recomputed against the player's current position rather than fixed when the chunk was first queued.
• The number of chunk positions in flight is bounded, instead of every relevant position being submitted up front.
• The n^2 sort in RelevanceSystem.addRelevanceEntity is gone or justified.
• The wake-up/backpressure design above is settled and written down, not left implicit.
• Measured: moving continuously in one direction at a large view distance generates nearest-first, verified by instrumenting generation order rather than by eye.

Technical Notes

2f05f3132 on feat/chunk-ordering-reactor is worth reading as a design reference even though it no longer applies. It inverts the flow to pull-based: RelevanceSystem stops creating chunks and only exposes neededChunks(); LocalChunkProvider.chunkFlux() is a Flux with backpressure; the pipeline requests CHUNKS_AT_ONCE at a time, and on each request the pending list is re-sorted by current relevance and only the nearest N handed over.

Reviving #4822 by rebasing is not viable — it predates the org.terasology.engine.* restructure (#5192) and conflicts on its first commit. Treat it as a specification, not a patch.

Constraints a replacement must respect that #4822 predates:

• It hardcodes NUM_TASK_THREADS = 2. develop has since made chunk threads configurable (feat: make number of chunk processing threads configurable #5237) and pool sizing processor-based (fix(ChunkProcessingPipeline): base thread pool size on available processors #5014).
• c645e8154 fixed the never-arriving-neighbour stall differently from the branch's eb48853fe.

Two loose ends inherited from the old discussions:

• perf: remove extra locking in pipeline to avoid thread contention #4825's lock removal is stranded. "perf: remove extra locking in pipeline to avoid thread contention" (@pollend) was merged into feat/chunk-ordering-reactor only and never reached develop — confirmed, not an ancestor, no equivalent commit. Worth redoing independently of the ordering work if that contention is still real.
• Testability. @pollend's (dismissed) review on feat: rework chunk ordering using Reactor #4822 noted the change limits the test scheduler to a single thread, and asked for a follow-up ticket describing what would need to change. That ticket was never filed.
• LOD chunks. @skaldarnar asked on feat: order chunks on demand #4773 about the impact on LOD chunk generation. Never resolved.

Sequencing: this gets easier once light merging moves out of the pipeline. Light merging is currently the only multi-chunk stage (the sole production uses of ChunkTaskProvider.createMulti), and it is what forces the pipeline to hold many chunks in flight pending neighbours — the branch's processingInfoReactor() defer-loop exists largely to service exactly that. With it gone the pipeline is a straight per-chunk sequence and a bounded pull model is considerably simpler.

Related

• feat: rework chunk ordering using Reactor #4822 — open, stalled; the most complete attempt. Should be closed or revived off the back of this issue rather than left indefinitely.
• feat: order chunks on demand #4773 — closed predecessor; canonical problem statement.
• Refactor usage of concurrency with reactor #4798 — open umbrella issue for the Reactor concurrency refactor.
• refactor: do light merging later, remove ChunkProcessingPipeline #4879 — draft late-light-merging PR stacked on feat: rework chunk ordering using Reactor #4822's branch.
• chore: remove DynamicPriorityBlockingQueue #4777 — removed DynamicPriorityBlockingQueue, an earlier attempt at keeping ordering fresh, two weeks before feat: rework chunk ordering using Reactor #4822 started.
• perf: remove extra locking in pipeline to avoid thread contention #4825 — pipeline lock removal, stranded on the branch, never merged to develop.
• feat: make number of chunk processing threads configurable #5237, fix(ChunkProcessingPipeline): base thread pool size on available processors #5014, feat: fix ExecutorCompletionService workaround in ChunkProcessingPipeline #5128 — subsequent pipeline work on develop a replacement must not regress.

[soloturn]

#5363 has landed the sequencing prerequisite noted above: light merging is no longer a pipeline stage, so no stage holds chunks pending their neighbours any more. Once that merges, the pipeline is a straight per-chunk sequence and a bounded pull-based ordering model gets considerably simpler — the defer-loop in #4822's processingInfoReactor() existed largely to service exactly that dependency.

One more data point for whoever picks this up, found while testing #5363 and not fixed there: RelevanceSystem.addRelevanceEntity streams a BlockRegion through .sorted(), but BlockRegion's iterator hands out a single reused, mutable Vector3i. Since sorted() must buffer before it emits anything, the buffered positions end up aliased to a stale value, so some createOrLoadChunk calls are made for the wrong position. It isn't a hang — updateRelevance()'s follow-up pass uses the defensive-copying ChunkRelevanceRegion.getNeededChunks() and still requests the correct positions a tick later — but it is wasted work, and it sits in the same .sorted() call this issue already flags as n^2. Both go away together if the eager-request path is replaced by a pull-based one.

[soloturn]

AI-assisted update. Filed by agent driven by @soloturn via GDD.

Profiled fast flight to test this issue's ordering hypothesis. Result: dispatch ordering isn't the bottleneck. Chunk generation throughput is - median ~109ms/chunk, thread pool saturated 94%+ of the time. A reimplementation of #4822's lazy/JIT dispatch design was benchmarked against the current comparator-sort approach and did not improve throughput (0.51x-0.72x "old/new" select-time ratio, old design faster) - not pushed, recommend closing #4822 on that basis rather than reviving it.

Two real bugs surfaced along the way, now up as #5374 (stacked on #5363, the late-light-merging branch this issue's "Sequencing" note anticipated):

• ChunkProcessingPipeline.invokeGeneratorTask raced two callers into generating the same chunk twice via non-atomic get-then-put; fixed with computeIfAbsent plus making the ready-but-undrained pipeline state visible to RelevanceSystem so it stops re-requesting it. Was regenerating chunks tens of times per session, each a full redo.
• LateLightMerger (main thread) and ChunkMeshWorker (render threads) raced on the same chunk light-array data - TeraSparseArray8Bit's lazy allocation isn't safe for that. Fixed with a per-chunk-position read/write lock (ChunkLightLocks), read side for meshing, write side for merging.

Also tried raising DEFAULT_TASK_THREADS' cap from 4 to use idle cores - OOM'd a constrained heap, reverted. The real fix for that is bounding in-flight chunk count by memory, not thread count; still open, out of scope for #5374.

Given the "Sequencing" note here already called out that light merging moving out of the pipeline makes the ordering work simpler - and #5363/#5374 do that now - this issue's acceptance criteria (recompute order, bound in-flight count, remove the O(n²) sort, settle backpressure) are still the right next step, just now on a pipeline whose real bottleneck is generation throughput, not the sort.