Оптимизация [закрытого] кода

All good answers.

I would refine the "measure" part of the advice. I perform measurement for the purpose of quantifying any improvements I might make. However, for finding what needs to be fixed (and that is a different purpose), I get several samples of the call stack, manually.

Suppose, for simplicity, the program takes 20 giga-cycles to run, when it should take 10. If I pause it 10 times at random, then in 5 of those occasions, more or less, it will be in one of those unnecessary cycles. I can see if the cycle is necessary by looking at each layer of the call stack. If any call instruction at any level of the stack could be eliminated, then the cycle is unnecessary. If such an instruction appears on multiple stacks, eliminating it will speed up the program, by an amount which is approximately the percentage of stack samples it is on.

Any instruction that shows up on multiple stacks is suspect - the more stacks, the more suspect. Now, call _main is probably not one I can remove, but
foo.cpp:96 call std::vector::iterator:++
if it shows up on multiple stacks, is definitely a focus of attention.

One may, for style reasons, not want to replace it, but one will know roughly what price in performance is being paid for that choice.

So optimizing consists of identifying suspects and finding a way to replace or eliminate them.

The hard part (and I've done this many times) is understanding what is necessary and what is not. For that, you're going to absorb an understanding of how and why things are done in that program, so if some activity is a cycle-hog, you can know how to safely replace it.

Some cycle-hogs may be simple to fix, but you will quickly run up against ones that you don't know how to safely replace. For that, you need to be more familiar with the code.

It will help if you can pick the brain of someone who's already worked on the program.

Otherwise (assuming the code is ~ 10^6 lines, like I've worked on) you can get some speedup fairly easily, but to go beyond that, it can take months to get to where you're comfortable making significant changes.

В первую очередь, не забывайте их:

• Преждевременная оптимизация является корнем всего зла
• Производительность прибывает из дизайна

Во-вторых;

Не принимайте пытаются видеть

Я думаю, что это - кардинальное правило оптимизации, протестируйте его, если Вы не тестируете его и доказываете, что это работает, Вы не знали бы.

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

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

Даже не потрудитесь пробовать что-либо без своего рода профилирования, я не могу подчеркнуть это достаточно! К сожалению, все профилировщики я знаю или сосу или являюсь дорогим (Yay для затрат на ведение бизнеса!), таким образом, я позволю другим предоставить рекомендации там :).

Вы знаете о необходимости в переписывании, когда данные говорят Вам о необходимости в переписывании которое звучит рекурсивным, но действительно просто означает, стоимость текущей архитектуры или программного стека достаточно отдельно для продвижения Вас по утесу производительности, таким образом, ничто, что Вы делаете в локальных изменениях, не может решить полную проблему. Однако перед уходом, Файл-> Новый... управляют, делают план, создают прототип и тестируют прототип, добивается большего успеха, чем существующая система для той же задачи: удивительно, как часто нет никакого noticable различия!

Шаги:

1. Мера
2. Проанализировать
3. Решить
4. Реализация
5. Повториться

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

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

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

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

Затем вернитесь к запуску и мере, проанализируйте, решите, реализуйте и т.д.

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

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

Для принятия кода нужна оптимизация, затем я использовал бы: 1.) Оптимизируют способ, которым буферы обрабатываются используемые - оптимизация Кэша. Задержки кэша являются одной большой площадью, которые сосут циклы ЦП как плохо. примерно в диапазоне 5-10% наверху Так используют буферы данных в кэше эффективный способ.

2.) Критические циклы и интенсивные функции MCPS могут быть кодированы в ассемблере или использовании низкого уровня intrinsics обеспеченный компилятором для этого цель h/w.

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

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

- AD

Сначала решите то, что Ваша цель оптимизации - ставит цель для синхронизации конкретных операций на данной аппаратной платформе. Измерьте уровень точно (удостоверьтесь, что Ваши результаты повторяемы) и в подобной производству среде (никакой VMs и т.д., если это не то, что Вы используете в производстве!).

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

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

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

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

Затем и только затем, начните анализировать код.

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

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

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

1. Используйте числовые массивы, а не массивы объектов. Например, C++ имеет "Сложный" тип данных. Операции на массиве их были намного медленнее, чем подобная операция на двух массивах плаваний. Это может быть обобщено для "использования типов машины" для любой производительности критический код.
2. Напишите код, чтобы позволить компилятору быть более эффективным при своих оптимизациях. Например, если у Вас есть массив фиксированного размера, используйте индексы массива так, чтобы автоматическая векторизация (функция компилятора Intel) могла работать.
3. Инструкции SIMD могут обеспечить хорошее ускорение, если Ваша проблема вписывается в вид домена, что они разработаны для (умножающиеся/делящие плавания или ints все одновременно). Это - материал как MMX, SSE, SSE2 и т.д.
4. Используя справочные таблицы с интерполяцией для дорогих функций, где точные значения не важны. Это не всегда хорошо, поскольку поиск данных в памяти мог бы быть дорогим самостоятельно.

Я надеюсь, что это дает Вам некоторое вдохновение!

Как уже говорили многие другие, профилирование - это ваш первый шаг.

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

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

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

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

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

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

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

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

Хорошие стратегии

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

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

Когда останавливаться

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