Оптимизация скорости

С ростом навыков и созданием более крупных проектов вы столкнётесь с тем, что "Ардуина" перестанет справляться с тем объёмом работы, который вы хотите от неё получить. Может банально не хватать быстродействия в расчётах, обновлении информации на дисплеях, отправки данных и прочих ресурсозатратных действий! Рассмотрим способы оптимизации скорости работы кода, в прошлом уроке речь шла об оптимизации памяти.

С чем компилятор справится сам #

Компилятор оптимизирует некоторые вычисления:

• Заменяет типы данных на более оптимальные там, где это возможно и не повлияет на результат. Например val /= 2.8345 выполняется в 4 раза дольше, чем val /= 2.0, потому что 2.0 была заменена на 2
• Заменяет операции целочисленного умножения на степени двойки (2^n) битовым сдвигом. Например, val * 16 выполняется в два раза быстрее, чем val * 12, потому что будет заменена на val << 4
  • Примечание: для операций целочисленного деления такая оптимизация не проводится и её можно сделать вручную (см. ниже)
• Заменяет операции взятия остатка от деления % на степени двойки битовой маской (см. ниже)
  • Примечание: такая оптимизация производится не всегда (по моим тестам), поэтому лучше всё таки заменять взятие остатка от деления на битовую маску
• Предварительно вычисляет всё, что можно вычислить (константы). Например val /= 7.8125 выполняется столько же, сколько val /= (2.5*10.0/3.2+12.28*3.2), потому что компилятор заранее посчитал и подставил результат всех действий с константами

Как измерить скорость #

Для большинства случаев достаточно стандартной конструкции с millis() / micros() - запомнить текущее время, выполнить действие, вычесть запомненное время из текущего. Точность измерения тем выше, чем меньше в "измеряемом" коде используется запрет прерываний. Минимальная единица измерения (для AVR Arduino) - 4 микросекунды, это разрешение функции micros():

void setup() {
    Serial.begin(115200);
}

void loop() {
    uint32_t us = micros();

    // измеряемый код
    delay(123);
    // измеряемый код

    us = micros() - us;
    Serial.println(us);
    delay(1000);
}

Для "взрослой" оптимизации кода (вычисления, IO) этой точности будет мало. Я написал библиотеку для измерения времени выполнения кода, она работает на:

• AVR (библиотека использует Timer 1)
• ESP8266
• ESP32

На AVR (Arduino Nano, UNO...) даёт точность до 1 такта процессора:

#include <Benchmark.h>

void setup() {
    Serial.begin(115200);
    benchBegin();
    delay(1);
    benchEnd(Serial);
}
void loop() {}

Оптимизация #

Типы переменных #

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

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

Отказ от float #

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

Просто избегайте использования float там, где задачу можно решить целочисленными типами. Если нужно перемножить-переделить кучу float'ов, то можно перевести их в целочисленный тип, умножив на 10/100/1000, смотря какая нужна точность, вычислить, а затем результат снова перевести в float. В большинстве случаев это получается быстрее, чем вычислять float напрямую:

// допустим, нам нужно хитро обработать значение float с датчика
// или хранить массив таких значений, не тратя лишнюю память.
// пусть sensorRead() возвращает float температуру с точностью до 1 знака.
// Превратим её в целочисленное, умножив на 10:
int val = sensorRead() * 10;

// теперь с целочисленным val можно работать без потери точности измерения и
// можно хранить его в двух байтах вместо 4-х.
// Чтобы превратить его обратно во float - просто делим на 10
float val_f = val / 10.0;

Fixed point #

Существует также такая штука как fixed point - числа с фиксированной точкой. С точки зрения пользователя они являются обычными десятичными дробями, но по факту являются целочисленными типами и вычисляются соответственно быстрее. Нативной поддержки fixed point в Arduino нет, но можно работать с ними при помощи самописных функций, макросов или библиотек, под спойлером найдёте пример, который можно использовать на практике:

// макросы для работы с fixed point
#define FIX_BITS        8
#define FLOAT2FIX(a)    (int32_t)((a*(1 << FIX_BITS)))      // перевод из float в fixed
#define INT2FIX(a)      (int32_t)((a) << FIX_BITS)          // перевод из int в fixed
#define FIX2FLOAT(a)    (((float)(a)/(1 << FIX_BITS)))      // перевод из fixed в float
#define FIX2INT(a)      ((a) >> FIX_BITS)                   // перевод из fixed в int
#define FIX_MUL(a, b)   (((int32_t)(a) * (b)) >> FIX_BITS)  // перемножение двух fixed

void setup() {
  Serial.begin(9600);
  float x = 8.3;
  float y = 2.34;
  float z = 0;

  // сначала переводим в fixed
  int32_t a = FLOAT2FIX(x);
  int32_t b = FLOAT2FIX(y);
  int32_t c = 0;

  z = x + y;    // складываем float
  c = a + b;    // складываем fixed

  // переводим fixed обратно в float
  float cFloat = FIX2FLOAT(c);

  // выводим для сравнения результата
  Serial.println(z);
  Serial.println(cFloat);
}

/*
   Тесты скорости выполнения:
   x = 8.3;             // 0.75 us  - присваивание float
   a = FLOAT2FIX(8.3);  // 0.75 us  - конвертация float числа в fixed
   a = FLOAT2FIX(x);    // 14.9 us  - конвертация float переменной в fixed

   z = x + y;           // 8.25 us  - сложение float
   c = a + b;           // 2.0 us   - сложение fixed

   z = x * y;           // 10.3 us  - умножение float
   c = FIX_MUL(a, b);   // 6.68 us  - умножение fixed

   z = FIX2FLOAT(c);    // 13.37 us - конвертация fixed в float
*/

void loop() {}

Также у меня есть простенькая библиотека для работы с такими числами.

Заменить умножение на 2^n битовым сдвигом #

В операциях целочисленного умножения, где второй множитель является константой или числом (val * 10), можно ускорить вычисление в том случае, когда число состоит из степени двойки (2 4 8 16 32 64 128...). Для этого нужно заменить умножение на 2^n сдвигом влево на n:

• val * 2 == val << 1
• val * 8 == val << 3
• val * 32 == val << 5
• И так далее

Заменить деление на 2^n битовым сдвигом #

В операциях целочисленного деления, где делитель является константой или числом (val / 10), можно ускорить вычисление в том случае, когда делитель состоит из степени двойки (2 4 8 16 32 64 128...). Для этого нужно заменить деление на 2^n сдвигом вправо на n:

• val / 2 == val >> 1
• val / 8 == val >> 3
• val / 32 == val >> 5
• И так далее

Заменяя сдвигом деление на степень двойки помним, что это работает правильно только для положительных чисел:

64 / 8   // == 8
64 >> 3  // == 8
63 / 8   // == 7
63 >> 3  // == 7

-64 / 8   // == -8
-64 >> 3  // == -8
-63 / 8   // == -7
-63 >> 3  // == -8 (!)

Как быть: если число меньше нуля, и оно не делится на делитель нацело, надо добавить к результату единицу:

// делим знаковое val на 8 (2^3):
if ((val < 0) && (val & ((1 << 3) - 1))) result = (val >> 3) + 1;
else result = val >> 3;

Заменить остаток от деления на 2^n битовой маской #

В операциях взятия целочисленного остатка от деления, где делитель является константой или числом (val % 10), можно ускорить вычисление в том случае, когда делитель состоит из степени двойки (2 4 8 16 32 64 128...). Для этого нужно заменить взятие остатка от 2^n на битовую маску (2^n - 1):

• val % 2 == val & 1
• val % 8 == val & 7
• val % 32 == val & 31
• И так далее

Вычисление выполняется в ~17 раз быстрее (AVR).

Заменить деление и остаток на Xdiv #

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

123 / 20;   // 6
123 % 20;   // 3

Можно избавиться от остатка, заменив его быстрым умножением:

int quot = 123 / 20;        // 6
int rem = 123 - quot * 20;  // 3

Также в стандартной библиотеке (справочник) есть инструмент для этого действия - функции div, ldiv и lldiv:

div_t res;
res = div(123, 20);
res.quot;   // 6
res.rem;    // 3

Заменить деление умножением #

В операциях целочисленного деления, где делитель является константой или числом (val / 10), можно заменить деление умножением на обратное число. Идея состоит в следующем:

a / b == a * (1 / b) == (a * x) >> n, где:

• x = (2^n) / b + 1
• a * x не должно превышать ячейку 32 бита (или 16 бит для более быстрого вычисления)
• n - "масштаб". Чем больше n, тем выше точность. Нужно подобрать так, чтобы было максимальным для 32 или 16 бит, при известном максимальном значении a

Алгоритм:

• Определить n. Выразим из формулы для x: 2^n < (MAX / a_max - 1) * b, где MAX - размер ячейки для операции умножения, имеет смысл 32 бит (4294967296) или 16 бит (65356)
• Посчитать x по формуле выше
• Заменить деление на (a * x) >> n для 16 бит или ((uint32_t)a * x) >> n для 32 бит
• Бонус - поиск остатка от деления. Достаточно вычесть из делимого произведение результата от деления на делитель: a % b == a - q * b, где q = a / b, посчитанное способом выше

Вычисление выполняется в ~2 раза быстрее (AVR).

Пример расчёта:

• Хочу оптимизировать деление на 6
• Делить буду переменную, которая у меня в программе принимает значения от 0 до 130
• Вычисления ограничим в ячейке 16 бит (макс. 65536) для бОльшей скорости
• Ищем n: (65536 / 130 - 1) * 6 = 3018, то есть 2^n не должно превышать 3018, ближайшее n == 11
• Пересчитываем x: x = (2^11) / 6 + 1 = 342
• Получим выражение для вычисления a / 6: (a * 342) >> 11

Заменить деление умножением на float #

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

val / 10;   // выполняется 14.54 мкс
val * 0.1;  // выполняется 10.58 мкс

Заменить возведение в степень умножением #

Для возведения в степень у нас есть удобная функция pow(a, b), но в целочисленных расчётах лучше ей не пользоваться: она выполняется гораздо дольше ручного перемножения, потому работает с float, даже если скормить ей целое:

val = pow(val, 5);                         // выполняется 20.33 us
val = (long)val * val * val * val * val;   // выполняется 4.47 us

Заменить сдвиг указателем #

Очень часто при работе с данными бывает нужно "склеить" 16-32 бит переменную из отдельных байтов или наоборот разобрать её на байты. Обычно в таких случаях используются сдвиги:

// получить старший байт из 16 бит переменной a
b = a >> 8;

// склеить два байта в 16 бит int
v = a | (b << 8);

// разбить 24 бит цвет на каналы
r = ((uint32_t)color >> 16) & 0xFF;
g = ((uint32_t)color >> 8) & 0xFF;
b = (uint32_t)color & 0xFF;

// склеить 24 бит цвет из трёх каналов
color = ((uint32_t)r << 16) | (g << 8) | b;

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

// получить старший (второй) байт из 16 бит переменной a
b = ((uint8_t*)&a)[1];

// склеить два байта в 16 бит int
((uint8_t*)&v)[0] = a;
((uint8_t*)&v)[1] = b;

// разбить 24 бит цвет на каналы
r = ((uint8_t*)&color)[2];
g = ((uint8_t*)&color)[1];
b = ((uint8_t*)&color)[0];

// склеить 24 бит цвет из трёх каналов
((uint8_t*)&color)[2] = r;
((uint8_t*)&color)[1] = g;
((uint8_t*)&color)[0] = b;

Как это работает (на первом примере) - мы берём адрес переменной a - &a, затем преобразуем его к указателю на тип данных uint8_t - (uint8_t*)&a. Чтобы получить доступ к нужному байту в переменной, достаточно обратиться к полученной конструкции как к массиву - ((uint8_t*)&a)[номер байта] для записи и чтения.

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

Предварительно вычислять то, что можно вычислить #

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

Ещё хороший пример: расчёт величин, которые ведут себя предсказуемо, например гармонические функции sin() и cos(). На их вычисление уходит довольно-таки много времени - 119.46 мкс! На практике синусы/косинусы практически никогда не вычисляют средствами микроконтроллера, их вычисляют заранее и сохраняют в виде массива. Да, опять два стула: тратить время на вычисление или занимать память уже посчитанными данными. Также не забываем, что компилятор сам оптимизирует вычисления и делает это весьма неплохо.

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

Читайте урок про разгон аппаратуры.

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

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

• switch работает только с целочисленными данными
• case должны быть константами

Причём чем дальше находится верное условие (через несколько сравнений), тем больше времени выполняется код. При использовании switch время каждый раз одинаковое!

// тест SWITCH
// keka равна 10
// время выполнения: 0.3 мкс (5 тактов)
switch (keka) {
  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;
}

// keka равна 100
// время выполнения: 0.3 мкс (5 тактов)
switch (keka) {
  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;  // выбираем это
}

// тест ELSE IF
// keka равна 10
// время выполнения: 0.50 мкс (8 тактов)
if (keka == 10) {   // выбираем это
} else if (keka == 20) {
} else if (keka == 30) {
} else if (keka == 40) {
} else if (keka == 50) {
} else if (keka == 60) {
} else if (keka == 70) {
} else if (keka == 80) {
} else if (keka == 90) {
} else if (keka == 100) {
}

// keka равна 100
// время выполнения: 2.56 мкс (41 такт)
if (keka == 10) {
} else if (keka == 20) {
} else if (keka == 30) {
} else if (keka == 40) {
} else if (keka == 50) {
} else if (keka == 60) {
} else if (keka == 70) {
} else if (keka == 80) {
} else if (keka == 90) {
} else if (keka == 100) {   // выбираем это
}

Конструкции со сравнениями и диапазонами также можно заменить на switch-case:

// условия
if (a > 0 && a < 10) {код}
else if (a >= 11 && a < 20) {код}
else if (a >= 21 && a < 30) {код}

// switch с диапазонами
switch (a) {
    case  0 ... 10: код; break;
    case 11 ... 20: код; break;
    case 21 ... 30: код; break;
}

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

Помнить про порядок условий #

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

if ( flag && getSensorState() ) {
    // какой-то код
}

Если flag имеет значение false, функция getSensorState() даже не будет вызвана! if будет сразу пропущен (или выполнен else, если он есть). Этим нужно пользоваться, расставляя условия в порядке возрастания процессорного времени, которое требуется для их вызова/выполнения, если это функции. Например, если наша getSensorState() тратит какое-то время для выполнения, то мы ставим её после флага, который является просто переменной. Это позволит сэкономить процессорное время в те моменты, когда флаг имеет значение false.

Использовать битовые операции #

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

Использовать указатели и ссылки #

Вместо передачи "объекта" в качестве аргумента функции по значению, передавать его по ссылке или по указателю: процессор не будет выделять память под копию аргумента и создавать эту копию в качестве формальной переменной - это сэкономит время!

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

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

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

void setup() {
    pinMode(pin, OUTPUT);
}
void loop() {
    for (;;) {
        digitalWrite(pin, 1);
        digitalWrite(pin, 0);
    }
}

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

Миновать loop #

Функция loop() является вложенной во внешний цикл с некоторыми дополнительными проверками, поэтому если вам очень важно минимальное время между итерациями loop() - просто работайте в своём цикле for(;;), например вот так:

void loop() {
    for (;;) {
        // ваш код
    }
}