воскресенье, 18 августа 2013 г.

Об итерировании статичных массивов в .NET, часть 1

Блог переехал. Актуальная версия поста находится по адресу: http://aakinshin.net/ru/blog/dotnet/static-array-iteration/.


Содержание поста было обновлено: результаты были уточнены, появилась вторая часть с подробным объяснением сложившейся ситуации.

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

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

В примере будем решать простую задачу: подсчёт суммы элементов массива. В первом случае мы будем использовать обычное боле класса, а во втором — статическое. Для замеров времени будем использовать BenchmarkDotNet (исходный код примера: ArrayIterationProgram.cs, тестировать следует в Release mode without debugging):

private const int N = 1000, IterationCount = 1000000;

private int[] nonStaticField;
private static int[] staticField;

public void Run()
{
    nonStaticField = staticField = new int[N];

    var competition = new BenchmarkCompetition();
    competition.AddTask("Non-static", () => NonStaticRun());
    competition.AddTask("Static", () => StaticRun());
    competition.Run();
}

private int NonStaticRun()
{
    int sum = 0;
    for (int iteration = 0; iteration < IterationCount; iteration++)
        for (int i = 0; i < N; i++)
            sum += nonStaticField[i];
    return sum;
}

private int StaticRun()
{
    int sum = 0;
    for (int iteration = 0; iteration < IterationCount; iteration++)
        for (int i = 0; i < N; i++)
            sum += staticField[i];
    return sum;
}

На своей машине я получил следующие результаты:

Non-static : 346ms
Static     : 535ms

Если мы взглянем на IL-код целевых методов, то увидим, что они различаются только в одном месте, при обращении к полю:

Non-static:
L_000b: ldarg.0 
L_000c: ldfld int32[] Benchmarks.StaticFieldBenchmark::nonStaticField
Static:
L_000b: ldsfld int32[] Benchmarks.StaticFieldBenchmark::staticField

Заметим, что физически оба поля ссылаются на одну и ту же область памяти. Мы можем ускорить работу со статическим полем, если перед многократным обращением к полю сохраним его в локальную переменную:

private int StaticRun()
{
    var localField = staticField;
    int sum = 0;
    for (int iteration = 0; iteration < IterationCount; iteration++)
        for (int i = 0; i < N; i++)
            sum += localField[i];
    return sum;
}

В итоге StaticRun будет работать столько же, сколько и NonStaticRun.

Объяснение такого поведения можно прочитать во второй части статьи.

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

  1. Решил проверить на моей рабочей машине.
    Non-static : 4091ms
    Static : 3683ms

    После ускорения
    Static-improve : 3799ms

    Странно))

    ОтветитьУдалить
    Ответы
    1. Действительно странно, нужно изучить этот вопрос более подробно.
      Вы использовали версию проекта с GitHub-а или что-то дописывали сами?
      И напишите, пожалуйста, конфигурацию вашей рабочей машины.

      Удалить
    2. Ещё хотелось бы уточнит, как именно вы запускаете Benchmark. Для получения правильных результатов следует использовать Release mode without debugging. Если вы запустите в Debug mode или с отладкой (F5 из студии), то результаты могут сильно измениться.

      Удалить
  2. Вообще по идее ldsfld сразу помещает значение поля в стек, зная его расположение, а ldfld сначала ищет, потом помещает.

    ОтветитьУдалить
    Ответы
    1. Думаю дело в том, что для ldfld указатель на this сразу загружен в стек (после JIT-а это может быть непосредственно регистр), нам остаётся лишь перейти к его полю. При работе со статическим полем в ldsfld нам необходимо сначала найти статический instance целевого класса, а только потом перейти к его полю.

      Удалить
  3. "Дело в том, что она значительно ниже, чем скорость доступа к локальным переменным и обычным полям." - на самом деле всё наоборот и только для значимых типов. Для ссылочных типов время почти одинаковое.

    ОтветитьУдалить
    Ответы
    1. А вы можете аргументировать свою позицию?
      В посте я привожу тест на производительность каждого варианта. Я запускал этот код на нескольких различных машинах, везде получал одинаковый результат. Данный пример работает только для ссылочных типов, а вот как раз для значимых — время работы будет практически одинаковое.

      Удалить
    2. Да, вроде мой косяк. Поторопился с выводами. Вчера комп у меня одно показывал, сегодня другое. Будет время надо бы подробней рассмотреть. Тема интересная намечается.

      Удалить
    3. Обратите внимание, что запускать бенчмарк нужно обязательно в Release mode without debugging (лучшее не из студии, а из консоли). В противном случае результаты могут скакать туда-сюда и не очень коррелировать с реальностью.

      Удалить
  4. Нужно понимать, что CLR-виртуальная стековая машина, без регистров.
    Когда JIT переводит IL в машинные команды,
    он смотрит сколько регистров у реальной машины (8 у x86, 16 у x64) и значительно упрощает граф программы.

    В данном случае (из-за особенностей бенчмака) ldarg.0 вполне могло быть вынесено за пределы цикла как «mov eax, *this».
    Но в реальности не выносится :-)

    Ниже дизассемблированный код операций доступа к полям (вырезаны идентичные инструкции):

    mov edx,dword ptr [ebp-10h] ; edx <- this
    mov edx,dword ptr [edx+4] ; edx <- nonStaticField

    mov edx,dword ptr ds:[03254F44h] ; edx <- staticField

    Получается, что этот эффект, не особеннось CLR, а скорее особенность архетектуры железки,
    и того, как проц работает с памятью.

    ОтветитьУдалить
    Ответы
    1. Спасибо за комментарий. Я более детально разобрался в проблеме, действительно, non-static ведёт в скорости только под x64. В ближайшее время я опубликую вторую часть поста, в которой объясню такую разницу с примерами дизассемблерного кода.

      Удалить