В real-time играх и серверах часто возникает задача: из N объектов нужно выбрать K лучших, чтобы обновить их в этом кадре.
AI для NPC: из 50 000 врагов обновить только 1000 самых важных.
Анимации: из 10 000 персонажей показать детальные анимации только для 200 ближайших к камере.
VFX: из 5000 частиц обновить только те, что в поле зрения.
Сетка LOD: из 100 000 объектов выбрать 5000 для высокого качества.
Типичный подход — посчитать оценку для каждого объекта, затем отсортировать весь массив и взять первые K элементов.
// Наивный подход: полная сортировка float[] scores = new float[N]; for (int i = 0; i < N; i++) scores[i] = Dot(features[i], weights); Array.Sort(scores, ids); // O(N log N) // Берём первые K
Проблема: сортировка 200 000 элементов занимает ~16 мс. Это весь бюджет кадра при 60 FPS. А ведь ещё нужно рендерить, обрабатывать физику, тикать AI.
Почему полная сортировка — это перебор
Сложность O(N log N). Для N = 200 000 это примерно 200 000 × 18 = 3.6 млн сравнений. Плюс аллокации временных массивов. Плюс GC-паузы.
А вам нужно всего K = 2000 элементов. Вы выбрасываете 198 000 отcортированных элементов. Это 99% потраченной работы впустую.
Дополнительная проблема: групповые квоты
Часто нужно не просто топ-K, а справедливое распределение между группами:
Анимации: не более 200 объектов
AI: не более 500 объектов
VFX: не более 300 объектов
Физика: не более 200 объектов
Сумма квот = K = 1200. Но если отсортировать общий список, одна группа (например, враги) может занять все топ-1200 мест, а другие группы (союзники, нейтралы) не получат ничего.
Правильное решение: отобрать топ-K с учётом квот на группу. Но как это сделать без многократной сортировки?
Решение: SIMD + селекция без полной сортировки
GameBudget.Net — библиотека для .NET 8.0+, которая решает обе задачи:
Топ-K через heap-селекцию: O(N log K) вместо O(N log N)
Групповые квоты через per-group heap: O(N log qᵍ) (где qᵍ — квота группы)
SIMD-умножение матриц для скоринга через SlidingRank.FastOps
dotnet add package GameBudget.Net --version 1.0.0
Ключевые идеи
Heap-селекция (без полной сортировки)
Проходим по всем N объектам.
Поддерживаем min-heap размером K.
Если новый элемент лучше худшего в куче — заменяем.
В конце heap содержит топ-K, извлекаем в отсортированном порядке.
Per-group селекция с квотами
Для каждой группы свой min-heap размером с квоту группы.
Каждый элемент попадает только в heap своей группы.
В конце собираем результат: сначала группа 0, затем группа 1, и т.д.
SIMD для массового скоринга
Вместо scalar-цикла — SIMD-умножение (AVX2, SSE).
16, 32, 64 признака обрабатываются за несколько инструкций.
Отличие от существующих решений
Решение | Принцип | Сложность | Аллокации на кадр | SIMD | Групповые квоты |
|---|---|---|---|---|---|
| Полная сортировка | O(N log N) | Есть (массивы) | ❌ | ❌ |
| Полная сортировка + делегаты | O(N log N) + overhead | Много (итераторы, делегаты) | ❌ | ❌ |
PriorityQueue (простейший) | Один heap | O(N log K) | Есть (узлы очереди) | ❌ | ❌ |
Рукописный selection алгоритм | quickselect | O(N) в среднем | Зависит от реализации | ❌ | ❌ |
GameBudget.Net | Heaps + SIMD | O(N log K) (или O(N log qᵍ)) | 0 B (caller-буферы) | ✅ | ✅ |
Подробнее о различиях
1. LINQ / Array.Sort
// Типичный LINQ-подход var topK = items .Select(i => new { Id = i.Id, Score = Dot(i.Features, weights) }) .OrderByDescending(x => x.Score) .Take(500) .ToArray(); // Множественные аллокации
Проблемы: аллокации на каждый элемент (анонимный тип), полная сортировка, делегаты на каждом шаге.
2. PriorityQueue из .NET
var heap = new PriorityQueue<int, float>(); for (int i = 0; i < N; i++) { float score = Dot(features[i], weights); if (heap.Count < K) heap.Enqueue(i, -score); else if (score > -heap.PeekPriority()) { heap.Dequeue(); heap.Enqueue(i, -score); } }
Проблемы: нет SIMD (скалярный dot), аллокации узлов внутри PriorityQueue, нет групповых квот.
3. QuickSelect (частичная сортировка)
// O(N) в среднем, но O(N²) в худшем QuickSelect(scores, k); var topK = scores.Take(k);
Проблемы: модифицирует исходный массив (нежелательно), нет SIMD, не поддерживает групповые квоты, нет стабильности между кадрами.
Быстрый старт
Шаг 1. Подготовка данных
using GameBudget.Net; using SlidingRank.FastOps; int n = 50_000; // количество объектов int d = 32; // количество признаков int k = 1000; // сколько выбрать // Матрица признаков: row-major (каждый объект — d чисел) float[] featuresData = new float[n * d]; // Веса признаков float[] weights = new float[d]; // ID объектов (опционально) int[] ids = new int[n]; for (int i = 0; i < n; i++) ids[i] = i; // ... заполняем данные ... var features = new EmbeddingMatrix(featuresData, n, d);
Шаг 2. Топ-K без групповых квот
using var scheduler = new FrameBudgetScheduler(maxEntities: n); int[] outIds = new int[k]; float[] outScores = new float[k]; int got = scheduler.SelectTopK( features: features, weights: weights, ids: ids, k: k, outIds: outIds, outScores: outScores ); // outIds и outScores содержат топ-K, отсортированные по убыванию оценки for (int i = 0; i < got; i++) { Console.WriteLine($"Rank {i}: ID={outIds[i]}, Score={outScores[i]:F4}"); }
Шаг 3. Топ-K с групповыми квотами
int groups = 8; // количество групп int[] groupIds = new int[n]; // ID группы для каждого объекта int[] quotas = new int[groups]; // сколько выбрать из каждой группы // Пример: равномерное распределение for (int g = 0; g < groups; g++) quotas[g] = k / groups; quotas[0] += k - (k / groups) * groups; // остаток в первую группу using var scheduler = new FrameBudgetScheduler(maxEntities: n, maxGroups: groups); int[] outIds = new int[k]; float[] outScores = new float[k]; int got = scheduler.SelectWithQuotas( features: features, weights: weights, ids: ids, groupId: groupIds, quotas: quotas, outIds: outIds, outScores: outScores ); // Результат сгруппирован: сначала все объекты группы 0 (отсортированы по score), // затем группы 1, и т.д.
Полный рабочий пример
using GameBudget.Net; using SlidingRank.FastOps; public class AILODScheduler { private FrameBudgetScheduler _scheduler; private int[] _outIds; private float[] _outScores; public AILODScheduler(int maxEntities, int maxK) { _scheduler = new FrameBudgetScheduler(maxEntities); _outIds = new int[maxK]; _outScores = new float[maxK]; } public int[] SelectTopNpc( float[] featuresData, // row-major: NpcCount × FeatureDim float[] weights, // FeatureDim int[] npcIds, // NpcCount int featureDim, int k) { int npcCount = npcIds.Length; var features = new EmbeddingMatrix(featuresData, npcCount, featureDim); int selected = _scheduler.SelectTopK( features, weights, npcIds, k, _outIds, _outScores ); return _outIds[0..selected]; } public void Dispose() => _scheduler.Dispose(); } // Использование var scheduler = new AILODScheduler(maxEntities: 50_000, maxK: 2000); // Каждый кадр int[] importantNpcs = scheduler.SelectTopNpc( featuresData: npcFeatures, weights: importanceWeights, npcIds: allNpcIds, featureDim: 32, k: 500 ); // Обновляем AI только для importantNpcs foreach (int id in importantNpcs) { UpdateAI(id); }
Производительность
Тестовый стенд: Intel Core i5-11400F, Windows 11, .NET 8, BenchmarkDotNet
Топ-K (dot + селекция)
Сценарий (N, D, K) | Базовый (scalar + сортировка) | GameBudget.Net (SIMD + heap) | Ускорение |
|---|---|---|---|
10 000, D=32, K=200 | 709.3 μs | 111.7 μs | 6.35× |
50 000, D=32, K=1000 | 4,256.6 μs | 726.2 μs | 5.86× |
200 000, D=16, K=2000 | 16,157.5 μs | 2,063.4 μs | 7.83× |
Групповые квоты (dot + селекция с квотами)
Сценарий (N, D, G, K) | Базовый (scalar + сортировка + выбор) | GameBudget.Net (SIMD + per-group heaps) | Ускорение |
|---|---|---|---|
10 000, D=32, G=8, K=200 | 1,364.9 μs | 122.7 μs | 11.12× |
50 000, D=64, G=16, K=1000 | 9,553.8 μs | 1,106.0 μs | 8.64× |
200 000, D=32, G=32, K=2000 | 35,216.1 μs | 2,944.0 μs | 11.96× |
Что это значит для игры:
200 000 объектов, выбор топ-2000 с квотами → 2.94 мс вместо 35 мс
Экономия ~32 мс на кадр
При 60 FPS это разница между 16 мс (успели) и 35 мс (фреймдроп)
Zero-аллокации: как это работает
В отличие от LINQ и стандартных коллекций, GameBudget.Net не создаёт мусора в горячем пути.
Что аллоцируется один раз при создании FrameBudgetScheduler:
Внутренние буферы для хранения временных данных
Heaps для каждой группы (при использовании квот)
Что не аллоцируется на кадр:
Массивы для результатов (вы передаёте свои)
Временные массивы для оценок (переиспользуются)
Объекты в куче (все структуры)
Как достичь zero-аллокаций:
// Плохо: аллокации на кадр int[] ids = Enumerable.Range(0, N).ToArray(); // новая аллокация float[] scores = new float[N]; // новая аллокация // Хорошо: переиспользование буферов int[] ids = _cachedIds; // переиспользуется float[] scores = _cachedScores; // переиспользуется Array.Clear(scores); // без аллокаций
Сценарии использования
Сценарий 1: LOD для AI (тысячи NPC)
Из 50 000 NPC выбираем 1000 самых важных для обновления AI.
// Признаки: расстояние до игрока, здоровье, угроза, участие в бою float[] npcFeatures = new float[npcCount * featureDim]; // ... заполняем var importantNpcs = scheduler.SelectTopK( features, importanceWeights, npcIds, k: 1000, outIds, outScores );
Сценарий 2: Анимации с групповыми квотами
Из 10 000 персонажей выбираем 500 для детальных анимаций, но с квотами: не более 200 врагов, не более 200 союзников, не более 100 нейтралов.
int[] quotas = new int[] { 200, 200, 100 }; // враги, союзники, нейтралы int[] selected = scheduler.SelectWithQuotas( features, animationWeights, characterIds, groupIds, quotas, outIds, outScores );
Сценарий 3: VFX и частицы
Из 5000 систем частиц обновляем только 300 самых важных (близких к камере или с высокой интенсивностью).
Сценарий 4: Сетка LOD в открытом мире
Из 200 000 объектов выбираем 10 000 для высокого качества рендеринга.
Сравнение с конкурентами (честно)
Аспект | Array.Sort | LINQ | PriorityQueue | Unity Burst | GameBudget.Net |
|---|---|---|---|---|---|
Скорость (N=200k) | 16 мс | 25+ мс | 8 мс | <1 мс (Burst) | 2 мс |
SIMD dot | ❌ | ❌ | ❌ | ✅ (через Mathematics) | ✅ |
Heap-селекция | ❌ | ❌ | ✅ (руками) | ❌ | ✅ |
Групповые квоты | ❌ | ❌ | ❌ | ❌ | ✅ |
Zero-аллокации | ❌ | ❌ | ❌ | ✅ | ✅ |
Работа везде (.NET) | ✅ | ✅ | ✅ | ❌ (только Unity) | ✅ |
Простота API | ✅ | ✅ | ❌ (ручная реализация) | ❌ (нужен Burst) | ✅ |
Когда стоит выбрать Unity Burst вместо GameBudget.Net
Вы работаете исключительно в Unity и уже используете Burst.
Вам нужно максимальное SIMD-ускорение за счёт нативного кода.
Вы готовы писать кастомную реализацию селектора под свою задачу.
Когда стоит выбрать GameBudget.Net
Вы работаете на чистом .NET (не Unity, или Unity без Burst).
Нужна поддержка групповых квот.
Важен zero-аллокации API.
Нужна простая интеграция без изучения Burst.
Интеграция с Unity
using UnityEngine; using GameBudget.Net; using SlidingRank.FastOps; public class AILODManager : MonoBehaviour { private FrameBudgetScheduler _scheduler; private int[] _npcIds; private float[] _featuresData; private float[] _weights; void Start() { int npcCount = 50000; int featureDim = 32; _scheduler = new FrameBudgetScheduler(maxEntities: npcCount); _npcIds = new int[npcCount]; _featuresData = new float[npcCount * featureDim]; _weights = new float[featureDim]; // Инициализация... } void Update() { // Обновляем признаки (расстояние до игрока, здоровье, угроза) UpdateFeatures(); // Выбираем топ-500 NPC для AI-обновления int[] outIds = new int[500]; float[] outScores = new float[500]; var features = new EmbeddingMatrix(_featuresData, _npcIds.Length, _weights.Length); int selected = _scheduler.SelectTopK( features, _weights, _npcIds, 500, outIds, outScores ); // Обновляем AI только для выбранных for (int i = 0; i < selected; i++) { UpdateAIForNpc(outIds[i]); } } void OnDestroy() => _scheduler.Dispose(); }
Бесплатное тестирование — без ограничений. Коммерческое использование требует лицензии.
NuGet: https://www.nuget.org/packages/GameBudget.Net
GitHub (бенчмарки): https://github.com/likeslines-maker/GameBudget.Net
GameBudget.Net — это библиотека для быстрой селекции топ-K объектов с поддержкой групповых квот.
В отличие от полной сортировки (Array.Sort, LINQ) она:
Работает за O(N log K) вместо O(N log N)
Использует SIMD для массового скоринга
Не создаёт аллокаций на кадр
Поддерживает групповые квоты (честное распределение между категориями)
В отличие от PriorityQueue из коробки:
Даёт готовый zero-аллокации API
Поддерживает групповые квоты
Использует SIMD dot вместо скалярного
В отличие от Unity Burst:
Работает на любом .NET (не только Unity)
Не требует изучения Burst и HPC#
Даёт простой API с групповыми квотами
Если ваш фрейм-бюджет страдает от полной сортировки тысяч объектов — попробуйте GameBudget.Net. Сортировка 200 000 объектов за 16 мс — это слишком дорого для того, чтобы выбросить 99% результата.
