Продолжу тему с TLSF аллокатором, о котором рассказала в предыдущем посте.

Главная непонятная тема - как происходит процесс упаковки свободных блоков? 🤔 Расскажу об одном из алгоритмов (их несколько для TLSF).

Если в общих чертах, то следующим образом:
1️⃣ При освобождении блока помечаем его как свободный
2️⃣ Пытаемся объединить с соседними свободными
3️⃣ Если получилось, то переносим получившийся (более большой) блок в нужный FLI/SLI

А что такое соседние свободные блоки? Тут под ними понимаются не блоки, которые лежат рядом в корзинке! Совсем нет! 🗣

У каждого блока есть заголовок - это какая-то служебная (meta) информация. Часто там хранится размер блока, всякие флаги, индексы, и, указатели на соседние блоки. Когда мы делим большой блок на несколько маленьких (откусываем кусочек), то мы создаем двусвязный список, чтобы потом можно было этот кусочек вернуть обратно в большой пирог.

А что такое двусвязный список? Это ссылки на соседей "слева" и "справа".
Поэтому алгоритм упаковки достаточно простой:
1️⃣ При освобождении блока помечаем его как свободный
2️⃣ Смотрим на соседей, вдруг они тоже свободные
3️⃣ Если свободные, то объединяем в более большой блок
4️⃣ Удаляем объединенные блоки из корзин FLI/SLI, в которых они хранились
5️⃣ Сохраняем новый большой блок в новую корзину FLI/SLI

Вуаля, упаковка произошла, дырок больше нет! ✨

Весь алгоритм выполняется за O(1): проверка на свободный блок - через операции с битмаской, поиск соседей - через двусвязный список, операции удаления/вставки - опять же немного пошаманить с битмаской и сохранить в нужную корзину.

Когда лучше всего использовать TLSF-аллокатор?
🔘 Нужны блоки памяти достаточно большого размера с длинным жизненным циклом (всякие долгоживущие массивы, которые хранятся в памяти, например, все время жизни игры)
🔘 Блоки разного размера
🔘 Нужна поддержка возврата и переиспользования (обычная арена не подходит)

В следующих постах расскажу о своей реализации аллокатора для вокселей: какой, почему именно такой, как я решила проблему с многопоточностью (та еще задачка 🧂), плюс небольшой бонус! 👏

P.S.: мем от ChatGPT прилагается 😛

#csharp #allocators

Всем привет! 💃

Продолжим тему с аллокаторами, ведь я о них не просто так рассказывала? 🫥 Как я писала в одном из постов - я переосмысляю подходы в своей генерации. Причина этому является то, что я уперлась в некоторые ограничения при масштабировании, ну и просто подросла 😛

Что я поняла, так это то, что хранить воксели и их мета-данные очень и очень важно, особенно учитывая тот момент, что их много, а алгоритмы часто работают со всеми (или почти всеми) вокселями в чанках. 🧂

И я пришла к мысли, что мне нужен свой аллокатор, который должен удовлетворять следующим требованиям:
1️⃣ Максимально быстрая аллокация непрерывных блоков памяти.
2️⃣ Минимум фрагментации памяти.
3️⃣ Максимум переиспользования памяти.

Я несколько раз пыталась аллоцировать сразу большой кусок памяти и его разрезать по чанкам и вокселям и как-то использовать. Это оказалось довольно медленно, так как часто память нужна уже "чистая", а аллоцирования и трогание (например очистка) памяти ведет к ее реальному выделению, а не только виртуальному бронированию.

С другой стороны, у меня алгоритмы не используют весь выделенный кусок сразу в один момент времени. Тут больше происходят действия вида "откусили кусочек", что-то поделали, часто даже 1-2 кадра, и отдали обратно. И только какая-то небольшая часть чанков и их память реально живет длительное время.

Из-за такого вида работы с памятью, мне не подходят аллокаторы Temp или TempJob. Они слишком мало живут. С другой стороны, Persistent аллокатор тоже не подходит, он хоть и живет долго, но он достаточно медленный и не избавляет от проблемы, что мне выдадут виртуальный кусок памяти, который на самом деле еще надо инициализировать, что ведет к неприятным задержкам.

Вариант, когда в Jobs мы используем Temp аллокатор, а результат вычислений копируем в Persistent память я тоже в итоге откинула. Это требует выделения памяти в большем количестве и добавляет копирование в конце. Не хочется делать те операции, от которых мы на самом деле можем избавиться. 😔

Что же делать? 🚪
Написать свой аллокатор и радоваться жизни! 🙌

Я пришла к гибридному варианту, когда простую идею о переиспользовании уже выделенных кусков памяти (то есть обычный pooling) натягивают на сегрегацию по размеру блоков и оборачивают это все в lock-free алгоритм для поддержки многопоточного доступа.

Я не выделяю сразу большого куска памяти (хотя какую-то инициализацию на старте игры стоит делать), так как это сложно управляется в многопоточном коде. Быстрый доступ без блокировок - та еще задачка. 🦊

Для аллокации шаги будут такими:
🔘 смотрим на размер запрошенного блока и находим пул, который больше всего подходит под него
🔘 смотрим, есть ли в пуле свободные блоки
🔘 если есть, то берем свободный блок, и откусываем от него (если он слишком большой для нас)
🔘 если нет, то запрашиваем у back-аллокатора (в моем случае это Persistent) новый кусок
🔘 полученный кусок возвращаем пользователю

Для деаллокации шаги похожи:
🔘 смотрим на размер блока и вычисляем пул, из которого этот блок был взят
🔘 кладем в пул и помечаем блок как свободный

Более подробно о том, как я реализовала свой аллокатор и как его подключила к Unity расскажу в следующих постах! 💃

И конечно же для него я написала Profiler Module с подробной статистикой. Спасибо, что подсказали про это! 🥰

#generation #allocators

SDF Functions

В поисках всякого про SDF и не только, наткнулась на неплохой сайт, где есть описание ооочень большого количества 3D SDF функций. 🗣

Выглядит прикольно, о некоторых я даже не подозревала, так как обычно сложные формы запекаются.

Хотите бублик?

float sdTorus( vec3 p, vec2 t )
{
  vec2 q = vec2(length(p.xz)-t.x,p.y);
  return length(q)-t.y;
}

Или может Звезду Смерти (Дарт Вейдер одобряет)?

float sdDeathStar( vec3 p2, float ra, float rb, float d )
{
  // sampling independent computations (only depend on shape)
  float a = (ra*ra - rb*rb + d*d)/(2.0*d);
  float b = sqrt(max(ra*ra-a*a,0.0));
  
  // sampling dependant computations
  vec2 p = vec2( p2.x, length(p2.yz) );
  if( p.x*b-p.y*a > d*max(b-p.y,0.0) )
    return length(p-vec2(a,b));
  else
    return max( (length(p            )-ra),
               -(length(p-vec2(d,0.0))-rb));
}

Там много интересного, в том числе и как производить всякие манипуляции с SDF-фигурами. 💃

Также ко многим примерам есть ссылочки на Shader Toy, где можно в динамике посмотреть фигуры. Крутотень! 🙌

#sdf #generation

Всем привет! 💃

Продолжим тему с аллокатором, который я реализовала для хранения различных данных вокселей. Как я уже рассказывала в предыдущем посте, я использую достаточно простой подход - обычный пуллинг памяти.

Как же устроен мой пул? 📝
1️⃣ Я выделяю заранее буфер на много-много указателей блоков. Да, я храню не сами блоки, я храню только указатели (8 байт). Сколько таких блоков может быть в пуле - подобрано эвристически в зависимости от моих задач. Размер этого буфера не меняется.
2️⃣ Я выделяю также и общий список Next Free. Этот список для каждого элемента хранит индекс следующего свободного. Получается односвязный список, по которому я могу найти за O(1) следующий свободный элемент. Скорость мне очень важна.
3️⃣ Я выделяю Thread Local Storage. Это необходимо, чтобы было как можно меньше пересечений между потоками и кэш-миссов из-за инвалидации кэша + меньше блокировок. В TLS хранится следующий свободный индекс для каждого потока.

Как же я ищу блок в пуле? 🚪
Давайте представим, что мы находимся в каком потоке.
1️⃣ Я смотрю в Thread Local Storage по индексу этого потока. Вдруг там есть свободный индекс, которые мы можем использовать.
2️⃣ Если не нашла, то я пытаюсь забрать свободные индексы, которые пока не принадлежат ни одному потоку. Дело в том, что я не разбиваю сразу все индексы из пула по всем потокам, я их "отдаю" пачками, по 16 штук при необходимости.
3️⃣ Получив индекс так или иначе, я обновляю связаный список Next Free и TLS. Это просто установка значения, что занимает снова O(1).
4️⃣ По полученному индексу я получаю указатель блока из пула, если он был раннее аллоцирован. Если же нет, то аллоцирую новый блок по указанному back-аллокатору (чаще всего, это Persistent).

Пример как можно найти доступный индекс:

do
{
   do
   {
      // читаем из TLS текущего потока
      idx = Volatile.Read(ref TLS[threadIndex]);
   }while (idx == -3);
   if(idx < 0)
     // в TLS нашего потока больше нет ничего
}while (Interlocked.CompareExchange(ref TLS[threadIndex], -3, idx) != idx);
// записали следующий свободный в наш TLS
Interlocked.Exchange(ref TLS[threadIndex], nextPtrs[idx]);

Пример как можно "отдать" еще 16 индексов потоку:

Interlocked.Exchange(ref poolData->FirstFreeTLS[threadIndex], -2); // помечаем, что мы будем еще выделять

if (allocatedCount < capacity)
{
   idx = Interlocked.Add(ref allocatedCount, 16) - 16; // пытаемся отдать все 16 индексов
   if (idx < capacity - 1)
   {
       var count = math.min(16, capacity - idx);
       for (var i = 1; i < count; ++i)
       {
           // сразу их записываем в список свободных
           nextPtrs[idx + i] = idx + i + 1;
       }
       nextPtrs[idx + count - 1] = -1;
       nextPtrs[idx] = -1; // текущий мы отдаем, поэтому он не свободен
       // и в TLS тоже записываем следующий свободный
       Interlocked.Exchange(ref TLS[threadIndex], idx + 1);
       return idx;
   }

   if (idx == capacity - 1)
   {
       // это был последний доступный в пуле, значит помечаем как "больше элементов нет"
       Interlocked.Exchange(ref TLS[threadIndex], -1);
       return idx;
   }
}
// ничего не нашли, следующих свободных нет
Interlocked.Exchange(ref TLS[threadIndex], -1);

А что если мы использовали все, что было в пуле, и что места под блоки? Тогда для потока я не смогу найти еще 16 индексов.
Получается, что мы израсходовали все, что у нас было. Но, вдруг, у других потоков еще есть свободные индексы?
Попробуем украсть их!

Алгоритм кражи тоже простой:
1️⃣ Пробегаемся по всем TLS всех потоков, кроме нашего текущего.
2️⃣ Смотрим, есть ли у них что-то, что можно украсть.
3️⃣ Если есть, то крадем. В TLS потока, у которого крадем, помечаем, что мы забрали индекс.

Пример кражи:

for(var threadIndex = 0; threadIndex != currentIndex; threadIndex < threadCount; threadIndex++)
{
   do
   {
      do
      {
         idx = Volatile.Read(ref TLS[threadIndex]);
      }while(idx == -3);
      
      if(idx < 0)
         break;
   }while (Interlocked.CompareExchange(ref TLS[threadIndex], -3, idx) != idx);
}

Спасибо за внимание! 💃

#generation #allocators

Всем привет! 💃

Вот и настал последний понедельник года, это время не только подвести итоги, но и пожелать друг другу хорошего в новом году! 🥔

Многие из вас растут как эксперты, у некоторых из вас есть свои пет-проекты, а кто-то может даже начинает игру с мыслями про будущие успехи.

Пусть 2026 год поможет довести начатое до результата, воплотит все ваши мечты и приведет вас к вершинам, о которых вы даже не задумываетесь сейчас! 🤑

Пусть следующий год будет годом роста, смелых экспериментов и новых достижений! 🙌

Спасибо вам всем, что читаете мой канал и терпеливо ждете новые посты. ❤️

Счастливого Нового Года! 🙌

Всем привет! 💃

Ох, давно я не писала чисто Entities-код, все джобы, аллокаторы и всякое остальное не очень интересное.

Недавно продолжила работу над проектом (новогодние праздники, плюс под конец декабря уволилась из компании, в которой работала, но это отдельная история), обновила версию Unity, пакетов, так как все же прошло много времени и много багов со стороны Unity было пофикшено.

Но столкнулась с новым для себя багом: в случае кастомного бутстрапа мира Entities + ручной загрузки ECS-сцен, можно в билде получить бесячую ошибку "Cannot find TypeIndex for type hash" 🤩

После часов поиска причины, нашла топик на форуме, в котором описывается, что ILPP в Entities 1.3.9+ сломан.

Текущий workaround - указать DISABLE_TYPEMANAGER_ILPP в настройках проекта, тогда все будет работать отлично.

Может быть кому-нибудь будет полезно ❤️

А как проходят ваши новогодние праздники? 😅

Всем привет! 💃

Наткнулась недавно на очень интересный сервис с 2д-проекцией игр из Steam.

На карте отображены все (наверное, не уверена) игры, которые находятся в Steam. Они сгруппированы по тегам, так что близкие по духу и жанру игры находятся близко друг к другу, таким образом образуя кластеры и жанровые островки. Удобненько!

Цветовая градация точек на карте зависит от общего количества отзывов. Это не показатель, на сколько игра продаваемая, но это хороший показатель узнаваемости на рынке.

Использовать можно как вспомогательный инструмент для общего анализа рынка, поиска ближайших конкурентов, поиска незанятых ниш и так далее. Короче, довольно занятная и интересная штуковина! 🥔

P.S.: есть отдельный, достаточно большой, остров 18+ игр, интересно то, что это именно остров 🗣

Всем привет! 💃

Работая с Timeline в Unity внезапно обнаружила, что можно очень просто добавлять поддержку кривых в пользовательские треки и клипы. 🗣

Все, что необходимо для получения результата как на скриншоте: пометить кастомный PlayableBehaviour атрибутом [Serializable] и создать сериализованное поле в треке или в клипе, вот как-то так:

[Serializable]
class MyAwesomeBehaviour : PlayableBehaviour {}

class MyAwesomeTrack : TrackAsset
{
   [SerializedField]
   MyAwesomeBehaviour _behaviour;
}

Тогда все свойства, для которых Unity может создать кривые (числовые значения, вектора), она создаст, а на Timeline в треке появится кнопка "показать кривые" и появится возможность их настраивать.

P.S.: Для клипов кстати еще появляется возможность переходить в окно Animation, будто клип - это анимация, прикольно. 😎

Всем привет! 💃

В прошлом посте я немного упомянула Timeline, теперь же хочу рассказать о небольшом нюансе при работе с ним в рамках DOTS, с которым сама столкнулась недавно.

Если ссылаться на TimelineAsset через WeakObjectReference и потом загружать его через API RuntimeContentManager, то в билде будет проблемка - все биндинги у треков будут пустыми. Иными словами, наша катсцена, которую мы с любовью делали какое-то время, не будет работать. 😤

Почему? Потому что, когда мы ссылаемся через WeakObjectReference на ассет катсцены, потом запекаем наши объекты в сцене через DOTS Baker, то в запеченные бандлы уходит копия ассета! А если это копия, то будет другой guid ассета, а если другой guid, то в таблице биндингов мы ничего не найдем, потому что в PlayableDirector поиск ведется по guid. Парам-пам-пам. 🤦

Решение как оказалось простое, хоть и не очень удобное: написать свою таблицу зависимостей для Timeline и вручную выставлять все биндинги в PlayableDirector перед запуском катсцены.

P.S.: Как я помню, что-то похожее было и с Addressables, Unity так и не решили эту боль 🫣