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

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

  После исследования этой области было принято решение «вскрывать» Excel при помощи атаки со словарём. Со стороны заказчика был предоставлен человек, который проводил тестирование готового решения и принимал непосредственное участие в разработке. В качестве языка был выбран C# как основной в проектах заказчика.

  В первый день нами была написана программа, которая могла атаковать .xls файл двенадцатью тысячами паролей за одну минуту. Это давало нам возможность проверить 120 000 паролей за отпущенные 10 минут и позволяло открывать приблизительно 2% файлов из тестового набора. Никто и не рассчитывал на 100% за отпущенное время, но двухпроцентная вероятность открыть файл - это довольно скромный результат. Очевидно, что повысить вероятность успешной атаки можно было путем увеличения словаря, но из-за жёсткого лимита времени это означало, что нужно ускорить код и перебирать пароли быстрее.

  За время работы над этой задачей я узнал очень много про оптимизацию кода на С#, и в этой статье постараюсь поделиться с вами некоторыми знаниями. Я составил статью таким образом, чтобы она была понятна самому неподготовленному читателю. Поэтому вы не встретите подробного описания механизма защиты .xls файлов или кода из настоящего проекта. Все примеры будут максимально простыми для чтения и осмысления. В конце статьи подведём итоги.

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

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

  Ну что ж, все предварительные слова сказаны. Пусть оптимизация начнётся!

  ▎Ох уж эти циклы

  Для разминки начнём с простого примера.

            for (var i = 0; i < 100000000; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    //делать что-нибудь...
                }
            }

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

  • var j – определяем временную переменную один раз за цикл.
  • j < N – проверяем условие N раз за цикл.
  • j++ эквивалентно j=j+1 – увеличиваем значение счётчика на единицу и присваиваем значение счётчику, делается N раз за цикл.

  Итого (N+2N)+1 = 3N+1 операций. В нашем случае N=10, т.е. за цикл выполняется 31 операция. За всю программу будет выполнено 3.1 миллиарда операций. Было бы неплохо избавиться от них, не правда ли? Но как это сделать? Каждая операция необходима. Мы просто уберём весь цикл.

            for (var i = 0; i < 100000000; i++)
            {
                // делать что-нибудь.. 1
                // делать что-нибудь.. 2
                // ..
                // делать что-нибудь.. 10
            }

  Да, так просто. Цикл делает фиксированное количество повторений – значит, ничего не мешает нам выполнить код цикла N раз. Вот вам первое правило оптимизатора.

Никогда не выполняйте операции, в которых нет прямой необходимости для работы кода

  Если ваше N достаточно большое, а оптимизация действительно не помешает, то вы легко сможете написать код, который «развернёт» ваш цикл.

  ▎Ахиллесова пята

  Теперь давайте рассмотрим другой пример кода.

            byte[] buffer;
  	    for (var i = 0; i < 100000000; i++)
            {
                buffer = new byte[256];

                for (int j = 0; j < buffer.Length; j++)
                {
                    // делать что-нибудь ещё..
                }
            }

  Я предупреждал, что примеры будут простые, но поверьте, такие куски кода мы встречаем постоянно, когда речь заходит о криптографии. К примеру, в инициализации алгоритма шифрования RC4. Инициализация проводится по алгоритму ключевого расписания (Key-Scheduling Algorithm), похожий код там можно встретить целых 2 раза. На моём домашнем компьютере этот код выполняется за 73 секунды. Что бы вы предложили оптимизировать тут?

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

  Я предлагаю вынести инициализацию массива buffer за пределы основного цикла.

	    buffer = new byte[256];
            for (var i = 0; i < 100000000; i++)
            {
                for (int j = 0; j < buffer.Length; j++)
                {
                    //делать что-нибудь ешё..
                }
            }

  Давайте посчитаем, что нам это даст. Этот участок кода занимал 0,078% всего времени. Код исполнялся 73 секунды. Соответственно, избавившись от инициализации массива, мы должны получить прирост производительности приблизительно на 0,5 секунды (0,6%). Неплохо, но и не впечатляет. Память в C# выделяется действительно быстро. Однако, если мы проведём замер, то убедимся, что теперь код выполняется на 4 секунды (5,4%) быстрее. Не похоже на погрешность в вычислениях. Вот мы и подошли вплотную к самому большому благу и проклятию всех управляемых языков программирования. Речь идёт о сборщике мусора.

  Сборщик мусора – это гениальное изобретение! Но его следует иметь в виду, если вы пишете высокопроизводительный код. Внутри цикла мы выделяем память под массив buffer огромное количество раз. Чем провоцируем сборщик мусора прибраться за нами. Он исправно выполняет свою работу, забирая у нашего приложения ценнейшее процессорное время. Отсюда ещё одно правило оптимизатора:

Не создавайте новый экземпляр объекта, если в этом нет крайней необходимости

  Это правило легко соблюсти в нашем упрощённом случае. Но в реальной жизни мы стараемся писать легко поддерживаемый код. Последнее, что бы нам хотелось делать, это создавать большое количество общих переменных для разнообразных временных буферов и других объектов. Было бы неплохо иметь какой-нибудь вспомогательный класс, который поможет разобраться со всем этим. К счастью, ребята из Microsoft позаботились о нас и создали BufferManager. У нас нет необходимости изобретать велосипед. Пользоваться этим классом достаточно просто, я не вижу причин не использовать BufferManager при написании высокопроизводительного кода, который активно работает с памятью.

  ▎И снова массивы

  Давайте посмотрим на первый цикл в инициализации алгоритма шифрования RC4.

            S = new int[256];
            for (var i = 0; i < 1000000; i++)
            {
                for (int j = 0; j < buffer.Length; j++)
                {
                    S[j] = j;
                }
            }

  В этом примере заполняется массив из 256 элементов значениями от 0 до 255. Внешний цикл, как и раньше, имитирует частое выполнение этого кода. Мы атакуем .xls файл словарём паролей за фиксированное время; чем быстрее будет инициализироваться наш RC4 алгоритм, тем больше паролей мы проверим и тем чаще нам нужно будет этот алгоритм инициализировать. Итак, что мы можем сделать, кроме избавления от цикла? Взглянем на этот код через профилировщик.

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

  Так-то лучше. Большая часть (56%) времени уходит на обеспечение работы цикла. Думаю, вы уже знаете, что с этим делать. Однако, на простое присвоение значения элементу массива тоже уходит много времени (32%). Странно, одна операция присвоения значения элементу массива занимает не многим меньше времени, чем 3 операции, обеспечивающие работу цикла. Давайте посмотрим на реально выполняемый код.

  Как вы можете видеть, прежде чем совершить присваивание (я выделил его рамкой), выполняется какая-то проверка, на что явно указывает условный переход jae. Это не что иное, как проверка на выход за границы массива. А откуда, вы думали, берётся IndexOutOfRangeException? В обычной ситуации мы будем благодарны ребятам из Microsoft за то, что они позаботились о нас и не дают сделать опасных ошибок. Но в данном случае это «медвежья» услуга. Отсюда следует ещё одно правило оптимизатора.

Избегайте посредников везде, где это возможно

  Что ж, давайте попробуем «объяснить» компилятору, что мы знаем, что делаем, и следить за нами не нужно. Для этого мы попробуем записать значение в память напрямую. Это небезопасное действие, поэтому его потребуется разрешить в настройках проекта.

  Код, в свою очередь, нужно обернуть в секцию unsafe. При помощи секции fixed объявим указатель на наш массив. Теперь наш массив не будет перемещён сборщиком мусора в другое место. Далее обращение к элементу массива делается как в старом добром «С».

            var buffer = new int[256];
            for (var i = 0; i < 1000000; i++)
            {
                unsafe
                {
                    fixed (int* b = buffer)
                    {
                        for (int j = 0; j < buffer.Length; j++)
                        {
                            *(b + j) = j;
                        }
                    }
                }
            }

  Проверим дизассемблером, что же теперь происходит во время присвоения значения элементу массива.

  Выглядит отлично! Никаких лишних операций. Мы убрали много ненужного в нашем случае кода. Я сделал несколько замеров. До оптимизации код выполнялся за 19,5 секунд, после оптимизации это время сократилось до 10,3 секунд. Мы только что ускорили код в 2 раза (на 97%). Что и подтверждает профилировщик.

  Теперь полезный код выполняется половину (49,2%) всего времени. Это просто отличный результат!

  Перед тем, как пойти дальше, хочу напомнить, что ребята из Microsoft замедлили наш код не потому, что они «буки». В обычной жизни проверка на выход за границы массива действительно нужна, а работа с памятью напрямую ¬- небезопасна. Будьте осторожны. Запись в произвольную область памяти чего попало приведёт к непредсказуемым результатам. В худшем случае, приложение аварийно завершится без сообщения об ошибке.