A Faster Merge Sort For Mesa 26.3 Vulkan Drivers To Benefit Ray-Tracing

One of the latest optimizations to the Mesa Vulkan drivers by Natalie Vock of Valve's Linux graphics team is faster and more vRAM efficient sorting for Morton code keys that are important for fast BVH construction and greater GPU parallelism. Morton code keys are 1D integer values from interleaving binary coordinates of 3D points for mapping spatial data into a single dimension. The Radeon RADV, Intel ANV, Turnip Adreno, and Lavapipe Mesa Vulkan drivers have all relied on the same sorting function for these keys. But Natalie Vock discovered some inefficiencies in the current sorting code and in turn made a custom merge-sort that should perform better for smaller data sets. And it should be more vRAM efficient too. Natalie Vock explained of this work in the three month old merge request: "A custom merge-sort is going to be a bit worse for larger problem sizes, but absolutely eviscerates radix sort for tiny problems. The mergesort operates within one single dispatch without any intermediate barriers, as well as [benefiting] from tighter coupling with the rest of AS build code to save a VRAM roundtrip writing out and reading back the unsorted keys. For sufficiently small problems (<512 elements on RADV with a subgroup size of 64), all keys can be generated and immediately sorted within shared memory without hitting VRAM even once (except to write out the sorted data)." This new custom-made merge sort is found to be faster especially on small BVHs and better efficiency with reduced vRAM roundtrips. After three months of testing and review while working out some bugs, last week the code was merged to Mesa 26.3 for benefiting all the open-source Vulkan drivers. For those interested in all the technical details, see the merge request.