Должны ли мы все еще оптимизировать «в малом»?

Question

Я изменял свой цикл for на инкремент, используя ++i вместо i++, и подумал, действительно ли это необходимо? Конечно, современные компиляторы делают эту оптимизацию самостоятельно.

В этой статье http://leto.net/docs/C-optimization.php, от 1997 года Майкл Ли занимается другими оптимизациями, такими как встраивание, разворачивание петли, заклинивание петли, инверсия петли, снижение прочности и многие другие. Они все еще актуальны?

Какие низкоуровневые оптимизации кода мы должны делать и какие оптимизации мы можем игнорировать?

Редактировать: Это не имеет никакого отношения к преждевременной оптимизации. Решение по оптимизации уже принято. Теперь вопрос в том, какой из них наиболее эффективен.

анекдот: однажды я просмотрел спецификацию требований, в которой говорилось: «Программист должен оставить сдвиг на единицу вместо умножения на 2».

Answer 1

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

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

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

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

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

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

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

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

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

ДОБАВЛЕНО: Теперь, чтобы попытаться ответить на ваш вопрос, следует выполнить низкоуровневую оптимизацию, когда диагностика говорит, что у вас есть горячая точка (т.е. некоторый код в нижней части стека вызовов появляется на достаточном количестве выборок стека вызовов (10%). или более), как известно, стоит значительного времени). И если горячая точка в коде, вы можете редактировать. Если у вас есть «горячая точка» в «новом», «удаленном» или строковом сравнении, посмотрите вверх по стеку, чтобы найти вещи, от которых нужно избавиться.

Надеюсь, это поможет.

Answer 2

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

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

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

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

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

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

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

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

Таким образом, такие «мелкомасштабные» оптимизации все еще могут быть необходимы, если 1) вам действительно нужна производительность, и 2) у вас есть информация, которой нет у компилятора.

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

Answer 3

Эти оптимизации все еще актуальны. Что касается вашего примера, использование ++ i или i ++ для встроенного арифметического типа не имеет никакого эффекта.

В случае пользовательских операторов увеличения / уменьшения, ++ i предпочтительнее, потому что это не подразумевает копирование увеличенного объекта.

Таким образом, хорошим стилем кодирования является использование префикса приращения / уменьшения в циклах.

Answer 4

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

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

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

Как отметил другой участник здесь , "оптимизация без измерения и понимания вовсе не является оптимизацией - это просто случайное изменение".

Если вы измерили и определили, что определенная функция или цикл является горячей точкой, существует два подхода для ее оптимизации:

• Во-первых, оптимизируйте его на более высоком уровне, уменьшив количество вызовов дорогостоящего кода. Это обычно приводит к большей выгоде. Улучшения уровня алгоритма попадают в этот уровень - алгоритм будет лучше, если big-O приведет к меньшему количеству выполнения кода горячей точки.
• Если количество вызовов не может быть уменьшено, вам следует подумать о микрооптимизации. Посмотрите на фактический машинный код, который испускает компилятор, и определите, что он делает, что является самым дорогостоящим - если выясняется, что происходит копирование временных объектов, то рассмотрите префикс ++ вместо постфикса. Если это делает ненужное сравнение в начале цикла, переверните цикл в do / while и так далее. Не понимая почему код медленный, любые общие микрооптимизации практически бесполезны.

Answer 5

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

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

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

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

Answer 6

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

Если вас не волнует переносимость, и вы немного разбираетесь в математике, вы можете также рассмотреть возможность использования любых векторных операций на вашей целевой платформе - SSE на x86, Altivec на PPC. Компиляторы не могут легко использовать эти инструкции без большой помощи, а встроенные функции довольно просты в использовании в наши дни. Еще одна вещь, которая не упоминается в документе, на который вы ссылаетесь, это наложение указателя. Иногда вы можете получить хорошие улучшения скорости, если ваш компилятор поддерживает какое-то ключевое слово restrict. Кроме того, конечно, важно думать об использовании кэша. Реорганизация кода и данных таким образом, чтобы эффективно использовать кэш, может привести к значительному увеличению скорости по сравнению с оптимизацией удаления нечетной копии или развертыванием цикла.

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

Answer 7

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

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

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

x = y / 2;

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

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

Answer 8

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

Стань зеленым, спаси планету, оптимизируй себя

Answer 9

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

#include <iostream>

int main()
{
  for (unsigned int i = 5; i != 0; i--)
    std::cout << i << std::endl;

  for (unsigned int i = 5; i != 0; --i)
    std::cout << "\t" << i << std::endl;

  for (unsigned int i = 5; i-- != 0; )
    std::cout << i << std::endl;

  for (unsigned int i = 5; --i != 0; )
    std::cout << "\t" << i << std::endl;
}

приводит к следующему:

5
4
3
2
1
        5
        4
        3
        2
        1
4
3
2
1
0
        4
        3
        2
        1

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

Answer 10

Есть три цитаты, которые я считаю, что каждый разработчик должен знать об оптимизации - я впервые прочитал их в книге Джоша Блоха «Эффективная Java»:

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

( Уильям А. Вульф )

Мы должны забыть о маленьких эффективность, скажем, около 97% время: преждевременная оптимизация корень зла.

( Дональд Э. Кнут )

Мы следуем двум правилам в отношении оптимизация:

Правило 1: не делай этого.

Правило 2: (только для экспертов). Не делай это пока - то есть, пока у вас нет совершенно ясно и неоптимизировано решение.

( М. А. Джексон )

Все эти цитаты (AFAIK), по крайней мере, 20-30 лет, время, когда процессор и память значат гораздо больше, чем сегодня. Я считаю, что правильный способ разработки программного обеспечения - это сначала иметь работающее решение, а затем использовать профилировщик для проверки узких мест в производительности. Однажды мой друг рассказал мне о приложении, которое было написано на C ++ и Delphi и имело проблемы с производительностью. Используя профилировщик, они обнаружили, что приложение потратило значительное количество времени на преобразование строк из структуры Delphi в структуру C ++ и наоборот - никакая микрооптимизация не может обнаружить это ...

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