Подождите, пожалуйста, выполняется поиск в заданном разделе

Методы оптимизации программ. Latency numbers every programmer should know

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

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

Для начала, немного прописных истин. Никто не занимается оптимизацией до тех пор, пока не придет заказчик (или коллега из отдела QA — не суть важно) и не скажет, что в таком-то месте программа работает слишком медленно. То есть, в первую очередь мы пишем программу с простым и понятным кодом, как следует тестируем ее и только потом, если понадобится, оптимизируем. Нет смысла оптимизировать программу, если (1) все работает и все довольны, (2) через полгода требования к программе поменяются и код придется переписать.

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

Также никто не бросается оптимизировать программу до тех пор, пока не станет понятно, насколько быстро она должна работать. Формулировка «таблица должна отрисовываться не дольше, чем за одну секунду» является правильной, а «таблица должна отрисовываться быстро» — нет. То есть, вы должны знать,в каком случае считать работу выполненной. Нельзя достичь цели, которая постоянно меняется. (Но если бизнес не хочет этого понимать, что ж… любой каприз за ваши деньги.)

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

Теперь перейдем непосредственно к методам. Я подозреваю, что некоторые из них вызовут у вас удивление, тем не менее…

Обновление ПО. Это может показаться невероятным, однако переход на последнюю версию какой-нибудь используемой в проекте библиотеки, СУБД, виртуальной машины Erlang‘а или ядра Linux может очень существенно увеличить скорость работы вашего приложения. Простое и, как правило, быстрое решение.

Настройка окружения. Используемая СУБД или операционная система могут быть настроены неправильно. Настройки по умолчанию MySQL и PostgreSQLпредполагают, что вы пытаетесь запустить СУБД на первопне. Один мой коллегарассказывал, как однажды в его практике приложение удалось существенно ускорить, просто попробовав различные параметры JVM. Этот метод даже проще, чем обновление ПО. Однако применять его, по понятным причинам, нужно после обновления. Или в случае, если обновление по каким-то причинам в обозримом будущем невозможно.

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

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

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

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

Распределение нагрузки. Если нагрузка на СУБД мала, можно воспользоваться триггерами или хранимками, разгрузив тем самым само приложение и уменьшив трафик. Или, наоборот, можно перенести всю логику в приложение, разгрузив СУБД. Для построения отчетов, создания резервных копий и выполнения других тяжелых операций над СУБД имеет смысл завести специальную реплику. СУБД можно настроить так, чтобы разные таблицы хранились на разных физических дисках. Можно отдать пользователю статическую страницу с JavaScriptи общаться с ним исключительно при помощи REST API. Пусть сам генерирует себе HTML. Статический контент можно держать на отдельном домене. Этим вы уменьшите трафик, так как на этот домен не будут отправляться кукисы. Незачемgzip’овать/шифровать данные в Apache или даже в самом приложении, еслис этой задачей намного лучше справится nginx. При помощи шардинга можно распределить нагрузку между несколькими репликами базы данных, процессами Erlang’а или экземплярами Memcached.

Ленивые вычисления. Грубо говоря, ленивые вычисления — это когда вместо конкретного значения возвращается анонимная функция, которая при вызове вычисляет это значение. В ряде языков программирования ленивые вычисления поддерживаются на уровне синтаксиса. Фокус в том, чтобы значение было вычислено непосредственно перед его использованием. Представьте себе ситуацию, когда мы отдаем данные в формате CSV и пользователь может задать фильтр, определяющий, какие столбцы должны быть переданы. В этом случае ленивые вычисления оказываются как нельзя кстати. Если окажется, что значение на самом деле не нужно, мы сэкономим время, которое было бы потрачено на его вычисление. Однако следует отметить, что ленивые вычисления приводят к увеличению объема используемой памяти и могут плохо работать с грязными функциями.

Отложенные расчеты. Зачем считать что-то прямо сейчас, если это можно сделать потом? При обработке HTTP-запроса мы можем моментально вернуть пользователю OK, а непосредственную работу выполнить в фоновом процессе. Если запрос очень важен, мы можем положить его в персистентную очередь задач, обрабатываемую по cron’у. Или группой непрерывно работающих процессов.В последнем случае мы даже имеем хорошие шансы получить горизонтальное масштабирование и, соответственно, реальное увеличение скорости, а не только видимое. Кроме того, отложенные задачи могут быть похожи. Например, им нужны одни и те же данные из БД. В этом случае при отложенной обработке N задач одной пачкой можно сходить в базу в N раз меньше.

Более подходящие алгоритмы и структуры данных. Quicksort быстрее сортировки пузырьком, а эллиптические кривые быстрее RSA. Если нужно проверить принадлежность элемента множеству, следует использоватьхэш-таблицы, а не односвязные списки. Правильные индексы и денормализация схемы базы данных могут существенно сократить время выполненияSQL-запросов. Если требуется синхронизировать некие данные, вместо полной их пересылки при каждом изменении лучше использовать схему снапшот + апдейты.

Аппроксимация. Это почти что случай более подходящего алгоритма, только с потерей точности. Вместо длинной арифметики часто можно обойтись обычными float’ами. При сборе статистики данные можно слать по UDP вместо TCP. Пусть небольшая часть пакетов не дойдет, а часть — придет дважды. При сборе статистики намного важнее изменение цифр, а не конкретные значения. Также, например, незачем строить график по всем точкам, если можно взять их подмножество и построить кривую Безье. Вместо дорогостоящего вычисления медианы часто можно посчитать среднее.

Переписывание на другой язык. Вполне может оказаться, что программу в существенной степени тормозит сборка мусора или, скажем, проверка типов на этапе выполнения. Переписывание небольших частей программы с Ruby на Scalaили с Erlang на OCaml может привести к ускорению этой программы. Если переписываемый кусок кода достаточно прост, можно с небольшим риском переписать его на Си или C++. Этот метод нужно использовать крайне осторожно. Он приводит к появлению зоопарка языков программирования, что усложняет поддержку проекта. Метод может не сработать, например, из-за накладных расходов на преобразование данных из одного представления в другое. Также он может быть опасен. Например, ошибка в NIF может привести к падению всей виртуальной машины Erlang’а, а не одного процесса.

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

Основы

Некоторые задачи часто могут быть выполнены более эффективно. Например, программа на языке Си, которая суммирует все целые числа от 1 до N:

int i, sum = 0;
for (i = 1; i <= N; i++)
  sum += i;

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

int sum = (N * (N+1)) / 2;

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

Компромиссы (tradeoff)

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

Различные области

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

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

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

Узкие места

Для оптимизации требуется найти узкое место (англ. bottleneck - бутылочное горлышко): критическую часть кода, которая является основным потребителем необходимого ресурса. Улучшение примерно 20 % кода иногда влечёт за собой изменение 80 % результатов (см. также принцип Парето). Для поиска узких мест используются специальные программы — профайлеры. Утечка ресурсов (памяти, дескрипторов и т. д.) также может привести к падению скорости выполнения программы, для их нахождения также применяются специальные программы (например, BoundsChecker (англ.)).

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

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

Простейшие приёмы оптимизации программ по затратам процессорного времени

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

Инициализация объектов данных

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

Программирование арифметических операций

В том случае, когда значительная часть времени работы программы отводится арифметическим вычислениям, немалые резервы повышения скорости работы программы таятся в правильном программировании арифметических (и логических) выражений. Важно, что различные арифметические операции значительно различаются по быстродействию. В большинстве архитектур, самыми быстрыми являются операции сложения и вычитания. Более медленным является умножение, затем идёт деление. Например, вычисление значения выражения Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu, где Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu — константа, для аргументов с плавающей точкой производится быстрее в виде Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu, где Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu — константа, вычисляемая на этапе компиляции программы (фактически медленная операция деления заменяется быстрой операцией умножения). Для целочисленного аргумента Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu вычисление выражения Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu быстрее произвести в виде Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu (операция умножения заменяется операцией сложения) или с использованием операции сдвига влево (что обеспечивает выигрыш не на всех процессорах). Подобные оптимизации называются понижением силы операций. Умножение целочисленных аргументов на константу на процессорах семейства x86 может быть эффективно выполнено с использованием ассемблерных команд LEA,SHL и ADD вместо использования команд MUL/IMUL:

; Исходный операнд в регистре EAX
ADD   EAX, EAX           ; умножение на 2

LEA   EAX, [EAX + 2*EAX] ; умножение на 3

SHL   EAX, 2             ; умножение на 4

LEA   EAX, [4*EAX]       ; другой вариант реализации умножения на 4

LEA   EAX, [EAX + 4*EAX] ; умножение на 5

LEA   EAX, [EAX + 2*EAX] ; умножение на 6
ADD   EAX, EAX

; и т.д.

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

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

Быстродействие также зависит и от типа операндов. Например, в языке Turbo Pascal, ввиду особенностей реализации целочисленной арифметики, операция сложения оказывается наиболее медленной для операндов типа Byte и ShortInt: несмотря на то, что переменные занимают один байт, арифметические операции для них двухбайтовые и при выполнении операций над этими типами производится обнуление старшего байта регистров и операнд копируется из памяти в младший байт регистра. Это и приводит к дополнительным затратам времени.

Программируя арифметические выражения, следует выбирать такую форму их записи, чтобы количество «медленных» операций было сведено к минимуму. Рассмотрим такой пример. Пусть необходимо вычислить многочлен 4-й степени:

Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu

При условии, что вычисление степени производится перемножением основания определенное число раз, нетрудно найти, что в этом выражении содержится 10 умножений («медленных» операций) и 4 сложения («быстрых» операций). Это же самое выражение можно записать в виде:

Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu

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

Циклы

Различается и время выполнения циклов разного типа. Время выполнения цикла со счетчиком и цикла с постусловием при всех прочих равных условиях , цикл с предусловием выполняется несколько дольше (примерно на 20-30 %).

При использовании вложенных циклов следует иметь в виду, что затраты процессорного времени на обработку такой конструкции могут зависеть от порядка следования вложенных циклов. Например, вложенный цикл со счетчиком на языке Turbo Pascal:

   for j := 1 to 100000 do
      for k := 1 to 1000 do a := 1;
   for j := 1 to 1000 do
      for k := 1 to 100000 do a := 1;

Цикл в левой колонке выполняется примерно на 10 % дольше, чем в правой.

На первый взгляд, и в первом, и во втором случае 100 000 000 раз выполняется оператор присваивания и затраты времени на это должны быть одинаковы в обоих случаях. Но это не так. Объясняется это тем, что инициализации цикла (обработка процессором его заголовка с целью определения начального и конечного значений счётчика, а также шага приращения счётчика) требует времени. В первом случае 1 раз инициализируется внешний цикл и 100 000 раз — внутренний, то есть всего выполняется 100 001 инициализация. Во втором случае таких инициализаций оказывается всего лишь 1001.

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

Если в циклах содержатся обращения к памяти (обычно при обработке массивов), для максимально эффективного использования кэша и механизма аппаратной предвыборки данных из памяти (англ. Hardware Prefetch) порядок обхода адресов памяти должен быть по возможности последовательным. Классическим примером подобной оптимизации является смена порядка следования вложенных циклов при выполнении умножения матриц.

При вычислении сумм часто используются циклы, содержащие одинаковые операции, относящиеся к каждому слагаемому. Это может быть, например, общий множитель (язык Turbo Pascal):

  sum := 0;
  for i := 1 to 1000 do
    sum := sum + a * x[i];
  sum := 0;
  for i := 1 to 1000 do
    sum := sum + x[i];
  sum := a * sum;

Вторая форма записи цикла оказывается более экономной.

Инвариантные фрагменты кода

Оптимизация инвариантных фрагментов кода тесно связана с проблемой оптимального программирования циклов. Внутри цикла могут встречаться выражения, фрагменты которых никак не зависят от управляющей переменной цикла. Их называют инвариантными фрагментами кода. Современные компиляторы часто определяют наличие таких фрагментов и выполняют их автоматическую оптимизацию. Такое возможно не всегда, и иногда производительность программы зависит целиком от того, как запрограммирован цикл. В качестве примера рассмотрим следующий фрагмент программы (язык Turbo Pascal):

   for i := 1 to n do
   begin
   ...
       for k := 1 to p do
             for m := 1 to q do
             begin
                   a[k, m] := Sqrt(x * k * m - i) + Abs(u * i - x * m + k);
                   b[k, m] := Sin(x * k * i) + Abs(u * i * m + k);
             end;
   ...
   am := 0;
   bm := 0;
   for k := 1 to p do
             for m := 1 to q do
             begin
                   am := am + a[k, m] / c[k];
                   bm := bm + b[k, m] / c[k];
             end;
   end;

Здесь инвариантными фрагментами кода являются слагаемое Sin(x * k * i) в первом цикле по переменной m и операция деления на элемент массива c[k] во втором цикле по m. Значения синуса и элемента массива не изменяются в цикле по переменной m, следовательно, в первом случае можно вычислить значение синуса и присвоить его вспомогательной переменной, которая будет использоваться в выражении, находящемся внутри цикла. Во втором случае можно выполнить деление после завершения цикла по m. Таким образом, можно существенно сократить количество трудоёмких арифметических операций.

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

  • C,
  • C++,
  • Высокая производительность,
  • Компиляторы,
  • Программирование микроконтроллеров

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

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

Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu


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

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

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

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

Память тоже имеет значение


Рассмотрим две функции, которые суммируют элементы матрицы. Они практически одинаковы, только первая функция обходит элементы матрицы построчно, а вторая — по столбцам.

int matrixsum1(int size, int M[][size])
{
    int sum = 0;

    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            sum += M[i][j];    // обходим построчно
        }
    }
    return sum;
}

int matrixsum2(int size, int M[][size])
{
    int sum = 0;

    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            sum += M[j][i];    // обходим по столбцам
        }
    }
    return sum;
}



Обе функции выполняют одно и то же количество инструкций процессора. Но на машине с Core i7 Haswell первая функция выполняется в 25 раз быстрее для больших матриц. Этот пример хорошо демонстрирует, что память тоже имеет значение. Если вы будете оценивать эффективность программ только в терминах количества выполняемых инструкций, вы можете писать очень медленные программы.

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

Иерархия памяти


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

На вершине иерархии находятся регистры процессора. Доступ к ним занимает 0 тактов, но их всего несколько штук. Далее идёт несколько килобайт кэш-памяти первого уровня, доступ к которой занимает примерно 4 такта. Потом идёт пара сотен килобайт более медленной кэш-памяти второго уровня. Потом несколько мегабайт кэш-памяти третьего уровня. Она гораздо медленней, но всё равно быстрее оперативной памяти. Далее расположена относительно медленная оперативная память.

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

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

Современная система имеет примерно такие характеристики:

Тип кэша Время доступа (тактов) Размер кэша
Регистры 0 десятки штук
L1 кэш 4 32 KB
L2 кэш 10 256 KB
L3 кэш 50 8 MB
Оперативная память 200 8 GB
Буфер диска 100'000 64 MB
Локальный диск 10'000'000 1000 GB
Удалённые сервера 1'000'000'000


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

Допустим, ваш компьютер имеет 8 ГБ оперативной памяти и диск размером 1000 ГБ. Но подумайте, что вы не работаете со всеми данными на диске в один момент. Вы загружаете операционную систему, открываете веб-браузер, текстовый редактор, пару-тройку других приложений и работаете с ними несколько часов. Все эти приложения помещаются в оперативной памяти, поэтому вашей системе не нужно обращаться к диску. Потом, конечно, вы закрываете одно приложение и открываете другое, которое приходится загрузить с диска в оперативную память. Но это занимает пару секунд, после чего вы несколько часов работаете с этим приложением, не обращаясь к диску. Вы не особо замечаете медленный диск, потому что в один момент вы работаете только с небольшим бъёмом данных, которые кэшируются в оперативной памяти. Вам нет смысла тратить огромные деньги на установку 1024 ГБ оперативной памяти, в которую можно было бы загрузить содержимое всего диска. Если бы вы это сделали, вы бы почти не заметили никакой разницы в работе, это было бы «деньги на ветер».

Так же дело обстоит и с маленькими кэшами процессора. Допустим вам нужно выполнить вычисления над массивом, который содержит 1000 элементов типа int. Такой массив занимает 4 КБ и полностью помещается в кэше первого уровня размером 32 КБ. Система понимает, что вы начали работу с определённым куском оперативной памяти. Она копирует этот кусок в кэш, и процессор быстро выполняет действия над этим массивом, наслаждаясь скоростью кэша. Потом изменённый массив из кэша копируется назад в оперативную память. Увеличение скорости оперативной памяти до скорости кэша не дало бы ощутимого прироста в производительности, но увеличило бы стоимость системы в сотни и тысячи раз. Но всё это верно только если программы имеют хорошую локальность.

Локальность


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

Рассмотрим, программу, которая суммирует элементы массива:

int sum(int size, int A[])
{
    int i, sum = 0;

    for (i = 0; i < size; i++)
        sum += A[i];
    return sum;
}


В этой программе обращение к переменным sum и i происходит на каждой итерации цикла. Они имеют хорошую временную локальность и будут расположены в быстрых регистрах процессора. Элементы массива A имеют плохую временную локальность, потому что к каждому элементу мы обращаемся только по разу. Но зато они имеют хорошую пространственную локальность — тронув один элемент, мы затем трогаем элементы рядом с ним. Все данные в этой программе имеют или хорошую временную локальность или хорошую пространственную локальность, поэтому мы говорим что программа в общем имеет хорошую локальность.

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

Перемещение данных между уровнями иерархии осуществляется блоками определённого размера. К примеру, процессор Core i7 Haswell перемещает данные между своими кэшами блоками размером в 64 байта. Рассмотрим конкретный пример. Мы выполняем программу на машине с вышеупомянутым процессором. У нас есть массив v, содержащий 8-байтовые элементы типа long. И мы последовательно обходим элементы этого массива в цикле. Когда мы читаем v[0], его нет в кэше, процессор считывает его из оперативной памяти в кэш блоком размером 64 байта. То есть в кэш отправляются элементы v[0]v[7]. Далее мы обходим элементы v[1], v[2], ..., v[7]. Все они будут в кэше и доступ к ним мы получим быстро. Потом мы читаем элемент v[8], которого в кэше нет. Процессор копирует элементы v[8]v[15] в кэш. Мы быстро обходим эти элементы, но не находим в кэше элемента v[16]. И так далее.

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

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

Дружелюбный к кэшу код


Как программисты вы должны стараться писать код, который, как говорят, дружелюбный к кэшу (cache-friendly). Как правило, основной объём вычислений производится лишь в нескольких местах программы. Обычно это несколько ключевых функций и циклов. Если есть вложенные циклы, то внимание нужно сосредоточить на самом внутреннем из циклов, потому что код там выполняется чаще всего. Эти места программы и нужно оптимизировать, стараясь улучшить их локальность.

Вычисления над матрицами очень важны в приложениях анализа сигналов и научных вычислениях. Если перед программистами встанет задача написать функцию перемножения матриц, то 99.9% из них напишут её примерно так:

void matrixmult1(int size, double A[][size], double B[][size], double C[][size])
{
    double sum;

    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++) {
            sum = 0.0;
            for (int k = 0; k < size; k++)
                sum += A[i][k]*B[k][j];
            C[i][j] = sum;
        }
}


Этом код дословно повторяет математическое определение перемножения матриц. Мы обходим все элементы окончательной матрицы построчно, вычисляя каждый из них один за другим. В коде есть одна неэффективность, это выражение B[k][j] в самом внутреннем цикле. Мы обходим матрицу B по стобцам. Казалось бы, ничего с этим не поделаешь и придётся смириться. Но выход есть. Можно переписать то же вычисление по другому:

void matrixmult2(int size, double A[][size], double B[][size], double C[][size])
{
    double r;

    for (int i = 0; i < size; i++)
        for (int k = 0; k < size; k++) {
            r = A[i][k];
            for (int j = 0; j < size; j++)
                C[i][j] += r*B[k][j];
        }
} 


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

Блокинг


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

Можно продемонстрировать это на примере. Допустим у вас есть ориентированный граф, представленный в виде матрицы смежности. Это такая квадратная матрица из нулей и единиц, так что если элемент матрицы с индексом (i, j) равен единице, то существует грань от вершины графа i к вершине j. Вы хотите превратить этот ориентированный граф в неориентированный . Об этом говорит сайт https://intellect.icu . То есть, если есть грань (i, j), то должна появиться противоположная грань (j, i). Обратите внимание, что если представить матрицу визуально, то элементы (i, j) и (j, i) являются симметричными относительно диагонали. Эту трансформацию нетрудно осуществить в коде:

void convert1(int size, int G[][size])
{
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            G[i][j] = G[i][j] | G[j][i];
}



Блокинг появляется естественным образом. Представьте перед собой большую квадратную матрицу. Теперь иссеките эту матрицу горизонтальными и вертикальными линиями, чтобы разбить её, скажем, на 16 равных блока (четыре строки и четыре столбца). Выберите два любых симметричных блока. Обратите внимание, что все элементы в одном блоке имеют свои симметричные элементы в другом блоке. Это наводит на мысль, что ту же операцию можно совершать над этими блоками поочерёдно. В этом случае на каждом этапе мы будем работать только с двумя блоками. Если блоки сделать достаточно маленького размера, то они поместятся в кэше высокого уровня. Выразим эту идею в коде:

void convert2(int size, int G[][size])
{
    int block_size = size / 12;    // разбить на 12*12 блоков
                                   // представим, что делится без остатка
    for (int ii = 0; ii < size; ii += block_size) {
        for (int jj = 0; jj < size; jj += block_size) {
            int i_start = ii;    // индекс i для блока принимает значения [ii, ii + block_size)
            int i_end   = ii + block_size;
            int j_start = jj;    // индекс j для блока принимает значения [jj, jj + block_size)
            int j_end   = jj + block_size;

            // обходим блок
            for (int i = i_start; i < i_end; i++)
                for (int j = j_start; j < j_end; j++)
                    G[i][j] = G[i][j] | G[j][i];
        }
    }
}


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

На машине с процессором Core i7 Haswell вторая функция не выполняется быстрее. На машине с более простым процессором Pentium 2117U вторая функция выполняется в 2 раза быстрее. На машинах, которые не выполняют предвыборку, производительность улучшилась бы ещё сильнее.

Какие алгоритмы быстрее


Все знают из курсов по алгоритмам, что нужно выбирать хорошие алгоритмы с наименьшей сложностью и избегать плохих алгоритмов с высокой сложностью. Но эти сложности оценивают выполнение алгоритма на теоретической машине, созданной нашей мыслью. На реальных машинах теоретически плохой алгоритм может выполнятся быстрее теоретически хорошего. Вспомните, что получить данные из оперативной памяти занимает 200 тактов, а из кэша первого уровня 4 такта — это в 50 раз быстрее. Если хороший алгоритм часто трогает память, а плохой алгоритм размещает свои данные в кэше, хороший алгоритм может выполняться медленнее плохого. Также хороший алгоритм может выполняться на процессоре хуже, чем плохой. К примеру, хороший алгоритм вносит зависимость данных и не может загрузить конвеер процессора. А плохой алгоритм лишён этой проблемы и на каждом такте отправляет в конвеер новую инструкцию. Иными словами, сложность алгоритма это ещё не всё. Как алгоритм будем выполняться на конкретной машине с конкретными данными имеет значение.

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

Допустим, очередь длиной 1000 элементов мы реализовали обоими способами. И нам нужно вставить элемент в середину очереди. Элементы списка хаотично разбросаны по памяти, поэтому чтобы обойти 500 элементов, нам понадобится 500*200=100'000 тактов. Массив расположен в памяти последовательно, что позволит нам наслаждаться скоростью кэша первого уровня. Используя несколько оптимизаций, мы можем двигать элементы массива, тратя 1-4 такта на элемент. Мы сдвинем половину массива максимум за 500*4=2000 тактов. То есть быстрее в 50 раз.

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

Заключение


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

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

В частности, рекомендуются следующие техники:

  • Сконцентрируйте ваше внимание на внутренних циклах. Именно там происходит наибольший объём вычислений и обращений к памяти.
  • Постарайтесь максимизировать пространственную локальность, читая объекты из памяти последовательно, в том порядке, в котором они в ней расположены.
  • Постарайтесь максимизировать временную локальность, используя объекты данных как можно чаще после того, как они были прочитаны из памяти.

Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu

NB: масштаб логарифмический!

Преждевременная пессимизация Легко на себя, легко по коду: при прочих равных условиях, особенно в отношении сложности кода и удобочитаемости, некоторые эффективные шаблоны проектирования и идиомы кодирования должны просто естественным образом вытекать из ваших кончиков пальцев и писать их сложнее, чем пессимизированные альтернативы. Это не преждевременная оптимизация; он избегает безнадежной пессимизации.- Херб Саттер, Андрей Александреску.Всякий раз, когда нам нужно оптимизировать код, мы должны профилировать его, просто и просто. Тем не менее, иногда имеет смысл просто знать номера шаров для относительных затрат на некоторые популярные операции, поэтому вы не будете делать крайне неэффективные вещи с самого начала (и, надеюсь, позже не понадобится профилировать программу ).

Итак, здесь идет речь - инфографика, которая должна помочь оценить затраты на определенные операции в цикле тактовых импульсов ЦП и отвечать на такие вопросы, как «эй, сколько обычно читается L2?». Хотя ответы на все эти вопросы более или менее известны, я не знаю ни одного места, где все они перечислены и представлены в перспективе. Также отметим, что, хотя перечисленные номера, строго говоря, применяются только к современным процессорам x86 / x64, ожидается, что аналогичные модели относительных эксплуатационных затрат будут наблюдаться на других современных процессорах с большими многоуровневыми кэшами (такими как ARM Cortex A или SPARC); с другой стороны, MCU (включая ARM Cortex M) различны, поэтому некоторые из шаблонов могут быть разными.

И последнее, но не менее важное: слово осторожности: все оценки здесь являются лишь показаниями на порядок; однако, учитывая масштаб различий между различными операциями, эти показания могут по-прежнему использоваться (по крайней мере, следует иметь в виду избегать «преждевременной пессимизации»).

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

если вы вызываете свою виртуальную функцию 100K раз в секунду на процессоре 3GHz - это, вероятно, не будет стоить вам более 0,2% от общего объема вашего процессора; однако, если вы вызываете одну и ту же виртуальную функцию 10M раз в секунду, это легко означает, что виртуализация поглощает двузначные проценты вашего ядра процессора.

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

latency numbers every programmer should knowМетоды оптимизации программ. Latency numbers every programmer should know - портал intellect.icu

Latency numbers every programmer should know

L1 cache reference ......................... 0.5 ns
Branch mispredict ............................ 5 ns
L2 cache reference ........................... 7 ns
Mutex lock/unlock ........................... 25 ns
Main memory reference ...................... 100 ns             
Compress 1K bytes with Zippy ............. 3,000 ns  =   3 µs
Send 2K bytes over 1 Gbps network ....... 20,000 ns  =  20 µs
SSD random read ........................ 150,000 ns  = 150 µs
Read 1 MB sequentially from memory ..... 250,000 ns  = 250 µs
Round trip within same datacenter ...... 500,000 ns  = 0.5 ms
Read 1 MB sequentially from SSD* ..... 1,000,000 ns  =   1 ms
Disk seek ........................... 10,000,000 ns  =  10 ms
Read 1 MB sequentially from disk .... 20,000,000 ns  =  20 ms
Send packet CA->Netherlands->CA .... 150,000,000 ns  = 150 ms

Assuming ~1GB/sec SSD

Методы оптимизации программ. Latency numbers every programmer should know - портал intellect.icu

подробнее на сайте https://intellect.icu/metody-optimizatsii-programm-latency-numbers-every-programmer-should-know-6185

Комментарии (0)


avatar

Чтобы оставить комментарий войдите или зарегистрируйтесь



Высоконагруженные проекты.Теория паралельные вычисления. Суперкомпьютеры. Распределенные системы