Repository navigation
Use radix sort for sort phase and sprite sorting #4291
Description
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
rdstandvoracious_mt_sortresults above are multi-threaded usingrayon, all the rest of the results are single-threadedrdsthas a hard dependency onrayon, 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#2voracious_radix_sorthas a non-default multi-threading featureradsortis single-threaded only
- According to crates.io, the crates have the following footprints:
radsort- 17.1kBrdst- 34.3kBvoracious_radix_sort- 178kB
- Flexibility
radsortwas the easiest to integrate using itssort_by_keyfunctionrdstandvoracious_radix_sortboth require implementation of some traits on the type being sorted, and require that the type implementCopy. This cannot be done for batched sprites currently becauseBatchedPhaseItemcontains aRange<f32>for which it is not possible to implementCopy
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
radsortis much slower in many cases - Try
voracious_radix_sortorrdstto see if they perform consistently better, thoughrdstwould likely not be approved unless its multi-threading were made optional.- Make multi-threading optional in
rdstif it turns out to be a preferable solution due to the smaller crate footprint
- Make multi-threading optional in
Activity
superdump commentedon Mar 22, 2022
I added a
BatchRangecontaining a start and end u32, derivingCopyand implementing afn as_range(&self) -> Range<u32>.I tried
rdst, which is multi-threaded by default and onbevymark -- 20000 8queue_spritesincreased from 9.82ms on main to 25.59ms, and the sort phase increased from 0.184ms on main to 2.13ms.many_spritesqueue_spritesincreased to 14.72ms (worse thanradsort) and sort phase increased to 1.29ms.many_cubes -- spheresort phase did decrease to 0.104ms, but that's still worse thanradsortfor every single case.bjorn3 commentedon Mar 22, 2022
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 commentedon Mar 22, 2022
I think that is only true for comparison sorts. Radix sort is not a comparison sort.
superdump commentedon Mar 22, 2022
I tried
voracious_radix_sortusingvoracious_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 8queue_spritesincreased from 9.82ms on main to 10.02ms, and the sort phase decreased from 0.184ms on main to 0.124ms.many_spritesqueue_spritesincreased from 11.34ms to 14.6ms and sort phase decreased from 0.106ms to 0.078ms.many_cubes -- spheresort phase decreased from 0.728ms to 0.118ms.So it is at least consistently better than
Vec::sort_by_keyfor the sort phase, by 0.06-0.61ms in these tests, with the main significant benefit formany_cubes -- sphere. It is not good for sorting inqueue_spriteswhich 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 commentedon Mar 22, 2022
superdump commentedon Mar 22, 2022
I realised that for the sort in
queue_sprites, the sprites don't need to be ordered by the sprite imageHandleId, just grouped. Perhaps there is a faster way to sort only by translation z and then group by image handle id.superdump commentedon Mar 23, 2022
I tried to rework
queue_spriteswith the following ideas:Vec<ExtractedSprite>only by translation z which should be faster for radix sortMy 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_spritesconsistently using radix sort. The best way to improve it was rather to pull in rayon and use itspar_sort_unstable_by. This made a big improvement toqueue_spritesinmany_spritesbut no improvement tobevymark. sort phase is a bit hit and miss being a bit slower for the sprites and faster formany_cubes.I guess
bevymarkdoesn't have enough sprites for the sort to make any difference - I am running it with-- 20000 8for a total of 160k sprites - wheremany_spriteshas 409,600 sprites.Summary
voracious_stable_sortis consistently as good or better for the sort phase and is single-threadedrayon::par_sort_unstable_byis as good or potentially significantly better forqueue_spritesmockersf commentedon Mar 23, 2022
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 commentedon Mar 23, 2022
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 commentedon Mar 24, 2022
Cart linked to #3460 (review) on Discord as relevant investigation of and discussion about how batching works in general and for sprites.
nessex commentedon Mar 25, 2022
For an additional option, I've just released
rdst = { version = "0.20.0", default-features = false }. If you disable the default featuremulti-threadingit 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 commentedon Mar 26, 2022
Nice, thanks!
nessex commentedon Mar 26, 2022
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.1which 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.
2 remaining items
superdump commentedon Mar 28, 2022
@nessex I don't know how the bit position radix sorting algorithm works, but would it be better to use u32 or u64 as the agnostic sort key data type given that CPU registers are 32/64 bits? Do you leverage SIMD already for packing the u8s into registers and operating on them? I imagine you could still do so for 32-/64-bit shuffles and masks and such too?
nessex commentedon Mar 28, 2022
rdst and voracious don't explicitly pack things into SIMD registers as it depends on the
get_level/ byte extraction functions' implementation for a given type. But both are structured to automatically vectorize fairly well if your byte extraction impl supports it.For sort_key, floats are fine I think. The operations are quite primitive and vectorize well:
https://github.com/Nessex/rdst/blob/d4377cea6dd9eb1fa49091c0592f9a58feac255d/src/radix_key_impl.rs#L167
Actually, I've just pushed
0.20.2which makes the float type ordering conform to the same deterministic ordering (including NaN) as the upcomingtotal_cmpnightly function. I'm not sure exactly what the appropriate ordering for NaN's needs to be for bevy, but they do seem to exist in the data... So this could be a consideration if deciding between f32 and anything else. You could newtype / use FloatOrd if you need something a bit different.james7132 commentedon Jun 21, 2022
After #5049, we're in a position to slot any of these radix sorts, and change which algorithm we use depending on sort mode. We can handle the stable sorts separately from the unstable ones. For 3D use cases, where unstable sorts can be used for every phase, we can easily use radsort or voracious and get a 5-7x speedup, and decide on an appropriate approach for the stable/batched 2D cases.
superdump commentedon Jun 23, 2022
Probably worth retesting with latest versions of the three radix sort crates I tried.
Allow unbatched render phases to use unstable sorts (#5049)
Allow unbatched render phases to use unstable sorts (bevyengine#5049)
Allow unbatched render phases to use unstable sorts (bevyengine#5049)
Allow unbatched render phases to use unstable sorts (bevyengine#5049)
rparrett commentedon Mar 17, 2023
Looking at
queue_spritesagain with Bevy 0.10.0 and key functions from Rob's old branch. Motivated again by #8100.noisy M1 Mac, Chrome
These are just frame times plucked from
LogDiagnosticsPlugin, no tracing.bevy-vs-pixiis very a similar benchmark to bevymark, but its z values are distributed differently.It spawns pairs of sprites with
z = rng.gen::<f32>()andz + f32::EPSILON.bevymarkwas run with a hardcodedBirdScheduled { per_wave: 1000, wave: 100 }bevy-vs-pixiwas run with 32k rects (64k sprites)cached in
ExtractedSprite
quadruple key
Really fascinating. Not sure what's going on with rdst multi-threading. I did at least verify that on those runs, rayon was either in or out of the dep tree. Also re-ran the
sort_unstable_by / wasmjust to be sure.Didn't include voracious because it doesn't seem possible to write a comparable key function.
rparrett commentedon Mar 17, 2023
I threw glidesort in there for fun.
superdump commentedon Nov 5, 2023
@rparrett I was revisiting this to see if it could be closed now. What I take from the above table is that glidesort is faster on ordered arrays and radsort is faster on random ones. In which case, I think sticking with radsort is the way to go. Did I understand correctly?
rparrett commentedon Nov 5, 2023
Sounds about right / matches what I was told about radsort / sounds good to me. There may be reason to rebenchmark later. The author (of radsort) is apparently cooking up a new release.
rparrett commentedon Jan 3, 2025
Done in #9882