Основные методики оптимизации кода: различия между версиями

Материал из me-robotics wiki
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
 +
<blockquote>'''Оптимизация программного кода''' — это модификация программ, выполняемая оптимизирующим компилятором или интерпретатором с целью улучшения их характеристик, таких как производительности или компактности, — без изменения функциональности.</blockquote>Последние три слова в этом определении очень важны: как бы не улучшала оптимизация характеристики программы, она обязательно должна сохранять изначальный смысл программы при любых условиях.
  
 
=== Оптимизация ===
 
=== Оптимизация ===
Строка 5: Строка 6:
 
Оптимизация должна быть естественной. Оптимизированный фрагмент кода должен легко вливаться в программу, не нарушая логики ее работы. Он должен легко вводится в программу, изменятся или удаляться из нее.
 
Оптимизация должна быть естественной. Оптимизированный фрагмент кода должен легко вливаться в программу, не нарушая логики ее работы. Он должен легко вводится в программу, изменятся или удаляться из нее.
  
−
Оптимизация должна приносить существенный прирост производительности. Оптимизированная программа должна работать минимум на 20%-30% эффективней, чем ее неоптимизированный аналог, иначе она теряет смысл. Зачем мучится и вносить изменения в уже готовый код, если результата это практически не даст?
+
Оптимизация должна приносить существенный прирост производительности. Оптимизированная программа должна работать минимум на 20%-30% эффективней, чем ее неоптимизированный аналог, иначе она теряет смысл. Разработка (и отладка) критических областей не должна увеличивать время разработки программы более чем на 10%-15%.
−
 
 
−
Разработка (и отладка) критических областей не должна увеличивать время разработки программы более чем на 10%-15%.
 
−
 
 
−
Как уже писалось ранее, сейчас на первый план выходит скорость разработки программ, так что все же не нужно отставать от остальной массы программистов. Себе же хуже.
 
  
 
Так же, перед тем как писать оптимизированный вариант, полезно иметь его неоптимизированный аналог. Обычно, оптимизированный код очень тяжел для восприятия, и если после его внедрения в программе появятся ошибки, то, подставив вместо него его менее эффективного собрата, мы можем определить, кто виноват в ошибках.
 
Так же, перед тем как писать оптимизированный вариант, полезно иметь его неоптимизированный аналог. Обычно, оптимизированный код очень тяжел для восприятия, и если после его внедрения в программе появятся ошибки, то, подставив вместо него его менее эффективного собрата, мы можем определить, кто виноват в ошибках.
−
 
−
=== Логика оптимизации программного кода ===
 
−
Теперь перейдем к самой философии оптимизации. Считается, что критические области следует писать на ассемблере, поскольку он дает наивысшую скорость работы. Но зачастую результат работы оптимизирующего компилятора работает медленней своего ассемблерного аналога на 2%-7% (не более 20%). И стоило ли из-за такого мизерного прироста тратить время на разработку ассемблерной реализации? Из этого следует, что намного лучше оптимизировать код, написанный на языке высокого уровня, оптимизировать саму логику работы программы.
 
  
 
'''Основные постулаты оптимизации:'''
 
'''Основные постулаты оптимизации:'''
Строка 23: Строка 17:
 
# Используйте ассемблер только там, где скорость работы очень важна. Как уже писалось ранее, сейчас ассемблер не дает огромного прироста скорости. Поэтому использовать его стоит лишь в самых «узких» местах программы.
 
# Используйте ассемблер только там, где скорость работы очень важна. Как уже писалось ранее, сейчас ассемблер не дает огромного прироста скорости. Поэтому использовать его стоит лишь в самых «узких» местах программы.
 
# Задумывайтесь над оптимизацией. Неправильная оптимизация может даже навредить программе, увеличить время ее разработки, практически не уменьшив скорость ее работы.
 
# Задумывайтесь над оптимизацией. Неправильная оптимизация может даже навредить программе, увеличить время ее разработки, практически не уменьшив скорость ее работы.
 +
 +
 +
=== Вырезание условий и свитчей ===
 +
----Компилятор вырежет целую ветку условий или свитчей, если заранее будет уверен в результате сравнения или выбора. Как его в этом убедить? Правильно, константой! Рассмотрим элементарный пример: условие или свитч (неважно) с тремя вариантами:
 +
[[Файл:Вырезание swtich.png|центр|мини|700x700пкс]]
 +
Если объявить <code>num</code> как обычную переменную – в скомпилированный код попадёт вся конструкция целиком, три условия или весь свитч. Если <code>num</code> сделать константой const или дефайном <code>#define</code> – компилятор ''вырежет весь блок условий или свитч'' и оставит только содержимое, которое получается при заданном <code>num</code>. В этом очень легко убедиться, скомпилировав код и посмотрев на объём занимаемой памяти в логе компилятора. При помощи данного трюка можно ускорить выполнение некоторых функций и уменьшить занимаемое ими место в памяти.
 +
 +
=== Использовать переменные соответствующих типов ===
 +
----Тип переменной/константы не только влияет на занимаемый ей объём памяти, но и на скорость вычислений! В реальном коде время может быть меньше. ''Примечание: время приведено для кварца 16 МГц.''
 +
{| class="wikitable"
 +
| rowspan="2" |Тип данных
 +
| colspan="3" |Время выполнения, мкс
 +
|-
 +
|Сложение и вычитание
 +
|Умножение
 +
|Деление, остаток
 +
|-
 +
|int8_t
 +
|0.44
 +
|0.625
 +
|14.25
 +
|-
 +
|uint8_t
 +
|0.44
 +
|0.625
 +
|5.38
 +
|-
 +
|
 +
|
 +
|
 +
|
 +
|-
 +
|int16_t
 +
|0.89
 +
|1.375
 +
|14.25
 +
|-
 +
|uint16_t
 +
|0.89
 +
|1.375
 +
|13.12
 +
|-
 +
|int32_t
 +
|1.75
 +
|6.06
 +
|38.3
 +
|-
 +
|uint32_t
 +
|1.75
 +
|6.06
 +
|37.5
 +
|-
 +
|
 +
|
 +
|
 +
|
 +
|-
 +
|float
 +
|8.125
 +
|10
 +
|31.5
 +
|}
 +
Как вы можете заметить, время вычислений отличается в разы даже для целочисленных типов данных, так что всегда нужно прикидывать, какая максимальная величина будет храниться в переменной, и выбирать соответствующий тип данных. Стараться не использовать 32-битные числа там, где они не нужны, а также по возможности не использовать <code>float</code>. В то же время, умножить <code>long</code> на <code>float</code> будет выгоднее, чем делить long на целое число. Такие моменты можно считать заранее как 1/число и умножать вместо деления в критических ко времени выполнения моментах кода.
 +
 +
=== Отказаться от float ===
 +
----Из таблицы выше вы также можете узнать, что на действия с числами с плавающей точкой микроконтроллер тратит в несколько раз больше времени по сравнению с целочисленными типами. Дело в том, что у большинства микроконтроллеров AVR (что стоят на Ардуинах) нет “хардверной” поддержки вычислений float-чисел, и эти вычисления производятся не очень оптимальными программными методами. На взрослых микроконтроллерах ARM такая поддержка, к слову, имеется. Что же делать? Просто избегайте использования <code>float</code> там, где задачу можно решить целочисленными типами. Если нужно перемножить-переделить кучу float‘ов, то можно перевести их в целочисленный тип, умножив на 10-100-1000, смотря какая нужна точность, вычислить, а затем результат снова перевести в <code>float</code>. В большинстве случаев это получается быстрее, чем вычислять float напрямую:
 +
[[Файл:Float.png|центр|мини|700x700пкс]]
 +
 +
 +
=== Заменить Ардуино-функции их быстрыми аналогами ===
 +
----Если в проекте очень часто используется периферия микроконтроллера (АЦП, цифровые входы/выходы, генерация ШИМ…), то нужно знать одну вещь: Ардуино (на самом деле Wiring) функции написаны так, чтобы защитить пользователя от возможных ошибок, внутри этих функций находится куча различных проверок и защит “от дурака”, поэтому они выполняются гораздо дольше, чем могли бы. Также некоторая периферия микроконтроллера настроена так, что работает очень медленно. Пример: <code>digitalWrite()</code> и <code>digitalRead()</code> выполняются около 3.5 мкс, когда прямая работа с портом микроконтроллера занимает 0.5 мкс, что почти на порядок быстрее. analogRead() выполняется 112 мкс, хотя если его настроить чуть по-другому, он будет выполняться почти в 10 раз быстрее, не особо потеряв в точности.
 +
 +
=== Использовать switch вместо else if ===
 +
----В ветвящихся конструкциях со множественным выбором по значению целочисленной переменной стоит отдавать предпочтение конструкции <code>switch-case</code>, она работает быстрее <code>else if</code> (изучали в уроках про условия и выбор). Но помните, что <code>switch</code> работает только с целочисленными значениями!
 +
 +
<code>// тест SWITCH</code>
 +
 +
<code>// keka равна 10</code><span class="enlighter-c0">// тест SWITCH</span>
 +
 +
<code>// время выполнения: 0.3 мкс (5 тактов)</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>switch (keka) {</code><span class="enlighter-text">num</span>
 +
 +
<code>case 10: break;  // выбираем это</code><span class="enlighter-text">num</span>
 +
 +
<code>case 20: break;</code>
 +
 +
<code>case 30: break;</code>
 +
 +
<code>case 40: break;</code>
 +
 +
<code>case 50: break;</code>
 +
 +
<code>case 60: break;</code>
 +
 +
<code>case 70: break;</code>
 +
 +
<code>case 80: break;</code>
 +
 +
<code>case 90: break;</code>
 +
 +
<code>case 100: break;</code>
 +
 +
<span class="enlighter-text">num</span><code>}</code><span class="enlighter-text">num</span>
 +
 +
<code>// keka равна 100</code><span class="enlighter-c0">// тест SWITCH</span>
 +
 +
<code>// время выполнения: 0.3 мкс (5 тактов)</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>switch (keka) {</code><span class="enlighter-text">num</span>
 +
 +
<code>case 10: break;</code>
 +
 +
<code>case 20: break;</code>
 +
 +
<code>case 30: break;</code>
 +
 +
<code>case 40: break;</code>
 +
 +
<code>case 50: break;</code>
 +
 +
<code>case 60: break;</code>
 +
 +
<code>case 70: break;</code>
 +
 +
<code>case 80: break;</code>
 +
 +
<code>case 90: break;</code>
 +
 +
<code>case 100: break;  // выбираем это</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>}</code><span class="enlighter-text">num</span>
 +
 +
<code>// тест ELSE IF</code><span class="enlighter-c0">// тест SWITCH</span>
 +
 +
<code>// keka равна 10</code><span class="enlighter-c0">// тест SWITCH</span>
 +
 +
<code>// время выполнения: 0.50 мкс (8 тактов)</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>if (keka == 10) {  // выбираем это</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 20) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 30) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 40) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 50) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 60) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 70) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 80) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 90) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 100) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>}</code><span class="enlighter-text">num</span>
 +
 +
<code>// keka равна 100</code><span class="enlighter-c0">// тест SWITCH</span>
 +
 +
<code>// время выполнения: 2.56 мкс (41 такт)</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>if (keka == 10) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 20) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 30) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 40) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 50) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 60) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 70) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 80) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 90) {</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>} else if (keka == 100) {  // выбираем это</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>}</code>
 +
 +
<span class="enlighter-text">num</span>
 +
 +
=== Использовать константы ===
 +
----Константы (<code>const</code> или <code>#define</code>) “работают” гораздо быстрее переменных при передаче их в качестве аргументов в функции. Делайте константами всё, что не будет меняться в процессе работы программы! Пример:
 +
 +
<code>byte pin = 3;    // частота будет 128 кГц (GyverCore)</code><span class="enlighter-c0">// тест SWITCH</span>
 +
 +
<code>//const byte pin = 3; // частота будет 994 кГц (GyverCore)</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>void setup() {</code><span class="enlighter-text">num</span>
 +
 +
<code>pinMode(pin, OUTPUT);</code>
 +
 +
<span class="enlighter-text">num</span><code>}</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>void loop() {</code><span class="enlighter-text">num</span>
 +
 +
<code>for (;;) {</code><span class="enlighter-text">num</span>
 +
 +
<code>digitalWrite(pin, 1);</code>
 +
 +
<code>digitalWrite(pin, 0);</code>
 +
 +
<code>}</code><span class="enlighter-text">num</span>
 +
 +
<span class="enlighter-text">num</span><code>}</code>
 +
 +
Почему это происходит? Компилятор оптимизирует код, и с константными аргументами он может выбросить из функции почти весь лишний код (если там есть, например, блоки <code>if-else</code>), и она будет работать быстрее.

Текущая версия на 21:08, 22 июня 2021

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

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

Оптимизация

В оптимизации есть несколько важных моментов:

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

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

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

Основные постулаты оптимизации:

  1. Начинать оптимизацию нужно с самых «узких» мест программы. Если мы будем оптимизировать те места, где и без нашего вмешательства все быстро работает, то прирост производительности будет минимален. Это основной закон оптимизации, от него мы и будем отталкиваться, разбирая остальные.
  2. Оптимизировать лучше те места, которые регулярно повторяются в ходе работы. Этот закон относится к циклам и подпрограммам. Если можно хотя бы немного оптимизировать цикл, то делайте это не задумываясь. Если в одной итерации мы добьемся прироста в 2%, то после 1000 повторений это уже будет достаточно большое значение.
  3. Старайтесь не слишком злоупотреблять оптимизацией единичных операций. Этот закон – своеобразное продолжение предыдущего. Оптимизируя фрагмент, который будет вызван лишь один раз, мы вряд ли добьемся ощутимого прироста (но если эффект будет ощутим (>10%, что бывает крайне редко), то оптимизация лишней не будет).
  4. Используйте ассемблер только там, где скорость работы очень важна. Как уже писалось ранее, сейчас ассемблер не дает огромного прироста скорости. Поэтому использовать его стоит лишь в самых «узких» местах программы.
  5. Задумывайтесь над оптимизацией. Неправильная оптимизация может даже навредить программе, увеличить время ее разработки, практически не уменьшив скорость ее работы.


Вырезание условий и свитчей

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

Вырезание swtich.png

Если объявить num как обычную переменную – в скомпилированный код попадёт вся конструкция целиком, три условия или весь свитч. Если num сделать константой const или дефайном #define – компилятор вырежет весь блок условий или свитч и оставит только содержимое, которое получается при заданном num. В этом очень легко убедиться, скомпилировав код и посмотрев на объём занимаемой памяти в логе компилятора. При помощи данного трюка можно ускорить выполнение некоторых функций и уменьшить занимаемое ими место в памяти.

Использовать переменные соответствующих типов

Тип переменной/константы не только влияет на занимаемый ей объём памяти, но и на скорость вычислений! В реальном коде время может быть меньше. Примечание: время приведено для кварца 16 МГц.

Тип данных Время выполнения, мкс
Сложение и вычитание Умножение Деление, остаток
int8_t 0.44 0.625 14.25
uint8_t 0.44 0.625 5.38
int16_t 0.89 1.375 14.25
uint16_t 0.89 1.375 13.12
int32_t 1.75 6.06 38.3
uint32_t 1.75 6.06 37.5
float 8.125 10 31.5

Как вы можете заметить, время вычислений отличается в разы даже для целочисленных типов данных, так что всегда нужно прикидывать, какая максимальная величина будет храниться в переменной, и выбирать соответствующий тип данных. Стараться не использовать 32-битные числа там, где они не нужны, а также по возможности не использовать float. В то же время, умножить long на float будет выгоднее, чем делить long на целое число. Такие моменты можно считать заранее как 1/число и умножать вместо деления в критических ко времени выполнения моментах кода.

Отказаться от float

Из таблицы выше вы также можете узнать, что на действия с числами с плавающей точкой микроконтроллер тратит в несколько раз больше времени по сравнению с целочисленными типами. Дело в том, что у большинства микроконтроллеров AVR (что стоят на Ардуинах) нет “хардверной” поддержки вычислений float-чисел, и эти вычисления производятся не очень оптимальными программными методами. На взрослых микроконтроллерах ARM такая поддержка, к слову, имеется. Что же делать? Просто избегайте использования float там, где задачу можно решить целочисленными типами. Если нужно перемножить-переделить кучу float‘ов, то можно перевести их в целочисленный тип, умножив на 10-100-1000, смотря какая нужна точность, вычислить, а затем результат снова перевести в float. В большинстве случаев это получается быстрее, чем вычислять float напрямую:

Float.png


Заменить Ардуино-функции их быстрыми аналогами

Если в проекте очень часто используется периферия микроконтроллера (АЦП, цифровые входы/выходы, генерация ШИМ…), то нужно знать одну вещь: Ардуино (на самом деле Wiring) функции написаны так, чтобы защитить пользователя от возможных ошибок, внутри этих функций находится куча различных проверок и защит “от дурака”, поэтому они выполняются гораздо дольше, чем могли бы. Также некоторая периферия микроконтроллера настроена так, что работает очень медленно. Пример: digitalWrite() и digitalRead() выполняются около 3.5 мкс, когда прямая работа с портом микроконтроллера занимает 0.5 мкс, что почти на порядок быстрее. analogRead() выполняется 112 мкс, хотя если его настроить чуть по-другому, он будет выполняться почти в 10 раз быстрее, не особо потеряв в точности.

Использовать switch вместо else if

В ветвящихся конструкциях со множественным выбором по значению целочисленной переменной стоит отдавать предпочтение конструкции switch-case, она работает быстрее else if (изучали в уроках про условия и выбор). Но помните, что switch работает только с целочисленными значениями!

// тест SWITCH

// keka равна 10// тест SWITCH

// время выполнения: 0.3 мкс (5 тактов)num

numswitch (keka) {num

case 10: break; // выбираем этоnum

case 20: break;

case 30: break;

case 40: break;

case 50: break;

case 60: break;

case 70: break;

case 80: break;

case 90: break;

case 100: break;

num}num

// keka равна 100// тест SWITCH

// время выполнения: 0.3 мкс (5 тактов)num

numswitch (keka) {num

case 10: break;

case 20: break;

case 30: break;

case 40: break;

case 50: break;

case 60: break;

case 70: break;

case 80: break;

case 90: break;

case 100: break; // выбираем этоnum

num}num

// тест ELSE IF// тест SWITCH

// keka равна 10// тест SWITCH

// время выполнения: 0.50 мкс (8 тактов)num

numif (keka == 10) { // выбираем этоnum

num} else if (keka == 20) {num

num} else if (keka == 30) {num

num} else if (keka == 40) {num

num} else if (keka == 50) {num

num} else if (keka == 60) {num

num} else if (keka == 70) {num

num} else if (keka == 80) {num

num} else if (keka == 90) {num

num} else if (keka == 100) {num

num}num

// keka равна 100// тест SWITCH

// время выполнения: 2.56 мкс (41 такт)num

numif (keka == 10) {num

num} else if (keka == 20) {num

num} else if (keka == 30) {num

num} else if (keka == 40) {num

num} else if (keka == 50) {num

num} else if (keka == 60) {num

num} else if (keka == 70) {num

num} else if (keka == 80) {num

num} else if (keka == 90) {num

num} else if (keka == 100) { // выбираем этоnum

num}

num

Использовать константы

Константы (const или #define) “работают” гораздо быстрее переменных при передаче их в качестве аргументов в функции. Делайте константами всё, что не будет меняться в процессе работы программы! Пример:

byte pin = 3; // частота будет 128 кГц (GyverCore)// тест SWITCH

//const byte pin = 3; // частота будет 994 кГц (GyverCore)num

numvoid setup() {num

pinMode(pin, OUTPUT);

num}num

numvoid loop() {num

for (;;) {num

digitalWrite(pin, 1);

digitalWrite(pin, 0);

}num

num}

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

Источник — http://wiki.me-robotics.ru/index.php?title=Основные_методики_оптимизации_кода&oldid=723