Эффективные стратегии оптимизации на современных компиляторах C ++

Question

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

Хорошо известно, что некоторые оптимизации, например, Развертывание цикла в наши дни обрабатывается компилятором гораздо эффективнее, чем программистом, вмешивающимся вручную. Какие методы все еще стоят? Очевидно, что я буду запускать все, что я пробую, через профилировщик, но если есть общепринятая мудрость относительно того, что работает, а что нет, это сэкономило бы мне значительное время.

Я знаю, что оптимизация очень зависит от компилятора и архитектуры. Я использую компилятор Intel C ++ для Core 2 Duo, но мне также интересно, что хорошо работает для gcc или для «любого современного компилятора».

Вот некоторые конкретные идеи, которые я рассматриваю:

• Есть ли польза от замены контейнеров / алгоритмов STL на свернутые вручную? В частности, моя программа включает очередь с очень большим приоритетом (в настоящее время std::priority_queue), манипулирование которой занимает много общего времени. Стоит ли изучать это, или реализация STL уже, вероятно, самая быстрая из возможных?
• Аналогичным образом, для std::vector s, чьи необходимые размеры неизвестны, но имеют достаточно малую верхнюю границу, выгодно ли заменять их статически распределенными массивами?
• Я обнаружил, что динамическое выделение памяти часто является серьезным узким местом, и что его устранение может привести к значительному ускорению. Как следствие, я заинтересован в компромиссах производительности, связанных с возвратом больших временных структур данных по значению, возвратом по указателю или передачей результата по ссылке. Есть ли способ надежно определить, будет ли компилятор использовать RVO для данного метода (при условии, конечно, что вызывающей стороне не нужно изменять результат)?
• Насколько кеш-ориентированными являются компиляторы? Например, стоит ли переупорядочивать вложенные циклы?
• Учитывая научную природу программы, числа с плавающей запятой используются повсеместно. Существенным узким местом в моем коде были преобразования из числа с плавающей запятой в целые числа: компилятор генерировал код, чтобы сохранить текущий режим округления, изменить его, выполнить преобразование, а затем восстановить старый режим округления - даже если в программе ничего не было когда-либо менял режим округления! Отключение этого поведения значительно ускорило мой код. Есть ли какие-либо похожие ошибки, связанные с плавающей точкой, о которых мне следует знать?
• Одним из следствий компиляции и связывания C ++ по отдельности является то, что компилятор не может выполнить то, что может показаться очень простой оптимизацией, такой как вызов методов метода, например strlen (), из условий завершения цикла. Есть ли какая-либо оптимизация, подобная этой, на которую мне следует обратить внимание, потому что они не могут быть выполнены компилятором и должны выполняться вручную?
• С другой стороны, есть ли какие-либо методы, которые мне следует избегать , потому что они могут мешать компилятору автоматически оптимизировать код?

Наконец, чтобы пресечь определенные виды ответов в зародыше:

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

Answer 1

Есть ли польза от замены контейнеров / алгоритмов STL на свернутые вручную? В частности, моя программа включает в себя очень большую очередь приоритетов (в настоящее время std :: priority_queue), манипулирование которой занимает много общего времени. Стоит ли изучать это, или реализация STL уже, вероятно, самая быстрая из возможных?

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

Некоторые контейнеры (например, map, set, list) полагаются на множество манипуляций с указателями. Хотя это и противоречит интуитивному пониманию, оно часто может привести к тому, что более быстрый код заменит их на vector. Результирующий алгоритм может перейти от O(1) или O(log n) к O(n), но из-за локальности кэша он может быть намного быстрее на практике. Профиль обязательно.

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

Аналогичным образом для std :: векторы, размеры которых неизвестны, но имеют достаточно малую верхнюю границу, выгодно ли заменять их статически распределенными массивами?

Опять же, это может помочь небольшое количество, в зависимости от варианта использования. Вы можете избежать выделения кучи, но только если вам не нужен массив, чтобы пережить стек ... или вы могли бы reserve() размер в vector, чтобы было меньше копирования при перераспределении.

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

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

Насколько кеш-ориентированными являются компиляторы? Например, стоит ли переупорядочивать вложенные циклы?

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

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

• Используйте explicit в ваших конструкторах с одним аргументом. Временный объект строительства и разрушения могут быть скрыты в вашем коде.

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

• Профиль, профиль, профиль. Настройте области, которые являются узкими местами.

Answer 2

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

Общий процесс:

• Научитесь любить представление дизассемблирования в своем отладчике или попросить систему сборки создавать файлы промежуточной сборки (.s), если это вообще возможно. Следите за изменениями или за вещами, которые выглядят вопиющими - даже без знакомства с заданной архитектурой набора команд, вы сможете увидеть некоторые вещи довольно четко! (Я иногда проверяю ряд файлов .s с соответствующими изменениями .cpp / .c, просто чтобы использовать прекрасные инструменты из моего SCM для просмотра кода и соответствующего изменения asm с течением времени.)
• Получите профилировщик, который может наблюдать за счетчиками производительности вашего ЦП или, по крайней мере, угадывать ошибки кеша. (AMD CodeAnalyst, cachegrind, vTune и т. Д.)

Некоторые другие специфические вещи:

• Понимание строгого алиасинга. Как только вы это сделаете, используйте restrict, если он есть у вашего компилятора. (Изучите здесь и катастрофу!)
• Проверьте различные режимы с плавающей запятой на вашем процессоре и компиляторе. Если вам не нужен денормализованный диапазон, выбор режима без него может привести к повышению производительности. (Похоже, вы уже сделали некоторые вещи в этой области, основываясь на обсуждении режимов округления.)
• Определенно избегайте выделения: вызовите reserve на std::vector, когда можете, или используйте std::array, когда вы знаете размер во время компиляции.
• Использование пулов памяти для увеличения локальности и уменьшения накладных / свободных накладных расходов; также для обеспечения выравнивания по кэш-линии и предотвращения пинг-понга.
• Используйте распределители кадров , если вы распределяете вещи по предсказуемым схемам и можете позволить себе освободить все за один раз.
• Do знать об инвариантах . То, что вы знаете, является инвариантом, может не относиться к компилятору, например, использование структуры или члена класса в цикле. Я считаю, что самый простой способ попасть в правильную привычку здесь - дать имя всему и предпочесть имена вне петель. Например. const int threshold = m_currentThreshold; или, возможно, Thing * const pThing = pStructHoldingThing->pThing; К счастью, вы можете увидеть вещи, которые нуждаются в этой обработке, в виде разборки. Это также помогает в дальнейшей отладке (в окнах отладки поведение окна наблюдения / локальности намного лучше)!
• Избегайте записи в циклах , если возможно - сначала накапливайте, затем записывайте или группируйте несколько записей вместе. YMMV, конечно.

ЗАПИШИТЕ свой std::priority_queue вопрос: вставка объектов в вектор (бэкэнд по умолчанию для priority_queue) имеет тенденцию перемещать множество элементов. Если вы можете разбить на фазы, где вы вставляете данные, затем сортируете их, а затем читаете их, как только они отсортированы, вам, вероятно, будет намного лучше. Хотя вы определенно потеряете локальность, вы можете найти более упорядоченную структуру, такую ​​как std :: map или std :: set, которая стоит накладных расходов - но это действительно в зависимости от ваших шаблонов использования.

Answer 3

Есть ли польза от замены контейнеров / алгоритмов STL на свернутые вручную?
Я бы рассматривал это только как последний вариант. Контейнеры и алгоритмы STL были тщательно протестированы. Создание новых стоит дорого с точки зрения времени разработки.

Аналогичным образом для std :: vectors, чьи необходимые размеры неизвестны, но имеют достаточно малую верхнюю границу, выгодно ли заменять их статически распределенными массивами?
Сначала попробуйте зарезервировать место для векторов. Проверьте метод std::vector::reserve. Вектор, который продолжает расти или меняться на большие размеры, будет тратить динамическую память и время выполнения. Добавьте некоторый код, чтобы определить правильное значение для верхней границы.

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

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

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

Учитывая научный характер программы, числа с плавающей запятой используются повсеместно. Существенным узким местом в моем коде были преобразования из числа с плавающей запятой в целые числа: компилятор генерировал код, чтобы сохранить текущий режим округления, изменить его, выполнить преобразование, а затем восстановить старый режим округления - даже если в программе ничего не было когда-либо менял режим округления! Отключение этого поведения значительно ускорило мой код. Есть ли какие-либо похожие ошибки, связанные с плавающей точкой, о которых мне следует знать?
Для точности сохраните все как double. Отрегулируйте для округления только при необходимости и, возможно, перед отображением. Это подпадает под правило оптимизации, Используйте меньше кода, исключите посторонний или мертвый код .

Также см. Раздел выше о резервировании пространства в контейнерах перед их использованием.

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

Одним из следствий компиляции и связывания C ++ по отдельности является то, что компилятор не может выполнить то, что может показаться очень простой оптимизацией, такой как вызовы методов типа strlen () из условий завершения цикла. Есть ли какая-либо оптимизация, подобная этой, на которую мне следует обратить внимание, потому что она не может быть выполнена компилятором и должна выполняться вручную?
Это неверное предположение. Компиляторы могут оптимизировать на основе сигнатуры функции, особенно если параметры правильно используют const. Мне всегда нравится помогать компилятору, перемещая постоянные вещи вне цикла. Для верхнего предельного значения, такого как длина строки, присвойте его переменной const перед циклом. Модификатор const поможет оптимизатору.

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

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

Идеи и концепции оптимизации

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

2. Устранить требования
Меньше кода, больше производительности.

3. Оптимизируйте дизайн перед кодом Часто производительность можно повысить, изменив дизайн по сравнению с реализацией проекта. Меньше дизайна способствует меньшему количеству кода, создает большую производительность.

4. Рассмотрим организацию данных Оптимизировать данные.
Организуйте часто используемые поля в substructures. Установите размеры данных, чтобы поместиться в строку данных строки кэша . Удалить постоянные данные из структур данных.
Максимально используйте спецификатор const.

5. Рассмотрим обмен страниц Операционные системы заменят вашу программу или задачу другой. Часто в «файл подкачки» на жестком диске. Разделение кода на куски, которые содержат сильно исполняемый код и менее исполняемый код, поможет ОС. Кроме того, сверните интенсивно используемый код в более узкие единицы. Идея состоит в том, чтобы уменьшить обмен кода с жесткого диска (например, выборка «далеких» функций). Если код должен быть заменен, он должен быть как одна единица.

6. Рассмотрим оптимизацию ввода / вывода (Включает файловый ввод / вывод тоже).
Большинство операций ввода-вывода предпочитают меньшее количество больших порций данных многим маленьким порциям данных. Жесткие диски любят крутиться. Большие пакеты данных имеют меньше служебных данных, чем меньшие пакеты.
Отформатируйте данные в буфер, затем запишите буфер.

7. Ликвидация конкуренции
Избавьтесь от любых программ и задач, которые конкурируют с вашим приложением для процессора (ов). Такие задачи, как сканирование вирусов и проигрывание музыки. Даже драйверы ввода-вывода хотят часть действия (именно поэтому вы хотите уменьшить количество транзакций ввода-вывода).

Это должно вас занять некоторое время. : -)

Answer 4

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

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

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

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

5. Я заметил, что вы не упомянули использование инструкций типа SSE. Могут ли они быть применимы к вашему типу обработки номера?

Удачи.

Answer 5

Здесь - хорошая статья на эту тему.

Answer 6

О контейнерах STL.

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

Люди спорят о сложности алгоритмов, используемых в STL. Здесь STL хорош: O (1) для list / queue, вектор (амортизированный) и O (log (N)) для map. Но это не реальное узкое место производительности для типичного приложения! Для многих приложений реальным узким местом являются операции с кучей (malloc / free, new / delete и т.

Типичная операция на list стоит всего несколько циклов ЦП. На map - несколько десятков, может быть больше (это зависит, конечно, от состояния кэша и журнала (N)). А типичные операции с кучей обходятся от нескольких тысяч (!!!) циклов ЦП. Например, для многопоточных приложений они также требуют синхронизации (операции с блокировкой). Кроме того, в некоторых ОС (например, Windows XP) функции кучи полностью реализованы в режиме ядра.

Так что фактическая производительность контейнеров STL в типичном сценарии зависит от количества операций кучи, которые они выполняют. И здесь они катастрофичны. Не потому, что они плохо реализованы, а из-за их дизайна . То есть это вопрос дизайна.

С другой стороны, есть другие контейнеры, которые сконструированы иначе. Однажды я спроектировал и написал такие контейнеры для своих нужд:

http://www.codeproject.com/KB/recipes/Containers.aspx

И это оказалось для меня превосходством с точки зрения производительности, и не только.

Но недавно я обнаружил, что я не единственный, кто думал об этом. boost::intrusive - это библиотека контейнеров, которая реализована аналогично тому, что я делал тогда.

Я предлагаю вам попробовать (если вы этого еще не сделали)

Answer 7

Есть ли польза от замены контейнеров / алгоритмов STL на свернутые вручную?

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

Единственное исключение, которое я видел, - заменить std :: string при копировании при записи на то, которое не требует синхронизации потоков.

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

Вряд. Но если вы используете много времени, выделяя до определенного размера, возможно, было бы выгодно добавить вызов Reserve ().

компромисс производительности при возврате больших временных структур данных по значению по сравнению с возвратом по указателю и при передаче результата по ссылке.

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

Насколько кеш-ориентированными являются компиляторы? Например, стоит ли переупорядочивать вложенные циклы?

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

Существенным узким местом в моем коде были преобразования из числа с плавающей запятой в целые числа

Да. Недавно я обнаружил ту же проблему.

Одним из следствий компиляции и связывания C ++ по отдельности является то, что компилятор не может выполнить то, что может показаться очень простой оптимизацией, такой как вызовы методов типа like strlen () из условий завершения цикла.

Некоторые компиляторы могут справиться с этим. Visual C ++ имеет опцию «генерации кода во время компоновки», которая эффективно повторно вызывает компилятор для дальнейшей оптимизации. А в случае таких функций, как strlen, многие компиляторы распознают это как встроенную функцию.

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

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

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

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

Answer 8

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

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

Вот пример такого рода процесса.

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

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

Answer 9

вот что я использовал:

• шаблоны для специализации границ самых внутренних циклов (делает их очень быстрыми)
• используйте __restrict__ ключевые слова для решения проблем с псевдонимом
• заранее зарезервируйте векторы для нормальных значений по умолчанию.
• избегайте использования карты (это может быть очень медленно)
• векторное добавление / вставка может быть значительно медленным. Если это так, необработанные операции могут сделать это быстрее
• N-байтовое выравнивание памяти (у Intel выровнена прагма, http://www.intel.com/software/products/compilers/docs/clin/main_cls/cref_cls/common/cppref_pragma_vector.htm)
• пытается сохранить память в кешах L1 / L2.
• скомпилировано с NDEBUG
• профиль с использованием oprofile, используйте opannotate для поиска определенных строк (тогда явно видны заголовки stl)

вот примеры частей данных профиля (чтобы вы знали, где искать проблемы)

 * Output annotated source file with samples
 * Output all files
 *
 * CPU: Core 2, speed 1995 MHz (estimated)
--
 * Total samples for file : "/home/andrey/gamess/source/blas.f"
 *
 * 1020586 14.0896
--
 * Total samples for file : "/home/andrey/libqc/rysq/src/fock.cpp"
 *
 * 962558 13.2885
--
 * Total samples for file : "/usr/include/boost/numeric/ublas/detail/matrix_assign.hpp"
 *
 * 748150 10.3285

--
 * Total samples for file : "/usr/include/boost/numeric/ublas/functional.hpp"
 *
 * 639714  8.8315
--
 * Total samples for file : "/home/andrey/gamess/source/eigen.f"
 *
 * 429129  5.9243
--
 * Total samples for file : "/usr/include/c++/4.3/bits/stl_algobase.h"
 *
 * 411725  5.6840
--

пример кода из моего проекта

template<int ni, int nj, int nk, int nl>
inline void eval(const Data::density_type &D, const Data::fock_type &F,
                 const double *__restrict Q, double scale) {

    const double * __restrict Dij = D[0];
    ...
    double * __restrict Fij = F[0];
    ...

    for (int l = 0, kl = 0, ijkl = 0; l < nl; ++l) {
        for (int k = 0; k < nk; ++k, ++kl) {
            for (int j = 0, ij = 0; j < nj; ++j, ++jk, ++jl) {
                for (int i = 0; i < ni; ++i, ++ij, ++ik, ++il, ++ijkl) {

Answer 10

Насколько кешированы компиляторы? Например, стоит ли переупорядочивать вложенные циклы?

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