Use radix sort for sort phase and sprite sorting

[superdump]

Background

We currently use sort_by_key to sort PhaseItems in the sort phase, and sort_unstable_by to sort extracted sprites in queue_sprites.

• sort_by_key - This sort is stable (i.e., does not reorder equal elements) and O(m * n * log(n)) worst-case, where the key function is O(m).
• sort_unstable_by - This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not allocate), and O(n * log(n)) worst-case.

For large numbers of items to sort, such as in bevymark or many_sprites where n > 100_000, and given sort keys that are a small and fixed number of bits such as the f32 that we are commonly using, a radix sort could/should be much faster.

crates

I investigated sorting 10M random f32s in the range 0.1f32..1000.0f32 (the default perspective camera near and far planes) and observed the following with the available radix sort crates:

1053.388ms      stable
391.499ms       unstable
60.359ms        rdst_single
16.067ms        rdst
79.550ms        voracious_sort
79.945ms        voracious_stable_sort
13.895ms        voracious_mt_sort
65.653ms        radsort

• multi-threading
  • rdst and voracious_mt_sort results above are multi-threaded using rayon, all the rest of the results are single-threaded
  • rdst has a hard dependency on rayon, though it can be configured to do single-threaded sorting. I created an issue about making multi-threading optional as we already have a threadpool in bevy and maybe we don't want to add another: Make rayon optional nessex/rdst#2
  • voracious_radix_sort has a non-default multi-threading feature
  • radsort is single-threaded only
• According to crates.io, the crates have the following footprints:
  • radsort - 17.1kB
  • rdst - 34.3kB
  • voracious_radix_sort - 178kB
• Flexibility
  • radsort was the easiest to integrate using its sort_by_key function
  • rdst and voracious_radix_sort both require implementation of some traits on the type being sorted, and require that the type implement Copy. This cannot be done for batched sprites currently because BatchedPhaseItem contains a Range<f32> for which it is not possible to implement Copy

Proof of Concept

I made a branch here that uses radsort: https://github.com/superdump/bevy/tree/render-radix-sort .

The sorting of ExtractedSprites in queue_sprites is significantly improved by using radsort::sort_by_key like this:

            radsort::sort_by_key(extracted_sprites, |extracted_sprite| {
                (
                    extracted_sprite.transform.translation.z,
                    match extracted_sprite.image_handle_id {
                        HandleId::Id(uuid, id) => {
                            ((uuid.as_u128() & ((1 << 64) - 1)) << 64) | (id as u128)
                        }
                        HandleId::AssetPathId(id) => {
                            ((id.source_path_id().value() as u128) << 64)
                                | (id.label_id().value() as u128)
                        }
                    },
                )
            });

With that, on an M1 Max, the median execution time of queue_sprites in bevymark -- 20000 8 over 1500 frames increased from 9.82ms to 17.09ms, which makes no sense to me. In many_sprites it decreased from 11.34ms to 9.47ms.

The median execution time of sort_phase_system for the relevant phase (Transparent2d for sprites, Opaque3d for 3D meshes) in many_cubes -- sphere it decreased from 0.728ms to 0.094ms. In bevymark -- 20000 8 it increased from 0.184ms to 1.95ms, which makes no sense. And in many_sprites it increased from 0.106ms to 1.19ms.

This is quite confusing. I haven't been able to figure out why the sort performance gets worse. radsort claims both best and worst execution time of O(n), space complexity of O(n), and that it is a stable sort so it does not reorder equal items. On the branch, all the sort_key implementations are inlined.

Next steps

• Figure out why radsort is much slower in many cases
• Try voracious_radix_sort or rdst to see if they perform consistently better, though rdst would likely not be approved unless its multi-threading were made optional.
  • Make multi-threading optional in rdst if it turns out to be a preferable solution due to the smaller crate footprint

[superdump]

I added a BatchRange containing a start and end u32, deriving Copy and implementing a fn as_range(&self) -> Range<u32>.

I tried rdst, which is multi-threaded by default and on bevymark -- 20000 8 queue_sprites increased from 9.82ms on main to 25.59ms, and the sort phase increased from 0.184ms on main to 2.13ms. many_sprites queue_sprites increased to 14.72ms (worse than radsort) and sort phase increased to 1.29ms. many_cubes -- sphere sort phase did decrease to 0.104ms, but that's still worse than radsort for every single case.

[bjorn3]

radsort claims both best and worst execution time of O(n)

According to wikipedia radixsort is O(nw) where n is the amount of elements and w is the length of the element. It is provably impossible to have a sort with a worst case better than O(n log n).

[superdump]

radsort claims both best and worst execution time of O(n)

According to wikipedia radixsort is O(nw) where n is the amount of elements and w is the length of the element. It is provably impossible to have a sort with a worst case better than O(n log n).

I think that is only true for comparison sorts. Radix sort is not a comparison sort.

[superdump]

I tried voracious_radix_sort using voracious_sort() which is an unstable radix sort. It does have a stable variant so I could try that too. It also has a multi-threaded variant. But I thought I'd start here.

bevymark -- 20000 8 queue_sprites increased from 9.82ms on main to 10.02ms, and the sort phase decreased from 0.184ms on main to 0.124ms. many_sprites queue_sprites increased from 11.34ms to 14.6ms and sort phase decreased from 0.106ms to 0.078ms. many_cubes -- sphere sort phase decreased from 0.728ms to 0.118ms.

So it is at least consistently better than Vec::sort_by_key for the sort phase, by 0.06-0.61ms in these tests, with the main significant benefit for many_cubes -- sphere. It is not good for sorting in queue_sprites which needs to consider not only the transform z (32 bits f32) but also the handle id (either 2 x u64 or u64 + u128), and I even cheated here and packed the f32 and handle id into a u128, dropping some of the bits and hoping to avoid collisions. In these tests the handles are all the same but I wanted to do something close to representative. Although, the sort phase should use a stable sort and that may impact performance so I'll try that.

[superdump]

sort method	many_sprites queue_sprites	many_sprites sort phase	bevymark queue_sprites	bevymark sort phase	many_cubes sort phase
main	11.34ms	0.106ms	9.82ms	0.184ms	0.728ms
radsort	9.47ms	1.19ms	17.09ms	1.95ms	0.094ms
rdst (multi-threaded)	14.72ms	1.29ms	25.59ms	2.13ms	0.104ms
voracious unstable	14.6ms	0.078ms	10.02ms	0.124ms	0.118ms
voracious stable	14.74ms	0.078ms	9.99ms	0.125ms	0.117ms
voracious multi-threaded unstable	14.76ms	0.098ms	10.04ms	0.155ms	0.237ms

[superdump]

I realised that for the sort in queue_sprites, the sprites don't need to be ordered by the sprite image HandleId, just grouped. Perhaps there is a faster way to sort only by translation z and then group by image handle id.

[superdump]

I tried to rework queue_sprites with the following ideas:

• Sort the Vec<ExtractedSprite> only by translation z which should be faster for radix sort
• Based on an assumption that in practice there would be multiple sprites at a z level, which I have since realised is wrong in many types of 2D games, when iterating the translation z order extracted sprites, push the ExtractedSprite onto a Vec in a HashMap<SpriteBatch, Vec>, and then when z changes, process the batches (which change based on whether the image handle id or colored state changed.

My assumption that z are relatively few compared to sprites was wrong and that wasn't a well-considered optimisation attempt. I was mostly following the path of the radix sort hammer working well for small sort keys.

Ultimately, I dropped that path. I don't know of a good way to improve queue_sprites consistently using radix sort. The best way to improve it was rather to pull in rayon and use its par_sort_unstable_by. This made a big improvement to queue_sprites in many_sprites but no improvement to bevymark. sort phase is a bit hit and miss being a bit slower for the sprites and faster for many_cubes.

sort method	many_sprites queue_sprites	many_sprites sort phase	bevymark queue_sprites	bevymark sort phase	many_cubes sort phase
main	11.34ms	0.106ms	9.82ms	0.184ms	0.728ms
rayon par_sort_	7.2ms	0.219ms	9.83ms	0.305ms	0.476ms

I guess bevymark doesn't have enough sprites for the sort to make any difference - I am running it with -- 20000 8 for a total of 160k sprites - where many_sprites has 409,600 sprites.

Summary

• voracious_stable_sort is consistently as good or better for the sort phase and is single-threaded
• rayon::par_sort_unstable_by is as good or potentially significantly better for queue_sprites

[mockersf]

would it be possible to adapt the sort based on counts or previous execution? do one frame with each, then do the next 500 frames with the best one?

[superdump]

would it be possible to adapt the sort based on counts or previous execution? do one frame with each, then do the next 500 frames with the best one?

I suppose you could, but looking at the results, we could implement the use of voracious_stable_sort for the sort phase, and rayon::par_sort_unstable_by for queue_sprites and probably obtain the fastest for all cases.

However, I didn’t make a PR for this because the sort phase gains are small and scene-dependent for the additional dependency on voracious_radix_sort, and distaste was expressed for including rayon due to competing threadpools and in the supposedly more realistic case of bevymark, there was no benefit.

Did I miss something in what you were asking?

[superdump]

Cart linked to #3460 (review) on Discord as relevant investigation of and discussion about how batching works in general and for sprites.

[nessex]

For an additional option, I've just released rdst = { version = "0.20.0", default-features = false }. If you disable the default feature multi-threading it can be used in entirely single-threaded mode without rayon and other large dependencies being pulled in.

This had a huge impact on bloat:
nessex/rdst#3 (comment)

[superdump]

Nice, thanks!

[nessex]

As discussed in discord, apart from the first few frames this is mostly just sorting already sorted Vecs. So it's really checking how fast you can detect that the Vec is already sorted. I just released rdst 0.20.1 which has a better check for this case, which should bring it a bit more in-line with the others.

In terms of bevy making use of radix sort, I think it would be good to work out what a good representative scene is. Trying to think up a worst-case scenario, some sort of sprite based particle system would probably be a pathological case for the sort phase.

Bevymark and many_sprites both don't stress this system very much as after the initial spawning, they don't alter the sort order of the relevant items.