Blog #cache

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

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

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

Самый простой пример аллокаций - это замыкание. Тут остановимся подробнее. Где могут скрываться аллокации, например, в такой конструкции: list.Where(x => x > 10).ToArray() Очевидно, что при вызове ToArray будет создан массив. Больше никаких аллокаций в данном примере не будет. Давайте рассмотрим второй пример: 

var a = 10; 
list.Where(x => x > a).ToArray() 

Тут к предыдущей аллокации добавляется еще замыкание с переменной "a". Проблема в том, что с этим мы ничего поделать не можем. Но давайте представим, что мы пишем свой замечательный Linq. Каким образом можно избежать аллокации? Нужно сделать просто передачу параметра:

public static void Where<TClosure, T>(this List<T> list, TClosure closure, System.Func<T, TClosure, bool> where) {
     if (where.Invoke(list[i], closure) == false) ... 
}  

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

Аллокации при боксинге. Боксинг (boxing) - это фактически создание ValueType в куче. Это довольно затратный процесс сам по себе, но самое главное - это тот факт, что когда-нибудь GC об этом вам напомнит. При обратном процессе (unboxing) этого не происходит.

Вообще аллокации в куче плохи тем, что они не очень cache-friedly. Но иногда нам нужно сделать аллокации. Представим ситуацию, когда мы аллоцируем массив с нодами, где у каждой ноды есть еще список нод:

var arr = new Node[1000]; 
for (int i = 0; i < arr.Length; ++i) {
     arr[i] = new Node() {
         nodes = new List<Node>(),
     }; 
} 

Обычно я встречал запись именно такую. Чем она плоха? Тем, что мы аллоцируем первую ноду, и сразу в ноде аллоцируем еще один объект (а может и несколько). Т.е. мало того, что куча в принципе не очень cache-friedly, так мы отказываемся от кэша совсем, создавая объекты таким образом. Как нужно было бы поступит?

var arr = new Node[1000]; for (int i = 0; i < arr.Length; ++i) {
     arr[i] = new Node(); // Создаем ноды, чтобы GC постарался их разместить в памяти последовательно } 
for (int i = 0; i < arr.Length; ++i) {
     arr[i].nodes = new List<Node>(); // Инициализируем данные каждой ноды 
} 

Таким образом, если мы не готовы писать cache-friedly код в целом, то хотя бы частично небольшими изменениями мы можем постараться помочь GC.