Как проанализировать время выполнения программы

Question

Я пытаюсь оптимизировать производительность программы на C++ и сократить время ее выполнения. Тем не менее, у меня возникают проблемы с выяснением, где находится узкое место.

Команда time показывает, что запуск самой программы занимает около 5 минут, а около 5 минут пользовательское процессорное время занимает 4,5 минуты.

Профилировщик ЦП (как gcc profiler, так и google perftool) показывает, что вызовы функций занимают всего 60 секунд всего процессорного времени. Я также попытался использовать профилировщик для выборки в реальном времени вместо процессорного времени, и это дает мне похожие результаты.

Профилировщик ввода / вывода (я использовал ioapps) также показывает, что ввод / вывод занимает всего около 30 секунд времени выполнения программы.

Таким образом, в основном у меня не учтено 3,5 минуты (наибольшая часть времени выполнения программы), и я считаю, что именно в этом и заключается узкое место.

Что я пропустил и как мне узнать, куда уходит это время?

Answer 1

Как предложил Öö Tiib, просто разбейте программу в отладчике. То, как я это делаю, это запускаю программу, переключаюсь в окно вывода, набираю Ctrl-C, чтобы прервать программу, переключаюсь обратно в окно GDB, печатаю "thread 1", чтобы быть в контексте основной программы, и введите "bt", чтобы увидеть трассировку стека.

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

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

<пламя>

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

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

А как насчет вопроса малого или большого количества образцов? Не лучше ли? Хорошо, предположим, у вас есть бесконечный цикл, или, если не бесконечный, он просто работает намного дольше, чем вы знаете, что должен? Будет ли 1000 образцов стека найти это лучше, чем один образец? (Нет.) Если вы посмотрите на это в отладчике, вы поймете, что находитесь в цикле, потому что это занимает в основном 100% времени. Это где-то в стеке - просто сканируйте стек, пока не найдете его. Даже если цикл занимает только 50% или 20% времени, это вероятность того, что каждый образец увидит его. Итак, если вы видите что-то, от чего вы можете избавиться всего за два образца, стоит сделать это. Итак, что покупают 1000 образцов?

Может быть, кто-то думает: "А что, если мы пропустим одну или две проблемы? Может, это достаточно хорошо". Ну так что? Предположим, что в коде есть три проблемы: P занимает 50% времени, Q - 25% и R - 12,5%. Хороший материал называется A. Он показывает ускорение, которое вы получаете, если вы исправите один из них, два или все три.

PRPQPQPAPQPAPRPQ original time with avoidable code P, Q, and R all mixed together
RQQAQARQ         fix P           - 2 x   speedup
PRPPPAPPAPRP     fix Q           - 1.3 x    "
PPQPQPAPQPAPPQ   fix R           - 1.14 x   "
RAAR             fix P and Q     - 4 x      "
QQAQAQ           fix P and R     - 2.7 x    "
PPPPAPPAPP       fix Q and R     - 1.6 x    "
AA               fix P, Q, and R - 8 x   speedup

Это дает понять, почему те, которые "уходят", действительно причиняют боль? Лучшее, что вы можете сделать, если пропустите, - это в два раза медленнее.

Их легко найти, если вы исследуете образцы. Примерно на половине образцов. Если вы исправите P и сделаете это снова, Q будет на половине выборок. Как только вы исправите Q, R будет на половине выборок. Исправьте R, и вы получите 8-кратное ускорение. Вам не нужно останавливаться на достигнутом. Вы можете продолжать идти, пока действительно не сможете найти что-то, что можно исправить.

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

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

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