Оптимизируй это. Часть 2

 ▎Долой проверки

  Новый день и новый кусочек кода, который мы будем разгонять до околосветовых скоростей. Пристегните ремни. Поехали!

            int k = 0;
            for (var i = 0; i < 1000000000; i++)
            {
                k = i + 1;
            }

  Перед вами одна бинарная операция сложения, результат которой помещается в переменную k. Неужели тут тоже можно что-то ускорить? Это было бы здорово. Такие операции встречаются сплошь и рядом не только в криптографических алгоритмах, но и в повседневном коде. Неужели есть «серебряная пуля», позволяющая ускорить любой код?

  На самом деле, нет. Этот код выполняется для вас настолько быстро, насколько может. Зачем же я показал его здесь? Всё дело в блоке unchecked. Очень часто можно встретить код наподобие приведённого ниже.

            unchecked
            {
                for (var i = 0; i < 1000000000; i++)
                {
                    k = i + 1;
                }
            }

  Согласно MSDN, блок unchecked используется для отключения проверки на переполнение типа. Это должно дать ускорение, верно? Рассмотрим операцию сложения подробнее. В обоих приведённых выше случаях наша строка кода будет выглядеть так:

  Независимо от наличия секции unchecked сложение выполняется максимально быстрым образом.

  Если вы прочитали статью о секции unchecked в документации до конца, то вы заметили, что все операции по умолчанию не проверяются на переполнение. Если же вы включите проверку, то вы замедлите код приблизительно в 4 раза.

            checked
            {
                for (var i = 0; i < 1000000000; i++)
                {
                    k = i + 1;
                }
            }

  Хорошо, мы разобрались. Отключение переполнения типа не добавляет скорости нашему коду. Тогда о чём этот раздел? Как раз об этом. Не используйте секцию unchecked для ускорения - это бессмысленно! Кто-нибудь обязательно увидит её в вашем коде и использует в своём, и так далее. Ещё хуже, если кто-нибудь «сообразительный», увидев её, догадается о существовании секции checked и включит проверку там, где посчитает наличие unchecked неоправданным. Отсюда новый совет оптимизатору.

Если вы не знаете, как эта штука работает, не используйте её

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

 ▎Подготовьтесь к работе

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

            for (int i = 0; i < 10000000; i++) //main loop
            {
                for (int j = 0; j < 256; j++)
                {
                    var res = arr[arr[j]] % arr[j];
                }
            }

  У нас есть массив arr, заполненный случайными числами от 1 до 255. Мы много раз в случайном порядке вычисляем остаток от деления разных элементов массива. Почему операцию «остаток от деления» я взял в качестве примера? Потому, что создатели криптографических алгоритмов обожают её, и эта операция ужасно медленная.

  . Наверное, это единственная бинарная операция, которая не позволяет однозначно вычислить все операнды, даже если мы знаем один из операндов и результат. За что так и полюбилась криптографам - ведь они такие скрытные. В работе RC4 эта операция встречается 4 раза. Как можно ускорить этот код? Почему бы нам не вычислить результат заранее?

            var moduloTable = new byte[256, 256];
            for (int i = 0; i < 256; i++)
            {
                for (int j = 1; j < 256; j++)
                {
                    moduloTable[i, j] = (byte)(i % j);
                }
            }
            unsafe
            {
                for (int i = 0; i < 10000000; i++) //main loop
                {
                    fixed (byte* modulo = moduloTable)
                    {
                        for (int j = 1; j < 256; j++)
                        {
                            var res = *(modulo + (arr[arr[j]] * 256) + arr[j]);
                        }
                    }
                }
            }

  Кстати, обратите внимание, как осуществляется прямой доступ к элементам двумерного массива.

  Сделаем замеры и сравним скорость работы кода. До оптимизации - 37,8 секунды и 34 секунды после. Несмотря на то, что мы предварительно вычисляем 65536 остатков от деления и добавляем в наш главный цикл 2 операции сложения, одну операцию умножения и одну операцию доступа к памяти, наш оптимизированный код выполняется на 10% быстрее! Хм, кажется теперь у нас есть ещё одно правило оптимизатора.

Вычисляйте заранее и используйте повторно всё, что возможно

  Вы можете сказать, что мой метод не подходит, если в качестве операндов используются числа, большие чем 255. Да, но обычно в криптографических алгоритмах работа ведётся с отдельными байтами и их комбинациями. К примеру, для оптимизации работы RC4, которую я применил, оказалось достаточно вычислить заранее всего 765*255 значений этой операции.

 ▎Параллелизм - наше всё

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

  Microsoft прилагает много усилий, чтобы обеспечить разработчиков всем необходимым для написание параллельного кода. Это не только сами возможности распараллеливания, но и шикарный отладчик, встроенный прямо в среду разработки (IDE visual studio) и позволяющий отлаживать отдельные потоки.

  Итак, возможности. Во-первых, рекомендую изучить пространство имён System.Threading. Для тех, кто «сидит» на .Net версии 2.0 Thread, наверное, единственный способ распараллелить свой код. Те, кто использует последние технологии, будут приятно удивлены, прочитав вот эту статью и изучив System.Threading.Tasks. Задачи (tasks) появились в .Net начиная с версии 4.0.

  Кстати, у нас было 2 реализации алгоритма атаки. Первый алгоритм с использованием Thread, а второй с использованием Task. И задачи показали на 10% лучшую производительность. Не знаю, с чем это связано: возможно, это просто различия в реализации именно нашего алгоритма, но факт остаётся фактом.

  И, в заключение, ещё один совет.

Старайтесь использовать все доступные ресурсы

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

 ▎Статика! Статика! Статика!

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

  Когда мы говорим о криптографических алгоритмах, то почти всегда имеем несколько массивов фиксированной длинны, которые хотим использовать повторно. RC4 не исключение. Почему не определить статические поля для таких массивов? Тогда сборщик мусора не будет беспокоиться об этих массивах на протяжении всего срока жизни программы. Для моей задачи это особенно актуально, т.к. на каждый пароль создаётся новый экземпляр класса алгоритма RC4, а это десятки тысяч экземпляров в секунду. Прирост в производительности должен быть существенным, и он действительно такой.

  Но что же делать с многопоточностью? Как мы знаем, статические переменные являются общими для всех потоков внутри процесса приложения. Мы можем пометить статическую переменную атрибутом ThreadStatic, и проблема будет решена!

  Хочу предостеречь вас от бездумного использования этого атрибута. Дело в том, что время доступа к полям зависит от того, как эти поля определены. Связано это с тем, что в случае с динамическими полями сначала нужно определить, к какому классу они принадлежат. Со статикой всё гораздо проще, пока мы не используем атрибут ThreadStatic.

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

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

  Если упорядочить все способы определения переменной по скорости доступа, мы получим следующую картину:

  •   •Локальная переменная – самый быстрый доступ.
  •   •Статическое поле – чуть медленнее.
  •   •Обычное поле – ещё немного медленнее.
  •   •Статическое поле с ThreadStatic – ужасно медленный доступ.

  В моём случае ускорение за счёт уменьшения циклов сборки мусора оказалось существенно больше замедления доступа к полю класса. В вашем случае всё может оказаться с точностью до наоборот. Будьте осторожны.

К каждой задаче по оптимизации подходите индивидуально

 ▎Подводя итоги

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

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

Паролей в минуту Вскрытых в тестовом наборе
До оптимизации 12 000 2%
После оптимизации 17 000 000 67%

  Неплохой прирост в производительности, не правда ли? Теперь на одной машине за 10 минут мы можем атаковать xls файл, используя 170 миллионов паролей. Конечно, многое зависит от сложности пароля, но статистика показывает, что словарный запас человека редко составляет более 30 тыс. слов, и уж совсем немногие пользуются генераторами паролей. Отсюда совет:

Никогда не выдумывайте пароль сами. Не используйте простые правила для генерации пароля. Используйте специальные генераторы паролей