Время является наиболее значимым индикатором.
Именно поэтому большинство профилировщиков по умолчанию используют время измерения / выборки или тактовые частоты ядра.Понимание того, где ваш код тратит свое время, является важным первым шагом к поиску ускорений. Сначала выясните что такое медленно, а затем выясните почему это медленно .
Существует два принципиально различных вида ускорений, которые вы можете искать,и время поможет вам найти их обоих.
Алгоритмические улучшения: в первую очередь, поиск способов выполнять меньше работы .Часто это самый важный вид, и на нем фокусируется ответ Майка Данлавей.Вы должны определенно не игнорировать это.Кэширование результата, который медленно пересчитывается, может стоить того, особенно если он достаточно медленный, чтобы загрузка из DRAM все еще была быстрее.
Использование структур данных / алгоритмов, которые могут более эффективно решить вашу проблему на реальных процессорах, находится где-то междуэти два вида ускорений.(например, связанные списки на практике часто медленнее, чем массивы, поскольку задержка погони за указателем является узким местом, если только вы не копируете большие массивы слишком часто ...)
Применение грубой обработкизаставить более эффективно выполнять ту же работу за меньшее количество циклов .(И / или более дружественный к остальной части программы с меньшим объемом кэша и / или меньшим количеством ветвлений, которые занимают место в предикторах ветвления, или что-то в этом роде.)
Часто включает в себя изменение макета данных, чтобы он стал больше кешадружественный и / или ручной векторизации с SIMD.Или делать это умнее.Или написание функции, которая обрабатывает общий особый случай быстрее, чем ваша обычная функция.Или даже ручной компилятор для создания лучшего ассемблера для вашего источника C.
Рассмотрите возможность суммирования массива float на современном x86-64: переход от скалярного сложения с привязкой ко времени ожидания до AVX SIMD с несколькими аккумуляторами можетдает ускорение 8 (элементов на вектор) * 8 (задержка / пропускная способность на Skylake) = 64x для массива среднего размера (все еще на одном ядре / потоке), в теоретическом лучшем случае, когда вы не сталкиваетесьдругое узкое место (например, пропускная способность памяти, если ваши данные не находятся в кеше L1d).Skylake vaddps / vaddss имеет задержку в 4 цикла, а обратная пропускная способность 2 на такт = 0,5 с.(https://agner.org/optimize/). Почему mulss занимает только 3 цикла в Haswell, в отличие от таблиц инструкций Агнера? , чтобы больше узнать о множественных аккумуляторах, чтобы скрыть задержку FP. Но это все равно теряет силу по сравнению с хранением итогового значения где-тои, возможно, даже обновляя итоговое значение с помощью дельты при изменении элемента. (Ошибка округления FP может накапливаться таким образом, в отличие от целых чисел.)
Если вы неНе вижу очевидного улучшения алгоритма или хотите узнать больше, прежде чем вносить изменения, проверьте, не останавливается ли процессор на чем-либо, или проверяет эффективность, выполняя всю работу, которую выполняет компилятор.
Instructions per clock (IPC) сообщает вам, близок ли процессор к своей максимальной пропускной способности или нет (или, точнее, мупы слитого домена, выданные за такт на x86, потому что, например, одна инструкция rep movsb является целойбольшой memcpy и декодирует много-много мопов. И cmp / jcc перегорает от 2-х инструкций до 1 моп, увеличивая IPC, но pipeliШирина по-прежнему фиксирована.)
Работа, выполняемая для каждой инструкции, также является фактором, но это не то, что вы можете измерить с помощью профилировщика : если у вас есть опыт, посмотрите на сгенерированный компилятором asm, чтобы увидеть, работает ли та же самая сменьше инструкций возможно.Если компилятор не выполнял автоматическую векторизацию или делал это неэффективно, возможно, вы можете выполнить намного больше работы для каждой инструкции, вручную векторизовав встроенные функции SIMD, в зависимости от проблемы.Или удерживая компилятор в лучшем выпуске asm, настраивая исходный код C для вычисления вещей естественным для asm способом.например, Каков эффективный способ подсчета установленных бит в позиции или ниже? .И посмотрите также C ++ код для проверки гипотезы Коллатца быстрее, чем рукописная сборка - почему?
Если вы обнаружите низкий IPC, выясните, почему byс учетом таких возможностей, как пропадание кеша или ветвления, или длинные цепочки зависимостей (часто причина низкого IPC, когда нет узких мест во внешнем интерфейсе или в памяти).
Или вы можете обнаружить, что это уже близко к оптимальному применениюдоступна грубая сила процессора (маловероятно, но возможно для некоторых проблем).В этом случае ваша единственная надежда - алгоритмические улучшения, чтобы выполнять меньше работы.
(частота процессора не фиксирована, но тактовые частоты ядра - хороший прокси. Если ваша программа не тратит время на ожидание ввода / вывода, тогда такты ядра могут быть больше полезными для измерения.)
Трудно обнаружить в основном последовательную часть многопоточной программы ;большинство инструментов не имеют простого способа найти потоки, используя циклы, когда другие потоки заблокированы.
Время, потраченное на функцию, не является показателем only . Функция может замедлить работу остальной части программы, коснувшись большого количества памяти , что приведет к вытеснению других полезных данных из кэша.Такого рода эффект возможен.Или наличие большого количества ветвей где-то может занимать некоторую часть способности ЦП к прогнозированию ветвлений, что приводит к большему количеству пропусков ветвей в других местах.
Но учтите, что просто найдите, куда расходует процессорвыполнение большого количества времени не самое полезное, в большой кодовой базе, где функции, содержащие горячие точки, могут иметь несколько вызывающих.Например, большое количество времени, проведенного в memcpy, не означает, что вам нужно ускорить работу memcpy, это означает, что вам нужно найти, какой вызывающий абонент часто вызывает memcpy.И так далее, создайте резервную копию дерева вызовов.
Используйте профилировщики, которые могут записывать снимки стека , или просто нажмите control-C в отладчике и посмотрите на стек вызовов несколько раз.Если определенная функция обычно появляется в стеке вызовов, она совершает дорогостоящие вызовы.
Related: linux perf: как интерпретировать и находить «горячие точки» , особенно в ответе Майка Данлавей, который подчеркивает это.
Алгоритмические усовершенствования, позволяющие вообще не выполнять работу, зачастую гораздо ценнее, чем выполнять ту же работу более эффективно.
Но если вы обнаружите очень низкий IPC для какой-то работы, вы не поймете,Как избежать этого, тогда обязательно посмотрите на перестановку структур данных для лучшего кэширования или избежание ошибочных прогнозов ветвлений.
Или, если высокий IPC все еще занимает много времени, ручная векторизация цикла может помочь, выполнив4x или более работы за инструкцию.