Infinity World (Дневники разработчицы)

Продолжу тему с TLSF аллокатором, о котором рассказала в предыдущем посте.Главная непонятная тема - как происходит процесс упаковки свободных блоков? 🤔 Расскажу об одном из алгоритмов (их несколько для TLSF).Если в общих чертах, то следующим образом:1️⃣ При освобождении блока помечаем его как свободный2️⃣ Пытаемся объединить с соседними свободными3️⃣ Если получилось, то переносим получившийся (более большой) блок в нужный FLI/SLIА что такое соседние свободные блоки? Тут под ними понимаются не блоки, которые лежат рядом в корзинке! Совсем нет! 🗣У каждого блока есть заголовок - это какая-то служебная (meta) информация. Часто там хранится размер блока, всякие флаги, индексы, и, указатели на соседние блоки. Когда мы делим большой блок на несколько маленьких (откусываем кусочек), то мы создаем двусвязный список, чтобы потом можно было этот кусочек вернуть обратно в большой пирог.А что такое двусвязный список? Это ссылки на соседей "слева" и "справа".Поэтому алгоритм упаковки достаточно простой:1️⃣ При освобождении блока помечаем его как свободный2️⃣ Смотрим на соседей, вдруг они тоже свободные3️⃣ Если свободные, то объединяем в более большой блок4️⃣ Удаляем объединенные блоки из корзин FLI/SLI, в которых они хранились5️⃣ Сохраняем новый большой блок в новую корзину FLI/SLIВуаля, упаковка произошла, дырок больше нет! ✨Весь алгоритм выполняется за O(1): проверка на свободный блок - через операции с битмаской, поиск соседей - через двусвязный список, операции удаления/вставки - опять же немного пошаманить с битмаской и сохранить в нужную корзину.Когда лучше всего использовать TLSF-аллокатор?🔘 Нужны блоки памяти достаточно большого размера с длинным жизненным циклом (всякие долгоживущие массивы, которые хранятся в памяти, например, все время жизни игры)🔘 Блоки разного размера🔘 Нужна поддержка возврата и переиспользования (обычная арена не подходит)В следующих постах расскажу о своей реализации аллокатора для вокселей: какой, почему именно такой, как я решила проблему с

Всем привет! 👋В прошлый раз я рассказала о нескольких типах аллокаторов, которые часто используются в геймдеве. Сегодня хочу продолжить эту тему и рассказать немного еще об аллокаторах, вернее об одном, который уже затрагивали в комментариях. 📝Two-Level Segregate Fit (TLSF) аллокаторОн же Persistent аллокатор в Unity в DOTS. Из названия понятно, что этот аллокатор двухуровневый. В чем это проявляется? 🚪ИдеяОсновная идея TLSF - классифицировать все запросы на блоки памяти по размеру этих блоков и хранить их на двух уровнях.Первый уровень, он же First Level Index (FLI), это грубое приближение классификации по размеру. Например, если нам нужен блок размером 60 байт, то FLI будет равен 5 (он же индекс корзины).Как же считается этот FLI?По размеру! 🗣 Берется размер, вот эти 60 байт, переводится в двоичный вид (111100) и берется старший бит (32). Это определяет диапазон [32...63]. Или же степень двойки 2^5 = 32.Следующим шагом, необходимо уточнить, в какой подкорзине относится наш запрос. Такая подкорзина называется Second Level Index (SLI). Для наших 60 байт это будет 14.Как считается SLI?На основе FLI и нашего размера! ✨ В начале вычисляется шаг. Формула простая:step = (верхняя граница диапазона - нижняя + 1) / 16А потом и сам SLI:SLI = (size - base) / stepАлгоритмДля выделения куска памяти необходимого размера алгоритм можно описать вот так:1️⃣ Смотрим на размер блока, который нам нужен и вычисляем FLI и SLI.2️⃣ Ищем свободный блок по вычисленным FLI и SLI. Тут применяется bitmap для быстрого поиска (O(1)).3️⃣ Если по указанным FLI/SLI нет свободного блока, идем в следующий SLI (или FLI, если в текущем закончились SLI), в котором есть, пусть и более большой по размеру.4️⃣ Если мы взяли блок не из своего FLI (то есть он большой для нас), то режем его. А остаток возвращаем.5️⃣ Обновляем bitmap: указываем, что FLI/SLI пусты.6️⃣ Возвращаем выбранный блок пользователю.Поговорим немного про bitmap.У каждого уровня (FLI/SLI) есть своя bitmap (обычно unsigned int). Каждый

Всем привет! 👋Продолжим тему с аллокаторами. Как я чуть раньше писала, аллокаторы решают часть проблем при работе с памятью.Но какие аллокаторы бывают? 🤔 Приведу несколько самых распространенных типов, которые часто используют при разработке игр.1️⃣ Arena AllocatorАрена-аллокатор - это такой аллокатор, при котором вся память выделяется большим единым куском. А потом она разрезается на кусочки, которые уже используются.Пример псевдокода:byte* memory = memalloc(1024*1024); // выделяем сразу большой кусокbyte* current = memory; // сохраняем указатель...byte* block = current;current = current + blockSize; // сдвигаем указатель для следующей аллокацииreturn block;Когда используется: 🔘 когда все элементы живут одинаково долго 🔘 когда можно разом выделить память и освободить ее 🔘 когда не надо индивидуальное освобождение объектовTempJob в Unity является именно Arena-аллокатором.2️⃣ Slab AllocatorSlab-аллокатор, он же пул памяти, при котором память тоже выделяется большим куском, но нарезается сразу на N участков одинакового размера. Это позволяет переиспользовать участки, если какие-то объекты больше их не используют.Пример псевдокода для аллоцирования:byte* memory = memalloc(1024*1024); // выделяем сразу большой кусокint* freeList; // список свободных элементовint freeCount = 0;int allocatedCount = 0;...if(freeCount > 0){ int idx = freeList[--freeCount]; return memory + idx * blockSize; // выдаем из пула}if(allocatedCount < capacity) return memory + (allocatedCount++) * blockSize; // выдаем следующий не аллоцированныйreturn null; // блоков больше нетПсевдокод для возврата:int idx = (ptr - memory) / blockSize; // вычисляем индекс блока по адресу памятиfreeList[freeCount++] = idx; // записываем индекс как свободныйКогда используется: 🔘 когда много объектов одного размера 🔘 когда важно выделять для них память 🔘 когда важно при этом освобождать память и ее переиспользоватьПост уже получился достаточно большим. Расскажу о других видах в следующий раз! 🥔#csharp #

Неделя работы с памятью объявляется открытой! 🙌У Алекса появился пост про память. Очень полезный в контексте Unity для разработчиков всех уровней. 🥹 Кто не видел - очень советую глянуть его презентацию.Я же хотела рассказать про такой аспект памяти, как ее фрагментация.О том, как аллоцируются наши кусочки памяти, откуда они берутся и как потом возвращаются - мы очень редко задумываемся. Часто нас интересует сам факт аллоцирования, не больше. Но что происходит, когда мы "отпускаем" ненужный блок памяти? Он просто помечается как неиспользуемый.Что будет, если мы захотим аллоцировать кусочек побольше? Мы не получим блок, который "освободили" на предыдущем шаге, так как он слишком маленький. Мы получим другой, более большой блок. 🤔А как же тот, маленький? 😭 А он остается, и совсем не факт, что когда либо будет использован. И такие блоки, разного размера, которые "чуть-чуть" не подходят могут постоянно появляться, создавая множество дырок. Память становится как "решето", мы начинаем требовать все больше физической памяти RAM, а найти нужный свободный блок становится все тяжелее.Это та самая фрагментация. И с этим надо что-то делать.📝1️⃣ Например, использовать пулы памяти.Выделяем большой кусок памяти, режем его на нужные нам кусочки одинакового размера и переиспользуем. Самый простой способ, который при этом очень эффективный.2️⃣ Аллокаторы. Можно реализовать свои аллокаторы (arena, slab и другие) или взять готовые. Они фактически тоже пулы "под капотом", только более умные и позволяют использовать блоки памяти разного размера.3️⃣ Аллокаторы с слиянием (coalescing). Еще более умная штуковина с этапом слияния свободных участков и последующим переиспользованием. Используется не так часто, потому что требует дополнительного прохода "упаковки" (да, кое-кого напоминает).А как же аллокаторы от Unity?- Temp и Temp Job: обычные arena аллокаторы.- Persistent: это уже malloc/free и частые аллоцирования приводят к фрагментации. 😔P.S.: в комментариях уточнили, что persistent -

Ну, что ж, пришло время расти над собой 👏В начале своего пути разработки генерации мира я не понимала многих концепций и часто считала одно лучше другого не понимая до конца какие-либо детали.Например, я считала, что AoS (array of structures) хорошо подходит для хранения вокселей. Это утверждение правильно только в одном случае: если работа с вокселями происходит сразу со всеми данными в этой структуре одновременно.Конечно, изначально в структурке Voxel я хранила только значение SDF. Но, код меняется, а значит пора пересмотреть некоторые вещи.Я начала хранить больше информации на каждый воксель: добавился тип вокселя, веса для материалов, дополнительные флаги и прочее. И, как оказалось в итоге, каждое поле из этой структуры необходимо только для конкретных алгоритмов моей генерации. Я никогда не читаю целый воксель из памяти для того, чтобы поработать со всеми данными.А что это значит? Пора переходить на SoA! Да! Structure of Arrays становится лучше для моей задачи! Но почему?Давайте обратимся к циферкам. 📝1️⃣ Представим, что у нас есть чанк с 32³ вокселями (32  768 всего).2️⃣ Размер кэш линии в среднем сейчас 64 байта (есть отличия между AMD и Intel в некоторых линейках CPU, но пренебрегаем).3️⃣ Нам необходимо прочитать все воксели и взять их значение SDF.🆘 AoS (Array of Structures), когда у нас одна структура , например SDF и тип вокселя:- на один воксель 8 байт: 4 байта (SDF) + 1 байт (тип) + 3 байта для выравнивания- один cache line помещает 8 вокселей: 64 байта делим на 8- что в худшем случае дает нам 4 096 кэш миссов! (32 768 делим на 8) Худший случай - нам каждый раз нужен воксель из другого места.✅ SoA (Structure of Arrays), когда мы значения храним в разных массивах:- у нас отдельно лежит SDF, это 4 байта- cache line вмещает 16 вокселей: 64 делим на 4- что в худшем случае дает нам примерно 2000 кэш миссов: 32 768 делим на 16.Разница большая! 🗣Конечно это просто цифры. В реальности ситуация не настолько плоха, мы часто читаем ближайшие элементы, из текущ

Всем привет! 🥰Столкнулась тут с интересной штуковинкой: многие знают такой замечательный инструмент, как Profiler Analyzer, который жизненно необходим во время оптимизирования кода.Так вот, давайте представим, что мы запускаем какую-то параллельную джобу (IJobFor). Нуу, допустим, 1000 раз:var jobHandle = job.ScheduleParallel(1000, 1, default);Причем, мы хотим, чтобы вызовы Execute у нас не батчились, поэтому ставим циферку 1 вторым аргументом.И что же я вижу в Profiler Analyzer? Count 15? И как это считать?🤔Ваши идеи? 🚪

Всем привет! 💃Я вернулась к коду, и первое, что я поняла: как же сложно вспоминать, на чем остановилась, спустя несколько месяцев! 🔥Но ничего, свежий взгляд, многое становится более явным, заодно какая никакая, но проверка временем 🥔 Некоторые решения в коде теперь кажутся какими-то…странными что ли? 😛Как вы помните, и как я вспомнила, я остановилась на проверке варианта «догенерации» вокселей в биоме по требованию, чтобы можно было правильно посчитать положение объектов на ландшафте. Самая большая проблема в том, что там много-много unsafe кода, и часть даже не обернуто во что-то более понятное 😤 Ах, сама виновата 🧂#generation

Иии, всем привет! 💃Наверное многие уже решили, что я забыла про канал и больше не будет постов 🫥 Спешу обрадовать - это не так! 🥔Последние несколько месяцев были очень тяжелыми и насыщенными, и я просто не успевала заниматься еще и проектом. Иногда такое случается, но все это время я все равно старалась хотя бы подумать над тем, что и как должно работать и выглядеть. 🙌И, с января, я продолжу разработку и начну, пусть не очень часто, но снова писать посты 💃 Планов полно, идей море, багов, которые ждут, что их пофиксят, еще больше! Заняться точно есть чем)Всех с наступающими праздниками и хорошего начала года! 🥰

Детерминированность окруженияС этой взрослой жизнью и взрослыми делами совсем не получается выделить время на проект 😭 Но дела рано или поздно заканчиваются, и часок-другой я все равно стараюсь найти)Во-первых, ¡Hola! всем, кто меня читает, и muchas gracias! 👋Во-вторых, я столкнулась с небольшим нюансом, о котором хочу рассказать. Ранее я уже показывала немного видосиков и картиночек генерации мира с объектами окружения. Тогда мне казалось, что я решила задачу, но как это обычно бывает - я ошибалась.Проблема:При генерации объектов окружения самая сложная задача - это правильно вычислить уникальный детерминированный идентификатор объекта, по которому можно идентифицировать этот самый объект как в сохранениях мира (если есть изменения), так и между инстансами игры в мультиплеере.Я привязывалась к мешу ландшафта в чанках: переводила координаты вершин в пространство вокселей и от этого считала идентификатор. Это будет работать, если во всех чанках мира только один уровень детализации (LOD), в ином случае - получаем недетерминированность. Из-за того, что на разных LOD меш содержит разные треугольники, можно получить некоторую вариативность в позиции в пространстве вокселей. Что приводит к неправильному положению объектов при смене LOD, неправильному идентификатору и дублированию объектов, невозможности связать данные сохранения и текущего мира и кучка других проблем.Как решить?Я пришла только к одному решению, которое будет работать всегда: считать позицию объектов окружения только в пространстве вокселей, причем всегда в LOD0. Это означает, что необходимо "догенеривать" воксели для чанков, у которых LOD выше 0. Ну, что ж, это плата за детерминированность. 🧂На данный момент тестирую этот подход, посмотрим чуть позже, что получится 😶#generation

Когда настраиваешь освещение/пост-процессинг/цвета, то очень быстро глаза "замыливаются" 🧂 Я с этим борюсь тем, что переключаюсь на другую задачу, и через некоторое время снова возвращаюсь к настройке.Что получилось настроить на текущий момент внутренними средствами Unity по освещению и пост-процессингу можно увидеть на скриншотах 🙌Где:1️⃣ Совсем без освещения и пост-процессинга.2️⃣ Промежуточный вариант освещения и пост-процессинга. Уже лучше, но цвета тусклые + оттенок слишком сильно уходит в зеленый.3️⃣ Текущий вариант. Цвета стали сочнее, зеленый оттенок стал меньше.Это все еще не окончательный вариант, через некоторое время вернусь и попробую получить результат еще лучше и ближе к тому, что я хочу)#demo_scene