Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Методы оптимизации программ. Сравнение времен задержки на различных уровнях архитектуры

Лекция



Привет, Вы узнаете о том , что такое оптимизация программ , Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое оптимизация программ , 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 (англ.)).

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

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

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

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

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

Во многих программах какую-то часть объектов данных необходимо инициализировать, то есть присвоить им начальные значения. Такое присваивание выполняется либо в самом начале программы, либо, например, в конце цикла. Правильная инициализация объектов позволяет сэкономить драгоценное процессорное время. Об этом говорит сайт https://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-й степени:

Методы оптимизации программ. Сравнение времен задержки на различных уровнях архитектуры

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

Методы оптимизации программ. Сравнение времен задержки на различных уровнях архитектуры

Такая форма записи называется схемой Горнера. В этом выражении 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. Таким образом, можно существенно сократить количество трудоемких арифметических операций.

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

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

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

Методы оптимизации программ. Сравнение времен задержки на различных уровнях архитектуры


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

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

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

На написание этой статьи меня вдохновила шестая глава из книги 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 такта. Потом идет пара сотен килобайт более медленной кэш-памяти второго уровня. Потом несколько мегабайт кэш-памяти третьего уровня. Она гораздо медленней, но все равно быстрее оперативной памяти. Далее расположена относительно медленная оперативная память.

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

продолжение следует...

Продолжение:


Часть 1 Методы оптимизации программ. Сравнение времен задержки на различных уровнях архитектуры
Часть 2 Вау!! 😲 Ты еще не читал? Это зря! - Методы оптимизации программ. Сравнение времен задержки на

См.также

Выводы из данной статьи про оптимизация программ указывают на необходимость использования современных методов для оптимизации любых систем. Надеюсь, что теперь ты понял что такое оптимизация программ , latency numbers every programmer should know, задержки в передаче данных и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Высоконагруженные проекты.Паралельные вычисления. Суперкомпьютеры. Распределенные системы

создано: 2016-05-01
обновлено: 2022-02-17
132435



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


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

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

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