Feel Good.

17 ноября 2010

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

5 комментариев:

  1. Интересный пример, спасибо. Конечно, оптимизации производительности на таком низком уровне встречаются ОЧЕНЬ редко. Но у меня недавно был пилотник, который высчитывал вероятности победы игроков в покер на различных комбинациях карт (в целях обучения) при помощи метода Монте-Карло. Там пришлось вплотную вооружиться профайлером и бороться за каждую миллисекунду, ведь почти миллион симуляций должны были вычисляться за пару секунд. Оказалось, что даже вызовы методов при таком количестве симуляций дают ощутимое падение производительности. А так как в C#, в отличие от С++, нельзя ЯВНО промаркировать инлайновые методы - лучше написать один длинный метод и забить на читаемость кода.

    ОтветитьУдалить
  2. Согласен, читаемость кода (или архитектура) и производительность обычно дружат в обратной зависимости. Такой тюнинг следует проводить только там, где он действительно(!) нужен.
    У меня имеется "realtime" сервис, который вычисляет кое-какие экономические показатели в потоке, а это как раз та задача где нужно бороться за миллисекунды.
    Оказалось, что .NET позволяет нам писать достаточно нагруженные приложения, и разработка таковых происходит намного быстрее(!) чем на C++, C.
    Если тюнинг вычислительной части не помог, то возможно следует приглядеться к CUDA.

    ОтветитьУдалить
  3. Первый пример - как раз основная причина, почему C называли медленным при расчетах по сравнению с FORTRAN. В фортране двумерные массивы хранятся по столбцам, поэтому "быстрый" код в нем как раз первый из примера. Тупой перенос этого кода на C приводит к падению производительности.

    ОтветитьУдалить
  4. Разве в последнем примере метод Do не должен обратиться к dump что бы подтянуть последний из памяти? всётаки dump это ссылка на объект, а не непосредвсено сам масив в памяти.

    ОтветитьУдалить
  5. @photoscar
    Спасибо за уточнение, да, можно было бы обращаться к массиву или к другому элементу (для того чтобы загрузить его в кэш), но это не самый удачный пример. Выложил новый пример, добавив поля l1,l2,....,l16 которые полностью заполняют кэш-строку для Some.

    PS: Либо рассматривать _x как массив: int[] _x = new[16]; А в методе Do _x[0]++;

    ОтветитьУдалить