djeedai / bevy_hanabi / 30753133293

58%

Build Type

push

github

Committed by web-flow

Commit Message

Parallelize GPU sorting (#555)

Switch GPU sorting of particles for ribbon effects from a naive
single-threaded insertion sort to a modern parallel sort.

This change introduces a modern parallel sort architecture, which
divides the sort task into 3 sequences of operations:
1. Intra-thread sorting of up to 16 elements with a simple odd-even
mergesort, into a local thread array.
2. Intra-workgroup "block sort" where all 64 threads of a workgroup
cooperate to mergesort those 64 sorted lists of 16 items into a sorted
list of 1024 items.
3. Final multi-pass mergesort taking lists of 1024 items and merging
them to obtain the final sorted array.

This change add state-of-the-art implementations for the first two
thread-level and workgroup-level sort passes. Parallelizing of the final
merge-sort pass is left for a future change, and is instead replaced
with a naive serial variant.

In the `worms.rs` example on an RTX 4070, this reduces the GPU time from
~16.32ms down to ~1.85ms (~11%), split between:

- The workgroup-level block sort (0.05ms).
- The subsequent merge sort, for cases where the total number of items
(particles) is > 1024 (0.55ms + 0.75ms + 0.51ms = 1.81ms; 3 passes).

Coverage Stats

228 of 389 new or added lines in 5 files covered. (58.61%)

6 existing lines in 3 files now uncovered.

5654 of 9639 relevant lines covered (58.66%)

678.56 hits per line