Jump flooding does not pay until 500 seeds

When a distance field has to be rebuilt every frame from sources that move, the analytic approach stops applying and you have two options: evaluate every source at every pixel, or jump flood. The standard advice is to jump flood. The standard advice does not come with a number.

Pause Restart

The measurement

Both methods, real WebGL2, 960×540, float render targets, median of 70 frames after a 30 frame warm-up, on an Apple M4 Max. Jump flooding is a seed splat plus ten ping-pong passes of nine taps each, which is ceil(log2(960)).

Seeds	Brute force	Jump flood	Winner
4	0.050 ms	0.417 ms	brute, 8x
16	0.050 ms	0.400 ms	brute, 8x
64	0.083 ms	0.400 ms	brute, 4.8x
128	0.133 ms	0.400 ms	brute, 3x
256	0.217 ms	0.400 ms	brute, 1.8x
512	0.383 ms	0.400 ms	even
1024	0.750 ms	0.417 ms	flood, 1.8x
2048	1.517 ms	0.417 ms	flood, 3.6x

Reading it

Jump flooding is flat. 0.400ms at four seeds and 0.417ms at two thousand, which is the entire promise of the algorithm delivered exactly. Its cost is ten full-screen passes and it does not care what is in them.

Brute force is linear, at 0.00071ms per seed above a floor of about 0.037ms. The fit is boring: predicted at 256 is 0.218ms, measured 0.217ms.

They cross at about 510 seeds. Below that brute force wins, and near the bottom of the range it wins by eight times while also being about fifteen lines of code with no render targets, no ping-pong, and no approximation.

That number is the useful output here, because the received wisdom is to reach for jump flooding as soon as a field has to be dynamic. For most of what a stylized 2D renderer actually does, forty lights, a hundred particles, a few dozen influence sources, brute force is both faster and simpler and the choice is not close.

Where the crossover moves

It is one number on one machine, so it is worth knowing which way it slides:

• Resolution moves both sides equally, so the crossover barely shifts. Both methods are linear in pixels.
• A more expensive seed pushes it down. These seeds are a distance to a point. Seeds that are line segments or arcs cost several times more each, which brings the crossover in proportionally.
• Fewer flood passes push it down a lot. Ten passes covers the whole screen. If sources only need to influence a 64 pixel radius, six passes will do and jump flooding gets 40% cheaper.
• Bandwidth-limited hardware pushes it up. Jump flooding is ten full-screen read-modify-writes of an RGBA32F target, which is the thing a weaker memory system hates most. On mobile the crossover is likely much higher than 500.

The other differences, which are not speed

• Jump flooding is approximate. It can produce small errors where cell boundaries meet awkwardly. Usually invisible, occasionally not, and never a thing brute force does.
• It quantizes to the grid. The output is a texture, so the field has the resolution of that texture and sub-pixel detail is gone. Brute force is exact and continuous at any zoom.
• It needs float render targets and ping-pong. On WebGL2 that is an extension check and two framebuffers. Not hard, and not nothing.
• It gives you the nearest seed's identity for free, which brute force also does but at the cost of carrying it through the loop. For anything that needs to know which source won, the flood output is already the right shape.

How this benchmark lied twice before it worked

Both worth repeating because they are the two standard ways a GPU measurement comes out confidently wrong:

1. The flush read the wrong target. Every pass rendered to a framebuffer object, and the timer's readPixels read the default framebuffer, so it waited for nothing. Brute force measured 0.000ms at every seed count, which looks like a triumph rather than a bug.
2. The seed pass was brute force in disguise. The first version seeded by looping over every seed at every pixel, which makes the "jump flood" path O(N) per pixel plus ten extra passes. It lost at every count, and the conclusion would have been the exact opposite of the truth.

The tell for the second one was in the data: the supposedly flat method was not flat. An algorithm whose whole property is independence from N is measurable against itself, and a curve where there should be a line is the measurement being wrong rather than the algorithm.

Rules of thumb

1. Brute force until about 500 moving seeds, on desktop, at 1080p or below. Verify it on your own hardware, it is an afternoon.
2. Jump flooding costs ceil(log2(maxdim)) full-screen passes and nothing else. It is flat by construction.
3. Cut flood passes to the influence radius you actually need. Ten passes buys screen-wide reach nobody asked for.
4. Expensive seeds bring the crossover down proportionally. Point seeds are the cheapest case.
5. Jump flooding is approximate and grid-quantized. Brute force is exact and continuous.
6. Benchmark by reading back the target you actually wrote, and distrust a flat curve you did not earn.

All 61 notes · How to use them · Credits

New notes as they land

One email when something new goes up. No newsletter, no schedule, nothing else.

Send me new notes

Double opt-in, so watch for a confirmation email. Unsubscribe any time.