Суть оптимизации
Разработчик из Valve Linux graphics team Нэнси Вокк (Natalie Vock) реализовала в Mesa 26.3 улучшенный алгоритм сортировки для ключей Мортона. Эти 1D-целочисленные значения критически важны для быстрого построения иерархических структур объемов (BVH) и повышения параллелизма на GPU. Ранее все основные открытые драйверы — Radeon RADV, Intel ANV, Turnip Adreno и Lavapipe — использовали единую функцию сортировки, которая оказалась неэффективной для небольших наборов данных.
Технические детали и метрики
Новый кастомный merge sort превосходит традиционный radix sort в сценариях с малым объемом данных. Ключевые преимущества новой реализации:
- Отсутствие барьеров: Сортировка выполняется в рамках одного dispatch без промежуточных барьеров синхронизации.
- Экономия VRAM: Алгоритм тесно интегрирован с кодом построения ускоренной структуры (AS build), что позволяет избежать лишних циклов записи и чтения несортированных ключей из видеопамяти.
- Работа с shared memory: Для задач с количеством элементов менее 512 (при размере подгруппы 64 на RADV) все ключи генерируются и сортируются непосредственно в разделяемой памяти, не обращаясь к VRAM вообще (за исключением финальной записи результата).
Сравнение подходов
| Характеристика | Старый подход (Radix Sort) | Новый подход (Merge Sort в Mesa 26.3) |
|---|---|---|
| Эффективность на малых данных | Низкая | Высокая («абсолютно уничтожает» radix sort) |
| Доступ к VRAM | Частые циклы чтения/записи | Минимизирован (только финальная запись) |
| Синхронизация | n||
| Промежуточные барьеры | Отсутствуют (одиночный dispatch) | |
| Применимость | Универсально, но с оверхолдом | Оптимизировано для малых BVH (<512 элементов) |
Значение для пользователей
Патч был слит в Mesa 26.3 после трех месяцев тестирования и исправления ошибок. Это улучшение коснется всех открытых драйверов Vulkan, что особенно заметно скажется на производительности трассировки лучей в играх и приложениях, использующих небольшие или средние сцены, где накладные расходы на сортировку были ранее существенным узким местом.
Источник: Phoronix ↗