Меня всегда очень интересовала оптимизация кода, даже когда в достижении наилучшего возможного времени выполнения на самом деле нет необходимости - я считаю, что попытки улучшить свой код и выжать как можно больше производительности могут быть одновременно забавным и полезным упражнением для обучения.
Недавно я переписал простой метод подсчета количества вхождений данного char в строку, и при этом у меня также была возможность поэкспериментировать с векторизованными инструкциями, это то, что я всегда считал увлекательным, но никогда не удосужился прочитать достаточно хорошо, чтобы использовать их в моем собственном коде.
Это сообщение в блоге представляет собой краткое введение в мир векторизованных инструкций на C #, и оно предназначено для разработчиков, которые никогда раньше не использовали их самостоятельно, как и я до сегодняшнего дня. Код, включенный в этот пост, ни в коем случае не является чем-то чрезвычайно продвинутым - я просто делюсь шагами, которые я лично предпринял для оптимизации этого конкретного алгоритма, и тем, что я узнал на этом пути.
Если вы никогда не тратили много времени на оптимизацию кода, я надеюсь, что этот пост еще больше заинтересует вас этой темой!
LINQ спешит на помощь
Первая реализация, которую каждый, вероятно, придумает при реализации аналогичного алгоритма (включая меня), использует API Count ‹T› (IEnumerable ‹T›, Func‹ T, bool ›) из System.Linq пространство имен. Этот API очень полезен, поскольку он обеспечивает простой способ решения этой проблемы, который чрезвычайно компактен для написания и при этом достаточно быстр. Нам просто нужно вызвать этот метод с помощью функции, которая проверяет каждый символ в нашей строке на тот, который мы ищем:
Это прекрасно работает и имеет большое преимущество в том, что практически невозможно ошибиться - как только этот метод будет реализован, вы, вероятно, никогда не обнаружите ошибку, исходящую от этого фрагмента кода, что, безусловно, является плюсом при работе с более крупными проектами. Но есть два основных недостатка:
- Распределение памяти: экземпляр Func‹ T, TResult ›, который мы используем в этом методе, генерирует закрытие, поскольку он захватывает наш параметр char c из метода вызывающего абонента. Если вы не знакомы с закрытием, вы можете прочитать о них в другом моем сообщении в блоге здесь. Достаточно сказать, что при каждом использовании этого метода среда выполнения выделяет объект, что вызывает ненужное использование памяти и давление сборщика мусора. Кроме того, мы также выделяем память для итератора строки, над которым работает метод LINQ.
- Медленное выполнение: используемый нами метод LINQ перебирает все символы через итератор, что намного медленнее, чем при использовании традиционного цикла for. В этом случае мы также вызываем наш делегат Func ‹T, TResult› для каждого отдельного символа, что опять же требует больших накладных расходов по сравнению с простым сравнением каждого символа напрямую.
Вернуться в прошлое
Давайте оставим удобную для пользователя страну функционального программирования и вернемся к классической, императивной реализации нашего алгоритма:
Во-первых, компилятор C # делает для нас интересную оптимизацию: тип string (вместе с массивами T []) обрабатывается особым образом при использовании в цикл foreach, и этот код преобразуется в классический цикл for. Это имеет то преимущество, что нам легче писать, поскольку нам не нужно вручную индексировать символы в строке, при этом производительность остается такой же, как у классического цикла. Кроме того, поскольку компилятор знает, что мы выполняем итерацию точно в пределах входной строки, он выдаст хорошо оптимизированный ассемблерный код без лишних проверок границ. Эта реализация намного быстрее, чем версия LINQ, и с ней проблема выделения памяти уже полностью решена.
Полный вперед
В предыдущей реализации было одно узкое место: каждая итерация цикла имеет одну условную ветвь, в частности, оператор if в строке 7. В высокопроизводительном коде количество ветвей всегда должно быть минимальным, а в высокопроизводительном коде - больше. -глубокое объяснение причины этого Я настоятельно рекомендую прочитать этот вопрос и ответ StackOverflow. Подводя итог, можно сказать, что ЦП будет пытаться предугадать результат выполнения инструкции перехода, и каждый раз, когда она ошибается, производительность будет относительно высокой. К счастью, в этом случае мы можем просто полностью удалить эту ветвь, используя то, как переменные bool хранятся в памяти во время выполнения.
С этого момента во фрагментах будут использоваться переменные и методы ref из Unsafe и MemoryMarshal класс. Я добавил подробные комментарии к каждой строке, чтобы упростить отслеживание, но если вы хотите углубиться в этот вопрос, не стесняйтесь читать мой предыдущий пост в блоге или официальные документы MS.
Это еще одно долгожданное улучшение, но мы еще не совсем там. Это примерно так быстро, как мы можем сделать, не углубляясь в более сложные техники. И теперь пора сделать это, добавив векторизацию.
Некоторые из вас могут правильно указать, что эту последнюю реализацию все еще можно улучшить, добавив разворачивание цикла. Это, безусловно, правда, но в целях данной публикации мы опустим эту часть.
Что вообще такое векторизованные инструкции?
Векторизованные инструкции, часто называемые инструкциями SIMD (одна инструкция с несколькими данными), представляют собой инструкции, которые используют специальные регистры в современных процессорах для ускорения определенных типов операций. Эти регистры могут содержать ряд значений рядом друг с другом, так что одна операция может выполняться над всеми из них одновременно.
Важно отметить, что размер регистра SIMD зависит от конкретного процессора и также влияет на количество значений, которые он может хранить в любое время. Чтобы быть точным, существуют разные инструкции SIMD, которые работают с разными регистрами SIMD, каждый из которых имеет определенный размер, но API C #, которые мы будем использовать, обеспечивают хорошую абстракцию над этим и предоставляют нам эти регистры как векторный тип, который может различаться по размеру. в зависимости от конкретного устройства, на котором мы выполняем наш код. Например, если в нашем распоряжении 128-битные регистры, мы сможем хранить либо 2 двойных значения (по 64 бита каждое), либо 4 int или значения с плавающей точкой (32 бита каждое), 8 ushort или коротких значений (по 16 бит) или 16 байтов или sbyte (по 8 бит). Регистры SIMD также могут быть недоступны вообще, поэтому мы всегда должны вручную проверять, так ли это, прежде чем выполнять наш векторизованный код.
Предположим, у нас есть два массива int [] и мы хотим записать в другой массив int [] того же размера сумму каждой пары значений. Вместо того, чтобы просматривать каждый элемент один за другим, мы могли бы загрузить порцию последовательных значений из каждого массива в два отдельных регистра SIMD, суммировать эти регистры в одной инструкции, а затем скопировать полученный регистр в нужное место в int [] массив, возвращаемый из метода. Нам нужен тип Vector ‹T›, который представляет собой регистр SIMD с элементами данного типа. Вот пример как традиционной реализации этого алгоритма с использованием цикла for, так и с использованием API Vector и Vector ‹T›:
Имея это доказательство концепции, мы можем теперь перейти к реализации нашего исходного метода Count, который использует возможности инструкций SIMD.
SIMD FTW
Возвращаясь к нашей исходной проблеме, есть небольшая сложность: тип Vector ‹T› не имеет API, который просто подсчитывает количество вхождений значения в регистр SIMD - нам придется реализовать это мы сами. К счастью, для этого требуется всего несколько битовых операций поверх базовой структуры SIMD, которую мы использовали в нашем предыдущем методе SumSimd:
Стоило ли?
Вот результаты при запуске 4 различных реализаций Count для образца текста (документ на 200 строк с кодом для 4 версий Count, описанных выше) и поиск '\ n'. Каждая реализация выполнялась в цикле с N итерациями каждый раз, чтобы минимизировать отклонения.
Мы видим, что реализация Count на базе SIMD в 110 раз быстрее, чем версия LINQ, и в 13 раз быстрее, чем foreach версия. Кроме того, мы видим, что версии foreach и SIMD вообще не используют память, тогда как версия LINQ выделяет 120 байт памяти для каждого отдельного вызова.
Стоят ли эти улучшения потраченного времени и усилий, полностью зависит от вас (тем более, что даже версия LINQ все еще работает всего за несколько микросекунд), но ускорение действительно заметно, по крайней мере, на бумаге, и все это был определенно забавным экспериментом!
Как и в предыдущем сообщении в блоге, я добавил ссылки на каждый API, который я использовал во всех фрагментах кода, если вы хотите узнать о них больше. Надеюсь, вам понравилось читать этот пост, дайте мне знать, если вы заметите какие-либо ошибки в любой из реализаций метода!
