Blog #lockfree

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

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 делаем обратную операцию.