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

Question

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

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

FORTRAN может быть быстрее, чем C, для некоторых видов операций из-за проблем alias . В теории с осторожным кодированием можно обойти это ограничение, чтобы оптимизатор мог генерировать более быстрый код.

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

• Буду признателен за указание используемой вами платформы и компилятора.
• Почему техника работает?
• Пример кода приветствуется.

Вот связанный вопрос

[Редактировать] Этот вопрос не об общем процессе для профилирования, а оптимизации. Предположим, что программа написана правильно, скомпилирована с полной оптимизацией, протестирована и запущена в производство. В вашем коде могут быть конструкции, которые запрещают оптимизатору выполнять свою работу наилучшим образом. Что вы можете сделать для рефакторинга, который снимет эти запреты и позволит оптимизатору генерировать еще более быстрый код?

[Изменить] Ссылка, связанная со смещением

Answer 1

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

Алгоритмы, используемые для управления кучей, заведомо медленны на некоторых платформах (например, vxworks). Хуже того, время, необходимое для возврата из вызова в malloc, сильно зависит от текущего состояния кучи. Следовательно, любая функция, которая вызывает malloc, будет иметь снижение производительности, которое не может быть легко объяснено. Это снижение производительности может быть минимальным, если куча все еще чиста, но после того, как устройство некоторое время работает, куча может стать фрагментированной. Звонки будут занимать больше времени, и вы не можете легко рассчитать, как производительность будет снижаться с течением времени. Вы не можете получить худшую оценку случая. Оптимизатор также не может оказать вам никакой помощи в этом случае. Что еще хуже, если куча станет слишком сильно фрагментированной, вызовы будут вообще терпеть неудачу. Решение состоит в том, чтобы использовать пулы памяти (например, glib slices ) вместо кучи. Вызовы распределения будут намного быстрее и детерминированными, если вы все сделаете правильно.

Answer 2

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

Всегда передайте аргументы функции в одном и том же порядке.

Если у вас есть f_1 (x,y, z), который вызывает f_2, объявляет f_2 как f_2 (x, y, z).Не объявляйте его как f_2 (x, z, y).

Причина этого заключается в том, что платформа C / C ++ ABI (соглашение о вызовах AKA) обещает передавать аргументы в определенных регистрах и расположениях стека.Когда аргументы уже находятся в правильных регистрах, тогда их не нужно перемещать.

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

Answer 3

Две техники кодирования, которые я не видел в приведенном выше списке:

Обойти компоновщик, написав код в качестве уникального источника

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

Но если вы хорошо спроектируете свою программу, вы также можете скомпилировать ее через уникальный общий источник. То есть вместо компиляции unit1.c и unit2.c затем связываются оба объекта, компилируется all.c, который просто #include unit1.c и unit2.c. Таким образом, вы получите выгоду от всех оптимизаций компилятора.

Это очень похоже на написание только заголовочных программ на C ++ (и даже проще на C).

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

Используя эту простую технику, я сделал несколько программ, которые написал в десять раз быстрее!

Как и ключевое слово register, этот прием также может скоро устареть. Оптимизация через компоновщик начинает поддерживаться компиляторами gcc: оптимизация времени соединения .

Отдельные атомарные задачи в циклах

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

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

Answer 4

Не делайте одну и ту же работу снова и снова!

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

void Function()
{
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomething();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingElse();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingCool();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingReallyNeat();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingYetAgain();
}

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

void Function()
{
   MySingleton* s = MySingleton::GetInstance();
   AggregatedObject* ao = s->GetAggregatedObject();
   ao->DoSomething();
   ao->DoSomethingElse();
   ao->DoSomethingCool();
   ao->DoSomethingReallyNeat();
   ao->DoSomethingYetAgain();
}

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

Answer 5

Я действительно видел, как это делается в SQLite, и они утверждают, что это приводит к повышению производительности ~ 5%: поместите весь ваш код в один файл или используйте препроцессор, чтобы сделать эквивалент этого. Таким образом, оптимизатор получит доступ ко всей программе и сможет выполнять больше межпроцедурных оптимизаций.

Answer 6

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

Пример:

int fac2(int x, int cur) {
  if (x == 1) return cur;
  return fac2(x - 1, cur * x); 
}
int fac(int x) {
  return fac2(x, 1);
}

Конечно, в этом примере нет проверки границ.

Позднее редактирование

Пока у меня нет прямого знания кода; Кажется очевидным, что требования использования CTE на SQL Server были специально разработаны таким образом, чтобы он мог оптимизироваться с помощью хвостовой рекурсии.

Answer 7

Совместите ваши данные с естественными / естественными границами.

Answer 8

Мне напомнили о чем-то, с чем я однажды столкнулся, когда симптомом было просто то, что у нас не хватало памяти, но в результате было существенно повышена производительность (а также огромное сокращение объема памяти).

Проблема в этом случае заключалась в том, что программное обеспечение, которое мы использовали, производило тонны небольших выделений. Например, выделение четырех байтов здесь, шести байтов там и т. Д. Множество маленьких объектов тоже работает в диапазоне 8-12 байтов. Проблема была не столько в том, что программе требовалось много мелочей, а в том, что она выделяла множество мелочей по отдельности, что увеличивало каждое выделение (на этой конкретной платформе) до 32 байт.

Часть решения состояла в том, чтобы собрать пул небольших объектов в стиле Александреску, но расширить его, чтобы я мог распределять массивы как небольших объектов, так и отдельных элементов. Это также очень помогло в производительности, так как в кэш-памяти одновременно помещается больше элементов.

Другая часть решения состояла в том, чтобы заменить безудержное использование членов char * с ручным управлением строкой SSO (оптимизация небольшой строки). Минимальное выделение 32 байта, я построил строковый класс, который имел встроенный 28-символьный буфер за символом *, поэтому 95% наших строк не нужно было делать дополнительное выделение (а затем я вручную заменял почти каждое появление char * в этой библиотеке с этим новым классом, было весело или нет). Это также помогло с фрагментацией памяти, что увеличило локальность ссылок для других объектов, на которые указывают ссылки, и аналогичным образом имело место повышение производительности.

Answer 9

Изящная техника, которую я узнал из комментария @MSalters к этот ответ позволяет компиляторам выполнять копирование, даже когда возвращаются различные объекты в соответствии с некоторыми условиями:

// before
BigObject a, b;
if(condition)
  return a;
else
  return b;

// after
BigObject a, b;
if(condition)
  swap(a,b);
return a;

Answer 10

1. Использовать максимально локальную область видимости для всех объявлений переменных.

2. Используйте const по возможности

3. Не используйте регистр, если вы не планируете профилировать как с так и без него

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

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

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