Performance: investigate faster sorting options

[aras-p]

Currently splat sorting uses AMD Fidelity FX based radix sorting. I actually have no idea how "good" or state-of-the-art it is, but some other options might be worth looking into:

• Alter the same sorting routine to not sort on full 32 bits of depth -- maybe 16, 20 or 24 bits would be just fine, especially if depth is quantized to be only within object's range. The current sort code is doing 4 bit radix rounds, so that would cut down on the number of rounds it does.
• Look into other sorting approaches. State of the art seems to be OneSweep radix sort, but that one might not work on all platforms (I think due to lack of globallycoherent on Metal?), plus most implementations of it seem to be hardcoded to nvidia SIMD width.

[b0nes164]

Hi @aras-p I'm the author of the OneSweep implementation for Unity.

It should be relatively simple to make a generalized version of my code that would support Nvidia and AMD and Metal. This is because, based on my own testing in CUDA, the performance of OneSweep is significantly impacted by the use of cooperative groups. Without cooperative groups, again based on my own testing, the performance of OneSweep is almost identical to the older technique reduce-then-scan However, reduce-then-scan has no forward thread progress requirements, making it amenable to Metal. Due to a mistake in testing, I mistakenly believed that use of cooperative groups was increasing performance; it's not. The issue is still the lookback phase, but it is unclear why the code in CUDA is so much more performant.

The moniker "OneSweep" is somewhat misleading (though by no fault of the authors) in that it seems to indicate that all the performance gains come from the use of Chained-Scan-With-Decoupled-Lookback in place of reduce-then-scan, when in reality the majority of the performance gains come from other techniques: GPU Multisplit, pre-scattering into shared memory, and increasing the radix bits. Importantly for us, none of these techniques are platform or hardware specific.

All this is to say that, based on my own testing in Unity DX12, the performance difference between OneSweep and reduce-then-scan is negligible, but the performance should be significantly faster than the current Fidelity FX implementation. For instance, Andrey Volodin was able to get great performance in his VR renderer using it. If you're interested I would love to contribute. Currently, I am currently working on implementing DietGPU in compute shaders, which is GPU based ANS compression, and could possibly be useful in piping data to the GPU.

[andybak]

Just want to say again that stochastic order independent transparency (using MSAA and SV_COVERAGE to smooth out the graininess) is worth considering as it potentially makes sorting unnecessary. It's used succesfully for displaying Quill animations on the Quest so it's proven on relatively low-powered hardware - and it looks pretty good.

Not that it removes the need for sorting entirely (It's worth keeping as a "best quality" mode for faster hardware) but I do suspect that the MSAA OIT will be good enough in most cases.

(feel free to remove this comment - it's slightly off-topic. I really should get around to a PR so I can settle this once and for all!)

[b0nes164]

I've made the generalized version of the reduce-then-scan (RTS from here on), with negligible performance penalties. In theory, it should be able to support wave-widths of up to 128. However, it may take some time to unit test because I need to borrow an AMD card.

After looking through the repository, I saw the issues related to sorting on hardware/platforms without wave intrinsics, and I'll handle that next. Without wave functions, we basically have to resort to an even older technique, where digit counts are accumulated in registers rather than shared memory. This is significantly slower because it means reducing the radix bits to avoid spilling the registers. However, there is no other way of maintaining the stability of the ordering otherwise, which would break the LSD radix sort.

For such low-end hardware, as @andybak mentioned, stochastic order independent transparency seems like a far better option.

[aras-p]

I've made the generalized version of the reduce-then-scan (RTS from here on), with negligible performance penalties

Sweet! If you have it ready for any sort of testing, that would be great! (I only have Windows/NVIDIA and Mac around here though)

After looking through the repository, I saw the issues related to sorting on hardware/platforms without wave intrinsics

While that would be "nice to have", it's not critical IMHO. Yes it would enable DX11 on Windows (if anyone needs it for whatever reason), and possibly some devices that people keep on asking about, but I've spent zero effort supporting yet (mobile, VR, etc.).

[b0nes164]

Preliminary results on iteration_30000 bicycle, medium asset preset, ~6.1M splats, 1920x1080, indicate about a ~30% framerate increase. On my 2080 super I went from about ~70 fps to about ~95 fps. You can see the performance uplift in the following nsight frame captures:

Previous:

New:

Honestly, I don't have very much experience debugging shaders in realtime, so my integration testing was very janky--I basically dispatched the sorting routine immediately during the GpuSorter.dispatch function call instead of through the command buffer. Then I checked if whatever was in the srcKeyBuffer and srcPayloadBuffer at the time was sorted correctly, so it will definitely need more testing, but the image appears to be free from visual artifacts.

I will make a pull request now if you want to try it out yourself on a beta branch while I begin testing on AMD hardware.

[aras-p]

Implemented by #82