23 March

Оптимизации в JIT-компиляторе для .NET 5

.NETCompilersC#
Некоторое время назад я начал удивительное путешествие в мир JIT-компилятора с целью найти места, куда можно засунуть свои руки и что-нибудь ускорить, т.к. по ходу основной работы накопился небольшой багаж знаний в LLVM и его оптимизаций. В этой статье я хотел бы поделиться списком моих улучшений в JIT (в .NET он называется RyuJIT в честь какого-то дракона или аниме — я не разобрался), большая часть которых уже попала в master и будет доступна в .NET (Core) 5. Мои оптимизации затрагивают разные фазы JIT, которые очень схематично можно показать следующим образом:



Как видно из схемы, JIT — это отдельный модуль, связанный с рантаймом узким Jit-Interface, по которому JIT консультируется по некоторым вещам, например, можно ли скастить один класс к другому. Чем позже JIT компилирует метод в слой Tier1, тем больше информации может предоставить рантайм, например, что static readonly поля можно заменить константой, т.к. класс уже статически проинициализирован.

Итак, начнем по списку.

PR #1817: Оптимизации boxing/unboxing в pattern matching


Фаза: Importer
Многие новые фичи C# частенько грешат вставкой CIL-опкодов box/unbox. Это очень затратная операция, которая является по сути аллокацией нового объекта на куче, копированием значения из стека в него, а потом еще и нагружает GC в итоге. В JIT уже есть ряд оптимизаций для этого случая, но я нашел пропущенные в C# 8 pattern matching, например:

public static int Case1<T>(T o)
{
    if (o is int x)
        return x;
    return 0;
}

public static int Case2<T>(T o) => o is int n ? n : 42;

public static int Case3<T>(T o)
{
    return o switch
    {
        int n => n,
        string str => str.Length,
        _ => 0
    };
}

И посмотрим asm-кодген до моей оптимизации (например, для int специализации) для всех трех методов:



А теперь после моего улучшения:



Дело в том, что оптимизация нашла паттерны IL кода

box !!T
isinst Type1
unbox.any Type2

при импорте и обладая информацией о типах, смогла просто проигнорировать эти опкоды и не вставлять боксинг-анбоксинг. Кстати, эту же оптимизацию я реализовал так же и в Mono. Тут и далее ссылка на Pull-Request содержится в заголовке описания оптимизации.

PR #1157 typeof(T).IsValueType ⇨ true/false


Фаза: Importer
Тут я обучил JIT сразу заменять Type.IsValueType на константу если это возможно. Это минус вызов и возможность вырезать целые условия и ветки в дальнейшем, пример:

void Foo<T>()
{
    if (!typeof(T).IsValueType)
        Console.WriteLine("not a valuetype");
}

И посмотрим кодген для Foo<int> специализации до улучшения:



И после улучшения:



Тоже самое можно сделать и с другими свойствами Type если это необходимо.

PR #1157 typeof(T1).IsAssignableFrom(typeof(T2)) ⇨ true/false


Фаза: Importer
Практически тоже самое — теперь можно проверять на принадлежность к иерархии в генерик методах без страха, что это не оптимизируется, пример:

void Foo<T1, T2>()
{
    if (!typeof(T1).IsAssignableFrom(typeof(T2)))
        Console.WriteLine("T1 is not assignable from T2");
}

Точно так же заменится на константу true/false и условие может быть удалено целиком. В таких оптимизациях, конечно, не без корнер-кейсов, о которых надо всегда помнить: System.__Canon shared генерики, массивы, ко(нтр)вариантность, нуллаблы, COM-объекты и т.п.

PR #1378 "Hello".Length ⇨ 5


Фаза: Importer
Не смотря на то, что оптимизация максимально очевидная и простая, для реализации её в JIT-e пришлось хорошенько попотеть. Все дело в том, что JIT не знал о содержимом строки, он видел строковые литералы (GT_CNS_STR), но ничего не знал о конкретном содержимом строк. Пришлось помочь ему путем обращения в VM (расширить вышеупомянутый JIT-Interface), а сама оптимизация по сути — это несколько строк кода. Юзкейсов довольно много, помимо очевидных, таких как: str.IndexOf("foo") + "foo".Length до неочевидных, в которых задействован инлайнинг (напоминаю: Roslyn не занимается инлайнингом, поэтому эта оптимизация в нем была бы неэффективна, в прочем, как и все другие), пример:

bool Validate(string str) => str.Length > 0 && str.Length <= 100;

bool Test() => Validate("Hello");

Посмотрим на кодген для Test (Validate заинлайнился):



а теперь кодген после добавления оптимизации:



Т.е. заинлайнили метод, заменили переменные строковыми литералами, заменили .Length от литералов на реальные длины строк, зафолдили константы, удалили мертвый код. Кстати, так как теперь JIT может проверять содержимое строки, то открылись двери для других оптимизаций связанных со строковыми литералами. Сама оптимизация была упомянута в анонсе первого превью .NET 5.0: devblogs.microsoft.com/dotnet/announcing-net-5-0-preview-1 в разделе Code quality improvements in RyuJIT.

PR #1644: Оптимизации баунд чеков.


Фаза: Bounds Check Elimination
Для многих не станет секретом, что каждый раз когда вы обращаетесь в массив по индексу, JIT за вас вставляет проверку на то, что массив не выходит за рамки и выбрасывает исключение если это происходит — в случае ошибочной логики вы не смогли бы прочитать случайную память, получить какое-то значение и продолжить далее.

int Foo(int[] array, int index)
{
    // if ((uint) array.Length <= (uint) index)
    //     throw new IndexOutOfRangeException();
    return array[index];
}

Такая проверка полезна, но она может сильно повлиять на производительность: во-первых, добавляет операцию сравнения и делает ваш безбранчевый код бранчевым, во-вторых — добавляет в ваш метод код вызова исключения со всеми вытекающими. Однако, JIT способен во многих случаях убрать эти проверки если сам себе докажет, что индекс никогда не выйдет за пределы и так, или что уже есть какая-то другая проверка и еще одну добавлять уже не нужно — Bounds(Range) Check Elimination. Я нашел несколько случаев, в которых он не справляется и поправил их (и в дальнейшем планирую еще несколько улучшений этой фазы).

var item = array[index & mask];

Вот в этом коде, я подсказываю JIT что & mask по сути ограничивает индекс сверху на значение mask, т.е. если JIT-у известно значение mask и длина массива — можно не вставлять баунд чек. Тоже самое для операций %, (& x >> y). Пример использования этой оптимизации в aspnetcore.
Так же, если мы знаем что в нашем массиве, например, 256 элементов и более, то если наш неизвестный индексер имеет тип byte — тот как бы он не старался, он никогда не сможет выйти out of bounds. PR: github.com/dotnet/coreclr/pull/25912

PR #24584: x / 2 ⇨ x * 0.5


Фаза: Morph
C этого PR и началось моё удивительное погружение в мир JIT оптимизаций. Операция «деление» медленнее, чем операция «умножение» (а если для целых чисел так и вообще — на порядок). Работает для констант только равных степени двойки, пример:

static float DivideBy2(float x) => x / 2; // = x * 0.5; 

Кодген до оптимизации:



и после:



Если сравним эти две инструкции для Haswell то всё станет понятно:

vdivss (Latency: 10-20,  R.Throughput: 7-14)
vmulss (Latency:     5,  R.Throughput:  0.5)

Далее последуют оптимизации, которые еще в стадии code-review и не факт, что будут приняты.

PR #31978: Math.Pow(x, 2) ⇨ x * x


Фаза: Importer
Тут всё просто: вместо вызова pow(f) для довольно популярного случая, когда степень — константа 2 (ну и бесплатно еще для 1, -1, 0) можно развернуть в простое x * x. Можно разворачивать и любые другие степени, но для этого необходимо подождать реализации режима “быстрая математика” в .NET, при котором можно пренебречь спецификацией IEEE-754 в угоду производительности. Пример:

static float Pow2(float x) => MathF.Pow(x, 2);

Кодген до оптимизации:



и после:



PR #33024: x * 2 ⇨ x + x


Фаза: Lowering
Тоже довольно простая микро(нано) пипхол-оптимизация, позволяет выполнить умножение на 2 без загрузки константы в регистр.

static float MultiplyBy2(float x) => x * 2;

Кодген до оптимизации:



После:



В целом, инструкция mul(ss/sd/ps/pd) одинакова по latency и throughput как и add(ss/sd/ps/pd), но необходимость подгрузить константу «2» может слегка замедлить работу. Вот, в примере кодгена выше vaddss всё сделала в рамках одного регистра.

PR #32368: Оптимизация Array.Length / c (или % с)


Фаза: Morph
Так уж вышло, что поле Length у Array — знаковый тип, а деление и остаток на константу намного эффективнее делать от беззнакового типа (и не только на степень двойки), просто сравните этот кодген:



Мой PR просто напоминает JIT-у что Array.Length хоть и знаковый, но по сути, длина массива НИКОГДА (если вы не анархист) не может быть меньше нуля, а значит можно смотреть на нее как на беззнаковое число и применять некоторые оптимизации как для uint.

PR #32716: Оптимизация простых сравнений в branchless код


Фаза: Flow analysis
Это уже другой класс оптимизаций, который оперирует базовыми блоками вместо выражений в пределах одного. Тут JIT немного консервативен и имеет пространство для улучшений, например вставки cmove где возможно. Я начал с простой оптимизации для вот такого случая:

x = condition ? A : B;

если А и Б — константы и разница между ними равна единице, например condition ? 1 : 2 то мы, зная что операция сравнение сама по себе возращает 0 или 1, можем заменить jump на add. В терминах RyuJIT это выглядит примерно так:



Рекомендую посмотреть описание самого PR, надеюсь там всё понятно описано.

Не все оптимизации одинаково полезны


Оптимизации требуют довольно высокую плату:
* Увеличение = усложнение существующего кода для поддержки и чтения
* Потенциальные баги: тестировать компиляторные оптимизации безумно сложно и легко что-то упустить и получить какой-нибудь сегфолт у пользователей.
* Замедление компиляции
* Увеличение размера бинаря JIT

Как вы уже поняли, далеко не все идеи и прототипы оптимизаций принимают и необходимо доказывать, что они имеют право на жизнь. Один из принятых способов доказать это в .NET является запуск утилиты jit-utils, которая совершит АОТ компиляцию некоторого набора библиотек (весь BCL и corelib) и сравнит ассемблерный код для всех методов до и после оптимизаций, вот как этот отчет выглядит для оптимизации "str".Length. Помимо отчета, есть еще определенный круг людей (таких как jkotas), которые одним взглядом могут оценить полезность и зарубить всё на корню с высоты своего опыта и понимания какие именно места в .NET могут быть бутылочным горлышком, а какие — нет. И еще: не судите оптимизации аргументом «так никто не пишет», «лучше бы просто показывали warning в Roslyn» — вы никогда не знаете, как будет выглядеть ваш код после того, как JIT заинлайнит всё, что возможно и зафолдит константы.
Tags:jit.net.net 5.0ryujitоптимизации
Hubs: .NET Compilers C#
+73
12k 77
Comments 81