можно ли сделать код еще более оптимизированным

Оптимизация кода

Какая бывает и зачем нужна.

Мы тут разбираемся в важных понятиях большой разработки:

Чтобы закрыть тему, поговорим об оптимизации.

Что такое оптимизация

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

Что пытаются улучшить:

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

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

Оптимизация скорости работы

Самая частая оптимизация кода — повышение скорости работы.

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

Примеры того, как можно добиться ускорения:

Оптимизация скорости загрузки

Это похоже на предыдущий пункт, но с одним отличием: чаще всего увеличивают видимую пользователю скорость загрузки программы, а не полноценную загрузку всего.

Этим приёмом часто пользуется компания Apple: они делают свои программы так, чтобы пользователь видел интерфейс практически сразу после запуска, но реально работать с программой можно лишь через 1–2 секунды. Дело в том, что на первое место ставится скорость отрисовки и загрузки интерфейса, а остальные модули программы загружаются на фоне, и на это тоже нужно время. Зато выглядит всё так, как будто программа запустилась моментально.

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

Оптимизация скорости ответа

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

При этом такие программы могут загружаться по 20–30 секунд или даже несколько минут. Никто не ждёт от них моментальной загрузки, а вот моментальная реакция на запросы — нужна.

Оптимизация для стабильности и отказоустойчивости

Если мы пишем код для больницы, в котором в реальном времени обрабатываем жизненные показатели всех пациентов, то нам важно такое:

Короче: программу должно быть очень сложно сломать.

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

Оптимизация для уменьшения объёма кода

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

Или другая ситуация: у нас есть код программы для одной версии умных часов, а нам нужно эти же функции перенести на другие часы, где контроллер попроще и памяти поменьше.

В этих случаях разработчики идут на разные хитрости: применяют упаковку кода, чтобы он распаковался в оперативной памяти в момент выполнения; или упрощают код, делая его менее стабильным или отказоустойчивым, зато более компактным.

Ещё могут использовать недокументированные возможности железа, чтобы расширить место для хранения программы или её компонентов. Например, в старом телефоне могут положить часть модулей программы в область памяти, где хранятся мелодии звонков. Мелодии занимают мало места, и часть остаётся свободной — в этом случае модуль маскируется под мелодию и отправляется туда.

Что дальше

Теперь мы полностью готовы работать над своим старым кодом: поддерживать легаси, делать рефакторинг и оптимизировать разные функции. Сделаем всё по очереди, но уже в другой раз.

Источник

Оптимизация кода сайта

Содержание статьи:

Определение скорости загрузки сайта

Количество посетителей на сайте напрямую связано со скоростью загрузки интернет-ресурса. Вы не будете ждать, пока загрузятся картинки или другая информация. Проще уйти к конкурентам. Представьте, что необходимо приобрести несколько товаров на сайте, а каждую страницу приходится ждать по минуте. Когда-то через модемы страницы появлялись в браузере спустя несколько минут. Эти времена прошли. Еще одним фактором в пользу ускорения загрузки страниц ресурса является поисковая выдача. Более быстрый сайт занимает более высокие строчки в Google.

Проверить скорость загрузки вашего интернет-портала можно на специальных сервисах:

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

Для оптимизации HTML-кода необходимо

Оптимизация CSS

CSS (Cascading Style Sheets — каскадные таблицы стилей) отвечает за визуальное отображение документа в браузере. Задает шрифты и цвета. Файл CSS весит менее 100 кб, однако не стоит недооценивать его оптимизацию.

Ухудшают SEO-оптимизацию такие элементы дизайна как фреймы и флеш. Они украшают ресурс, однако непрактичны.

Технология Adobe Flash делает интернет-ресурс более привлекательным. Появляются анимация, голосовое сопровождение. Однако минусов у нее больше. Сайт долго грузится из-за сложностей с кешем. Информация заполняет большое количество оперативной памяти ПК. Для отображения требуется установка Adobe Flash player. Google и Yandex индексируют только главную страницу подобного сайта. Для продвижения в поисковиках придется сделать еще один сайт на HTML. Также флеш-эффекты не поддерживаются на гаджетах от Apple.

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

Для ручной оптимизации CSS требуется

Оптимизация JavaScript

Как оптимизировать картинки на сайте

Вес изображений заметно влияет на скорость загрузки интернет-ресурса. Оптимизировать картинки можно

Сервисы для автоматической HTML и CSS оптимизации

Оптимальным вариантом является Clean CSS.com. Этот сервис позволяет контролировать процесс сжатия. С его помощью вы можете независимо друг от друга оптимизировать картинки, шрифты, удалить пробелы. Также предусмотрена возможность выбрать среднюю скорость сжатия. Это существенный плюс, поскольку при высокой и низкой скоростях код становится нечитаемым для дальнейшей корректировки. Результатом сжатия в CleanCSS.com будет текстовый файл. Он покажет произошедшие изменения, в том числе в синтаксических конструкциях контента.

Существуют также сервисы CSS Optimizer, CY-PR.com, CSS Compressor и плагин Autoptimize. Каждый из них одновременно со сжатием может удалить нужные элементы кода и нарушить работу сайта.

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

Автоматически проверить результат оптимизации позволяют сервисы:

Окончательную проверку ресурса на наличие ошибок стоит провести с помощью валидатора validator.w3c.org.

Продвигаешь свои товары и услуги в интернете? У нас для тебя еще больше инструментов, лайфхаков и вдохновения на Яндекс.Дзен.Подписывайся!

Источник

Оптимизация кода: процессор

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

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

На написание этой статьи меня вдохновила пятая глава из книги Computer Systems: A Programmer’s Perspective. Все программы протестированы на машине с процессором Pentium 2117U, производительность на вашей машине может быть другая. В другой статье из этой серии, «Оптимизация кода: память», мы рассматриваем техники оптимизации для лучшего использования кэша.

Блокировщики оптимизации

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

Функция twiddle2 выглядит более эффективной, она выполняет всего три запроса к памяти (прочитать *xp, прочитать *yp, записать *xp), в то время, как twiddle1 выполняет шесть запросов (четыре чтения и две записи). Можно ожидать, что эти две функции имеют одинаковое поведение. Однако представьте, что xp и yp указывают на одну и ту же ячейку памяти. Тогда twiddle1 увеличит *xp в четыре раза, а twiddle2 — в три раза. Эти функции имеют разное поведение в некотором случае. По этой причине компилятор не посмеет трансформировать менее эффективную функцию в более эффективную.

Другой блокировщик оптимизации — вызов функций. Вообще, вызовы функций влекут накладные расходы, и нам нужно стараться их избегать. Рассмотрим пример:

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

В этом члучае func1 и func2 вернут разные результаты. Компилятору тяжело определить, имеет вызов функции побочные эффекты или нет. Когда он не может этого сделать, он рассчитывает на худшее и не выполняет оптимизацию.

Демонстрационная программа

Обычно медленные программы выполняют вычисления над большими массивами данных. Разумно будет оценивать эффективность таких программ в среднем количестве тактов, которые процессор тратит на обработку одного элемента массива. Введём метрику CPE (cycles per element). Если мы говорим, что программа имеет производительность CPE 2.5, значит она в среднем тратит 2.5 такта процессора на обработку одного элемента.

Мы представим простую программу, на примере которой продемонстрируем мощные приёмы оптимизации. Структура vec является вектором элементов типа float. Функция combine0 вычисляет результат перемножения всех элементов вектора. Эту функцию мы и будем оптимизировать. Размер массива сделаем 5000 и инициализируем его случайными числами.

Для измерения CPE можно использовать инструкцию rdtsc, это счётчик тактов с момента последнего сброса процессора. Нужно сравнить значения счётчика до и после выполнения программы. Предупреждаю, что это ненадёжный метод. Для большей надёжности можно просто замерять потраченное процессорное время. Следующая программа пусть будет шаблоном, который демонстрирует оба метода.

Избавляемся от неэффективностей цикла

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

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

Функция strlen обходит всю строку пока не встретит нулевой символ, и делает это в каждой итерации. Это катастрофически замедляет программу. Для больших строк цикл будет выполняться в тысячи раз медленнее, чем более эффективный. В идеале компилятор должен распознать, что вызов strlen всегда возвращает то же самое значение, и вынести его за пределы цикла. Но для этого нужно глубоко проанализировать тело цикла и определить, что хотя программа и изменяет символы в строке, никакой символ она не превращает в нулевой. Это за пределами возможностей современных компиляторов.

Избавляемся от лишних обращений к памяти

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

Подсчитаем сколько раз мы обращаемся к памяти в каждой итерации. Мы читаем элемент из массива, читаем dest, складываем эти значения и записываем результат в dest. Всего три обращения к памяти. Нам не нужно каждый раз читать и писать в dest после обработки очередного элемента. Мы введём временную переменную-аккумулятор, в которой будем хранить результат, и только в самом конце произведём запись в dest. Саму переменную-аккумулятор компилятор разместит в регистре, поэтому мы избавимся от ненужных обращений к памяти.

Теперь мы выполняем только одно обращение к памяти в каждой итерации. Производительность улучшается с CPE 11.05 до CPE 5.02. Если вы ожидаете, что компилятор сам догадается и выполнит эту оптимизацию, то подумайте что будет если dest указывает на какой-либо элемент в векторе. В этом случае версии с аккумулятором и без вычислят разное значение. Компилятор не может знать чему будут равны указатели, поэтому готовится к наихудшему и не выполняет оптимизацию. Вызовы функций и указатели серьёзно блокируют оптимизирующие возможности компилятора.

Раскрутка цикла

Мы достигли CPE 5.02. Это не простое число, мой процессор тратит 5 тактов на выполнение умножения чисел с плавающей точкой. Можно сказать, что мы достигли определённой нижней границы.

Мой процессор тратит один такт на выполнение сложения чисел типа int. Интересно, если вместо перемножения значений типа float, я буду складывать значения типа int, добьюсь ли я производительности CPE 1.0? Я вношу необходимые изменения в свою программу. Запускаю и получаю всего CPE 1.58. Откуда такая неэффективность?

Всё дело в том, что при выполнении цикла, процессор выполняет не только инструкции вычисления, в которых мы заинтересованы, но также инструкции, обслуживающие цикл: инкрементирование счётчика, проверка условия, переход в начало цикла. То есть обслуживание цикла имеет свои накладные расходы, и процессор производит много ненужной работы. Если тело цикла маленькое, эти «пустые» вычисления занимают большую долю процессорного времени.

Техника раскрутки цикла заключается в том, что за одну итерацию обрабатываются не один, а несколько элементов. Мы как бы «раскручиваем» цикл, увеличивая длину его тела и уменьшая количество витков. Таким образом мы выполняем меньше итераций, за одну итерацию совершаем больше полезной работы, и накладные расходы составляют уже не такую большую долю. Давайте немного изменим функции, складывающую целые числа:

Теперь программа добавляет к аккумулятору два элемента за итерацию. Обратите внимание, что последний элемент может быть не обработан в цикле, поэтому его нужно добавить к аккумулятору позже. CPE падает с 1.58 до 1.15. Обрабатывая четыре элемента за итерацию, я получаю CPE 1.03, что близко к тому значению, которое хотел получить.

Введение в работу процессора

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

Процессор разбит на части, которые выполняют разные типы задач, мы их называем функциональными блоками. Каждый блок выполняет определённый ряд задач: чтение из памяти, запись в память, сложение целых чисел, умножение чисел с плавающей точкой и т. д. Мой процессор имеет два блока, которые выполняют сложение целых чисел. Это значит, что он может параллельно выполнять два сложения.

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

Считывание инструкций наперёд называется предвыборкой. Если во время предвыборки процессор встречает ветвление (к примеру, конструкция if-else), он пытается угадать, какая ветвь будет взята и считывает инструкции оттуда. Если позже он понимает, что была взята неправильная ветвь, он сбрасывает произведённые вычисления, восстанавливает предыдущее состояние и идёт по другой ветви. Такая ошибка стоит процессору нескольких потерянных тактов. Для многих процессоров это примерно 20 тактов.

Конвейер

Мой процессор имеет один функциональный блок, выполняющий умножения чисел с плавающей точкой, и на одно умножение он тратит пять тактов. И казалось бы, если нам нужно выполнить N умножений, нам придётся потратить 5*N тактов. Но это не так, благодаря такому устройству как конвейер.

В американских фильмах вы наверняка видели как клиент в столовой проходит с подносом нескольких поваров, и каждый ковшом накладывает ему что-то своё. Это и есть конвейер. Представим столовую с пятью поварами, и обслужиться у одного из них занимает один такт. Они могли бы обслуживать клиентов так: сначала один клиент проходит всех поваров, потом второй, потом третий и так далее. В этом случае каждые пять тактов от них отходил бы клиент с полным подносом. Но это неэффективно. Лучше если все клиенты выстроятся в очередь, и каждый такт эта очередь будет продвигаться к следующему повару. В этом случае каждый такт от поваров будет отходить клиент с полным подносом. Заметьте, что обслуживание одного клиента всё равно будет занимать пять тактов, но обслуживание N клиентов (если N велико) займёт примерно N тактов.

По принципу конвейера устроены функциональные блоки в процессоре. Они разделяют всю работу на несколько этапов, и на разных этапах могут одновременно обрабатываться разные инструкции. Несмотря на то, что выполнение одной инструкции может занимать несколько тактов, многие блоки могут принимать в конвейер новую инструкцию каждый такт. Такие блоки называются полностью конвейерными. Все операции, кроме деления, выполняются в полностью конвейерном режиме. Деление считается сложной операцией, занимает 3-30 тактов и вообще не имеет конвейера.

Зависимость данных и несколько аккумуляторов

Но если конвейер позволяет нам тратить один такт на операцию, почему тогда мы получили CPE 5.02, а не CPE 1.02? Всё дело в такой плохой вещи как зависимость данных. Вернёмся к примеру со столовой. Допустим, первый повар в столовой накладывает или рис или гречку, и по странному правилу, каждый клиент, пройдя всех поваров, решает что должен наложить первый повар следующему клиенту. Тогда мы не можем начать обслуживание следующего клиента пока текущий клиент не пройдёт всех поваров. Нам приходится ждать, потому что есть определённая зависимость. Также и в работе процессора. Мы говорим, что между данными есть зависимость, если для начала работы над одними данными нам нужны другие данные, и мы должны дождаться завершения работы над ними.

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

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

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

Как видите, мы поддерживаем два независимых аккумулятора, которые в конце перемножаются, чтобы дать окончательный результат. CPE падает до с 5.02 до 2.5. Давайте сделаем раскрутку с четырьмя аккумуляторами:

CPE падает до 1.28. При восьми аккумуляторах я получаю CPE 1.04, что практически равно тому, что можно выжать из моего процессора. При написании кода в таком стиле нужно не забывать обрабатывать оставшиеся несколько элементов.

Мой процессор имеет только один функциональный блок, который выполняет умножение чисел с плавающей точкой. Core i7 Haswell имеет два таких блока, на нём наше приложение может достичь CPE 0.5, но пришлось бы использовать больше аккумуляторов. Вообще, если операция занимает C тактов и её выполняют N блоков, необходимое количество аккумуляторов может быть C*N.

Ассоциативность

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

Если у нас есть последовательность целых чисел, то неважно в каком порядке мы их будем складывать или перемножать, мы всё равно получим один и тот же результат, даже если будет переполнение. Мы говорим, что операции сложения и умножения для целых чисел являются ассоциативными операциями. Сложение и умножение для чисел с плавающей точкой не являются ассоциативными. Допустим в последовательности чисел типа float есть очень маленькие числа и очень большие. Если мы сначала перемножим очень маленькие, то получим ноль. Умножая все остальные на ноль, мы в итоге получим ноль. Если же изначально очень маленькие мы будем умножать на очень большие, в итоге мы могли бы получить адекватный результат.

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

Векторизация

Мы ещё можем улучшить производительность. CPE 1.04, который мы достигли — не предел. Современные процессоры поддерживают специальные расширения, называемые SSE или AVX, которые позволяют работать над векторами данных. В процессоре есть специальные векторные регистры, называемые %ymm0—%ymm15, размером 16 или 32 байта. Текущие AVX регистры имеют размер 32 байта и могут содержать четыре 64-битных числа, или восемь 32-битных числа, не важно целых или с плавающей точкой. Можно считать из памяти в один такой регистр сразу 32 байта данных, считать 32 байта данных в другой регистр и выполнить арифметическую операцию сразу над четырьмя или восьмью числами параллельно.

Это железо находится в процессоре неиспользуемое, пока вы явно не задействуете его. GCC поддерживает расширение языка C, которое позволит вам это сделать. Можно, конечно, написать код на ассемблере, но тогда программа перестанет быть переносимой. Используя эти возможности процессора, можно дальше увеличить производительность программы в 4 или 8 раз, в зависимости от размера регистров. В нашем случае, мы могли бы понизить CPE до 0.25 или 0.12.

Итоги оптимизации

Мы начали с программы, которая имела производительность CPE 11.05. Потом мы избавились от лишних вызовов функций и запросов к памяти и улучшили производительность до CPE 5.02. Потом использовали раскрутку цикла с несколькими аккумуляторами. Так смогли избавиться от зависимости данных, смогли полностью загрузить конвейер и получили CPE 1.04. То есть мы увеличили скорость выполнения программы в 11 раз. Используя векторизацию, можно заставить программу выполняться в 44—88 раза быстрее по сравнению с первоначальной версией.

Вы можете возразить, что мы применяем все эти техники оптимизации и сравниваем производительность с первоначальной версией, которая была скомпилирована лишь с базовым уровнем оптимизации. И, возможно, нам не нужно знать все эти техники, потому что компилятор применит их за нас, если мы прикажем ему компилировать с высоким уровнем отпимизции. Хорошо, давайте скомпилируем первоначальную версию программы с высоким, третьим уровнем оптимизации и посмотрим на что способен компилятор. Я получаю производительность CPE 5.02. Это далеко от CPE 1.04, которое мы получили, вручную трансформируя код. Знание всех этих приёмов оптимизации позволило нам добиться пятикратного увеличения производительности. Мы можем использовать векторизацию, чтобы дальше увеличить производительность в 4-8 раз, компилятор за вас этого не сделает.

Проблемы и ограничения

Количество функциональных блоков, которые выполняют чтение и запись в память, может быть узким местом производительности. Заметим, что эти блоки полностью конвейерные и могут принимать новую инструкцию каждый такт. Мой процессор имеет один блок, выполняющий чтение данных из памяти в процессор. Если для обработки одного элемента, мне нужно будет получить из памяти два числа, я не смогу сделать лучше, чем CPE 2.0, потому что получение двух чисел займёт два такта. Core i7 Haswell имеет четыре блока, которые выполняют сложения целых чисел. Но если вам нужно сложить элементы целочисленного вектора, вы не сможете добиться CPE 0.25. Потому что этот процессор имеет только два блока, выполняющих чтение из памяти — это устанавливает нижнюю границу на CPE 0.5.

Значение каждого аккумулятора хранится в отдельном регистре. x86-64 процессор имеет 16 регистров для целых чисел и 16 YMM регистров для чисел с плавающей точкой. Если мы будем использовать слишком много аккумуляторов, для них может не хватить регистров. Придётся хранить значения некоторых из них в памяти, что ухудшит производительность. Если увеличить количество аккумуляторов в нашей программе с 8 до 20, производительность падает с CPE 1.04 до CPE 1.35.

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

Другие техники оптимизации: реассоциация

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

Этот цикл имеет производительность CPE 5.02. По правилам языка C, когда нет скобок, операции умножения выполняются слева направо. В данном случае, легко увидеть, что все операции умножения зависят от переменной acc. Процессор не может начать умножать в следующей итерации, пока не завершит все умножения в текущей. Расставим скобки по-другому:

Значение переменных x, y и z в одной итерации не зависят от их значений в любой другой. Поэтому, пока выполняется текущая итерация, процессор может заранее вычислять два последних умножения в следующих итерациях. Производительность улучшается до CPE 1.69.

Другие техники оптимизации: условная передача данных

Как уже было сказано, процессор выполняет предвыборку, то есть считывает инструкции наперед. Если ему встречается ветвление (команды ассемблера je, jg, jl и т. д. ), он пытается угадать по какой ветви пойдёт вычисление. Если он угадывает неправильно, то теряет несколько тактов. Это называется условная передача управления.

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

Идея заключается в том, чтобы уменьшить количество ветвлений в программе, сделав поток выполнения более прямым. Для этого некоторые передачи управления выгодно заменить на передачу данных. Обычно компилятор транслирует конструкции if-else, используя команды ассемблера je, jg, jl и т. д., но иногда может использовать команду cmov. Рассмотрим такую конструкцию if-else:

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

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

Иногда компилятор не выполняет эту оптимизацию, потому что считает, что это ухудшит производительность. Мы можем заставить его выполнить её если перепишем код в более функциональном стиле, как представлено в предыдущем примере. Рассмотрим реальную программу.

Обе функции делают одно и то же. Они параллельно обходят пары чисел из двух массивов, устанавливая в массив a наименьшее из них, а в массив b наибольшее. Только вторая функция использует хитрую технику: она вычисляет минимальное число, вычисляет максимальное число и записывает каждое из чисел в своё место. Условия в вычислении переменных min и max настолько простые, что компилятор использует для них условную передачу данных. Разница в производительности наибольшая, если выполнить компиляцию с третьим уровнем оптимизации: minmax1 — CPE 15.6, minmax2 — CPE 1.18 (в 13.2 раз быстрее).

Заключение

Современный процессор скрывает огромную вычислительную мощь. Но чтобы получить к ней доступ, нужно писать программы в определённом стиле. Решить какие трансформации и к какой части кода применить есть «чёрная магия» написания быстрого кода. Обычно анализ совмещают с экспериментом: пробуют разные подходы, делают измерения производительности, исследуют код ассемблера для обнаружения узких мест.

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

Мы предложили базовую стратегию оптимизации кода:

Источник