Искусство программирования для Unix

Реймонд Эрик Стивен

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

12.2. Измерения перед оптимизацией

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

Читателям следует

вспомнить шесть правил Роба Пайка, описанных в главе 1. Один из первых уроков, который усвоили программисты Unix, заключается в том, что интуиция — неверный советчик при определении местоположения "бутылочных горлышек", причем даже для того, кто очень хорошо знает свой код. Unix-системы, в отличие от большинства других операционных систем, обычно поставляются вместе с профайлерами (profiler — подпрограмма протоколирования), и их стоит использовать.

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

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

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

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

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

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

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

Более важно то, что многие средства учета времени создают такое впечатление, будто время, затраченное на подпрограммы, относится к вызывающей программе. (Данная особенность характерна для профайлера gprof(1), распространяемого в составе Unix-систем с открытыми исходными кодами). Простое вычитание времени вызываемой программы из времени вызывающей не даст достоверных результатов, если одну и ту же программу могут вызывать несколько других программ — результатом было бы искусственное сокращение времени всех вызывающих программ. Особенно опасным является распространенный случай функции с несколькими узлами вызова, одни из которых создают множество простейших вызовов, а другие создают несколько сложных.

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

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

Естественное сглаживание данных, определяемое моделью, характеризуется выявлением главных факторов и пренебрежением второстепенных, связанных с шумом. Например, при использовании кубической модели в подпрограмме обращения матрицы в MATHLAB на случайных матрицах от 10×10 до 1000×1000, очевидно, что фактически получается 3 куба с четко определенными границами, которые примерно соответствуют областям "в кэше", "в памяти, но вне кэша" и "вне памяти". Данные демонстрируют такой эффект, даже если не искать его, а просто изучать отклонения от наилучших результатов.

Стив Джонсон.

12.3. Размер кода

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

Рассмотрим целевую машину как иерархию типов памяти, упорядоченных по удаленности от процессора. Она включает в себя собственные регистры процессора; его конвейер инструкций; кэш первого уровня (L1); кэш второго уровня (L2); вероятно, кэш третьего уровня (L3); оперативная память (которая среди специалистов старой школы Unix до сих пор изящно называется основой (core)); и дисковые накопители, на которых располагается область подкачки. Такие технологии, как SMP, кластеры с общей памятью и технология доступа к неоднородной памяти (Nonuniform Memory Access — NUMA) добавляют больше уровней в картину, но только расширяют общий разброс.