Learning

GPU Programming · Lesson 05

No holes in the horde

Remove, compact, and append without rebuilding the resident body store.

GPU-Owned Body Lifecycles

A compact dialogue on GPU-side removal, compaction, appending, overflow, synchronization, and ping-pong buffers.

Download audio · Read the script

Transcript

Host: The goal is a GPU-owned lifecycle: start with four bodies, remove one, append three, and finish with six live bodies packed into indices zero through five.

Learner: So the invariant is that live bodies fill exactly zero up to active count, with no holes, while everything from active count to capacity is spare?

Host: Exactly. Five dispatches run in order: reset, remove, compact, append, finish. A barrier separates each pair because every later phase consumes an earlier write.

Learner: And the two body buffers avoid trouble during compaction: read the source, write the destination, then swap their roles instead of copying back?

Host: Right. Each survivor or birth reserves a slot with atomicAdd on next count. Reservations are unique; slots beyond capacity raise overflow and are never written.

Learner: But reservation order depends on which invocation reaches the counter first. That means dense packing is guaranteed, while source order and the losing birth are not?

Host: Yes. At capacity six, four minus one plus three gives active six and overflow zero. At capacity five, active is five and overflow one, though any addition may lose.

Learner: My takeaway: the CPU submits tiny removal and addition queues, while GPU counters and ping-pong buffers own the lifecycle. Readbacks only prove the result, and indices are not identities.

Lesson 4 kept one fixed-capacity body buffer alive across ticks, but its logical count stayed on the CPU. That works only while the CPU knows every birth and death. Your target architecture does not grant it that knowledge.

Today’s win: start with four GPU-resident bodies, remove one, append three, and finish with six densely packed live bodies. The CPU uploads only two tiny request queues. A GPU counter owns the new logical count; an asynchronous readback appears only once as proof.

The lifecycle invariant: live bodies occupy exactly [0, active_count); every index from active_count to capacity is spare. No hole survives the lifecycle pass.

01 One list, five dependent dispatches

Dispatch Reads Writes
Reset Nothing next_count = 0, overflow = 0
Remove Removal indices Clears source ALIVE flags
Compact Live source records Dense destination records + next_count
Append Addition records More destination records + counters
Finish next_count Clamped active_count

The source and destination are two persistent, fixed-capacity buffers. After the pass, swap their roles; do not copy destination back over source. This ping-pong arrangement prevents a compacting invocation from overwriting a source record that another invocation has not read yet.

A barrier belongs between every pair above because the later dispatch consumes an earlier write. Godot exposes that dependency as compute_list_add_barrier(). The underlying Vulkan rule is read-after-write: shader writes must be made available and visible before the next compute dispatch reads them. (Godot: compute_list_add_barrier, Vulkan synchronization examples)

02 Lab: watch the holes disappear

Run one dispatch at a time. Reset a few times: the destination order changes because invocations may reach the counter in any order. Then lower capacity from six to five and predict the two final counters before running.

At capacity six, the arithmetic is 4 − 1 + 3 = 6: active count six, overflow zero. At capacity five, the same requests produce active count five and overflow one. Which birth loses the race is deliberately unspecified; the overflow count is the promise.

03 The one-line allocator

uint slot = atomicAdd(counts.next_count, 1u);
if (slot < params.capacity) {
    destination.data[slot] = body;
} else {
    atomicAdd(counts.overflow_count, 1u);
}

atomicAdd returns the counter’s old value. That makes the old value a unique reservation ticket: one invocation gets slot 0, another gets slot 1, and no two get the same slot. The GLSL specification guarantees atomicity for integer members of storage buffers, but it does not guarantee which invocation arrives first. (GLSL 4.60 §8.11)

Two guarantees, one non-guarantee

That last point is architectural: a body index is a location, not an enduring identity. Compaction invalidates stored indices. This demo removes an index immediately; production code uses GPU-side death flags or validated handles when requests can be delayed.

04 The lifecycle shader

Create res://lifecycle.glsl. One pipeline performs all five phases; a 16-byte push-constant block selects the phase and carries its queue length.

#[compute]
#version 450

layout(local_size_x = 64, local_size_y = 1, local_size_z = 1) in;

const uint FLAG_ALIVE = 1u << 0;
const uint MODE_RESET   = 0u;
const uint MODE_REMOVE  = 1u;
const uint MODE_COMPACT = 2u;
const uint MODE_APPEND  = 3u;
const uint MODE_FINISH  = 4u;

struct Body {
    vec2 position;
    vec2 velocity;
    float radius;
    float health;
    uint flags;
    uint padding;
};

layout(set = 0, binding = 0, std430) restrict buffer SourceBodies {
    Body data[];
} source;

layout(set = 0, binding = 1, std430) restrict writeonly buffer DestinationBodies {
    Body data[];
} destination;

layout(set = 0, binding = 2, std430) restrict readonly buffer AdditionQueue {
    Body data[];
} additions;

layout(set = 0, binding = 3, std430) restrict readonly buffer RemovalQueue {
    uint indices[];
} removals;

layout(set = 0, binding = 4, std430) restrict buffer Counters {
    uint active_count;
    uint next_count;
    uint overflow_count;
    uint padding;
} counts;

layout(push_constant, std430) uniform Params {
    uint mode;
    uint item_count;
    uint capacity;
    uint padding;
} params;

void main() {
    uint id = gl_GlobalInvocationID.x;

    if (params.mode == MODE_RESET) {
        if (id == 0u) {
            counts.next_count = 0u;
            counts.overflow_count = 0u;
        }
        return;
    }

    if (params.mode == MODE_REMOVE) {
        if (id >= params.item_count) { return; }
        uint index = removals.indices[id];
        if (index < counts.active_count) {
            atomicAnd(source.data[index].flags, ~FLAG_ALIVE);
        }
        return;
    }

    if (params.mode == MODE_COMPACT) {
        if (id >= counts.active_count) { return; }
        Body body = source.data[id];
        if ((body.flags & FLAG_ALIVE) == 0u) { return; }

        uint slot = atomicAdd(counts.next_count, 1u);
        if (slot < params.capacity) {
            destination.data[slot] = body;
        } else {
            atomicAdd(counts.overflow_count, 1u);
        }
        return;
    }

    if (params.mode == MODE_APPEND) {
        if (id >= params.item_count) { return; }
        uint slot = atomicAdd(counts.next_count, 1u);
        if (slot < params.capacity) {
            destination.data[slot] = additions.data[id];
        } else {
            atomicAdd(counts.overflow_count, 1u);
        }
        return;
    }

    if (params.mode == MODE_FINISH && id == 0u) {
        counts.active_count = min(counts.next_count, params.capacity);
    }
}

The compact dispatch launches for physical capacity, not a CPU copy of the current count. Every invocation reads the explicit GPU-resident active_count before touching a record. Physical array length still never stands in for logical count.

05 Godot: bind once, change the mode

Create res://lifecycle_demo.gd, attach it to any node, and run under Forward+. The helpers preserve the 32-byte schema from Lesson 3 and make the five bindings visible.

extends Node

const LIFECYCLE_SHADER: RDShaderFile = preload("res://lifecycle.glsl")
const STRIDE := 32
const CAPACITY := 6
const START_COUNT := 4
const ADDITION_COUNT := 3
const REMOVAL_COUNT := 1
const LOCAL_SIZE := 64
const FLAG_ALIVE := 1 << 0

const MODE_RESET := 0
const MODE_REMOVE := 1
const MODE_COMPACT := 2
const MODE_APPEND := 3
const MODE_FINISH := 4

var _shader := RID()
var _pipeline := RID()
var _body_a := RID()
var _body_b := RID()
var _additions := RID()
var _removals := RID()
var _counters := RID()
var _set_a_to_b := RID()
var _set_b_to_a := RID()
var _front_is_a := true

func _ready() -> void:
    RenderingServer.call_on_render_thread(_gpu_setup)

func write_body(bytes: PackedByteArray, index: int,
        position: Vector2, velocity: Vector2) -> void:
    var offset := index * STRIDE
    bytes.encode_float(offset + 0, position.x)
    bytes.encode_float(offset + 4, position.y)
    bytes.encode_float(offset + 8, velocity.x)
    bytes.encode_float(offset + 12, velocity.y)
    bytes.encode_float(offset + 16, 2.0)
    bytes.encode_float(offset + 20, 10.0)
    bytes.encode_u32(offset + 24, FLAG_ALIVE)
    bytes.encode_u32(offset + 28, 0)

func storage_uniform(binding: int, buffer: RID) -> RDUniform:
    var uniform := RDUniform.new()
    uniform.uniform_type = RenderingDevice.UNIFORM_TYPE_STORAGE_BUFFER
    uniform.binding = binding
    uniform.add_id(buffer)
    return uniform

func make_set(rd: RenderingDevice, source: RID, destination: RID) -> RID:
    var uniforms := [
        storage_uniform(0, source),
        storage_uniform(1, destination),
        storage_uniform(2, _additions),
        storage_uniform(3, _removals),
        storage_uniform(4, _counters),
    ]
    return rd.uniform_set_create(uniforms, _shader, 0)

func _gpu_setup() -> void:
    var rd := RenderingServer.get_rendering_device()
    if rd == null:
        push_error("Global RenderingDevice unavailable; use Forward+.")
        return

    _shader = rd.shader_create_from_spirv(LIFECYCLE_SHADER.get_spirv())
    _pipeline = rd.compute_pipeline_create(_shader)

    var a_bytes := PackedByteArray()
    a_bytes.resize(CAPACITY * STRIDE)
    write_body(a_bytes, 0, Vector2(0, 0), Vector2.RIGHT)
    write_body(a_bytes, 1, Vector2(10, 0), Vector2.RIGHT)
    write_body(a_bytes, 2, Vector2(20, 0), Vector2.RIGHT)
    write_body(a_bytes, 3, Vector2(30, 0), Vector2.RIGHT)
    _body_a = rd.storage_buffer_create(a_bytes.size(), a_bytes)

    var b_bytes := PackedByteArray()
    b_bytes.resize(CAPACITY * STRIDE)
    _body_b = rd.storage_buffer_create(b_bytes.size(), b_bytes)

    var add_bytes := PackedByteArray()
    add_bytes.resize(ADDITION_COUNT * STRIDE)
    write_body(add_bytes, 0, Vector2(100, 0), Vector2.LEFT)
    write_body(add_bytes, 1, Vector2(110, 0), Vector2.LEFT)
    write_body(add_bytes, 2, Vector2(120, 0), Vector2.LEFT)
    _additions = rd.storage_buffer_create(add_bytes.size(), add_bytes)

    var remove_bytes := PackedInt32Array([1]).to_byte_array()
    _removals = rd.storage_buffer_create(remove_bytes.size(), remove_bytes)

    var counter_bytes := PackedByteArray()
    counter_bytes.resize(16)
    counter_bytes.encode_u32(0, START_COUNT)
    _counters = rd.storage_buffer_create(counter_bytes.size(), counter_bytes)

    _set_a_to_b = make_set(rd, _body_a, _body_b)
    _set_b_to_a = make_set(rd, _body_b, _body_a)
    _gpu_lifecycle(rd)

func groups_for(item_count: int) -> int:
    return ceili(float(item_count) / LOCAL_SIZE)

func push_and_dispatch(rd: RenderingDevice, list: int,
        mode: int, item_count: int, groups: int) -> void:
    var params := PackedByteArray()
    params.resize(16)
    params.encode_u32(0, mode)
    params.encode_u32(4, item_count)
    params.encode_u32(8, CAPACITY)
    rd.compute_list_set_push_constant(list, params, params.size())
    rd.compute_list_dispatch(list, groups, 1, 1)

func _gpu_lifecycle(rd: RenderingDevice) -> void:
    var lifecycle_set := _set_a_to_b if _front_is_a else _set_b_to_a
    var list := rd.compute_list_begin()
    rd.compute_list_bind_compute_pipeline(list, _pipeline)
    rd.compute_list_bind_uniform_set(list, lifecycle_set, 0)

    push_and_dispatch(rd, list, MODE_RESET, 1, 1)
    rd.compute_list_add_barrier(list)
    push_and_dispatch(rd, list, MODE_REMOVE, REMOVAL_COUNT, groups_for(REMOVAL_COUNT))
    rd.compute_list_add_barrier(list)
    push_and_dispatch(rd, list, MODE_COMPACT, CAPACITY, groups_for(CAPACITY))
    rd.compute_list_add_barrier(list)
    push_and_dispatch(rd, list, MODE_APPEND, ADDITION_COUNT, groups_for(ADDITION_COUNT))
    rd.compute_list_add_barrier(list)
    push_and_dispatch(rd, list, MODE_FINISH, 1, 1)
    rd.compute_list_end()

    _front_is_a = not _front_is_a
    rd.buffer_get_data_async(_counters, _on_counts_readback)

func _on_counts_readback(bytes: PackedByteArray) -> void:
    var active_count := bytes.decode_u32(0)
    var overflow_count := bytes.decode_u32(8)
    print("active=", active_count, " overflow=", overflow_count)
    RenderingServer.call_on_render_thread(_request_body_proof.bind(active_count))

func _request_body_proof(active_count: int) -> void:
    var rd := RenderingServer.get_rendering_device()
    var front := _body_a if _front_is_a else _body_b
    rd.buffer_get_data_async(front, _on_bodies_readback.bind(active_count))

func _on_bodies_readback(bytes: PackedByteArray, active_count: int) -> void:
    print("dense positions (order is unspecified):")
    for i in active_count:
        var offset := i * STRIDE
        var position := Vector2(
            bytes.decode_float(offset + 0),
            bytes.decode_float(offset + 4))
        print(i, ": ", position)

func _exit_tree() -> void:
    var owned := [_set_a_to_b, _set_b_to_a, _pipeline, _body_a, _body_b,
        _additions, _removals, _counters, _shader]
    RenderingServer.call_on_render_thread(func():
        var rd := RenderingServer.get_rendering_device()
        for rid in owned:
            if rid.is_valid():
                rd.free_rid(rid)
    )

The body proof should contain positions 0, 20, 30, 100, 110, and 120 in some order. Position 10 was removed. The important output is stable even when the order is not:

active=6 overflow=0
dense positions (order is unspecified):
0: (...)
...

The two asynchronous downloads are diagnostics, not lifecycle inputs. Remove them and the next tick still has its source buffer and logical count entirely on the GPU.

06 Your practice: force a bounded failure

Predict before running

  1. Change CAPACITY from 6 to 5.
  2. Write down the expected active and overflow values.
  3. Run three times and note which addition position is absent.
  4. Explain why the missing position may change while both counters remain correct.

Expected: active=5 overflow=1. If overflow remains zero, check the bounds test before the destination write. If results change only when you remove the barriers, you have observed a synchronization bug—not useful nondeterminism.

07 Retrieval

Answer without scrolling back. One attempt each.

08 Where to go from here

Primary source — read one section. GLSL 4.60 §8.11, Atomic Memory Functions defines exactly what atomicAdd does, what it returns, and which storage locations it may update. For the dispatch boundaries, keep the Khronos compute-to-compute synchronization example beside Godot’s compute_list_add_barrier() entry.

Keep for reference. The new GPU lifecycle cheat sheet compresses the phase order, slot-reservation pattern, invariants, and failure modes. The glossary now includes atomic operation, append queue, compaction, overflow counter, and ping-pong buffers.

Next lesson: render procedural quads from the active body buffer and let the GPU-resident count determine how many instances are drawn.