GPBPF

GPU-Powered bedrock pattern finder.

Searches a rectangular area of a Minecraft world for a bedrock pattern and prints every matching column — 400 billion columns in 14 seconds on an RTX 3070. Java Edition 1.18 – 26.3 in the Overworld and the Nether, plus the classic Nether of 1.0 – 1.12.2; see Versions and dimensions for why that gap is a gap. Comes with a web GUI for drawing patterns instead of spelling them out as command-line arguments.

It began as a C/CUDA port of this fork of this project I found on reddit, and is developed as its own tool now rather than held in lockstep with the unmaintained original.

The generator is the exception. The hash, the RNG stream, the seeding chain and the per-layer probabilities belong to Minecraft, not to this project — a pattern finder whose RNG has drifted reports coordinates that do not exist in anybody's world, and it does so silently. So it is pinned by recorded vectors and checked on every build — see Validation. Everything around it, the interface and the output and the inherited warts, is ours to change; CONTRIBUTING.md says how.

Build

make          # CPU, OpenMP-parallel. Works anywhere with gcc + openssl-devel.
make cuda     # CUDA build. Falls back to the CPU path at runtime if no GPU.

make cuda needs the CUDA toolkit. If nvcc is not on PATH the Makefile looks in /usr/local/cuda/bin.

CUDA 13.x supports gcc ≤ 15, so on a newer host compiler the build uses g++-15 via -ccbin when it is installed (sudo dnf install gcc15 gcc15-c++, or set NVCC_HOST=/path/to/g++). If no supported host compiler is found it falls back to -allow-unsupported-compiler and prints a loud warning — nvcc does not vouch for code generated that way, so treat such a build as unverified until make test passes.

Requires openssl-devel (MD5, used once at startup for seed derivation).

Usage

Not frozen — see CONTRIBUTING.md — but stable today:

gpbpf <worldSeed> <fromX> <fromZ> <toX> <toZ> [<block>...]
      [--version <mcver>] [--dimension overworld|nether] [--resume <columns>]

• fromX/fromZ inclusive, toX/toZ exclusive.
• --version picks the generation era. 1.18 – 26.3 is the default and needs no flag; 1.0 – 1.12.2 selects the classic Nether generator, which ignores the world seed. --version 1.15 is refused, with the reason.
• --dimension picks whose rules to search, and so which layers exist: overworld (the default) has bedrock at y −64…−60, nether at y 0…4 and again at 123…127. It is not cosmetic — the two dimensions run on different random number generators. See Versions and dimensions.
• --resume <columns> skips that many columns of the range, taking the number straight off a stopped run's own output — see Stopping and resuming. It may appear anywhere in the argument list (--resume=N also works); a block argument can never be mistaken for it, since every block contains a comma and a colon.
• Each <block> is X,Y,Z:B — X/Z are pattern-relative offsets, Y is an absolute world height, B is 1 for bedrock and 0 for not-bedrock.
• With no <block> arguments, the pattern is loaded from ./pattern/*.txt: the filename stem is the Y level (-60.txt → y = −60), line index is Z, character index is X. Only 0 and 1 are meaningful; every other character (including spaces) is skipped, which is how ragged rows encode don't-care cells.

gpbpf 12345 0 0 20000 20000 0,-60,0:1 1,-60,0:1 0,-60,1:1
gpbpf --dimension nether 12345 0 0 20000 20000 0,126,0:1 1,126,0:1
gpbpf --version 1.12.2 --dimension nether 0 -5000 -5000 5000 5000 0,126,0:1

Versions and dimensions

Bedrock generation changed exactly once between 1.0 and 26.3, at 1.18 (21w40a), when it stopped being a by-product of chunk generation and became a positional function of the world seed. Everything since is identical: the rules, the anchors, the random names and the generation heights they resolve against are byte-identical in the game's own worldgen data at every release tag from 1.18 to 26.3-snapshot-9. 26.3 moved them from an inline surface_rule into a material_rule registry, which changed the file layout and nothing else.

So --version selects between two engines, not one per release:

Versions	How bedrock is generated	Searchable?
1.18 – 26.3	vertical_gradient surface rule; a positional random derived from the world seed. Overworld and Nether.	Yes, default
1.13 – 1.17.1	Same chunk Random, but bedrock is placed after that chunk's 256 surface builders have drawn from it.	No — see below
1.0 – 1.12.2	Random(chunkX·341873128712 + chunkZ·132897987541), replayed per chunk. Nether only.	Yes, --version 1.12.2

Why 1.13 – 1.17 is refused rather than approximated

NoiseChunkGenerator.buildSurfaceAndBedrock creates one WorldgenRandom, seeds it from the chunk coordinates, hands it to all 256 of the chunk's surface builders, and only then calls setBedrock with it. Those builders consume between zero and a dozen draws each — SoulSandValleySurfaceBuilder draws nothing, NetherSurfaceBuilder draws three, FrozenOceanSurfaceBuilder draws from inside loops — so where the bedrock draws land depends on the chunk's biomes and on its terrain. Reaching the layer means generating the world.

A tool that guessed here would emit coordinates that look right and are wrong, which is the single failure this project exists to avoid, so --version 1.15 prints the reason and exits.

Why the classic era is the Nether only

The classic Nether is a closed loop: three nextDouble() per column, then a nextInt(5) ladder down the column, and nothing else touches that Random between the chunk seeding and the bedrock. The noise fields decide which block goes where, never how many times the stream is drawn from, so the whole layer is a pure function of (chunkX, chunkZ) — the same in every world. Verified identical in Mojang's own 1.0, 1.7.10 and 1.12.2 jars.

The classic Overworld is not: its terrain loop spends an extra nextInt(4) on any column whose filler is sand, which shifts the stream for every column after it in that chunk. Present in 1.0 and still there in 1.12.2. So Overworld bedrock depends on the terrain, and therefore on the seed, and therefore is out of reach for the same reason 1.13 – 1.17 is.

The classic era ignores the world seed, and says so on stderr. That changes what a search means: it finds where a pattern is, not whether it is at your seed. This is the "read the coordinates off a Nether-roof screenshot" case, and the answer is the same for everybody.

What varies by dimension

dimension	rule	RNG	bedrock at
Overworld	bedrock_floor	xoroshiro128++	y ≤ −64 always; −63…−60 at 80/60/40/20%
Nether	bedrock_floor	java.util.Random	y ≤ 0 always; 1…4 at 80/60/40/20%
Nether	bedrock_roof	java.util.Random	y ≥ 127 always; 126…123 at 80/60/40/20%

The Overworld has no roof rule at all, and the End has no bedrock layer. The Nether is on java.util.Random rather than xoroshiro because its noise settings carry legacy_random_source: true — which is also why its terrain survived the 1.18 rewrite unchanged. Note the roof band runs the other way to the floor: solid at the top and thinning downward, because vanilla wraps that rule in not.

The classic Nether lands on the same layers with the same odds, so a pattern drawn for one era is legal in the other. It is a different pattern, though — same odds, different columns — which is exactly why the era is a flag and not a footnote.

Minecraft Bedrock Edition the game is a different codebase with a different RNG and is not supported; the name collision is unfortunate. This searches the bedrock block in Java Edition.

Web GUI

screenshot:

make web      # http://localhost:8765

Because typing 25 block arguments for a 5×5 pattern is not a good time. Draw the pattern on a grid instead, one tab per Y layer, and the page tells you how selective it is before you run anything:

• Expected match count, measured. A rough number from the per-layer probabilities (−63 is 80% bedrock, −62 60%, −61 40%, −60 20%, and the Nether's two bands run 80/60/40/20% from their solid ends) appears as you draw. A moment later the server samples the real search and replaces it with a measured figure and an interval. A pattern that would emit 12 GB of text says so before you run it, and one that can never match — wanting bedrock at y=-59, say — says that too. Measuring rather than modelling is not gold-plating; see Layers are not independent.
• Scan more than one orientation. A pattern copied off a screenshot or a video rarely comes with a reliable compass bearing, so Scan picks how many turns to look for: as drawn, as drawn + 180° for a formation whose axis you can read but whose direction you cannot, or all four quarter turns. Each is a separate run of the binary, merged into one result, and every match is labelled with the turn that hit and outlined in the viewer at that turn. A pattern that maps onto itself under a turn is scanned once rather than twice, so a symmetric drawing does not report every match two or four times over.
• A bedrock viewer. Pan around the actual bedrock at any layer and see a match with the pattern outlined on top of it, rather than taking a coordinate on faith. It is a one-block search per frame, so it costs no new search code.
• The equivalent command, always visible at the bottom, so the GUI doubles as a command builder and never hides what it ran. Text seeds are converted the same way Minecraft converts them (String.hashCode), since the CLI itself takes only integers.

Needs python3 (stdlib only, no packages). web/serve.py shells out to the same ./gpbpf binary this repo builds — no C code is involved in serving, so the GUI cannot affect the generator. Run make cuda first if you want the GPU build behind it; both targets produce ./gpbpf.

It binds 127.0.0.1 and refuses searches that would match every column. --host exposes it to the network and warns when you use it.

The GUI caps searches at 2 billion columns (about 44,700 × 44,700) so a stray zero cannot turn a ten-second search into an all-day one. The cap is the server's, not the search engine's — the CLI is uncapped. Raise the GUI's with:

make web AREA=20000000000          # or: python3 web/serve.py --max-area 20000000000

For a genuinely large search, prefer copying the equivalent command from the bottom of the page and running ./gpbpf yourself. The cap exists because this is a server: a browser has no Ctrl-C, so every run holds a handler thread and a child process until the cancel path reaches it, and --host can put that on the network. On the CLI you own the process and Ctrl-C is free.

A running search can be stopped from the progress box. Cancel search kills the binary rather than only closing the connection — a search holds its handler thread for as long as gpbpf runs, so the page names each request and asks POST /api/cancel to kill that name over a second connection. Dropping the request browser-side would stop the waiting and leave the GPU working.

A run also gives up after Timeout seconds, which is a field in the Pattern card rather than a server flag — a scan that needs longer gets it without a restart. --timeout sets what that field starts at (300s). The budget covers the whole request, so scanning four orientations shares it instead of taking four times as long, and a run that exceeds it says timed out rather than reporting the SIGKILL as gpbpf exited -9.

Timeout 0 runs with no limit, and the unit next to the field swaps to no limit so a 0 s timeout cannot be read as a bug. Past a certain size there is no timeout worth guessing — a full-border scan is measured in days — and the honest options are an unbounded run or a number invented to look reassuring. It is opt-in per request because it removes the only automatic way a wedged search lets go of its handler thread; Cancel search is then the only thing that stops it, which it can, since it kills the process over a second connection.

While a search runs, the box shows elapsed time, a bar, and a time remaining, from two sources in order of preference:

Measured, once the binary starts reporting. The page polls /api/progress on a second connection — the same reason Cancel needs one, since the search itself is a single blocking request that cannot report on itself. The server picks the counters out of gpbpf's stderr as they arrive, so they are real columns searched, not an estimate. Multi-orientation searches fill one bar across the whole request rather than four that each restart at zero.

Extrapolated, before that. gpbpf stays silent for its first two seconds, and a search shorter than that never reports at all, so the bar starts as an extrapolation from the throughput of your last search, kept in localStorage. That self-calibrates to the machine and to whether CUDA is in play, which no constant in the page could. The first ever search shows elapsed only rather than inventing a bar, and a run that outlasts its estimate holds at 99% and says past the … estimate rather than sitting at 100% while still working. Runs under a second are mostly process startup, so they do not update the calibration.

make webtest  # server results must equal the CLI's, byte for byte

Layers are not independent

The estimate multiplies the per-layer probabilities, which assumes each block's draw is independent of the others. That holds within a single Y layer and breaks badly across layers. Measured over 100M columns, seed 12345, blocks at dx = 0…4 on each layer:

pattern	measured rate	independent model	ratio
5 blocks, 1 layer (−63)	0.328114	0.32768	1.00
10 blocks, 2 layers	0.0266059	0.0254802	1.04
15 blocks, 3 layers	9.2761e-4	2.6092e-4	3.6
20 blocks, 4 layers	3.96e-6	8.3493e-8	47

Two probes at the same column but different Y share a deriver, and their hashes differ only in a few low bits before bd_hash mixes them, so bedrock stacks vertically far more often than chance. This is the generator's own behaviour, not a porting artefact: the CPU and CUDA builds return byte-identical counts for every row above.

The error is always in the direction of more matches, which is the unhelpful one for a number whose job is to warn about output size. So the GUI does not rely on the model: POST /api/estimate runs the real search over a slice and extrapolates, which needs no independence assumption at all. The model number is still shown instantly while you draw, then replaced.

Three things make that sampling honest:

• Two stages, so the output stays bounded. A pattern matching most columns would stream gigabytes through a naive fixed-size sample. The first sample is ~260k columns; a permissive pattern reaches its hit target there and stops, and one that does not is by definition rare enough that the second, larger sample cannot emit more than a few tens of thousands of lines.
• The slice spans every Z. Match rates are not spatially uniform — over nine disjoint 10000×10000 tiles the spread was 2.6%, 7.8× what Poisson noise predicts, and it grouped almost entirely by Z. That follows from bd_hash: z is multiplied by a full 64-bit constant while x wraps in 32 bits. A full-height strip lands within 1.6% of the true rate; a square block of the same column count was off by up to 6.1%.
• The interval admits that. Reported bounds combine Poisson counting error with a 2.5% spatial term measured from those strips, so a large sample never claims a precision the method cannot deliver.

When the search area is smaller than the sample budget the whole thing is counted and the figure is exact, not estimated.

Validation

make test     # ./fp_proof, then tools/check.py, then tools/model.py

30 cases pinning the generator: all four probability bands, every band edge, the always-bedrock early returns, the Overworld's absence of a roof rule, classic patterns straddling a chunk boundary, negative and past-wrap coordinates, extreme seeds, pattern/*.txt versus equivalent explicit block args, output ordering, the distance field at extreme coordinates, and the two columns where nextFloat() lands exactly on the probability. Plus two checks that need no vector because they compare two of our own runs: --resume against the tail of a full one, and the classic era under two different seeds, which have to be identical. Needs nothing but the built binary and python3 — no Java, no network, no second checkout.

The expected results live in tools/vectors.json as match counts and SHA-256 digests, and two programs have to agree on them. tools/check.py runs the binary and asks whether the output is unchanged. tools/model.py recomputes every case from Minecraft's own worldgen rules, in Python and by a different route than bedrock.h, and asks whether it is right — because one implementation cannot catch a wrong derivation, which is how the Nether roof ran inverted for as long as it did. A diff against the vectors is a bug here, not a stale vector. Re-record only when you have independently established the new output is right — "the gate is red and I want it green" is not that.

Three cases use different comparison modes because they test different things. Most compare the match set, so they would not notice an ordering regression; one compares the raw sequence across negative and positive coordinates, which is where a radix key without the signed bias would put the negatives last. Another compares whole output lines, making it the only case that sees the distance field. The pattern/*.txt case needs no vector at all — it checks two of our own invocations against each other, so it cannot go stale.

fp_proof runs first and is a separate kind of check: it enumerates the entire input space of the float comparison rather than sampling it, and it restates every band — modern and classic — from vanilla rather than reading it back out of bedrock.h, since a band that agrees with itself proves nothing. See below.

The classic era was established differently again, because it predates anything data-driven. Its algorithm was read out of Mojang's own 1.0, 1.7.10 and 1.12.2 jars, where ChunkProviderHell.replaceBlocksForBiome is identical, and then checked against a transcription of it running on a real java.util.Random — so nextInt(5)'s rejection loop and nextDouble()'s two draws came from the JDK rather than from a rewrite of them. 569 chunks agreed exactly, including coordinates where the chunk-seed multiply wraps. tools/model.py is the standing check; the one-shot oracle is reconstructible from the algorithm quoted in CONTRIBUTING.md.

Where the generator would silently drift

Three details in bd_hash diverge if reimplemented naively, and are the reason the vectors include coordinates past |x| ≈ 686 (the Nether's java.util.Random chain has two traps of its own — see CONTRIBUTING.md):

• x * 3129871 is a 32-bit multiply that wraps, then sign-extends. It is not (long)x * 3129871L.
• (long)z * 116129781L really is 64-bit. The asymmetry with the x term is deliberate and must be preserved.
• The final >> is an arithmetic shift, sign-propagating, not a logical one.

nextFloat() cannot drift: next(24) is exactly representable in binary32 and the multiplier is exactly 2⁻²⁴, so the multiply only adjusts the exponent. The build passes -ffp-contract=off / --fmad=false so no FMA contraction can change a rounding. Never add --use_fast_math.

The comparison's strictness is a separate question from its precision, and fp_proof only answers the second. nextFloat() returns k·2⁻²⁴ and two of the four probabilities — 0.8 and 0.6 — are exact multiples of 2⁻²⁴, so a draw can land exactly on p and < versus <= becomes observable. Seed 12345 does it at (269, 4168) on y=-63. Two vectors pin that; before they existed, flipping the operator passed the entire gate.

The generator specifies the comparison in double; bd_probe does it in float. That is a narrowing, so it is licensed by exhaustion rather than by argument: nextFloat() has exactly 2²⁴ possible outputs, and after bd_classify only four probabilities (0.8/0.6/0.4/0.2) can reach a comparison — every other y resolves to a constant verdict. tools/fp_proof.c enumerates that entire space (386M comparisons, ~0.3 s) and make test runs it before the parity harness. If it ever fails, bd_probe must go back to (double)f < p.

Performance

RTX 3070 + 12-thread CPU, 20000×20000 = 400M columns, 20 probabilistic blocks (the prefilter below cannot remove any of them, so this is the honest case).

GPU kernel time alone, measured with nsys:

	kernel
before optimization	622.8 ms
after	51.4 ms (12.1×)

End-to-end wall clock on the same search with sparse output:

build	before	after
CPU (OpenMP, 12 threads)	1.21 s	1.03 s
CUDA	0.95 s	0.27 s

Roughly 0.2 s of the CUDA figure is context init, so for small ranges the CPU path can still win. Two changes got this:

The probability was recomputed 6.6 billion times to produce one of four values. p depends only on a pattern block's y, never on (x,z), but lerpFromProgress ran inside the per-probe hot loop — and it contains a double-precision divide. There is no hardware FP64 divider, so nvcc emits a MUFU.RCP + Newton-Raphson DFMA sequence, and consumer Ampere runs FP64 at 1:64 rate. Ablating it measured at 67% of kernel time. It is now computed once per pattern block on the host, which is bit-exact by construction — the same double arithmetic, just hoisted. The kernel now contains zero FP64 instructions (SASS went 416 → 288 instructions).

Blocks with a constant outcome are resolved at load time. Any block outside the probabilistic bands — or with p ≥ 1 or p ≤ 0 — has an outcome independent of (x,z). If it contradicts the pattern the whole search is provably empty; if it agrees it is redundant and dropped. Patterns made largely of such blocks get far more than 12× (one 20-block test went 1086 ms → 25 ms) because the work was never real to begin with.

Two things that sound promising and measurably are not: replacing the 64-bit integer multiplies in bd_hash gains 6%, and removing the 64-bit div/mod used to unflatten the thread index gains nothing at all — nvcc hoists the invariant reciprocal out of the loop, so it costs 3 instructions for the whole kernel.

At 400 billion columns

800,000 × 500,000 = 400,000,000,000 columns(bigger than the current pre-update donutSMP world), seed 12345, RTX 3070. A thousand times the area of the largest benchmark below, and the first workload where CUDA's ~0.2 s of context initialisation is genuinely irrelevant.

pattern	CUDA	CPU, 12 threads	matches
3×3 plate at y=−60 (9 blocks, 1 layer)	14.0 s (28.6 G col/s)	326.3 s (1.23 G col/s)	205,143
20 blocks across y=−63…−60 (4 layers)	36.4 s (11.0 G col/s)	—	1,827,374

CUDA is 23× the 12-thread CPU path here, and both produced the same 205,143 matches. The Java original would need about four hours at its measured 27.6M columns/s, so this is roughly a 1000× span end to end.

The two rows differ because of the early exit in bd_check: the plate's first probe is p=0.2, so 80% of columns are rejected after one RNG call, while the 20-block pattern starts on the y=−63 layer at p=0.8 and keeps 80% of columns alive into a second probe. The plate row is also a check on the search itself — 205,143 against 400e9 × 0.2⁹ = 204,800 predicted, 0.17% off.

Both rows predate the selectivity sort below. The plate row is unaffected — all nine of its blocks pass at 0.2, so there is nothing to reorder. The 20-block row is exactly the gap the sort closes, and no longer starts on a p=0.8 probe.

Tiling

The CUDA path walks the range in tiles rather than issuing one launch for the whole thing. A single launch hits three walls at scale:

• the display driver kills a kernel that runs for minutes;
• the match buffer is fixed and per launch, so a dense pattern overflows it and the search used to end there — "results truncated, search a smaller range";
• the match counter is a 32-bit atomic.

That last one sets the tile ceiling and is not a tuning knob: a tile can match on every column, so a tile wider than UINT_MAX could wrap the counter and make an overflowing launch look like a small one — silent truncation, the exact failure the buffer check exists to prevent. The ceiling is 2³¹ columns, ~0.16 s at 13 G col/s.

A tile is a contiguous window of the flattened index, which is already x-major/z-minor, so tiles need no 2D geometry. The size adapts rather than being tuned, because match density cannot be known before the search: a tile that overflows the buffer is halved and retried, one that comes back nearly empty doubles.

What that buys, on a deliberately dense pattern (0,-60,0:0, ~80% of columns match) over 30M columns:

	matches
one launch	16,777,216 — the buffer, truncated
tiled	24,001,022 — equals the CPU path exactly

It costs nothing on searches that were already fine: the 400e9-column plate above runs 13.76 s tiled against 13.72 s in a single launch.

A full-border scan is ~1.7M launches, about 17 s of launch overhead spread across ~31 hours. The remaining ceiling is host RAM for matches, not the GPU — see Known limits.

Progress

Searches that run longer than two seconds report to stderr, at most one line a second:

gpbpf: progress 40533753856/400000000000 10.133%

stderr because stdout is the match stream — web/serve.py parses it, and a status line in the middle would read as a match. Silent below two seconds, so ordinary searches and the parity harness see no new output at all, and a multi-day scan spends ~100 KB on it.

Counted in columns rather than as a bare percentage because that is exactly what --resume takes.

Stopping and resuming

Matches are collected in memory and printed at the end, so a scan killed at hour 30 used to lose all 30 hours of them — and a resume offset alone would then let you continue past ground whose results were gone. So Ctrl-C stops gracefully: the search finishes the tile (GPU) or column (CPU) it is on, prints what it found, and says where to pick up.

^C
gpbpf: stopped at column 115695681536 of 400000000000 (28.924%); results above are complete up to there
gpbpf: resume with: --resume 115695681536

gpbpf 12345 -400000 -250000 400000 250000 <blocks> > part1.txt   # ^C
gpbpf 12345 -400000 -250000 400000 250000 <blocks> --resume 115695681536 > part2.txt
cat part1.txt part2.txt          # byte-identical to the uninterrupted run

That last line is the contract, and it holds on both paths — verified at 400e9 columns (59,143 + 146,000 = 205,143 matches, identical including order) and in make test, which stops a search mid-flight and rejoins the halves.

A stopped run exits 2, so gpbpf … && next-step will not treat a partial scan as a whole one. Everything it printed is complete and correctly ordered for the ground actually covered.

Two details worth knowing:

• Anything past the resume point is discarded before printing. On the CPU path schedule(dynamic) lets a fast thread finish columns well above the frontier; keeping them would double-count when the halves are joined (measured: 1,370 duplicates on a 2.6M-match stop). Discarding costs work already done, which is the cheaper mistake.
• The resume point is conservative on the CPU path. Dynamic chunks are handed out in increasing x, so every x below the lowest one still in flight is complete — that is the frontier, and resuming above it would skip ground nobody searched. On the CUDA path tiles are strictly sequential, so it is exact.

The GUI's Cancel is unaffected: it sends SIGKILL, which cannot be caught, and it wants the results discarded anyway.

Ordering the pattern

bd_check exits on the first mismatch, so the order of the pattern decides how many probes an average column costs. A block's pass probability is p where the pattern wants bedrock and 1 − p where it wants air, and the expected probe count is dominated by whatever sits first: a pattern led by p=0.2 costs 1 + 0.2 + 0.04 + … ≈ 1.25 probes per column, one led by 0.8 costs ≈ 5.

A painted pattern arrives in close to the worst order for this, and not by accident — most cells of a screenshot are air, and an air cell on the dense y=−63 layer passes 80% of the time. So main.c sorts the pattern ascending by pass probability before searching. Reordering cannot change the result: bd_probe seeds only from (x+dx, y, z+dz) and carries no state between blocks, so bd_check is a conjunction of independent predicates. The selectivity sort permutes vector pins that — it was recorded from the build immediately before the sort landed, and mixes both Y levels and wants so the sort really does permute it.

Measured both ways, against a build taken from the commit immediately before the sort. Output byte-identical in both pairs.

workload	as painted	sorted
4×4 patch on y=−60 (13 air, 3 bedrock), 3.6e9 columns, 12-thread CPU	11.46 s	3.78 s (3.0×)
20 blocks across y=−63…−60, 400e9 columns, CUDA	45.32 s (8.8 G col/s)	31.15 s (12.8 G col/s, 1.5×)

The GPU gains less than the CPU, and that is the interesting part. A warp runs 32 columns in lockstep, so it costs the maximum over its threads, not the average — early exit only pays when every column in the warp exits together. The CPU takes the full benefit per column; the GPU takes it per warp. Both are worth having, neither is free, and quoting the CPU's 3× as the headline would misrepresent the GPU path this project is named for.

The win is bounded by how badly ordered the input was: a pattern already written selective-first gains nothing, which is why the 3×3 plate rows above are unchanged.

# args spelled out: zsh does not word-split unquoted parameters, so a variable
# would arrive as one argument
time ./gpbpf 12345 -400000 -250000 400000 250000 \
  0,-60,0:1 0,-60,1:1 0,-60,2:1 \
  1,-60,0:1 1,-60,1:1 1,-60,2:1 \
  2,-60,0:1 2,-60,1:1 2,-60,2:1

Versus the original

Measured against the real bedrock_finder-1.1.0.jar built from the Java sources (RTX 3070, 12-thread CPU, JVM 25). The original is single-threaded, so the 1-thread column separates the algorithmic win from the threading win. All runs produced identical match counts.

workload	Java	ours, 1 thread	ours, 12 threads	ours, CUDA
3×3 plate, 100M columns	3.62 s	0.55 s (6.6×)	0.06 s (60×)	0.32 s (11×)
20-block pattern, 50M columns	5.42 s	1.23 s (4.4×)	0.15 s (36×)	0.35 s (16×)
1 block, 16M columns / 3.2M matches	10.54 s	0.23 s (46×)	0.09 s (117×)	0.41 s (26×)
20-block pattern, 400M columns	~43 s (extrapolated)	—	1.16 s	0.51 s

Two things worth reading off this. CUDA is not always the fastest option — below roughly 100M columns its ~0.2 s context initialisation costs more than the whole search, and the 12-thread CPU path wins. It pulls ahead on large areas, which is the last row. The original's weakest point is output, not search: the 3.2M-match row is 10.5 s in Java, most of it printing.

These are historical: a snapshot taken against the original at the point this stopped being a port. Reproducing our side needs nothing extra — args written out rather than built in a variable, because zsh does not word-split unquoted parameters and it would arrive as one argument:

# 3x3 plate at y=-60; prefix OMP_NUM_THREADS=1 for the single-thread column
time ./gpbpf 12345 0 0 10000 10000 \
  0,-60,0:1 0,-60,1:1 0,-60,2:1 \
  1,-60,0:1 1,-60,1:1 1,-60,2:1 \
  2,-60,0:1 2,-60,1:1 2,-60,2:1

Output path

Once the kernel was fast, printing became the bottleneck. On a search emitting 4.6M matches (178 MB of text), end-to-end wall clock is 1.13 s → 0.42 s:

phase	before	after
sort	406 ms	84 ms
format + write	408 ms	17 ms

The sort is an LSD radix sort, 4 passes of 16 bits over (x,z) packed into one key, replacing qsort's indirect comparator. The ^0x80000000 bias makes signed ordering agree with unsigned ordering.

Formatting improved in two steps: replacing printf (~85 ns per call) with hand-written integer formatting took it to 129 ms, and spreading it across the OpenMP team took it to 17 ms. Threads fill their own slice of one pool and the wave is written back in thread order, so no thread touches stdout, there is no locking, and output order is unchanged. Output is byte-identical whether run on one thread or twelve.

hypot is deliberately left alone: sqrt(x*x + z*z) would be faster but could change the displayed distance for large coordinates. Parallelising it along with the formatting made that trade unnecessary.

Known limits

• The CUDA path caps the pattern at 2048 blocks (64 KB constant memory). Detected and reported, never silently truncated. The 2²⁴-entry match buffer is no longer a limit on the search — it is per launch, and an overflowing tile is halved and retried (see Tiling).
• Match output is buffered in memory before printing, so a search emitting hundreds of millions of matches needs proportional RAM. This is now the binding limit on a very large scan, not the GPU: at roughly 8 bytes a match, a billion matches is 8 GB. Selectivity is the fix — a pattern carrying enough information to be unique over the area you are scanning (~52 bits over a full 2b2t border) produces a handful of matches, not billions.
• The "blocks from origin" field may differ in the last ulp between libm implementations. Cosmetic — it is a display value, and only one vector compares it. Saturation is handled explicitly: C's narrowing of a double past INT_MAX is undefined, so hypot_i clamps instead of finding out.
• A missing pattern/ directory leaves the pattern empty, which matches every column, so the CLI prints one line per column searched. Inherited from the Java original and not yet changed; the web GUI already refuses it. This is interface rather than generator, so it is fair game to fix — see CONTRIBUTING.md.
• Nether results have not been compared against a real world. They are derived from the game's own worldgen data and agreed on by two independent implementations (see Validation), which is what caught the inverted roof band this tool shipped until 2026-08-19 — but nobody has yet flown to y=127 in a real Nether at a known seed and diffed a 16×16 patch. Worth doing before you trust a Nether hit that matters. Overworld results are unaffected: 19 of the 22 pre-existing vectors carried over untouched.
• The classic era runs on the CPU only. Its probe replays a whole chunk (~64k LCG steps) rather than sampling a positional random, which the column-per-thread kernel is the wrong shape for; a chunk-per-thread one would fit it well and does not exist yet. The CPU path also recomputes each chunk once per x rather than once, because the search loop is x-major — 16× more replay than needed, and the loop order rather than the cache is the ceiling. Fine for a few million columns, not for a world border.
• A search spanning more than 2⁶³ columns is refused by the CUDA path and falls back to the CPU, because the flattened index would not fit in long long. Reaching it needs nearly the full int32 range on both axes; the CPU path is correct there but would take geological time. Searches wider than 2³¹ columns on a single axis are handled: search.cu unflattens the thread index in 64-bit and narrows once, rather than truncating the quotient first.