Bevy-spine-gpu (3/4): Painter’s order and instancing

In post 2, spine-gpu’s data path came down to two flat buffers per frame and a single instanced draw per skeleton type. It wasn’t always one draw. For a long time spine-gpu issued one draw command per character and per slot, 144,000 of them per frame at 8,000 characters, because I believed that was the only way to get the overlaps right. It wasn’t. This post is about that mistake: what the GPU actually guarantees about drawing order, what the fix bought, and why the frame time barely noticed.

All numbers are from the same machine as before (Ryzen 9 9950X3D, RTX 5080, Vulkan, 1920×1080) and the scene from post 1: Ella, 27 bones and 18 slots, playing a random animation at a random phase. spine-gpu runs on Bevy 0.14. The code is in bevy-spine-gpu, the benchmark in bevy-spine-gpu-benchmark.

Why order matters

A Spine character is a stack of images: back arm, body, head, front arm, each one a slot. They are drawn back to front with alpha blending, so whatever is drawn later ends up on top. There’s no depth buffer; the order is the depth. That’s painter’s order.

With many characters, it applies twice. Within a character, the slots have to come in the skeleton’s order. Between characters, a character has to be drawn completely, all 18 slots, before the next one starts. Otherwise Ella’s front arm ends up behind the body of the Ella standing behind her.

What the old code did

spine-gpu has always kept the mesh of a skeleton type in one index buffer, with the slots one after another in draw order. Drawing one character is then just a range of that index buffer. The question was how to draw thousands of characters.

The old code built an indirect buffer every frame, with one DrawIndexedIndirect command per character and slot, and drew it with a single multi_draw_indexed_indirect:

for first_instance in 0..n_instances {
    for (first_index, vertex_count) in slots.iter().copied() {
        // We draw each instance separately so overlaps look always correct.
        // In principle this could still heavily use instancing if we take
        // care to only draw non-overlapping meshes/instances at the same time.
        // Currently not considered worth the hassle.
        indirect_args.push(DrawIndexedIndirect {
            vertex_count,
            instance_count: 1,
            first_index,
            vertex_offset: 0,
            first_instance: first_instance as u32,
        });
    }
}

The comment is from the old code, and it shows what I (wrongfully) assumed: that an instanced draw renders its instances “at the same time”, in no particular order, so overlapping instances could come out wrong. Instancing would only be safe for characters that don’t overlap. In hindsight I shouldve done the research on indexed draws before coding this up and writing the comment, but still this errs on the safe side in terms of correctness.

At 8,000 characters that’s 144,000 commands of 20 bytes, 2.9 MB per frame, written on the CPU and uploaded into a newly created buffer every frame.

What the GPU actually guarantees

GPUs do run thousands of vertices and fragments in parallel. But the API promises that the result is as if primitives (here: triangles) were processed one after another, in a well-defined order. The Vulkan spec calls it primitive order: draw commands in submission order, then for each draw its instances from lowest to highest, then within an instance the primitives in index buffer order. Blending writes to the framebuffer in that order. D3D12 and Metal give the same guarantee. The hardware keeps it with ordering logic at the end of the pipeline: fragments of different triangles can be shaded in parallel, but they are blended in primitive order.

So one instanced draw over the whole index buffer, draw_indexed(0..n, 0, 0..instances), rasterizes all slots of instance 0 back to front, then all slots of instance 1, and so on. That’s exactly the sequence the 144,000 commands spelled out by hand. The old code didn’t buy any ordering the single draw doesn’t already have. It just paid for it per command.

Proving it’s identical

I measured the switch on the old code (before the data path changes of post 2), with a temporary environment variable that replaces the per-slot commands with one instanced command per skeleton type, and nothing else. Both modes ran back to back at 2,000 to 32,000 characters, and the whole sweep twice.

First: same pixels? With the animation frozen, the screenshots of both modes are byte-identical PNGs, same SHA-256. Not “looks the same”, the same bytes.

Then the cost:

Per-slot draws vs one instanced draw, at 2,000 to 32,000 characters: render thread and GPU time drop by a third to a half, the frame time stays the same

At 8,000 characters:

  • GPU time (PresentMon): 5.34 → 3.42 ms, −36%. At 32,000: 24.8 → 13.0 ms, −48%.
  • Render thread: 3.10 → 1.91 ms, −38%.
  • Frame time: 8.81 → 8.52 ms, −3%.

The GPU numbers make a nice worked example. At 32,000 characters the instanced version saves 11.8 ms of GPU time per frame and 576,000 − 1 draw commands. That’s about 20 ns per draw command. Each of these draws is small, one slot of one character, a few triangles. At that size, the fixed cost of a draw (the command processor reading the command, setting up the draw, a pipeline that doesn’t fill up with so little work) is a large part of the cost. The render thread saved about 8 ns per command: building it, and uploading 20 bytes.

Why the frame time didn’t move

The GPU work almost halved, the render thread lost 40%, and the frame got 3% faster. That’s not a measurement error; it’s Amdahl’s law. spine-gpu’s frame is set by the main thread, which samples the animations: 7.2 of the 8.8 ms at 8,000 characters. Bevy runs the render thread in parallel with the next frame’s main thread, and the GPU in parallel with both. Making either of them faster doesn’t help while they’re waiting for the main thread anyway. In the old version at 32,000 characters, the GPU was busy for 25 ms of a 41 ms frame and idle for the rest.

So did the change not matter? It did, it just didn’t show yet. Had the main thread been twice as fast, the per-slot version would have been GPU-bound, and the frame time would have shown the full difference. Post 4 is about the main thread.

The other order: between characters

One instanced draw keeps the order within a skeleton type, and between characters it’s the order of the instance buffer. In spine-gpu, that’s spawn order (with a swap on despawn). That’s fine for things that don’t overlap, or don’t move, like buildings. For characters walking around a 2D scene, it’s wrong: a character lower on screen should be in front of the one above it, and that changes every time someone moves.

So spine-gpu has a second draw group. Skeleton types loaded as sorted are drawn after all others, and their instances are ordered across all those types by a per-instance sort key (render/draw_order.rs). Every frame, on the render thread:

  1. Update last frame’s order: drop despawned instances, append new ones, refresh the keys.
  2. Sort it. Only small items (entity, key, type, position in the buffer) are sorted, never the instance data. The sort is stable, and Rust’s sort is adaptive: when only a few characters swap places, the input is almost sorted and the sort is close to linear.
  3. Cut the sorted order into runs of consecutive instances of the same type.
  4. Pack the instances in sorted order into the instance buffers, after the unsorted ones.

Each run is then a contiguous range of instances and gets one instanced draw. With a single skeleton type, that’s still one draw, however the characters are sorted. The worst case is several types, randomly mixed: with three types, the next character in the order is of a different type two thirds of the time, so 8,000 characters make about 5,300 runs, each with its own draw, bind group and index buffer.

The benchmark has scenes for exactly this: y-sorted, characters bobbing up and down so that the order keeps changing, with one type or three copies of Ella as different types. At 8,000 characters, render thread, unsorted → sorted:

Render thread time at 8,000 characters, unsorted vs y-sorted: 0.68 → 1.01 ms for one type, 0.68 → 1.30 ms for one type moving, 0.69 → 2.64 ms for three types moving
  • One type, standing still: 0.68 → 1.01 ms.
  • One type, moving: 0.68 → 1.30 ms.
  • Three types, moving: 0.69 → 2.64 ms. The extra 5,300 runs cost about 1.3 ms, 0.25 µs per run.

GPU time is the same for all of these scenes, about 2.6 ms: the GPU draws the same triangles, only in a different order and split into more draws. The frame time grows by up to 5% in the moving scenes, and that growth is on the main thread, not the render thread. I haven’t profiled where it comes from.

For comparison: the other three renderers show no difference between sorted and unsorted scenes. They go through Bevy’s sorted 2D phase either way.

The render thread now has room: 2.6 ms of work next to 7.2 ms of main thread. Once the main thread gets faster, the worst case is what will show first. Since the vertices are pulled from storage buffers anyway, one way out would be to put all types into shared buffers and draw all runs with one multi_draw_indexed_indirect, one command per run. That would be back to indirect draws, but per run instead of per character and slot. I haven’t tried it.

Summary

  • The old code drew every slot of every character as its own indirect command, 144,000 per frame at 8,000 characters, because I thought instancing would mix up the overlaps.
  • Graphics APIs guarantee primitive order: instance by instance, then index by index. One instanced draw per skeleton type gives byte-identical pixels.
  • GPU time −36 to −48%, render thread −38%. Frame time −3%, because the main thread sets the frame time.
  • Sorting characters across types costs about 0.25 µs per run of same-type characters on the render thread, and no GPU time.

Next, post 4: the main thread, where the frame time actually goes now.