false sharing - это ситуация, когда несколько потоков одновременно обращаются к разным переменным, которые находятся в одной кеш-линии. Кеш-линия - это минимальная единица данных, которая копируется из оперативной памяти в кеш процессора.

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

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

#threading #cache

Как устроен QuadTree?
QuadTree - это структура данных, которая используется для разбиения двумерного пространства на более мелкие области. Каждый узел дерева представляет собой квадратную область (ячейку) внутри основной области. Если ячейка слишком большая, то она разбивается на четыре одинаковых подъячейки, каждая из которых может быть либо пустой, либо содержать объекты.

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

Для добавления объектов в QuadTree необходимо сперва знать, какой ячейке они принадлежат. Каждый объект добавляется в самую мелкую ячейку, которая полностью охватывает его. Если ячейка становится слишком заполненной, то она разбивается на более мелкие. Проще говоря, нужно делать rect.Contains() несколько раз, чтобы понять куда отнести элемент.

Поиск объектов в QuadTree осуществляется путем перебора узлов дерева. Начиная с корня, мы проверяем, находится ли ячейка, в которой мы ищем объект, в пределах текущей ячейки узла. Если да, то мы переходим к следующему уровню дерева и продолжаем поиск в ячейках потомков. Если нет, то мы переходим к следующему соседнему узлу.

Преимущества QuadTree заключаются в том, что он позволяет быстро находить объекты в двумерном пространстве, а также быстро выполнять операции вставки и удаления объектов. Недостатком может быть то, что при неправильном выборе размера ячеек и глубины дерева, может возникнуть слишком большая структура, что негативно скажется на производительности.

На практике мы такое используем для поиска целей для атаки.

Существует еще и Octree для 3D, алгоритм работы по сути ничем не отличается.

#datastructures #algorithms

Ребят, хотел бы порекомендовать личный блог моего товарища, которого наверняка многие знают;)

Задачи для Unity разработчиков, актуальные новости игровой разработки, авторские мысли. Всё это есть в блоге Григория Дядиченко.

Если вам интересна Unity разработка, виртуальная и дополненная реальность, фриланс или аутсорс бизнес — подписывайтесь на канал!

Я уже писал о том, что можно контролировать партиклы из кода. Но я не написал о том, что можно одним вызовом Emit запустить партикл систему, и на каждый такой вызов будет воспроизводиться система.

Для этого нужно указать sub emitter у основной партикл системы, а все модули основной системы отключить. Мы это использовали для поджигания травы (Кто не видел пост - https://news.1rj.ru/str/unsafecsharp/48), чтобы нарисовать огонь для каждой травинки.

Да, весь прикол в том, что вся эта радость будет рисоваться в 1 DrawCall, т.к. партикл система знает все, что нужно о своих подсистемах, за что ей отдельное спасибо.

В итоге мы контролируем огонь через Emit + GetParticles/SetParticles, а что там за огонь - это уже vfxер нарисует, настраивая обычную систему. Имейте ввиду, что ограничение в подсистемах на maxParticles должен быть расчитан на все системы, а не на одну.

#particles #code #performance

Немного про код-стайл.

Лет 5-6 назад я встретил в одном из плагинов facebook следующую запись:

public some::Item Method() {
    ...
}

Я особо не задумывался зачем оно надо, но потом я сформулировал идею: использовать :: между using-сокращением и типом, т.е. когда мы пишем using someVar = Some.Type;
Тогда в коде будет

someVar::Example

Позже я стал замечать примерно такую же концепцию в разных фреймах:

global::SomeClass.someVar

#code #codestyle

Немного занимательного Burst и векторизации

Мы хотим выполнить несколько итераций (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.
И да, первый вариант векторизуется и будет работать быстрее.

#burst #vectorization #performance

Используйте битмаски. Я редко встречаю код с битмасками, уж не знаю почему, но в основном люди предпочитают обходить их стороной. Разбираемся, ведь в них нет ничего сложного.

Битовые маски могут использоваться для манипулирования отдельными битами в числе. Это может быть полезно, например, чтобы проверить, является ли определенный бит установленным или снятым.


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 и на вывод в лог.

#bitmask #code

Давайте теперь про Layout структур.

Давайте представим, что у нас есть 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 _;
}

#burst #struct #structlayout #alignment #simd

Господа! Осталось полчаса до старта нашего второго созвона;) Кто еще не зарегался - велкам! https://news.1rj.ru/str/unsafecsharp/39

Мы знаем, что структуры нужно инициализировать в конструкторе полностью:


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;
}
}

#structs #lifehack

Для дебага полезная штука - написать свой Proxy:

[System.Diagnostics.DebuggerTypeProxyAttribute(typeof(DebugClass))]
public class YourClass { ... }


Где DebugClass - это отдельный класс, который может содержать геттеры и поля. Еще у него должен быть конструктор, который будет принимать инстанс YourClass.
Это сильно помогает при дебаге сложных штук.

#debug #code

Про CC коллекции.

CC (`Concurrent Collections`) коллекции - это набор коллекций данных, разработанных для работы в многопоточной среде. Одной из особенностей CC коллекций является их lock-free (без блокировок) реализация, которая позволяет не блокировать весь многопоточный поток при обращении к коллекции.

Все CC коллекции стараются обходиться без lock, т.е. в нормальном режиме работы - либо вообще без lock, либо в редких исключениях его использование.
Давайте разберем простой пример, чтобы было понятно как именно работают такие коллекции.
Допустим, что нам нужно написать коллекцию Stack<> (возьмем самую простую). В однопоточной реализации мы используем массив элементов + индекс, который говорит нам где мы находимся в данный момент. При Push мы просто кладем элемент по индексу и увеличиваем индекс, а при Pop просто уменьшаем индекс. Ну еще при Push нам нужно проверить размер массива и сделать новый, если это нужно.

А теперь в многопоточность.
Как реализовать такую коллекцию? Давайте не будем вообще создавать никаких массивов, а будем использовать односвязный список из нод. Node - это объект, который имеет указатель на предыдущий элемент и данные внутри себя.
Коллекция же имеет только ссылку на head-ноду. При добавлении элемента нам нужно создать ноду и каким-то образом ее запихнуть к последней, используем Interlocked.CompareExchange и заменяем head на наш элемент. При Pop делаем обратную операцию.

#multithreading #threading #collections #lockfree

🥕Задачка
У вас есть строка вида «aabbbccde»
Вам нужно написать алгоритм, который уберет все дубликаты символов, которые стоят вместе, то есть останется только «abcde». Для строки «aabbccaabb» ответ будет «abcab».
Нужен алгоритм, использовать всякие regex нельзя;)

🥕ME.BECS
Примерно вот так выглядит граф систем в ME.BECS :)

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


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 мы передаем номер текущего потока. Тогда этот счетчик будет работать без оверхеда на добавление совсем. А когда операции закончились - мы суммируем все счетчики и возрващаем значение.

#multithreading #threading #collections #lockfree

Используйте указание на конкретный тип в 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 🙂

#enum #code #structlayout

Написал немного про поиск пути, буду выкладывать ссылки на статьи в телеграф, если нужны картинки или хочу описать что-нибудь более подробно.

https://telegra.ph/Unity-Poisk-puti-05-28

#pathfinding #algorithms

🥕Задачка
Предыдущая задачка была совсем простая, поэтому вот вам посложнее, но снова про строки;)

У вас есть строка вида «aabbbccde»
Вам нужно написать алгоритм, который переставит символы так, чтобы не осталось символов, идущих подряд. Если это невозможно, то вернуть null.
«aabbbccde» = «ababcbcde»
«aaccbbcccc» = null
«aabbaac» = «ababaca»
«aaabbbb» = «bababab»

Дополнительно:
Возможно ли эту задачу без аллокаций, если исходная строка приходит в виде массива char?

🥕Как определить пересекаются ли OBB и OBB?

OBB - это Oriented Bounding Box, это такой Rect с поворотом, но в 3D 🙂

Попробуйте ответить на этот вопрос до того, как посмотрите мое решение. Напишите в комменты свой вариант решения (просто описание алгоритма) хотя бы для 2D. Интересно было бы сравнить.

Мой вариант решения тут:
https://telegra.ph/Kak-poschitat-peresechenie-OBB-i-OBB-05-30

Давайте немного про сеть поговорим.

Какие протоколы мы используем?

TCP (Transmission Control Protocol) и UDP (User Datagram Protocol) - это два наиболее распространенных протокола передачи данных. Основное отличие между ними заключается в том, что TCP является протоколом, обеспечивающим надежную передачу данных, а UDP - протоколом без установления соединения и без гарантии доставки данных.

TCP обеспечивает контроль над передачей данных, используя механизмы подтверждения и повторной передачи пакетов в случае потерь или ошибок. Он также гарантирует, что данные будут доставлены в правильном порядке и без дублирования. TCP используется для передачи данных, которые требуют высокой степени надежности. Например, мы хотим передать информацию об игроке от сервера клиенту.

UDP, с другой стороны, не обеспечивает надежной передачи данных и не гарантирует их доставку. Он используется для передачи данных, которые не требуют высокой степени надежности, например, для передачи последней позиции игрока, когда нам не важно где он находился до этого.

RUDP (Reliable User Datagram Protocol) - это протокол, который сочетает в себе преимущества TCP и UDP. Он обеспечивает надежную передачу данных, как TCP, но без установления соединения, как UDP. RUDP используется для передачи данных с гарантией доставки, но не гарантирует порядок пакетов.

В случае с TCP при получении пакетов 1, 3, 4, 5, TCP отдаст только пакет 1, а остальные пакеты придержит до тех пор, пока пакет 2 не будет доставлен. Таким образом можно замечать некую «тормознутость» при использовании TCP, когда пакетов нет-нет, а потом хоп, и вдруг сразу и много. С RUDP/UDP такого не происходит.

Закончу на моей любимой шутке: я бы рассказал вам шутку про UDP, но боюсь что она до вас не дойдет.

#network #theory