4 января 2013 г.

Основы оптимизации прикладных программ на Delphi

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

Эта статья служит введением в оптимизацию прикладных программ на Delphi.

Неправильная оптимизация

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

Это - близорукий подход. Не только я, но и многие известные эксперты (Стив МакКоннелл, Дональд Кнут, Гарольд Абельсон, Энтони Хоар, Джеральд Сассман, Гордон Белл и др.) говорят примерно одно и то же: преждевременная оптимизация — это корень всех бед. "Программы пишутся для компьютера" - это заблуждение. Программы в первую очередь пишутся для людей, которые будут их читать. Иными словами, писать код нужно в первую очередь для людей, а лишь во вторую очередь - для машины. Именно поэтому простота и ясность лучше сложности и эффективности. К оптимизации нужно обращаться, когда в этом возникает необходимость, не нужно делать это заранее. Если в программе нет проблем с производительностью, то ваша упреждающая оптимизация - это впустую потраченное время и (часто) более запутанный и сложный код. Фактически, вы ухудшаете свою программу - путём её (ненужного и излишнего) усложнения и увеличения времени разработки.

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

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

Когда нужно начинать оптимизацию?

Итак, вывод: оптимизацию надо начинать...
  1. Когда закончена разработка программы, и написан ясный и корректный код.
  2. Когда есть объективная потребность в оптимизации ("медленно работает, а нельзя ли быстрее?").
    Подсказка: причина "этот код можно улучшить" не является объективной потребностью в оптимизации.
Заметьте, что это также отвечает на вопрос, когда не нужно проводить оптимизацию.

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

С чего начать?

Итак, выше я сказал, с чего не надо начинать - не нужно оптимизировать всё подряд, причём до того, как вы выясните, что это нуждается в оптимизации. Оптимизировать одноразовые операции — это просто потеря времени. Вывод? Оптимизировать надо то, что тормозит. Это означает, что начинать вам нужно с определения того, что у вас тормозит. Медленная работа? Высокие потребляемые ресурсы? Ещё чем-то недовольны? Ага, вот это будем оптимизировать. Нет проблем? Всё, не трогаем, не надо ничего оптимизировать.

Таким образом, вам не нужно оптимизировать весь код подряд. Нужно оптимизировать "узкие места" (англ. bottleneck - бутылочное горлышко): критические части кода, которые являются основным потребителем необходимого ресурса. К примеру, вы можете оптимизировать какой-то участок кода, ускорив его выполнение в 1000 раз. Хорошо, теперь ваша программа выполняется на 1 миллисекунду быстрее (потому что до изменений код выполняется за 1 микросекунду). Поздравляю, вы потратили месяц работы, чтобы ваша программа вместо 60 секунд выполнялась за 60 секунд минус одну миллисекунду. Вместо этого вы могли бы потратить пять минут, чтобы выяснить, какой же код работает эти 60 секунд и оптимизировать его. Вы можете потратить всего несколько часов, чтобы ускорить программу в несколько раз. Иными словами, изменение лишь малой части кода приведёт к значительным изменениям. Изменение же любого другого кода не окажет практически никакого эффекта на эффективность.

Как определить, какой код является узким местом? Следующая ошибка начинающих - пытаться это угадать. "Ну, вот здесь я делаю вот так, это явно ужасно медленно, поэтому вот он, плохой код, это же очевидно". Неверно! Почти никогда вы не угадаете правильно. Сколько я ни занимался оптимизацией своих программ, где-то в 80% случаев я даже близко не был прав в своих предположениях о том, что вызывает тормоза. Вы, наверное, подумали о том, что я, видимо, просто не очень опытен в вопросах оптимизации. Это вполне может быть так (я не буду спорить), но дело ведь не в этом. Подумайте вот о чём: сколько раз вы использовали отладчик, чтобы найти причину бага в программе? Вы использовали инструмент, чтобы разобраться в вашем ясном и предположительно корректном коде. Вы не смогли угадать, в чём проблема с выполнением кода - вам потребовался для этого помощник-инструмент. А если вы не смогли выполнить "в уме" такую простую операцию (проверить корректность кода), то почему же вы считаете, что можете сделать "в уме" гораздо более сложную вещь - разобраться, почему корректный код работает медленно (что включает в себя не только знание кода, как для отладки, но и знание временных характеристик кода, железа, а также внешнего окружения)?

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

Итак, если для отладки вы использовали инструмент - отладчик, то для оптимизации вы также должны использовать инструмент. И он называется профайлером (profiler). Профайлер - это подвид отладчика. Он запускает вашу программу под отладкой и отслеживает, какой код будет выполнять ваша программа. После работы вы сможете выяснить, чем была занята программа, какой код в ней дольше всего выполнялся.

Посмотрите на это и с такой стороны: если вы хотите улучшить производительность, то вы же должны как-то определять, чего вам удалось достичь. Иными словами, на сколько вы улучшили (или, быть может, ухудшили) производительность программы своими изменениями? Оптимизирование - это улучшение характеристик программы. А если у вас на руках нет фактических данных о программе, то чем вы, вообще-то, занимаетесь? Уж явно не оптимизацией...

Практический пример: работа с AQTime

Один из самых известных профайлеров для Delphi - это AQTime. Более того, его начальная версия входит в состав современных версий Delphi. Начальной версии вполне достаточно для начальной оптимизации. В ней нет поддержки .NET, других сред программирования, профилирования 64-битных приложений и профилирования на уровне строк (а только на уровне функций). А если у вас старая версия Delphi, где AQTime нет, либо вам не хватает возможностей начальной версии - вы вполне можете скачать пробную версию (trial) редакции Pro. Поэтому давайте на примере AQTime посмотрим, как надо начинать оптимизацию программы.

Запустите Delphi и откройте в ней свой проект. Затем вам нужно настроить проект для отладки, как это описано в этой статье. Если кратко, то я рекомендую включить опции "Compiler/Stack Frames", "Compiler/Debug information", "Compiler/Local Symbols", "Compiler/Use Debug DCUs", "Linker/Debug information" (aka "TD32 Info"), "Linker/Place debug information in separate file" (есть не во всех версиях Delphi) и "Linker/Map file" = Detailed. Затем сохраните проект и сделайте проекту Build (не просто Compile). Кроме того, если ваша программа использует пакеты или DLL - то эти пакеты и DLL также нужно пересобрать с отладочными опциями. Если это невозможно (для пакетов) - хотя бы временно отключите сборку с пакетами.

Примечание: если вы используете внешние утилиты, которые модифицируют вашу программу (вроде упаковщиков или трейсера исключений) - убедитесь, что утилиты не трогают отладочную информацию и запускаются до AQTime. К примеру, чтобы использовать AQTime одновременно с EurekaLog, нужно отключить в EurekaLog опцию "Delete service files after compilation".

Примечание: если у вас возникают проблемы с профайлером (не хочет он профилировать ваш проект) - как правило рецепты решения этих проблем те же, что и при отладке (поскольку профайлер - это тоже отладчик). Т.е. проблемы с отладочной информацией. TO-DO список для решения таких проблем можно найти здесь. Кроме того, где и как искать отладочную информацию задаётся в настройках AQTime (AQTime / Options / Services / Symbols).

В этой статье в качестве проекта я буду использовать программу Cycles из примеров AQTime. Вы можете найти её в папке C:\Users\Public\Documents\AQtime 7 Samples\Performance\Delphi\. Эта программа специально сделана как пример для поиска узких мест с производительностью процессора. Там есть всего одна кнопка, которая запускает такой код:
procedure ProfilingTest(Param: Integer);
var 
  i: Integer;
begin
  DoActionA;
  DoActionB;
  for i := 1 to Param do
    DoActionC;
  MessageBox(MainForm.Handle, 'Execution finished.', 'Performance Sample', MB_OK);
end;
Т.е. код просто вызывает несколько процедур. Часть процедур - в цикле. Вызываемые процедуры являются простыми заглушками (с вызовом Sleep), а также они вызывают друг друга, но в реальных программах, понятно, они будут делать что-то полезное.

Где здесь узкое место? Цикл? Или, быть может, DoActionA выполняется дольше, чем весь цикл вместе взятый? Чтобы это узнать, нам нужно запустить этот код под профалером AQTime. Для любых действий с AQTime в IDE есть одноимённый пункт меню. Для начала вам нужно указать, что вы хотите отслеживать. AQTime может профилировать использование процессора, выделение памяти, покрытие кода и т.д. Поскольку сейчас нас интересует скорость выполнения, то мы выберем Performance Profiler:

Меняем текущий профайлер на "Performance"
Далее нужно использовать пункт AQTime / Run With Profiling. Когда вы делаете это в первый раз, то в ваш проект будет добавлена необходимая информация для AQTime (настройки, отчёты и т.п.).

Проект после добавления в него AQTime
Ну и, конечно же, команда AQTime / Run With Profiling запустит программу под выбранным профайлером:


Собственно, здесь вам ничего менять не надо, поэтому просто жмите на "Run".

Примечание: современные системы могут динамически менять частоту процессора в зависимости от нагрузки. К примеру, в простое частота может быть 1'200 МГц, но под нагрузкой подниматься до 3'800 МГц. Подобная возможность полезна для экономии энергии, но она может исказить результаты профилирования. Поэтому лучше всего отключить её в BIOS на время профилирования или запускать профилирование на виртуальной машине. Тем не менее, для грубой прикидки можно работать и с ней.

Помимо предупреждения о настройках проекта и процессоре, AQTime может показать сообщение о невозможности измерения времени выполнения некоторых процедур:


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

Собственно, все эти предупреждения нужно либо исправить, либо проигнорировать (дополнительно установив флажок "Don't show again").

Итак, программа начнёт работать под профайлером. Вы не сможете отлаживать программу (точки останова, пауза и т.п.). Вы должны запустить в программе интересующий вас код и дать ему поработать, после чего закрыть программу. Учтите, что под профайлером программа будет выполняться несколько медленнее, чем в свободном прогоне (обычно - на 10-20% медленнее, в зависимости от кода). Когда вы закроете программу, AQTime автоматически покажет вам отчёт по выбранной метрике:

Отчёт профайлера после выполнения программы
(щёлкните для увеличения)
Более того, если вы переключитесь на исходный код, то слева от строк кода вы увидите временные характеристики последнего прогона под профайлером:

Информация по времени выполнения функций
(щёлкните для увеличения)
Как я уже сказал выше, бесплатные (начальная и Trial) версии AQTime дадут вам информацию только по функциям/процедурам/методам в целом. А информацию по отдельным строкам показывает только платная (Pro).

Вам также доступны некоторые настройки по отображению - в чём измерять (секунды, миллисекунды и т.п.), какие значения показывать (колонки), сортировка (по общему времени, по числу вызовов и т.п.). Правда, изменение состава колонок - не самая очевидная операция, поскольку для неё нет кнопки в панели инструментов. Вот как вы можете это сделать: щёлкните правой кнопкой мыши по заголовку колонки и выберите "Field Chooser".


После чего перетаскивайте колонки, как вам удобнее. Чтобы удалить колонку - перетащите её из отчёта в окно "Field Chooser". Чтобы добавить колонку - перетащите её из окна "Field Chooser" в отчёт.

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


Как вы можете видеть, профайлер даёт вам множество информации. Но что же с ней нужно делать? Смысл работы с профайлером заключается в том, что вы фильтруете информацию. Таким образом, профайлер должен давать вам возможность фокусироваться на том, что вы хотите знать. Т.е. вы "задаёте вопрос", профайлер показывает вам ответ, вы уточняете "вопрос" - и так далее, пока не будет найдено проблемное место. Именно таким циклическим образом работают с профайлером.

Итак, как вы можете фильтровать информацию? Во-первых, в настройках AQTime на вкладке General есть опция "Exclude standard source files". Если её включить - в отчёт не попадёт информация по модулям RTL/VCL, оставляя только ваш код. Таким образом, это аналог опции "Use Debug DCUs" в Delphi. И смысл её такой же: если вы не можете изменить код RTL/VCL, то зачем его профилировать? Вы можете выбросить его из рассмотрения и сфокусироваться на коде, который вы можете изменять.

Также в опциях есть настройка по исключению произвольных модулей/функций. Вы можете добавить в список игнорирования модули сторонних библиотек или функции, которые вы не сможете изменить. Эта настройка находится в AQTime / Options / General / Ignore Files and Routines.

Ну и, конечно же, вы можете исключить из профилирования код без отладочной информации. Это делается опцией AQTime / Options / General / General Preferences / Exclude routines with no source info. Если вы включаете эту опцию, то вы сможете контролировать, что нужно профилировать, используя обычные директивы {$D+} и {$D-} в вашем Delphi коде.

Далее, вы можете включать и выключать профилирование во время прогона программы используя пункт меню "Enable Profiling" / "Disable Profiling" из меню AQTime в IDE. Надо сказать, что это не самый интуитивный пункт. Когда там написано "Disable Profiling" (и слева от надписи есть отметка) - это означает, что профайлер собирает данные. И наоборот: надпись "Enable Profiling" (и отсутствие отметки слева от надписи) означает, что профайлер не работает. Вы можете использовать эту команду, чтобы не собирать информацию по коду, который вас не интересует. Например, вы отключили профайлер, запустили профилирование, дошли до нужного места, включили профайлер, запустили код, дождались окончания его работы, отключили профайлер и вышли. Тогда в финальном отчёте у вас будет гораздо меньше лишнего кода.

Альтернативный вариант - использование т.н. областей (Area) или триггеров (Trigger). Вы можете создать одну или несколько областей, включить в область функции и исключить или включить область в профилирование. Также области имеют настройки, которые можно изменять (типа, что будем отслеживать в этой области). Триггеры же - это аналог точек останова в отладчике. Вы можете "расставить" их по коду, и они будут включать или выключать профилирование при выполнении кода. И, как и точки останова, триггеры поддерживают похожие свойства (pass count и т.п.). Я не буду подробно описывать эти возможности - они вполне понятно описаны в справке по AQTime: Using Profiling Areas и Using Triggers.

Итак, эти возможности позволяют вам создать отчёт только по тому коду, что вас интересует.

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

Значит ли это, что мы нашли узкое место, которое и нужно оптимизировать? Подождите, всё может быть не так просто. Хотя в некоторых случаях достаточно такого простого анализа, как вы сразу находите проблемное место, иногда бывает и так, что эта картина не полностью отражает действительность. Ведь вопрос не только в том, какая функция работает медленно, сколько в том, почему она работает медленно. И на это может быть несколько причин:
  • Сама функция работает быстро, но её очень много вызывают
  • Сама функция работает быстро, но вызывает другую функцию, которая работает медленно
  • Сама функция работает медленно (например, проводит много операций, либо её скорость определяется задержками железа)
Вот чтобы узнать точную причину, вам нужно анализировать значения нескольких счётчиков - "Time with children" (время, включая дочерние вызовы), "Hit count" (общее число вызовов), "Shared time" (как распределяется время между собственно функцией и вызываемыми из неё), различные процентные отношения, глубину рекурсии и т.д. Иногда бывает полезно и значение "First Time" (время первого вызова) - например, если это функция типа "init-on-demand".

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

Отчёт после фильтрации - всего четыре кандидата
(щёлкните для увеличения)
Если не считать корневую для вычислений процедуру ProfilingTest, то самой тяжёлой оказывается DoActionC (см. "Time with Children"). Однако другие счётчики показывают, что она не делает практически ничего, а только вызывает другие подпрограммы (см. "Shared Time" или сравните "Time" и "Time with Children").

Версия AQTime Pro позволила бы вам просмотреть дерево вызовов и проанализировать строки. Но начальная версия такой возможности не имеет. Поэтому вы должны переключиться на исходный код и сравнить его со счётчиками. Откуда мы можем сделать вывод:
  1. Высокое (собственное) время ProfilingTest вызвано вызовом MessageBox, который просто ждал, пока пользователь закроет окно.
  2. DoActionC вызывает DoActionA и DoActionB, которые и занимают основное время выполнения функции.
Мы также знаем, что DoActionA вызывали 11 раз и она суммарно заняла 5.5 секунд (в среднем - 0.5 секунд на вызов), а DoActionB вызывали 101 раз и её общее время - 10 секунд (в среднем - 0.1 на вызов).

Таким образом, чтобы улучшить производительность нашей программы, мы должны либо улучшить работу DoActionA, либо уменьшить число вызовов DoActionB. Обратите внимание, что "естественный" выбор для оптимизации (DoActionC) не появляется в нашем списке. Как бы мы узнали об этом без профайлера? Ведь в коде у нас есть цикл. "Ууу, цикл - это же долго и медленно, значит надо оптимизировать его, сейчас я перепишу DoActionC на ассемблере..." - и в результате вы бы потратили время на оптимизацию, которая выиграла бы у вас долю секунды. Профайлер же явно показал, что проблема вовсе не там.

Не стоит делать и то и другое (оптимизация DoActionA и уменьшение вызовов DoActionB) одновременно. Сначала попробуйте, к примеру, уменьшить число вызовов DoActionB. Посмотрите, не стала ли производительность приемлемой (ну и заодно проверьте корректность программы). Заново запустите профилирование - не вылезла ли на первый план какая-то другая подпрограмма?

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

Краткие выводы по профилированию:
  • Вы не угадаете, в чём проблема производительности, пока не запустите программу под профайлером.
  • Быстрый способ найти узкое место - взять несколько элементов с максимальным значением "Time". Но не всегда это будет верный ответ.
  • Второй способ - взять подпрограмму с максимальным "Time with Children" и разобрать её дерево вызова.
  • Нужно использовать значения нескольких счётчиков, чтобы восстановить картину происходящего.
  • Редакция Pro позволит вам сделать это удобно. С начальной редакцией вам придётся много переключаться между отчётом и исходным кодом.
  • Начальная редакция не показывает производительность по строкам, поэтому вам придётся угадывать, либо разбивать код на подпрограммы.

Некоторые базовые приёмы оптимизации прикладных программ

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

Прежде всего замечу, что оптимизировать нельзя всё сразу. Как правило, любая оптимизация - это инженерный компромисс (tradeoff) между скоростью работы и потреблением памяти. И то и другое удаётся уменьшить редко. Поэтому вы либо ускоряете работу за счёт большего использования памяти ("trade memory for speed"), либо уменьшаете потребление памяти ценой более медленной работы ("trade speed for memory"). Что из этого предпочтительнее?

Современные системы позволяют установить большое количество дешёвой памяти (в самом деле, сегодня комплект на 16 Гб стоит всего 3000 рублей), но частота процессоров практически не меняется уже много лет: в 2002 году выпустили P4 с 3 ГГц - и современные процессоры не далеко ушли от него (по частоте). Так что процессоры становились многоядернее, эффективнее, но не быстрее по частоте (общий рост же производительности достигается другими трюками). Современный серийный процессор для платформы x86 имеет штатную частоту примерно 3.5 ГГц (максимальная номинальная частота для процессоров других платформ - всего лишь 5.2 ГГц). Как видите, за 10 лет частота практически не изменилась. Сравните это с памятью: в 2002 году типовый размер одной планки был 256 Мб - много меньше современных 8 гигабайтных планок. Конечно, сравнивать процессоры по частоте не очень корректно - как я уже сказал, производительность зависит не только от частоты, тем не менее видно, что оперативная память и дисковая подсистема развиваются значительно быстрее, чем процессоры, которые упираются в какие-то физические ограничения. Именно поэтому сегодня оптимизация по скорости выполнения за счёт памяти является (как правило) предпочтительнее противоположной. Но, конечно, всё зависит от конкретной ситуации.

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

Обычно для прикладного программиста наибольший прирост производительности происходит при смене алгоритма. Микрооптимизации типа экономии на одном сложении съедаются неэффективным алгоритмом. Поэтому в первую очередь нужно улучшать O-сложность алгоритма. Само собой, O-сложность конкретного алгоритма обычно нельзя изменить, поэтому можно только выбрать другой алгоритм. К примеру, классический пример - сортировка последовательностей. Пузырьковая сортировка имеет сложность O(n2), а быстрая сортировка (quick sort) - O(n * lg(n)) (в среднем). Есть алгоритмы и с наихудшим случаем гарантированно не хуже O(n * lg(n)) и даже O(n) для наилучшего случая. Но здесь уже надо смотреть не ассимптотическую оценку алгоритма, а скрытые накладные расходы. Слишком сложный алгоритм с лучшей оценкой на малых объёмах данных будет работать медленнее алгоритма с худшей оценкой, но более простого в реализации. Именно поэтому нет универсального ответа "что лучше". "Наилучший" алгоритм будет зависеть от ваших данных.

Итак, первое, что вы должны сделать - попытаться найти другой алгоритм для вашего узкого места. В интернете не проблема найти описания алгоритмов, их характеристики и реализации на разных языках. Начиная от Википедии, заканчивая специализированными сайтами. Ну и, конечно же, всегда есть Google и даже форумы ("подскажите быстрый алгоритм"). Выберите несколько разных алгоритмов, которые, как вы предполагаете, должны быть быстрее того, что у вас уже написано. Реализуйте их, и заново запустите программу под профайлером. Посмотрите, как изменится скорость выполнения программы. Выберите самый быстрый вариант.

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

Во-первых, очевидные вещи вроде выноса инвариантов за пределы цикла. Если что-то не меняется, то зачем вычислять заново это что-то каждый раз, если можно вычислить его один раз, а затем использовать многократно? Это - лишь конкретный пример более общей техники кэширования результата вычислений. Поэтому этот приём можно применять не только для цикла, но и для более сложного кода. К примеру, пусть у вас есть какой-то объект, вы делаете ему метод типа ToString, который возвращает представление содержимого объекта в виде строки. Реализации метода будет заключаться в постройке строки по внутренним полям объекта. Но если ваш (или чужой) код будет вызывать ToString слишком часто, то эта простая реализация может стать узким местом. Почему бы тогда не сохранять результат выполнения ToString в новом поле объекта (кэшировать его), а перестраивать только при изменениях объекта? Конечно, такой приём также потребует логического введения поля типа "Modified", которое будет устанавливаться при изменениях в объекте и сбрасываться при вызове перестройке кэша (внутри вызова ToString).

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

Подвидом кэширования можно рассматривать табличную оптимизацию. К примеру, алгоритмы кодирования или преобразования кодировок. Наивная реализация обычно заключается в проходе по строке и анализе каждого символа, плюс вычисление преобразованного символа. Таким образом, код может выполнять множество различных операций (как логических проверок, так и вычислений) для каждого символа. Но ведь результат вычислений для каждого символа не зависит ни от чего, кроме самого символа. Кроме того, символы встречаются в строках многократно. Тогда почему бы не ввести табличку, в которой для каждого символа будет представлен его преобразованный вариант? Табличку можно инициализировать при старте программы, либо при первом преобразовании. Конечно, пересчёт всех возможных символов - не самая быстрая операция и это не будет эффективно, если вам нужно сделать единственное преобразование короткой строки. Но если вам нужно выполнять преобразования много и часто, то единственная инициализация таблицы скомпенсируется выигрышем от последующих преобразований. Почему? Да потому что с таблицей преобразования будут тривиальны: Str[i] := Table[Str[i]].

Чем-то похожей на табличную оптимизацию является хэш-функция. Её обычно применяют в алгоритмах поиска. Как правило, поиск заключается в переборе элементов какого-то массива. Вы можете улучшить поиск использованием предварительной сортировки с последующими (многократными) бинарными поисками, но иногда есть вариант ещё лучше: если вам удастся предложить удобную и компактную хэш-функцию для ключа, то вы сможете избавиться от перебора, а "поиск" будет выглядеть примерно как-то так: Found := Assigned(Item[Hash(Key)]) .

Ещё один частный случай "код, который никогда не выполняется" - отложенные вычисления. Пусть у вас есть какой-то сложный объект. Вы тратите много времени, чтобы подготовить его к работе, загрузить все его данные (это может быть конструктор или отдельный метод типа Init/Load - не важно). Но если вы часто создаёте такой объект и используете лишь малую часть его возможностей, то куча кода инициализации будет выполняться зря. Поэтому вы можете использовать технику отложенных вычислений, также известную как инициализация по запросу (init on demand) и ленивая инициализация (lazy initialization). Введите флаг, был ли объект инициализирован. В конструкторе не проводите тяжёлых вычислений. Пусть каждый метод доступа вызывает внутренний метод (скажем, CheckInit). Метод CheckInit проверит флаг: если он установлен, то метод не будет ничего делать, если флаг сброшен - метод произведёт инициализацию объекта и установит флаг. Таким образом, вы будете откладывать тяжеловесный код максимально далеко - пока он точно не понадобится.

Покупать оптом - дешевле. Этот приём работает не только в обычной жизни, но и в оптимизации программ. Часто бывает так, что выполнение отдельного действия требует какой-то подготовки (до) и финализации (после). Соответственно, если вы выполняете множество однотипных действий в цикле, то подготовку и финализацию можно вынести за цикл, выполнив их всего один раз (до и после цикла соответственно). Такая пакетная обработка обычно реализуется методами типа BeginUpdate/EndUpdate. Метод BeginUpdate устанавливает флаг "идёт пакетная операция" и выполняет подготовительные действия (если они есть), а метод EndUpdate сбрасывает флаг и выполняет финализацию. Соответственно, каждая операция проверяет флаг и, если он установлен, пропускает подготовку/финализацию. Поскольку Delphi является RAD средой для GUI программ, то самое типичное место, где вы встретите этот приём - блокировка прорисовки пользовательского интерфейса на время обработки элементов. Таким образом, это ещё один пример кода, который никогда не выполняется.

Одна из вариаций "покупать оптом - дешевле"/"пакетной обработки" - вызовы функций ядра, а именно - чрезмерно частые вызовы функций ядра. Дело в том, что вызов функции ядра (обычно это функции из kernel32/ntdll) требует переключения аппаратного режима процессора в режим ядра и переключения адресных пространств, что занимает очень много времени (по меркам процессора, понятно). Соответственно, вы можете существенно ускорить выполнение кода, если будете собирать данные в кучу, а затем делать единственный вызов функции ядра, вместо многих. Обычно это применимо к разнообразным функциям ввода-вывода. Типичный пример - не читать файл побайтово, а читать блоками. Ещё лучше - использовать проекцию файла.

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

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

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

Наконец, у нас всегда есть микрооптимизации (векторизация, смешение сложения и умножения для загрузки конвейера, замена долгих инструкций более быстрыми, упаковка и выравнивание данных, ошибки страниц и попадания в кэш, уменьшение ветвлений и т.д.). Я не буду их рассматривать в этой статье. Почти всегда, если вы добираетесь до этого этапа, вы уже значительно оптимизировали задачу, так что применение микрооптимизаций (и ассемблерного кода) не даст значительного выигрыша в скорости для 90% задач, обычно решаемых прикладными программистами на Delphi. Тем более, что тема это обширная и непростая - в одной этой статье (которая, к тому же, вводная) рассмотреть ещё и это не получится. Кроме того, какие-то базовые вещи вроде замены умножения сдвигами оптимизирующий компилятор может выполнить и сам (хотя в Delphi он, скажем честно, "не фонтан"). Поэтому интересующихся отправляю гуглить. Можете попробовать начать отсюда или с книг вроде таких:

Оптимизация ПО. Сборник рецептов | Ричард Гербер, Арт Бик, Кевин Смит, Ксинмин Тиан | ISBN 978-5-388-00131-3, 0976483211Оптимизация ПО. Сборник рецептов | Ричард Гербер, Арт Бик, Кевин Смит, Ксинмин Тиан | ISBN 978-5-388-00131-3, 0976483211
Техника оптимизации программ. Эффективное использование памяти | Крис Касперски | ISBN 5-94157-232-8Техника оптимизации программ. Эффективное использование памяти | Крис Касперски | ISBN 5-94157-232-8

Заключение

Итак, в этой вводной статье я попробовал рассказать про оптимизацию Delphi программ, рассказать про типичные ошибки и что нужно делать. Суммируя всё вышесказанное, делать вам нужно это:
  1. Профилирование
  2. Алгоритмическая оптимизация
  3. Архитектурно-независимая оптимизация
  4. Архитектурно-ориентированная оптимизация ("микрооптимизация")
Иными словами, оптимизировать надо сверху-вниз, а не наоборот.

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

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

15 комментариев :

  1. Спасибо за статью. Когда-то писал мод, на Pawn, для мультиплеера Gta - San Andreas, так вот каждый кто просил помощи на форуме сразу начинался срач, мол "ты нуб, зачем лезешь? ты не оптимизировал даже код". Каждый второй пользователь форума был болен этой оптимизацией. Часто мысли о преждевременной оптимизации мешают составлению основного алгоритма.

    ОтветитьУдалить
  2. Я раньше думал, что при включченной оптимизации, компилятор самостоятельно выполняет оптимизации типа "вынесения общей переменной из цикла" или "замена сложного выражения локальной переменной". И лишь недавно узнал, что это было довольно наивно.

    Кстати, для обнаружения возможных мест для оптимизации, может помочь встроенная в IDE функция "Audits & Metrics". Как минимум, она умеет находить места, где можно упростить цикл и сделать код понятнее. Правда, для того, чтобы прочуствовать всю силу (и некоторую глючноть) этой функции, нужна Architect или Enterprise редакция Delphi.

    ОтветитьУдалить
  3. Кстати об AqTime и исключении VCL функций из профайлера.

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

    Единстенное подозрение падало на функцию сохранения/загрузки размеров форм (и кое-каких других данных) в TIniFile. Как мне сначала показалось, это никак не могло заметно повлиять на производительность. Но всё же решил проверить профайлером. Оказалось, что больше всего времени в функции загрузки/сохранения потребляли именно WinApi функции чтения/записи в ini файл (TIniFile - это просто обёртка над стандатртными windows функциями для работы с Ini-файлом). Тут же захотелось сравнить, а не будет ли быстрее работать с TMemIniFile (реализация на чистом Delphi). Заменил код, прогнал профайлером. Оказалось, что да, TMemIniFile работает гораздо-гораздо быстрее. Выкатил новый апдейт. И, таки да, недовольные пользователи подтвердили, что формы стали открываться заметно быстрее.

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

    Но это так, редкий случай.

    ОтветитьУдалить
  4. А ты бесплатный AQTime использовал? Pro-шка же показывает строки, и там сразу будет видно, что вызов такой-то строки (работа с ini) занимает много времени. Да если даже и бесплатную - если работа с ini в отдельной процедуре, то всё на неё укажет.

    Кстати, это пример оптимизации "оптом - дешевле". Read/WritePrivateProfileString в Win32/Win64 вынуждена на каждый вызов заново открывать файл, заново парсить его, заново искать значение. Это было не так страшно в Win16, где была вытесняющая многозадачность, и поэтому можно было кэшировать представление в памяти до момента передачи управления другой программе. Ну а TMemIniFile может один раз открыть и распарсить файл, а затем работать с представлением в памяти. Короче, типа BeginUpdate/EndUpdate получается.

    ОтветитьУдалить
  5. >А ты бесплатный AQTime использовал?
    Платный использовал. Но суть не в этом.

    А в том, что AQTime меня тогда как раз и показал, то, что функции Read/WritePrivateProfileString (точно не помню и мне сейчас лень смотреть какие там функции тогда были, поэтому предположу, что именно эти=)) съедают больше всего времени. И уже копая от этиъ функций в обратную сторону через дерево вызовов в том же AqTime я докопался до своего кода (точнее, там использовался чужой компонент (Ehlib-овский), который и использовал TIniFile).

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

    На поиски решения меня насторожил именно тот факт, что функции Read/WritePrivateProfileString выполнялись для каждой формы по несколько раз и занимали при этом довольно много времени.

    С тех пор, кстати, везде где нужна работа с ini-файлами, предпочитаю использовать TMemIniFile вместо TIniFile.

    ОтветитьУдалить
  6. Довольно интересная тема, поделюсь своим небольшим примером

    Я использовал базовый AQTime в XE2, но позже понял, что сделать свой мини-профайлер не составит большого труда (конкретно под нужные цели).

    ОтветитьУдалить
  7. Поддерживаю, я - за профайлер. Правда в простых случаях, я частенько расставляю в контрольных точках банальный GetTickCount и вывод результатов в лог...

    ОтветитьУдалить
  8. Ну, в общем-то, смысл поста был не в том, что надо использовать именно AQTime, а в том, чтобы использовать хоть какие-то измерения. В частности, GetTickCount/QueryPerformanceCounter - это и есть примитивный профайлер.

    ОтветитьУдалить
  9. Хорошая статья. А я для определения узкого места использую такой прием: если во время исполнения долгого кода нажать паузу то с высокой долей вероятности попадешь именно в тормозящий код, часто этого достаточно.

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

    С этим моментом рискну не согласиться.
    Замена массива объектов на массив записей (в delphi) в случае часто вызываемых функций поиска (сотни тысяч раз) может существенно ускорить работу.
    Профилировал программу, использовал GpProfile. По отчету профайлера немалое время занимали вызовы поиска по кэшу из двух десятков объектов. Заменил список объектов (TObjectList) на массив записей из ключа поиска и ссылки на объект, и искал теперь по этому массиву, не обращаясь при поиске непосредственно к объектам. Скорость программы выросла в десять раз.
    В другой еще более часто вызываемой функции тоже нужный объект искался по нескольким ключам (Integer). Здесь замена трех независимых массивов на один массив записей увеличила скорость всей программы в пятьдесят раз. Причем пока массивов было два, программа работала не так уж медленно.

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

    ОтветитьУдалить
  11. Имелось в виду только следующее: далеко разнесённые по виртуальной памяти блоки могут оказаться рядом в физической памяти и поэтому быть выбраны в кэш как последовательные. Я просто встречал советы, которые, похоже, явно не учитывают что прикладные программы работают с виртуальной памятью, а не физической.

    Но, конечно, я не говорю, что улучшать локальность вообще не нужно.

    ОтветитьУдалить
  12. Кстати, кажется начиная с XE или XE2, появился модуль System.Diagnostics, и там есть секундомер TStopWatch. Очень удобная обёртка над GetTickCount, QueryPerformanceCounter.

    Просто вызвать .StartNew ... .Stop, а затем посмотреть Elapsed: TTimeSpan (операторы Implicit и Explicit перегружены, чтобы сразу выдавать строку)

    ОтветитьУдалить
  13. AQTime -- один из самых ценных инструментов. Довольно часто находит такие узкие места, которые никогда и в голову не придут при "ручной" оптимизации.

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

    Кстати, настроить колонки от профилировщика в делфи можно -- надо щелкнуть правой кнопкой по этим колонкам и выбрать пункт "Profile" -> "Customize" -- откроется окно, где можно галочками указать, какие колонки показывать рядом с кодом.

    Более того, если делать отладку в отдельном приложении AQTime, а не в делфи, то дополнительно можно выбирать формат отображения тех значений, что рядом с кодом -- например, в виде прогресс-бара (чем больше величина, тем он длиннее) -- что очень удобно и наглядно (см. скриншот: https://dl.dropbox.com/u/6645734/CloudShot/shot_25012013_182150.png )

    ОтветитьУдалить

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и (опционально) ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку (поддерживается OpenID).

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

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