Какие хорошие методы оптимизации кода?

Question

Я хотел бы понять хорошие методы и методологию оптимизации кода.

1. Как мне избежать преждевременной оптимизации, если я уже думаю о производительности.
2. Как мне найти узкие места в моем коде?
3. Как мне убедиться, что со временем моя программа не станет медленнее?
4. Каковы некоторые распространенные ошибки производительности, которых следует избегать (например, я знаю, что в некоторых языках плохо возвращаться в пределах части catch блока try {} catch {}

Answer 1

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

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

Возьми свою "оптимизацию":

const int windowPosX = (screenWidth * 0.5) - (windowWidth * 0.5);

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

Но не верьте мне на слово. Посмотрите, что на самом деле делает компилятор. gcc 4.3.3 в 32-битной Ubuntu (-O3, -msse3, -fomit-frame-pointer) компилирует это:

int posx(unsigned int screen_width, unsigned int window_width) {
  return (screen_width / 2) - (window_width / 2);
}

к этому:

00000040 <posx>:
  40:   8b 44 24 04             mov    eax,DWORD PTR [esp+0x4]
  44:   8b 54 24 08             mov    edx,DWORD PTR [esp+0x8]
  48:   d1 e8                   shr    eax,1
  4a:   d1 ea                   shr    edx,1
  4c:   29 d0                   sub    eax,edx
  4e:   c3    

Две смены (с использованием непосредственного операнда) и вычитание. Очень дешевый. С другой стороны, он компилирует это:

int posx(unsigned int screen_width, unsigned int window_width) {
  return (screen_width * 0.5) - (window_width * 0.5);
}

на это:

00000000 <posx>:
   0:   83 ec 04                sub    esp,0x4
   3:   31 d2                   xor    edx,edx
   5:   8b 44 24 08             mov    eax,DWORD PTR [esp+0x8]
   9:   52                      push   edx
   a:   31 d2                   xor    edx,edx
   c:   50                      push   eax
   d:   df 2c 24                fild   QWORD PTR [esp]
  10:   83 c4 08                add    esp,0x8
  13:   d8 0d 00 00 00 00       fmul   DWORD PTR ds:0x0
            15: R_386_32    .rodata.cst4
  19:   8b 44 24 0c             mov    eax,DWORD PTR [esp+0xc]
  1d:   52                      push   edx
  1e:   50                      push   eax
  1f:   df 2c 24                fild   QWORD PTR [esp]
  22:   d8 0d 04 00 00 00       fmul   DWORD PTR ds:0x4
            24: R_386_32    .rodata.cst4
  28:   de c1                   faddp  st(1),st
  2a:   db 4c 24 08             fisttp DWORD PTR [esp+0x8]
  2e:   8b 44 24 08             mov    eax,DWORD PTR [esp+0x8]
  32:   83 c4 0c                add    esp,0xc
  35:   c3                      ret

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

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

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

Answer 2

1. Не думайте о производительности, думайте о ясности и правильности.
2. Используйте профилировщик.
3. Продолжайте использовать профилировщик.
4. См. 1.

Answer 3

РЕДАКТИРОВАТЬ Этот ответ первоначально появился в другом вопросе (который был объединен), где ОП перечислил некоторые возможные методы оптимизации, которые он только что предположил, должны работать. Все они в значительной степени опирались на предположения (например, x << 1 всегда быстрее, чем x * 2). Ниже я пытаюсь указать на опасность таких предположений.

---

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

В противном случае это - просто - не имеет значения.

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

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

Кстати:

Инициализировать константы, когда вы их объявляете (если можете)…

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

Answer 4

Правила Клуба Оптимизации:

1. Первое правило Клуба оптимизации - вы не оптимизируете.
2. Второе правило Клуба оптимизации - вы не оптимизируете без измерения.
3. Если ваше приложение работает быстрее, чем базовый транспортный протокол, оптимизация завершена.
4. Один фактор за раз.
5. Нет маркетроидов, нет расписаний маркетроидов.
6. Тестирование будет продолжаться столько, сколько потребуется.
7. Если это ваша первая ночь в Клубе оптимизации, вы должны написать контрольный пример.

http://xoa.petdance.com/Rules_of_Optimization_Club

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

Правила № 6 и № 7: Всегда проводите тесты. Если вы оптимизируете, вы проводите рефакторинг, и вы не хотите проводить рефакторинг без наличия надежного набора тестов.

Answer 5

Всегда хорошо помнить, что вещи «стоят». Некоторые примеры C #:

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

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

• Исключения очень дорогие. Это одна из причин, по которой исключения должны использоваться только в исключительных ситуациях.

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

---

Относительно ваших "оптимизаций":

• Сомневаюсь, что арифметика с плавающей запятой (* 0.5) быстрее целочисленного деления (/ 2).

• Если вам нужен массив размером 300, вы должны инициализировать массив размером 300. В степенях 2 нет ничего «волшебного», что делает массивы размером 256 более эффективными.

• «требуется 2 вызова в коде» неправильно.

Answer 6

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

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

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

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

Answer 7

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

• Использовать профилировщик
• Используйте нетривиальный объем данных при тестировании. Если возможно, сделайте это огромное количество данных.
• Используйте вменяемые алгоритмы, когда все становится напряженно.
• Используйте профилировщик, чтобы проверить, что любая «оптимизация», которую вы сделали, действительно верна, например, недавнее фиаско java jar, где операция O (1) была выполнена как O (n).

Answer 8

1. Написать читаемый код, показывающий намерение . не микрооптимизируйте - вы не можете перехитрить JIT.
2. Научитесь использовать профилировщик, например, jvisualvm в Sun JDK, и используйте it.

Answer 9

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

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

---

Извините за напыщенную речь, теперь за ваш актуальный вопрос:

Знай свое окружение!
Это включает в себя все детали низкого уровня - например, доступ к памяти нелинейности, вещи, которые компилятор может оптимизировать, и т. д. Хитрость не в том, чтобы беспокоиться о том, что многим не стоит беспокоиться, просто имейте в виду.

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

Подумайте об алгоритмах, прежде чем думать о деталях реализации.
Большинство низкоуровневых оптимизаций дают коэффициент 1,1, а другой алгоритм - коэффициент 10. Хорошая (!) Стратегия кэширования может дать коэффициент 100. Выяснение того, что вам действительно не нужно совершать вызов дает вам Деформацию 10.

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

Answer 10

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