Деление

Не во всех процессорах имеются инструкции для выполнения операций деления. Например, их нет в Cortex-M0. Поэтому часто вместо этого компилятор реализует деление путем вызова кода из стандартной библиотеки. В зависимости от реализации и типов входных данных такая операция может занять до 100 тактов. Следовательно, там, где возможно, лучше избегать операций / и %. Так или иначе, деление чисел на константу может быть эффективно переписано.

В книге «Алгоритмические трюки для программистов» Генри Уоррена-младшего (Hacker’s Delight, Henry S. Warren Jr.) есть целая глава, посвящённая делению целочисленных переменных.

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

void get_digits(uint32_t value, uint8_t *digits) {
    digits[2] = value % 10;
    value /= 10;
    digits[1] = value % 10;
    value /= 10;
    digits[0] = value;
}

Более эффективно эту же функцию можно записать так:

void get_digits(uint32_t value, uint8_t *digits) {
    digits[0] = value / 100;
    value -= digits[0] * 100;
    digits[1] = value / 10;
    value -= digits[1] * 10U;
    digits[2] = value;
}

Или другой пример. Циклический буфер — часто использующаяся программистами структура, при реализации которой требуется операция деления с остатком. Допустим, размер хранится в buffer_size, а позиция в буфере — это offset, тогда:

offset = (offset + increment) % buffer_size;

Такую запись лучше заменить на следующую:

offset += increment
if (offset >= buffer_size) {
    offset -= buffer_size;
}

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

Другим популярным «хаком» является замена на побитовое смещение, когда деление производится на степени двойки.

// a == 8;
a /= 2;
// a == 4

Более эффективная запись:

// a == 0b 0000 1000
a >>= 2;
// a == 0b 0000 0100

Изменено:

Эффективный код для Cortex-M: 3 комментария

  1. >Вопрос 48. Какой тип целочисленной переменной лучше всего СПОЛЬЗОВАТЬ в микроконтроллере PIC24 и почему?

  2. Здравствуйте.
    Мучаю STM32F030F4P6 и изучаю вашу книгу.
    Замерял сегодня скорость выполнения вышеприведённых циклов на разных оптимизациях кода O1 O2 O3.
    И у меня получилось что цикл
    for (i = 0; i < 1000000; i++) {} выполняется на любой оптимизации за 4800 микросекунд
    цикл for ( i = 1000000; i != 0; i—){} выполняется за 4800 микросек. только на оптимизации O1 . При оптимизации O2 и O3 он выполняется за 10800 микросекунд.
    цикл
    n = 1000000;
    do {
    // code here
    } while (—n != 0); на любой оптимизации выполняется за 10800 микросекунд

    может это связано с компиляцией и оптимизацией именно для данного чипа.
    но лучше я буду писать for (i = 0; i < 1000000; i++){}

  3. Взял осциллограф и всё перепроверил. Оказалось что у меня таймер переполнялся.
    Думаю что мои коменты публиковать не нужно )

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.