Написал немного про поиск пути, буду выкладывать ссылки на статьи в телеграф, если нужны картинки или хочу описать что-нибудь более подробно.
1 min read
0 Comments
Read More
Написал немного про поиск пути, буду выкладывать ссылки на статьи в телеграф, если нужны картинки или хочу описать что-нибудь более подробно.
Используйте указание на конкретный тип в enum, если вы используете меньше, чем int:
enum MyEnum : byte {
Value1,
Value2,
Value3,
Value4,
} Таким образом:
struct Test {
public MyEnum e1;
public MyEnum e2;
public MyEnum e3;
public MyEnum e4;
} Будет запаковано как 4 байта. Но не забывайте, что любая математика с enum приводит к int 🙂
Давайте напишем счетчик, значение которого мы хотим увеличивать из разных потоков, а после того как все потоки закончат работу, мы выводим это число.
public class Counter {
public int value;
public void Increment() => Interlocked.Increment(ref this.value);
}Вот вроде бы и все, но на самом деле - можно быстрее. Каким образом?
public class Counter {
public int[] values;
public int Count {
get {
var count = 0;
for (int i = 0; i < this.values.Length; ++i) count += this.values[i];
return count;
}
}
public void Increment(int threadIndex) => ++this.values[threadIndex];
} Т.е. мы должны знать количество потоков и порядковый номер потока, в котором работаем (В Unity Jobs есть JobsUtility.ThreadIndex и JobsUtility.ThreadIndexCount).
Т.е. мы создаем Counter с массивом по количеству потоков и при каждой операции Increment мы передаем номер текущего потока. Тогда этот счетчик будет работать без оверхеда на добавление совсем. А когда операции закончились - мы суммируем все счетчики и возрващаем значение.
CC (`Concurrent Collections`) коллекции - это набор коллекций данных, разработанных для работы в многопоточной среде. Одной из особенностей CC коллекций является их lock-free (без блокировок) реализация, которая позволяет не блокировать весь многопоточный поток при обращении к коллекции.
Все CC коллекции стараются обходиться без lock, т.е. в нормальном режиме работы - либо вообще без lock, либо в редких исключениях его использование.
Давайте разберем простой пример, чтобы было понятно как именно работают такие коллекции.
Допустим, что нам нужно написать коллекцию Stack<> (возьмем самую простую). В однопоточной реализации мы используем массив элементов + индекс, который говорит нам где мы находимся в данный момент. При Push мы просто кладем элемент по индексу и увеличиваем индекс, а при Pop просто уменьшаем индекс. Ну еще при Push нам нужно проверить размер массива и сделать новый, если это нужно.
А теперь в многопоточность.
Как реализовать такую коллекцию? Давайте не будем вообще создавать никаких массивов, а будем использовать односвязный список из нод. Node - это объект, который имеет указатель на предыдущий элемент и данные внутри себя.
Коллекция же имеет только ссылку на head-ноду. При добавлении элемента нам нужно создать ноду и каким-то образом ее запихнуть к последней, используем Interlocked.CompareExchange и заменяем head на наш элемент. При Pop делаем обратную операцию.
Для дебага полезная штука - написать свой Proxy:
[System.Diagnostics.DebuggerTypeProxyAttribute(typeof(DebugClass))]
public class YourClass { ... }Где DebugClass - это отдельный класс, который может содержать геттеры и поля. Еще у него должен быть конструктор, который будет принимать инстанс YourClass.
Это сильно помогает при дебаге сложных штук.
Мы знаем, что структуры нужно инициализировать в конструкторе полностью:
struct MyStruct {
public int field1;
public int field2;
...
public int fieldN;
public MyStruct(int field1) {
this.field1 = field1;
// тут нужно инициализировать все поля
this.field2 = default;
...
this.fieldN = default;
}
} Иногда полей много и можно написать гораздо короче:
struct MyStruct {
public int field1;
public int field2;
...
public int fieldN;
public MyStruct(int field1) {
this = default;
this.field1 = field1;
}
} Давайте представим, что у нас есть 2 структуры:
public struct V3 {
public float3 x;
}
public struct V4 {
public float4 x;
}А теперь напишем джобу, которая перекладывает данные из одного массива в другой:
[BurstCompile]
public struct MyJob : IJob {
[ReadOnly] public NativeArray<V3/V4> source;
public NativeArray<V3/V4> dest;
public void Execute() {
for (int i = 0; i < source.Length; ++i) {
dest[i] = source[i];
}
}
}Какой вариант джобы будет работать быстрее? Логика подсказывает нам, что V3, т.к. данных копировать нужно меньше, да и вообще размер будет намного меньше. Давайте разберемся же, что там получается на выходе: Для V3 варианта мы должны скопировать структуру значение за значением, т.е. 3 раза.
Для V4 варианта мы вроде должны скопировать 4 значения. Но тут вламывается векторизация и выходит, что вариант V4 будет работать примерно на треть быстрее, чем вариант V3. Но не расстраивайтесь, можно все исправить: (да, можно исправить разными способами)
public struct V3 {
public float3 x;
public float _;
}Я редко встречаю код с битмасками, уж не знаю почему, но в основном люди предпочитают обходить их стороной. Разбираемся, ведь в них нет ничего сложного.
Битовые маски могут использоваться для манипулирования отдельными битами в числе. Это может быть полезно, например, чтобы проверить, является ли определенный бит установленным или снятым.
int value = 0b1011; // ставим дефолтное значение
// проверка, является ли второй бит установленным
if ((value & (1 << 1)) != 0) {
// бит установлен
}
// установка третьего бита
value |= (1 << 2); // теперь value == 0b1111
// сброс третьего бита
value &= ~(1 << 2); // теперь value == 0b1011Можно использовать биты в enum, записывать их можно по-разному:
enum MyEnum {
None = 0,
Value1 = 1 << 0,
Value2 = 1 << 1,
Value3 = 1 << 2,
Value4 = 1 << 3,
Value5 = 1 << 4,
Value1OrValue3 = Value1 | Value3,
}
enum MyEnum {
None = 0,
Value1 = 0x1,
Value2 = 0x2,
Value3 = 0x4,
Value4 = 0x8,
Value5 = 0x10,
Value1OrValue3 = Value1 | Value3,
}Записи эквиваленты друг другу, я встречал оба варианта.
Для вывода можно использовать аттрибут System.Flags, но он не является обязательным, хотя влияет на отображение в Unity Inspector и на вывод в лог.
Мы хотим выполнить несколько итераций (jobCount) и внутри каждой итерации еще по 128 итерации. Внутри всего этого мы хотим посчитать сумму из NativeArray input и положить в массив NativeArray arrSum:
for (int j = 0; j < jobCount; ++j) {
for (int i = 0; i < 128; ++i) {
var sum = arrSum[i];
sum += input[(j * 128) + i];
arrSum[i] = sum;
}
} Как видно из примера, массив input намного больше, чем arrSum. Мы думаем-думаем и решаем оптимизировать наш код. Получается примерно следующее:
for (int i = 0; i < 128; ++i) {
var sum = arrSum[i];
for (int j = 0; j < jobCount; ++j) {
sum += input[(j * 128) + i];
}
arrSum[i] = sum;
} Т.е. мы поменяли местами, т.к. и ежу понятно, что чем меньше мы обращаемся к массиву, тем быстрее должно работать.
Пример на самом деле плохой, но показывает нам, что нужно проверять код в Burst Inspector.
И да, первый вариант векторизуется и будет работать быстрее.
Лет 5-6 назад я встретил в одном из плагинов facebook следующую запись:
public some::Item Method() {
...
}Я особо не задумывался зачем оно надо, но потом я сформулировал идею: использовать :: между using-сокращением и типом, т.е. когда мы пишем using someVar = Some.Type; Тогда в коде будет
someVar::Example
Позже я стал замечать примерно такую же концепцию в разных фреймах:
global::SomeClass.someVar
Я уже писал о том, что можно контролировать партиклы из кода. Но я не написал о том, что можно одним вызовом Emit запустить партикл систему, и на каждый такой вызов будет воспроизводиться система.
Для этого нужно указать sub emitter у основной партикл системы, а все модули основной системы отключить. Мы это использовали для поджигания травы (Кто не видел пост - https://t.me/unsafecsharp/48), чтобы нарисовать огонь для каждой травинки.
Да, весь прикол в том, что вся эта радость будет рисоваться в 1 DrawCall, т.к. партикл система знает все, что нужно о своих подсистемах, за что ей отдельное спасибо.
В итоге мы контролируем огонь через Emit + GetParticles/SetParticles, а что там за огонь - это уже vfxер нарисует, настраивая обычную систему. Имейте ввиду, что ограничение в подсистемах на maxParticles должен быть расчитан на все системы, а не на одну.
QuadTree - это структура данных, которая используется для разбиения двумерного пространства на более мелкие области. Каждый узел дерева представляет собой квадратную область (ячейку) внутри основной области. Если ячейка слишком большая, то она разбивается на четыре одинаковых подъячейки, каждая из которых может быть либо пустой, либо содержать объекты.
В QuadTree каждая нода может иметь до четырех потомков, которые представляют собой разделенную ячейку.
Для добавления объектов в QuadTree необходимо сперва знать, какой ячейке они принадлежат. Каждый объект добавляется в самую мелкую ячейку, которая полностью охватывает его. Если ячейка становится слишком заполненной, то она разбивается на более мелкие. Проще говоря, нужно делать rect.Contains() несколько раз, чтобы понять куда отнести элемент.
Поиск объектов в QuadTree осуществляется путем перебора узлов дерева. Начиная с корня, мы проверяем, находится ли ячейка, в которой мы ищем объект, в пределах текущей ячейки узла. Если да, то мы переходим к следующему уровню дерева и продолжаем поиск в ячейках потомков. Если нет, то мы переходим к следующему соседнему узлу.
Преимущества QuadTree заключаются в том, что он позволяет быстро находить объекты в двумерном пространстве, а также быстро выполнять операции вставки и удаления объектов. Недостатком может быть то, что при неправильном выборе размера ячеек и глубины дерева, может возникнуть слишком большая структура, что негативно скажется на производительности.
На практике мы такое используем для поиска целей для атаки. Существует еще и Octree для 3D, алгоритм работы по сути ничем не отличается.