Искусство программирования для Unix - Эрик Реймонд

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

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

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

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

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

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

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

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

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

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

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

Это меняет некоторые традиционные советы на прямо противоположные. Оптимизация компилятора, подобная развертке цикла, которая освобождает сравнительно дорогие машинные инструкции в обмен на увеличение общего размера кода, может оказаться более нецелесообразной. Другим примером является предвычисление небольших таблиц — например, таблица значений функции sin(x) от величины угла для оптимизации вращения в ядре 3D графики потребует на современной машине 365×4 байт. До того как процессоры стали быстрее, чем память, чтобы требовать кэширования, это было очевидной оптимизацией скорости. В настоящее время, возможно, быстрее будет пересчитывать результаты каждый раз, чем расплачиваться за дополнительные потери кэша, вызванные хранением таблицы.

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

12.4. Пропускная способность и задержка

Другим последствием использования быстрых процессоров является то, что производительность обычно ограничивается затратами на I/O-операции и (особенно в случае программ, использующих Internet) затратами на сетевые транзакции. Следовательно, разработчику полезно знать, как проектировать сетевые протоколы для достижения высокой производительности.

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

О задержке я могу сказать не много. Версия X11 далеко "оторвалась" от Х10 в предотвращении полных циклов обращения: Render-расширение уходит еще дальше. X (и в настоящее время HTTP/1.1) является протоколом потоковой передачи. Например, мой портативный компьютер способен выполнять более 4 млн. прямых запросов (8 млн. холостых запросов) в секунду. Однако полные циклы "запрос-ответ" в сотни или тысячи раз дороже. Каждый раз, когда клиент может выполнить какую-либо операцию, не обращаясь к серверу, является огромным выигрышем.

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

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