Каковы хорошие стратегии для улучшения производительности моего кода?

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

Давайте предположим, что я оценил соотношение производительности и читаемости / возможности повторного использования / обслуживания программного обеспечения, над которым я работаю, и решил, что пришло время повысить производительность. Давайте также предположим, что я знаю, что у меня нет лучшего алгоритма для моей проблемы (с точки зрения флопа / с и пропускной способности памяти). Вы также можете предположить, что моя кодовая база написана на низкоуровневом языке, таком как C, C ++ или Fortran. Наконец, давайте предположим, что в коде нет параллелизма или что нас интересует производительность только на одном ядре.

Какие самые важные вещи попробовать в первую очередь? Как я могу узнать, сколько производительности я могу получить?

Во-первых, как отметили специалисты и Дэн , профилирование необходимо. Я лично использую Intel VTune Amplifier в Linux, так как он дает мне очень детальный обзор того, где и на что было потрачено время.

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

• Локализация памяти : данные, которые считываются / используются вместе, также хранятся вместе, или вы собираете кусочки здесь и там?

• Выравнивание памяти : действительно ли ваши двойники выровнены до 4 байтов? Как вы упаковали structs? Чтобы быть педантичным, используйте posix_memalignвместо malloc.

• Эффективность кэширования : локальность решает большинство проблем эффективности кэширования, но если у вас есть небольшие структуры данных, которые вы часто читаете / пишете, это помогает, если они являются целочисленным кратным или частью строки кэша (обычно 64 байта). Это также помогает, если ваши данные выровнены по размеру строки кэша. Это может значительно сократить количество операций чтения, необходимых для загрузки фрагмента данных.

• Векторизация : Нет, не сходите с ума с помощью ассемблера, закодированного вручную. gccпредлагает векторные типы, которые автоматически переводятся в SSE / AltiVec / любые другие инструкции.

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

• Арифметическая точность : вам действительно нужна арифметика двойной точности во всем, что вы делаете? Например, если вы вычисляете поправку в итерации Ньютона, вам обычно не нужны все цифры, которые вы вычисляете. Для более глубокого обсуждения см. Эту статью.

Некоторые из этих трюков используются в daxpy_cvec этой теме. Сказав это, если вы используете Fortran (не язык низкого уровня в моих книгах), вы будете иметь очень мало контроля над большинством этих "уловок".

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

Обновить

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

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

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

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

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

Кроме того, будьте готовы к тому, что CS скажет: « эта проблема уже решена », и просто дайте вам ссылку на статью. Совет: прочитайте эту статью и, если она действительно имеет отношение к вашей проблеме, примените любой предложенный алгоритм. Это не CS самодовольный, это CS, который просто помог вам. Не обижайтесь, помните: если проблема неинтересна в вычислительном отношении, т. Е. Она уже решена и решение показано оптимальным, они не будут работать над ним, тем более кодируют его для вас.

В связи с этим помните, что большинство CS не являются экспертами в своей области, и объясните проблему с точки зрения того, что вы делаете, а не как и почему . Мы обычно действительно не заботимся о том, почему и как , ну, что мы делаем лучше всего.

Например, в настоящее время я работаю с группой компьютерных космологов над написанием лучшей версии их кода моделирования, основанного на SPH и Multipoles . Потребовалось около трех встреч, чтобы перестать говорить с точки зрения темной материи и гало галактик (да?) И углубиться в суть вычислений, то есть, что им нужно найти всех соседей в пределах данного радиуса каждой частицы, вычислить некоторые количество над ними, а затем снова обойти всех упомянутых соседей и применить это количество в некоторых других вычислениях. Затем переместите частицы или, по крайней мере, некоторые из них, и сделайте все это снова. Видите ли, хотя первое может быть невероятно интересным (это так!), Последнее - это то, что мне нужно понять, чтобы начать думать об алгоритмах.

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

Научное программное обеспечение мало чем отличается от другого программного обеспечения в том, что касается того, как узнать, что нужно настраивать.

Метод, который я использую, является случайной паузой . Вот некоторые из ускорений, которые он нашел для меня:

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

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

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

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

Если я могу просто расширить последнее: подпрограмма умножения матриц DGEMM вызывает LSAME для декодирования своих символьных аргументов. Если посмотреть на процентные показатели по времени (единственная статистика, на которую стоит обратить внимание), профилировщики, считающиеся «хорошими», могут показать, что DGEMM использует некоторый процент от общего времени, например, 80%, и LSAME, используя некоторый процент общего времени, например, 50%. Глядя на первое, вы испытаете искушение сказать: «Что ж, это должно быть сильно оптимизировано, поэтому я мало что могу с этим поделать». Глядя на последнее, у вас возникнет соблазн сказать: «А? О чем это все? Это просто крошечная рутина. Этот профилировщик должен ошибаться!»

Это не так, это просто не говорит вам, что вам нужно знать. Случайная пауза показывает, что DGEMM находится на 80% выборок стека, а LSAME - на 50%. (Вам не нужно много образцов, чтобы обнаружить это. Обычно 10 достаточно.) Более того, во многих из этих примеров DGEMM находится в процессе вызова LSAME из пары разных строк кода.

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

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

ДОБАВЛЕНО: Итак, чтобы ответить на два последних вопроса:

Какие самые важные вещи попробовать в первую очередь?

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

Как я могу узнать, сколько производительности я могу получить?

Образцы стека дадут вам очень приблизительную оценку того, какая доля времени будет сохранена. (Он следует за распределением , где - это количество выборок, которые отображают то, что вы собираетесь исправить, а - общее количество выборок. стоимость кода, который вы использовали для его замены, который, будем надеяться, будет небольшим.) Тогда коэффициент ускорения будет который может быть большим. Обратите внимание, как это ведет себя математически. Если и , среднее значение и мода равны 0,5 для коэффициента ускорения 2. Вот распределение: если вы не склонны к риску, то да, вероятность мала (0,03%) это$x$$\beta(s+1,(n-s)+1)$$s$$n$$1/(1-x)$$n=10$$s=5$$x$

$x$ меньше 0,1, для ускорения менее 11%. Но балансировка - это равная вероятность того, что больше 0,9, а коэффициент ускорения больше 10! Если вы получаете деньги пропорционально скорости программы, это неплохо.$x$

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

ДОБАВЛЕНО: В ответ на беспокойство Педро по поводу ложных срабатываний, позвольте мне попытаться построить пример, где они могут произойти. Мы никогда не решаем потенциальную проблему, если не видим ее два или более раз, поэтому мы можем ожидать ложных срабатываний, когда видим проблему как можно меньше раз, особенно когда общее количество выборок велико. Предположим, мы берем 20 образцов и видим его дважды. То есть его стоимость составляет 10% от общего времени выполнения, способа его распространения. (Среднее значение распределения выше - оно составляет .) Нижняя кривая на следующем графике - это распределение:$(s+1)/(n+2)=3/22=13.6\%$

Подумайте, взяли ли мы целых 40 образцов (больше, чем я когда-либо имел) и увидели проблему только в двух из них. Расчетная стоимость (режим) этой проблемы составляет 5%, как показано на более высокой кривой.

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

Существует гораздо более серьезный риск - «ложный негатив». Это когда есть проблема, но она не найдена. (Этому способствует «предвзятость подтверждения», когда отсутствие доказательств обычно рассматривается как доказательство отсутствия.)

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

Я хотел бы призвать пользователей профилировщиков сообщать о факторах ускорения, которые они фактически получают на практике.

Есть еще один момент, который нужно сделать повторно. Вопрос Педро о ложных срабатываниях.

Он упомянул, что могут возникнуть трудности при рассмотрении небольших проблем в высоко оптимизированном коде. (Для меня небольшая проблема - это та, которая составляет 5% или менее от общего времени.)

Поскольку вполне возможно построить программу, которая является полностью оптимальной, за исключением 5%, этот вопрос может быть решен только эмпирически, как в этом ответе . Чтобы обобщить из эмпирического опыта, это выглядит так:

Программа, как написано, обычно содержит несколько возможностей для оптимизации. (Мы можем назвать их «проблемами», но они часто представляют собой совершенно хороший код, просто способный к значительному улучшению.) Эта диаграмма иллюстрирует искусственную программу, занимающую некоторое время (скажем, 100 с), и она содержит проблемы A, B, C, ... что при обнаружении и исправлении сэкономите 30%, 21% и т. д. от первоначальных 100-х.

Обратите внимание, что проблема F стоит 5% от первоначального времени, поэтому она «маленькая», и ее трудно найти без 40 или более выборок.

Тем не менее, первые 10 выборок легко обнаруживают проблему А. ** Когда это исправлено, программе требуется всего 70 секунд для ускорения 100/70 = 1,43x. Это не только ускоряет выполнение программы, но и увеличивает пропорционально процентное соотношение оставшихся проблем. Например, для задачи B первоначально потребовалось 21 с, что составляло 21% от общего числа, но после удаления A, B отнимает 21 с из 70 с, или 30%, поэтому легче определить, когда весь процесс повторяется.

После того, как процесс повторяется пять раз, теперь время выполнения составляет 16,8 с, из которых проблема F составляет 30%, а не 5%, так что 10 выборок легко это находят.

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

Если проблемы с A по F обнаружены и устранены, ускорение составляет 100 / 11,8 = 8,5x. Если один из них пропущен, например, D, то ускорение составляет всего 100 / (11,8 + 10,3) = 4,5x. Это цена, заплаченная за ложные негативы.

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

** Требуется минимум 2 попадания по задаче, чтобы найти ее, если не известно, что существует (почти) бесконечный цикл. (Красные галочки представляют 10 случайных образцов); Среднее количество выборок, необходимых для получения 2 или более совпадений, когда проблема составляет 30%, составляет ( отрицательное биномиальное распределение ). 10 образцов находят его с вероятностью 85%, 20 образцов - 99,2% ( биномиальное распределение ). Для того, чтобы получить вероятность обнаружения проблемы, в R, оценить , например: .$2/0.3=6.67$1 - pbinom(1, numberOfSamples, sizeOfProblem)1 - pbinom(1, 20, 0.3) = 0.9923627

ДОБАВЛЕНО: доля сэкономленного времени соответствует бета-распределению , где - количество выборок, а - число, отображающее проблему. Однако коэффициент ускорения равен (при условии, что все сохранены), и было бы интересно понять распределение . Оказывается, следует за дистрибутивом BetaPrime . Я смоделировал это с 2 миллионами образцов, получая это поведение:β ( s + 1 , ( n - s ) + 1 ) n s y 1 / ( 1 - x ) x y y - $x$$\beta(s+1,(n-s)+1)$$n$$s$$y$$1/(1-x)$$x$$y$$y-1$

         distribution of speedup
               ratio y

 s, n    5%-ile  95%-ile  mean
 2, 2    1.58    59.30   32.36
 2, 3    1.33    10.25    4.00
 2, 4    1.23     5.28    2.50
 2, 5    1.18     3.69    2.00
 2,10    1.09     1.89    1.37
 2,20    1.04     1.37    1.17
 2,40    1.02     1.17    1.08

 3, 3    1.90    78.34   42.94
 3, 4    1.52    13.10    5.00
 3, 5    1.37     6.53    3.00
 3,10    1.16     2.29    1.57
 3,20    1.07     1.49    1.24
 3,40    1.04     1.22    1.11

 4, 4    2.22    98.02   52.36
 4, 5    1.72    15.95    6.00
 4,10    1.25     2.86    1.83
 4,20    1.11     1.62    1.31
 4,40    1.05     1.26    1.14

 5, 5    2.54   117.27   64.29
 5,10    1.37     3.69    2.20
 5,20    1.15     1.78    1.40
 5,40    1.07     1.31    1.17

Первые два столбца дают 90% доверительный интервал для коэффициента ускорения. Средний коэффициент ускорения равен за исключением случая, когда . В этом случае оно не определено, и, по мере того, как я увеличиваю количество моделируемых значений , эмпирическое среднее значение увеличивается.s = n $(n+1)/(n-s)$$s=n$$y$

Это график распределения факторов ускорения и их средних значений для 2 попаданий из 5, 4, 3 и 2 выборок. Например, если взять 3 выборки, и 2 из них являются попаданиями в проблему, и эту проблему можно устранить, средний коэффициент ускорения будет равен 4x. Если 2 попадания видны только в 2 выборках, среднее ускорение не определено - концептуально, поскольку программы с бесконечными циклами существуют с ненулевой вероятностью!

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

Что может повлиять на производительность?

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

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

Даже если целевая архитектура не изменяется, изменения уровня операционной системы также могут повлиять на производительность. Исправления «Спектр» и «Расплавление» оказали огромное влияние на некоторые рабочие нагрузки, поэтому они могут привести к переоценке ваших оптимизаций.

Как я могу сохранить мой код оптимизированным?

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

Модульность также означает возможность использовать один и тот же набор тестов на всех ваших оптимизированных и unoptimised версий, что позволяет убедиться , что все они ведут себя так же и профиль каждого из них быстро в как на, как сравнение. Я немного подробнее расскажу в своем ответе на Как задокументировать и научить других «оптимизированному до неузнаваемости» вычислительно интенсивному коду? ,

дальнейшее чтение

Кроме того, я бы настоятельно рекомендовал взглянуть на превосходную статью Ульриха Дреппера « Что каждый программист должен знать о памяти» , название которой - дань уважения столь же фантастической статье Дэвида Голдберга « Что должен знать каждый компьютерщик об арифметике с плавающей точкой» .

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

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

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

Linux

gprof довольно хорош, но он говорит только о том, сколько времени занимает каждая функция, а не каждая строка.

Apple OS X

Вы можете попробовать Акулу . Он доступен на сайте Apple Developer в разделе «Загрузки»> «Инструменты разработчика»> CHUD 4.6.2, более старая версия здесь . CHUD также содержит другие инструменты профилирования, такие как интерфейс BigTop, инструмент поиска индекса PMC, профилировщик уровня функций Saturn и множество других команд. Акула придет с версией командной строки.

Что касается производительности, которую вы можете получить, возьмите результаты профилирования вашего кода и, скажем, вы идентифицируете часть, которая занимает «p» часть времени. Если бы вы улучшили производительность этой части только с коэффициентом «s», ваше общее ускорение составило бы 1 / ((1-p) + p / s). Поэтому вы можете максимально увеличить свою скорость в 1 / (1-р) раз. Надеюсь, у вас есть области с высоким р! Это эквивалент закона Амдала для последовательной оптимизации.

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

1. По возможности используйте высокооптимизированные (или профессионально оптимизированные) библиотеки. Некоторые примеры могут включать FFTW, OpenBlas, Intel MKL, библиотеки NAG и т. Д. Если вы не очень талантливы (как разработчик GotoBLAS), вы, вероятно, не сможете победить профессионалов.

2. Используйте профилировщик (довольно много в следующем списке уже были названы в этой теме - Intel Tune, valgrind, gprof, gcov и т. Д.), Чтобы узнать, какие части вашего кода занимают больше всего времени. Нет смысла тратить время на оптимизацию фрагментов кода, которые вызываются редко.

3. Из результатов профилировщика посмотрите на часть кода, которая заняла больше всего времени. Определите, какова природа вашего алгоритма - это процессор или память? Каждый требует различного набора методов оптимизации. Если вы получаете много кеш-памяти, узкая часть может быть в памяти - процессор тратит такты, ожидая, когда память станет доступной. Подумайте, подходит ли цикл к кэшу L1 / L2 / L3 вашей системы. Если в вашем цикле есть операторы if, проверьте, говорит ли профилировщик что-либо о неверном прогнозе ветвления? Какое наказание за неправильное прогнозирование ветки в вашей системе? Кстати, вы можете получить данные о неправильном прогнозе ветвления из Справочного руководства по оптимизации Intel [1]. Обратите внимание, что штраф за неправильное прогнозирование ветки зависит от процессора, как вы увидите в руководстве Intel.

4. Наконец, решите проблемы, выявленные профилировщиком. Ряд методов уже обсуждался здесь. Ряд хороших, надежных, комплексных ресурсов по оптимизации также доступны. Чтобы назвать только два, есть Справочное руководство по оптимизации Intel [1] и пять руководств по оптимизации от Agner Fog [2]. Обратите внимание, что есть некоторые вещи, которые вам могут не понадобиться, если компилятор уже сделал это, например, развертывание цикла, выравнивание памяти и т. Д. Внимательно прочитайте документацию вашего компилятора.

Рекомендации:

[1] Справочное руководство по оптимизации архитектур Intel 64 и IA-32: http://www.intel.sg/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf.

[2] Агнер Фог, «Ресурсы по оптимизации программного обеспечения»: http://www.agner.org/optimize/

• «Оптимизация программного обеспечения в C ++: руководство по оптимизации для платформ Windows, Linux и Mac»
• «Оптимизация подпрограмм на языке ассемблера: руководство по оптимизации для платформ x86»
• «Микроархитектура процессоров Intel, AMD и VIA: руководство по оптимизации для программистов на сборках и производителей компиляторов»
• «Таблицы инструкций: списки задержек инструкций, пропускной способности и сбоев микроопераций для процессоров Intel, AMD и VIA»
• «Соглашения о вызовах для различных компиляторов C ++ и операционных систем»

Я не ученый в области вычислительной техники, как многие другие здесь (так что я могу ошибаться :)), но в наши дни нет смысла тратить слишком много времени на последовательную производительность, если мы используем стандартные библиотеки. Возможно, стоит потратить дополнительное время / усилия на то, чтобы сделать код более масштабируемым.

В любом случае, вот два примера (если вы их еще не читали) о том, как была улучшена производительность (для неструктурированных проблем FE).

Серийный номер : см. 2-ую половину реферата и связанный текст.

Параллельно : особенно фаза инициализации, в разделе 4.2.

Возможно, это скорее мета-ответ, чем ответ ...

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

Многое из хорошего совета, который выдает @Pedro, может быть реализовано путем настройки компиляции, а не программы.

Простой способ профилирования программы (в Linux) - использование perfв statрежиме. Самый простой способ это просто запустить

perf stat ./my_program args ...

и это даст вам кучу полезной статистики производительности:

Performance counter stats for './simd_test1':

     3884.559489 task-clock                #    1.000 CPUs utilized
              18 context-switches          #    0.005 K/sec
               0 cpu-migrations            #    0.000 K/sec
             383 page-faults               #    0.099 K/sec
  10,911,904,779 cycles                    #    2.809 GHz
 <not supported> stalled-cycles-frontend
 <not supported> stalled-cycles-backend
  14,346,983,161 instructions              #    1.31  insns per cycle
   2,143,017,630 branches                  #  551.676 M/sec
          28,892 branch-misses             #    0.00% of all branches

     3.885986246 seconds time elapsed

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

Вы также можете попробовать, perf record ./my_program; perf reportчто является простым способом для профилирования. Прочитайте справочные страницы, чтобы узнать больше.