Нашли ошибку или опечатку? Выделите текст и нажмите

Поменять цветовую

гамму сайта?

Поменять
Обновления сайта
и новые разделы

Рекомендовать в Google +1

Аппаратно-зависимые оптимизации

93

Теоретически, разработчиков приложений для .NET никогда не должен волновать вопрос оптимизации под конкретную аппаратную платформу. В конце концов, цель IL и JIT-компилятора состоит в том, чтобы обеспечить возможность выполнения управляемых приложений на любой аппаратной платформе, где установлен фреймворк .NET Framework, и обеспечить независимость от разрядности операционной системы, особенностей процессора и поддерживаемого им набора машинных инструкций.

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

В этой короткой статье мы рассмотрим несколько примеров оптимизации под конкретные особенности процессоров, которые могут увеличивать производительность приложения на одном компьютере, и не оказывать никакого влияния на другом. В основном мы будем рассматривать процессоры Intel, в частности семейства Nehalem, Sandy Bridge и Ivy Bridge, но большая часть рекомендаций с равным успехом применимы и к процессорам AMD.

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

Единственный поток команд и множество потоков данных

Архитектуры с параллельным доступом к данным также называют архитектурами с поддержкой инструкций, обрабатывающих множество данных (Single Instruction Multiple Data, SIMD). Эта особенность современных процессоров позволяет обрабатывать большие объемы данных (больше одного машинного слова) единственной инструкцией. Фактическим стандартом инструкций SIMD являются потоковые SIMD-расширения (Streaming SIMD Extensions, SSE), используемые в процессорах Intel, начиная с Pentium III. Этот набор инструкций добавляет новые 128-разрядные регистры (с префиксом XMM) а также инструкции, оперирующие ими.

В последних процессорах Intel появилась поддержка дополнительных векторных расширений (Advanced Vector Extensions, AVX), расширяющих набор команд SSE поддержкой 256-разрядных регистров и дополнительными инструкциями SIMD. В качестве примеров инструкций SSE можно привести:

  • целочисленная и вещественная арифметика;

  • сравнение, перемешивание, преобразование типов данных (из целых в вещественные);

  • поразрядные операции;

  • поиск минимального и максимального значений, копирование по условию, вычисление контрольной суммы CKC32, определение количества битов, установленных в 1 (эта команда поддерживается набором инструкций SSE4 и более поздних).

Вы можете спросить, не медленнее ли такие инструкции, использующие «новые» регистры, чем стандартные, потому что если это так, любые выгоды в смысле производительности могут оказаться призрачными. К счастью это не так. В процессорах Intel i7 инструкция сложения вещественных чисел (FADD) в 32-разрядных регистрах имеет пропускную способность, равную одной инструкции за такт, и задержку 3 такта. Эквивалентная ей инструкция ADDPS, оперирующая 128-разрядными регистрами, также имеет пропускную способность, равную одной инструкции за такт, и задержку 3 такта.

Задержка и пропускная способность

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

  • задержка инструкции - это время (обычно измеряемое в тактах), необходимое для выполнения единственной инструкции от начала до конца;

  • пропускная способность - это количество инструкций одного типа, которые могут быть выполнены в единицу времени (обычно измеряется в тактах).

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

Использование этих инструкций в глубоком цикле может обеспечить 8-кратный прирост производительности, в сравнении с простейшими последовательными программами, обрабатывающими вещественные или целые числа по одному. Например, взгляните на следующий (специально упрощенный) код:

// Предполагается, что A, B и C - массивы 
// вещественных чисел одинакового размера 
for (int i = 0; i < A.length; ++i)
{
    C[i] = A[i] + B[i];
}

Ниже приводится код, генерируемый JIT-компилятором в таких ситуациях:

; ESI - указатель на A, EDI - на B, ECX - на C, 
; EDX - переменная цикла
    xor edx,edx
    cmp dword ptr [esi + 4],0
    jle END_LOOP
	
NEXT_ITERATION:
    fld dword ptr [esi + edx*4 + 8]    ; загрузить A[i], без проверки границ
    cmp edx,dword ptr [edi + 4]        ; проверка границ перед доступом к B[i]
    jae OUT_OF_RANGE
    FADD dword ptr [edi + edx*4 + 8]   ; прибавить B[i]
    cmp edx,dword ptr [ecx + 4]        ; проверка границ перед доступом к C[i]
    jae OUT_OF_RANGE
    fstp dword ptr [ecx + edx*4 + 8]   ; сохранить в C[i]
    inc edx
    cmp dword ptr [esi + 4],edx        ; конец?
    jg NEXT_ITERATION
END_LOOP:

В каждой итерации цикла выполняется единственная инструкция FADD, складывающая два 32-разрядных вещественных числа. Однако, при использовании 128-разрядных инструкций SSE, одновременно можно было бы выполнять четыре итерации цикла, как показано ниже (следующий код не выполняет проверку границ и предполагает, что число итераций кратно 4):

xor edx, edx
NEXT_ITERATION:
    movups xmm1, xmmword ptr [edi + edx*4 + 8]   ; скопировать 16 байт из B в xmm1
    movups xmm0, xmmword ptr [esi + edx*4 + 8]   ; скопировать 16 байт из A в xmm0
    addps xmm1, xmm0                             ; сложить xmm0 и xmm1 и 
	                                             ; сохранить результат в xmm1
    movups xmmword ptr [ecx + edx*4 + 8], xmm1   ; скопировать 16 байт из xmm1 в C
    add edx, 4                                   ; индекс цикла увеличить на 4
    cmp edx, dword ptr [esi + 4]
    jg NEXT_ITERATION

На процессоре с поддержкой AVX в каждой итерации можно было бы обрабатывать еще больше данных (с использованием 256-разрядных регистров YMM*), и получить еще больший прирост производительности:

 xor edx, edx
NEXT_ITERATION:
    vmovups ymm1, ymmword ptr [edi + edx*4 + 8]   ; скопировать 32 байта из B в ymm1
    vmovups ymm0, ymmword ptr [esi + edx*4 + 8]   ; скопировать 32 байта из A в ymm0
    vaddps ymm1, ymm1, ymm0                       ; сложить ymm0 и ymm1 и 
	                                              ; сохранить результат в ymm1
    vmovups ymmword ptr [ecx + edx*4 + 8], ymm1   ; скопировать 32 байта из ymm1 в C
    add edx, 8                                    ; индекс цикла увеличить на 8
    cmp edx, dword ptr [esi + 4]
    jg NEXT_ITERATION

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

JIT-компилятор использует лишь малую часть инструкций SSE, даже при том, что они доступны практически во всех процессорах, выпускавшихся в последние 10 лет. В частности, JIT-компилятор использует SSE-инструкцию MOVQ для копирования структур среднего размера через регистры XMM* (при копировании больших инструкций используется REP MOVS), а также SSE2-инструкции для преобразования вещественных чисел в целые. Но JIT-компилятор не выполняет векторизацию циклов, как это было сделано вручную в примерах выше, хотя современные компиляторы C++ (включая Visual Studio 2012) поддерживают такую возможность.

К сожалению в C# отсутствуют какие-либо ключевые слова, позволяющие встраивать ассемблерный код в управляемые программы. Конечно, вы всегда можете реализовать чувствительные к производительности части приложений в виде модулей на C++ и использовать механизм взаимодействий в .NET для доступа к ним, но это довольно неудобно. Существует два других подхода к встраиванию инструкций SIMD, не прибегая к созданию отдельного модуля.

Простейший способ выполнить произвольный машинный код в управляемом приложении (с применением легковесной программной прослойки) заключается в том, чтобы динамически сгенерировать машинный код и затем вызвать его. Ключевым здесь является метод Marshal.GetDelegateForFunctionPointer(), возвращающий управляемого делегата, указывающего на местоположение в неуправляемой памяти, где может храниться произвольный код. Следующий пример выделяет виртуальную память с флагом защиты EXECUTE_READWRITE, позволяющим скопировать байты кода в память и затем выполнить их. Как результат, на процессоре Intel i7-860 скорость выполнения увеличивается более чем в два раза!

// ...
using System.Runtime.InteropServices;

// ...

public class Program
{
    [UnmanagedFunctionPointer(CallingConvention.StdCall)]
    delegate void VectorAddDelegate(float[] C, float[] B, float[] A, int length);

    [DllImport("kernel32.dll", SetLastError = true)]
    static extern IntPtr VirtualAlloc(
        IntPtr lpAddress, UIntPtr dwSize, IntPtr flAllocationType, IntPtr flProtect);

    public static void Main(string[] args)
    {
        // Следующий массив байтов был получен с помощью ассемблера
        // с поддержкой SSE - это законченная функция, принимающая 
        // четыре параметра (три вектора и длину) и складывающая их
        byte[] sseAssemblyBytes = { 0x8b, 0x5c, 0x24, 0x10, 0x8b, 0x74, 
                                    0x24, 0x0c, 0x8b, 0x7c, 0x24,
                                    0x08, 0x8b, 0x4c, 0x24, 0x04, 0x31, 
                                    0xd2, 0x0f, 0x10, 0x0c, 0x97,
                                    0x0f, 0x10, 0x04, 0x96, 0x0f, 0x58, 
                                    0xc8, 0x0f, 0x11, 0x0c, 0x91,
                                    0x83, 0xc2, 0x04, 0x39, 0xda, 0x7f, 
                                    0xea, 0xc2, 0x10, 0x00 };

        IntPtr codeBuffer = VirtualAlloc(
            IntPtr.Zero,
            new UIntPtr((uint)sseAssemblyBytes.Length),
            new IntPtr(0x1000 | 0x2000), // MEM_COMMIT | MEM_RESERVE
            new IntPtr(0x40)             // EXECUTE_READWRITE
        );

        Marshal.Copy(sseAssemblyBytes, 0, codeBuffer, sseAssemblyBytes.Length);
        VectorAddDelegate addVectors = (VectorAddDelegate)Marshal
            .GetDelegateForFunctionPointer(codeBuffer, typeof(VectorAddDelegate));

        // Теперь для сложения векторов можно использовать 'addVectors'

    }
}

Совершенно иной подход, который, к сожалению, не поддерживается средой выполнения Microsoft CLR, заключается в расширении JIT-компилятора и добавлении в него возможности генерировать инструкции SIMD. Этот подход поддерживается сборкой Mono.Simd. Разработчики управляемых приложений, использующие среду выполнения Mono .NET, могут подключить сборку Mono.Simd и использовать поддержку JIT-компилятора, преобразующего операции с такими типами, как Vector16b и Vector4f в соответствующие инструкции SSE.

Распараллеливание инструкций

В отличие от параллельного доступа к данным, когда для работы с более крупными фрагментами данных используются специализированные инструкции, распараллеливание на уровне инструкций (Instruction-Level Parallelism, ILP) - это механизм, позволяющий одновременно выполнять несколько инструкций на одном и том же процессоре.

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

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

В дополнение к конвейерам, процессоры поддерживают также суперскалярное выполнение (superscalar execution), когда на одном и том же процессоре одновременно используется несколько не занятых устройств для выполнения однотипных операций.

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

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

for (int k = 1; k < 100; ++k)
{
    first[k] = a * second[k] + third[k];
}

for (int k = 1; k < 100; ++k)
{
    first[k] = a * second[k] + first[k - 1];
}

for (int k = 1; k < 100; ++k)
{
    first[k] = a * first[k - 1] + third[k];
}

Мы миллион раз выполнили эти циклы на одном из наших компьютеров с массивами из 100 целых чисел. Первый цикл выполнялся в среднем 190 миллисекунд, второй примерно 210 миллисекунд и третий - около 270 миллисекунд. Такая существенная разница объясняется особенностями распараллеливания инструкций. В первом цикле отсутствуют какие-либо зависимости между инструкциями - итерации могут выполняться в конвейере процессора в любом порядке и одновременно. Во втором цикле наблюдается зависимость - значение first[k] зависит от значения first[k - 1]. Однако операция умножения (которая должна быть выполнена до сложения) лишена такой зависимости. В третьем цикле ситуация складывается еще хуже: даже инструкция умножения не может быть выполнена независимо от результатов предыдущей итерации.

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

			
int[] arr = new int[10];

// Простейший алгоритм, страдающий зависимостью между итерациями
int max = arr[0];
for (int k = 1; k < 100; ++k)
{
    max = Math.Max(max, arr[k]);
}

// оптимизированный ILP-алгоритм, устраняющий некоторые зависимости 
// внутри итераций, две строки могут выполняться процессором параллельно
int max0 = arr[0];
int max1 = arr[1];
for (int k = 3; k < 100; k += 2)
{
    max0 = Math.Max(max0, arr[k - 1]);
    max1 = Math.Max(max1, arr[k]);
}

max = Math.Max(max0, max1);

К сожалению, JIT-компилятор в CLR препятствует данной конкретной оптимизации, генерируя недостаточно оптимальный машинный код для второго цикла. В первом цикле наиболее важные значения (max и k) умещаются и хранятся в регистрах. Во втором цикле JIT-компилятор не способен уместить все значения в регистрах; если max1 или max0 будет храниться в памяти, это приведет к значительной потере производительности. Соответствующая реализация на C++ дает ожидаемую прибавку в скорости - деление задачи поиска пополам увеличивает производительность в два раза, а еще одно деление (поиск четырех локальных максимумов) увеличивает производительность еще на 25%.

Распараллеливание инструкций можно объединить с распараллеливанием данных. Оба примера, рассматриваемые ниже (цикл, выполняющий умножение и сложение, и поиск максимального значения), могут получить дополнительные выгоды от использования инструкций SIMD. Для поиска максимального значения используется SSE4-инструкция PMAXSD, оперирующая двумя множествами из четырех упакованных 32-разрядных целых чисел и отыскивающая максимальное значение в каждой паре чисел в двух множествах.

Следующий код (использующий встроенные функции Visual C++ из заголовочного файла <smmintrin.h>) выполняется в 3 раза быстрее, чем лучшая версия, представленная выше, и в 7 раз быстрее, чем простейшая реализация:

__m256i max0 = *(__m256i*)arr;

for (int k = 4; k < 100; k + = 4) {
	max0 = _mm_max_epi32(max0, *(__m256i*)(arr + k));
}

int part0 = _mm_extract_epi32(max0, 0);
int part1 = _mm_extract_epi32(max0, 1);
int part2 = _mm_extract_epi32(max0, 2);
int part3 = _mm_extract_epi32(max0, 3);

int finalmax = max(part0, max(part1, max(part2, part3)));

Минимизировав зависимости между инструкциями, чтобы получить дополнительные выгоды от параллельного их выполнения, можно дополнительно получить весьма существенный прирост производительности за счет распараллеливания данных (иногда называют векторизацией (vectorization)).

Управляемый и неуправляемый код

Оппоненты .NET часто говорят, что управляемая природа среды выполнения CLR привносит дополнительные накладные расходы, что делает невозможным реализацию высокопроизводительных алгоритмов с использованием C#, .NET Framework и CLR. На протяжении всех предыдущих статей мы видели разные проблемы производительности, о которых вы должны помнить, если хотите выжать из своих управляемых приложений максимальную производительность. К сожалению, всегда будут возникать ситуации, когда неуправляемый код (на C++, C или даже на языке Ассемблера) будет показывать более высокую производительность, чем его управляемый аналог.

Мы не собираемся анализировать и классифицировать каждый пример, когда реализация алгоритма на C++ обладает более высокой производительностью, чем его версия на C#. Однако все они обладают некоторыми общими чертами, проявляющимися чаще других.

  • Численные алгоритмы, реализованные на C++, обычно выполняются быстрее, даже после применения оптимизаций на C#. Основными причинами, как правило, являются: проверки границ (которые JIT-компилятором устраняются лишь в некоторых случаях и только при работе с одномерными массивами), применение инструкций SIMD компиляторами C++ и другие оптимизации, доступные компиляторам C++, такие как сложное встраивание и оптимальное использование регистров.

  • Некоторые шаблоны управления памятью отрицательно сказываются на производительности сборщика мусора. Иногда в коде на C++ можно использовать «правильные» приемы управления памятью, организуя пулы памяти или повторно используя выделенные блоки неуправляемой памяти, полученные из других источников, недоступных коду .NET.

  • Код на C++ обладает непосредственным доступом к Win32 API и не требует привлечения механизмов взаимодействий, таких как маршалинг параметров и передачи их через границы потоков выполнения. Высокопроизводительные приложения, использующие слишком подробный интерфейс операционной системы, в .NET могут выполняться значительно медленнее из-за наличия промежуточного уровня, обеспечивающего возможность взаимодействий.

На сайте CodeProject можно найти замечательную статью «Head-to-head benchmark: C++ vs. NET» Дэвида Пайпграсса (David Piepgrass), где автор разрушает некоторые ошибочные представления о производительности управляемого кода. Например, в своей статье Пайпграсс демонстрирует, что коллекции в .NET обладают значительно более высокой производительностью, чем некоторые эквиваленты из стандартной библиотеки шаблонов C++. То же относится и к построчному чтению файлов с использованием ifstream и StreamReader. С другой стороны, некоторые из его тестов подчеркивают отсутствие некоторых возможностей в 64-разрядном JIT-компиляторе, а нехватка поддержки инструкций SIMD в CLR (о чем рассказывалось выше) является еще одним фактором, обеспечивающим преимущество C++.

Исключения

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

  • Используйте исключения только в исключительных случаях: если предполагается, что исключения будут происходить слишком часто, подумайте о применении защитного стиля программирования вместо возбуждения исключений. Из этого правила есть исключения (преднамеренная игра слов), но когда требуется высокая производительность, если исключение может возникать более чем в 10 случаях из 100, такие ситуации не следует обрабатывать с применением исключений.

  • Проверяйте исключительные условия перед вызовом метода, который может возбудить исключение. Примером такого подхода может служить реализация свойства Stream.CanRead и семейства статических методов TryParse типов значений (например, int.TryParse).

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

Наиболее ощутимые накладные расходы, связанные с возбуждением и обработкой исключений, можно разделить на несколько категорий:

  • чтобы сконструировать исключение, требуется выполнить обход стека вызовов (для получения трассировочной информации), причем эти накладные расходы тем больше, чем глубже оказывается стек вызовов;

  • возбуждение и обработка исключений требует взаимодействий с неуправляемым кодом - механизмом обработки программных и аппаратных исключений в ОС Windows (Windows Structured Exception Handling, SEH) - и выполнения цепочки обработчиков в SEH;

  • исключения изменяют направление потока выполнения и потока данных, вызывая ошибки чтения страниц памяти и промахи кеша.

Чтобы выяснить, оказывают ли исключения отрицательное влияние на производительность, можно воспользоваться счетчиками производительности из категории .NET CLR Exceptions (Исключений CLR .NET). В частности, счетчик # of Exceps Thrown/sec (Число исключений/сек) может помочь точно определить проблемы с производительностью, когда возбуждаются тысячи исключений в секунду.

Механизм рефлексии

Механизм рефлексии (Reflection) заработал плохую репутацию «убийцы производительности» во многих сложных приложениях. Отчасти такая репутация вполне заслуженна: в механизме рефлексии имеются чрезвычайно дорогостоящие операции, такие как вызов функции по имени с использованием Type.InvokeMember или создание экземпляра объекта вызовом Activator.CreateInstance с заданными параметрами.

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

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

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

Пройди тесты