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

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

гамму сайта?

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

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

Оптимизации JIT-компилятора

124

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

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

Если по каким-то причинам вам потребуется запретить выполнение оптимизаций JIT-компилятором, например, чтобы не сталкиваться при отладке со встроенными методами или хвостовыми вызовами (обсуждаются ниже), необязательно изменять код или использовать режим сборки Debug. Достаточно просто создать .ini-файл с тем же именем, что и выполняемый файл приложения (например, MyApp.ini) и добавить в него следующие три строки:

[.NET Framework Debugging Control]
GenerateTrackingInfo = 1
AllowOptimize = 0

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

Стандартные оптимизации

Практически все оптимизирующие компиляторы, даже самые простые, выполняют некоторые стандартные оптимизации. Например, JIT-компилятор способен сократить следующий код на C# до нескольких машинных инструкций x86:

// Оригинальный код C#
static int Add(int i, int j)
{
    return i + j;
}

static void Main()
{
    int i = 4;
    int j = 3 * i + 11;

    Console.WriteLine(Add(i, j));
}
; Оптимизированный код на языке ассемблера x86
call 682789a0                   ; System.Console.get_Out()
mov ecx,eax
mov edx,1Bh                     ; вызов Add(i,j) замещен результатом, 27 (0x1B)
mov eax,dword ptr [ecx]         ; далее следует стандартная последовательность
mov eax,dword ptr [eax + 38h]   ; виртуальный метод TextWriter.WriteLine
call dword ptr [eax + 14h]

Эта оптимизация выполняется не компилятором C#. Если заглянуть в сгенерированный им код на языке IL, в нем будут присутствовать и локальные переменные, и вызов метода Add. Любые оптимизации выполняются JIT-компилятором.

Эта оптимизация называется сверткой констант (constant folding), и существует еще множество подобных простых оптимизаций, таких как свертка общих подвыражений (common subexpression reduction), например в выражениях, таких как a + (b * a) - (a * b * c), значение a*b достаточно вычислить только один раз. JIT-компилятор способен выполнять такие стандартные оптимизации, но нередко справляется с этим значительно хуже, в сравнении с другими оптимизирующими компиляторами, такими как компилятор Microsoft Visual C++. Причина такого отставания в том, что JIT-компилятор имеет очень ограниченную среду выполнения и должен компилировать методы очень быстро, чтобы избежать значительных задержек при первом обращении к ним.

Встраивание методов

Эти оптимизации часто уменьшают объем кода и практически всегда уменьшают время выполнения, замещая последовательность инструкций вызова метода его телом. Виртуальные методы не встраиваются JIT-компилятором (даже при вызове конечного (sealed) метода у экземпляра производного типа); методы интерфейсов подвергаются частичному встраиванию; только статические и не виртуальные могут встраиваться всегда. Там где важна высокая производительность, например, в простых свойствах и методах часто используемых базовых классов, желательно избегать виртуальных методов и реализации интерфейсов.

Точные критерии, используемые JIT-компилятором для определения, какие методы могут встраиваться, недоступны. Однако экспериментальным путем нам удалось вскрыть некоторые из них:

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

  • методы, включающие обработку исключений, никогда не встраиваются;

  • рекурсивные методы никогда не встраиваются;

  • методы, имеющие параметры составных типов значений, локальные переменные или возвращаемые значения никогда не встраиваются;

  • методы, размеры тел которых превышают 32 байта на языке IL никогда не встраиваются (это ограничение можно преодолеть с помощью значения MethodImplOptions.AggressiveInlining атрибута MethodImpl.

В последних версиях среды выполнения CLR были убраны некоторые искусственные ограничения, препятствующие встраиванию методов.

Например, начиная с версии .NET 3.5 SP1, 32-разрядный JIT-компилятор способен встраивать методы, принимающие параметры некоторых составных типов значений, таких как структура Point2D, которая описывалась при обсуждении типов значений. В этой версии некоторые операции с составными типами значениями замещаются эквивалентными операциями с простыми типами, при определенных условиях (операции с экземпляром типа Point2D преобразуются в операции с двумя значениями типа int), что обеспечивает лучшую оптимизацию кода, выполняющего операции со структурами в целом. Например, взгляните на следующий простой код:

public struct Point2D
{
    public int X, Y;
}

// ...

private static void MethodThatTakesAPoint(Point2D pt) 
{
    pt.Y = pt.X ^ pt.Y;
    Console.WriteLine(pt.Y);
}

// ...

Point2D pt;
pt.X = 3;
pt.Y = 5;
MethodThatTakesAPoint(pt);

JIT-компилятор в среде выполнения CLR 4.5 весь этот фрагмент кода скомпилирует в функциональный эквивалент Console.WriteLine(6), где аргумент 6 является результатом выражения 3^5. JIT-компилятор способен выполнять встраивание и распространение констант пользовательских типов значений. В версии CLR 2.0 JIT-компилятор фактически вызывает метод без какой-либо видимой оптимизации:

; вызывающий код
mov eax,3
lea edx,[eax + 2]
push edx
push eax
call dword ptr ds:[1F3350h] (
    Program.MethodThatTakesAPoint(Point2D), mdToken: 06000003)

; код метода
push ebp
mov ebp,esp
mov eax,dword ptr [ebp + 8]
xor dword ptr [ebp + 0Ch],eax
call mscorlib_ni + 0x22d400 (715ed400) (
    System.Console.get_Out(), mdToken: 06000773)
mov ecx,eax
mov edx,dword ptr [ebp + 0Ch]
mov eax,dword ptr [ecx]
call dword ptr [eax + 0BCh]
pop ebp
ret 8

Несмотря на отсутствие возможности обеспечить принудительное встраивание методов, когда JIT-компилятор не считает это необходимым, у нас есть механизм, позволяющий запретить встраивание. Значение MethodImplOptions.NoInlining атрибута MethodTmpl запрещает встраивание метода, снабженного таким атрибутом - кстати говоря, это весьма полезная возможность для микрохронометража.

Отключение проверки границ

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

uint[] array = new uint[100];
array[4] = 0xBADC0FFE;
; Сгенерированный код на языке ассемблера x86
mov ecx,offset 67fa33aa        ; тип элемента массива
mov edx,64h                    ; размер массива
call 0036215c                  ; создать новый массив (CORINFO_HELP_NEWARR_1_VC)
cmp dword ptr [eax + 4],4      ; eax + 4 - длина массива, 4 - индекс

jbe NOT_IN_RANGE               ; если длина меньше или равна индексу, выполнить след. инструкцию
mov dword ptr [eax + 18h], 
    0BADC0FFEh                 ; смещение вычисляется на этапе 
                               ; JIT-компиляции (0x18 = 8 + 4*4)
							   
; Остальная часть программы - переход через метку NOT_IN_RANGE
NOT_IN_RANGE:
    call clr!JIT_RngChkFail    ; возбудить исключение

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

for (int k = 0; k < array.Length; ++k)
{
    array[k] = (uint)k;
}
; Сгенерированный код на языке ассемблера x86 (оптимизированный)
xor edx,edx                     ; edx = k = 0
mov eax,dword ptr [esi + 4]     ; esi = array, eax = array.Length
test eax,eax                    ; если массив пуст,
jle END_LOOP                    ; пропустить цикл

NEXT_ITERATION:
mov dword ptr [esi + edx*4 + 8],edx    ; array[k] = k

inc edx                         ; ++k
cmp eax,edx                     ; пока array.Length > k,
jg NEXT_ITERATION               ; перейти к следующей итерации
END_LOOP:

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

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

// Проверка границ отсутствует
for (int k = 0; k < array.Length - 1; ++k)
{
    array[k] = (uint)k;
}

// Проверка границ отсутствует
for (int k = 7; k < array.Length; ++k)
{
    array[k] = (uint)k;
}

// Проверка границ отсутствует.
// JIT-компилятор удалит -1 из проверки границ
// и начнет со второго элемента
for (int k = 0; k < array.Length - 1; ++k)
{
    array[k + 1] = (uint)k;
}

// Проверка границ выполняется
for (int k = 0; k < array.Length / 2; ++k)
{
    array[k * 2] = (uint)k;
}

// Проверка границ выполняется, 
// staticArray - это статическое поле вмещающего класса
uint[] staticArray = array;
for (int k = 0; k < staticArray.Length; ++k)
{
    staticArray[k] = (uint)k;
}

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

Хвостовые вызовы

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

public static int GCD(int a, int b)
{
    if (b == 0) 
	    return a;
    
	return GCD(b, a % b);
}

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

public static int GCD(int a, int b)
{
START:
    if (b == 0) 
        return a;

    int temp = a % b;
    a = b;
    b = temp;

    goto START;
}

Благодаря оптимизации из реализации исчезли рекурсивные вызовы - фактически рекурсивный алгоритм был преобразован в циклический. Эту оптимизацию можно выполнять вручную, когда это возможно, однако при определенных условиях JIT-компилятор способен применять ее автоматически. Ниже представлены две версии метода gcd - первая скомпилирована 32-разрядным JIT-компилятором из CLR 4.5, а вторая 64-разрядным JIT-компилятором из CLR 4.5:

; 32-разрядная версия, параметры в ECX и EDX
push ebp
mov ebp,esp
push esi
mov eax,ecx          ; EAX = a
mov ecx,edx          ; ECX = b
test ecx,ecx         ; if b == 0, returning a
jne PROCEED
pop esi
pop ebp
ret

PROCEED:
cdq
idiv eax,ecx         ; EAX = a / b, EDX = a % b
mov esi,edx
test esi,esi         ; if a % b == 0, returning b 
                     ; (базовый случай рекурсии)
jne PROCEED2
mov eax,ecx
jmp EXIT

PROCEED2:
mov eax,ecx
cdq
idiv eax,esi
mov ecx,esi          ; рекурсивный вызов в следующей строке

call dword ptr ds:[3447A0h] (Program.GCD(Int32, Int32), mdToken: 06000002)

EXIT:
pop esi
pop ebp
ret                  ; повторное использование возвращаемого
                     ; значения (в EAX) из рекурсивного вызова
					 
					 
; 64-разрядная версия, параметры в ECX и EDX
sub rsp,28h          ; создание кадра стека - производится только один раз!

START:
mov r8d,edx
test r8d,r8d         ; if b == 0, return a
jne PROCEED
mov eax,ecx
jmp EXIT
PROCEED:
cmp ecx,80000000h
jne PROCEED2:
cmp r8d,0FFFFFFFFh
je OVERFLOW          ; различные проверки на переполнение
xchg ax,ax           ; два байта NOP (0x66 0x90) для выравнивания

PROCEED2:
mov eax,ecx
cdq
idiv eax,r8d         ; EAX = a / b, EDX = a % b
mov ecx,r8d          ; повторно инициализировать параметры
mov r8d,edx          ; ...
jmp START            ; и перейти в начало (без вызова функции)
xchg ax,ax           ; два байта NOP (0x66 0x90) для выравнивания

EXIT:
add rsp,28h
ret

OVERFLOW:
call clr!JIT_Overflow
nop

Совершенно очевидно, что 64-разрядный JIT-компилятор использует хвостовую оптимизацию, чтобы избавиться от рекурсивных вызовов метода, а 32-разрядный - нет. Детальное исследование условий, при которых два JIT-компилятора применяют оптимизацию хвостовых вызовов, далеко выходит за рамки этой статьи, поэтому приведем лишь краткий список некоторых эвристик:

  • 64-разрядный JIT-компилятор более свободен в выборе оптимизации хвостовых вызовов и часто применяет ее, даже когда компилятор языка (например, компилятор C#) не предлагает использовать ее добавлением префикса tail в коде на языке IL:

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

    2. когда вызываемые методы возвращают значения, типы которых отличаются от типа значения, возвращаемого вызывающим методом;

    3. когда вызываемые методы имеют слишком много параметров, параметры имеют разное выравнивание или типы параметров/возвращаемого значения оказываются слишком большими типами значений (значительно ослаблено в CLR 4.0).

  • 32-разрядный JIT-компилятор менее склонен к этой оптимизации и выполняет ее, только при наличии префикса tail в коде на языке IL.

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

Более подробную информацию о префиксе tail, языка IL, используемого, чтобы подсказать JIT-компиляторам о возможности выполнить оптимизацию хвостового вызова, а также о критериях, используемых JIT-компилятором для оптимизации хвостовых вызовов, можно найти в Интернете:

  • префикс tail, который не используется компилятором C#, но часто используется компиляторами функциональных языков программирования (включая F#) описывается на сайте MSDN, в разделе с описанием класса System.Reflection.Emit;

  • список условий, когда JIT-компилятор применяет оптимизацию хвостовых вызовов (в версиях CLR ниже 4.0), можно найти в статье Дэвида Бромана (David Broman) "Tail call JIT conditions";

  • в CLR 4.0 произошли изменения в особенностях применения оптимизации хвостовых вызовов JIT-компилятором, которые подробно описаны в статье "Tail Call Improvements in .NET Framework 4".

Пройди тесты