False sharing

Казалось бы, зачем задумывываться о процессах, происходящих на таком низком уровне, как кэширование данных в L1 и L2 кешах (L1, L2 cache), если Вы программируете под .NET. Очевидно для повышения быстродействия программы (perfomance) за счет уменьшения кэш-промахов (Cache Miss). Самый простой и классический пример демонстрирующий проблему Cache Miss, это "неправильный" обход массива. При "правильном" обходе количество промахов будет минимально, следовательно участок кода выполнится быстрее:

int size = 10000;

int[,] matrix = new int[size, size];

 

// Вариант 1

// Очень медленный вариант

for (int col = 0; col < size; col++)

    for (int row = 0; row < size; row++)

        matrix[row, col] = 0;

 

// Вариант 2

// Быстрый вариант

for (int row = 0; row < size; row++)

    for (int col = 0; col < size; col++)

        matrix[row, col] = 0;

Еще один пример (с wikipedia), допустим нам необходимо как-то вычислять поле Foo.x, в нашем случае это простая инкрементация:

// Вариант 1

// Очень медленный

Foo foo = new Foo();

for (int i = 0; i < MaxIter; i++)

    foo.x++;

против

// Вариант 2

// С локальной переменной, быстрый.

Foo foo = new Foo();

int sum = 0;

for (int i = 0; i < MaxIter; i++)

    sum = sum + 1;

где

class Foo

{

    public int x = 0;

}

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

// Вариант 1

// Создадим экземпляры Some в главном потоке

Some some1 = new Some();

Some some2 = new Some();

Some some3 = new Some();

 

// Запустим 3 паралельных задачи

Parallel.Invoke

(

    () => { for (int i = 0; i < MaxIter; i++) { some1.Do(); } },

    () => { for (int i = 0; i < MaxIter; i++) { some2.Do(); } },

    () => { for (int i = 0; i < MaxIter; i++) { some3.Do(); } }

);

против

// Вариант 2

// Запустим 3 паралельных задачи

// Инициализация Some будет происходить внутри каждой задачи.

Parallel.Invoke

(

    () => { Some some1 = new Some(); for (int i = 0; i < MaxIter; i++) { some1.Do(); } },

    () => { Some some2 = new Some(); for (int i = 0; i < MaxIter; i++) { some2.Do(); } },

    () => { Some some3 = new Some(); for (int i = 0; i < MaxIter; i++) { some3.Do(); } }

);

Q:Какой из этих двух вариантов выполнится быстрее?
A: Все зависит от реализации метода Some.Do. Если метод Do изменяет состояние объекта Some таким образом, что строка (cache line) загруженная в кэш станет недействительной, то почти наверняка, второй вариант будет выполнятся намного быстрее первого (ситуация False Sharing), иначе оба варианта потребуют примерно одинаковое время на выполнение.
Например, подобная реализация Some увеличит время исполнения первого варианта относительно второго:

// Реализация Some с изменяемым состоянием

class Some

{

    int _x = 0; // состояние объекта Some

 

    public void Do()

    {

        // изменение состояния

        _x++;

    }

}

Но стоит увеличить объект таким образом, что кэшируемые данные окажутся в разных кэш-строках, то скорость выполнения первого и врогого варианта сравняется:

// Реализация Some с изменяемым состоянием

class Some

{

    int _x = 0; // состояние объекта Some

 

    // больше чем размер кэш-строки

    long l1;

    long l2;

    long l3;

    long l4;

    long l5;

    long l6;

    long l7;

    long l8;

    long l9;

    long l10;

    long l11;

    long l12;

    long l13;

    long l14;

    long l15;

    long l16;

 

    public void Do()

    {

        // изменение состояния

        _x++;

    }

}

Ссылки:

1. False sharing
2. MSDN: False sharing
3. Patterns for Parallel Programming: Understanding and Applying Parallel Patterns with the .NET Framework 4