Условные операторы

Эффективный код для Cortex-M

chrns

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

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

Современные процессоры (не только ARM) имеют функцию «предсказания» (англ. prediction) следующей инструкции, основанной на статистике. Однако предсказание не всегда верно, а значит, конвейер приходится перезагружать, понижая тем самым производительность. Чем больше условных операторов, тем хуже. Вложенные условные операции — хуже вдвойне!

Для демонстрации «проблемности» таких операций рассмотрим небольшой пример.

uint32_t sum = 0;
// start count
for (uint32_t i = 0; i < 1000; i++)
    if (<condition> == 0) sum++;
// stop count

Достаточно просто, не правда ли? Необходимо как минимум 1000 раз проверить условие <condition>, и, если оно верно, проитерировать значение sum. В самом плохом случае (без учета оптимизации, когда <condition> будет выдавать постоянно true), потребуется порядка пяти тысяч операций. Составим несколько условий, подсчитав необходимое число тактов, и сравним с реальным значением.

Условие цикла, увеличение i на 1, проверка в if и сложение. Значения в таблице приведены с включенным флагом -O1, а измерения осуществлялись при помощи SysTick.

УсловиеШаблонТакты
(i & 0xFFFFFFFF)Всегда T107910
(i & 0x00000000)Всегда F5011
(i & 2)TTFF …9015
(i & 4)TTTTFFFF …8016

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

Другой пример плохой реализации — составное условие. Допустим, необходимо проверить принадлежность входного числа x ⊂ [0,32) к некоторому множеству ([1,3,6,8,27,29]). Выразить в виде кода это можно следующим образом:

uint8_t is_belong(uint32_t n) {
    if ( (n == 1) || (n == 3) || (n == 6) || (n == 8) || (n == 27) || (n == 29) )
        return 1;
    return 0;
}

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

/*
  29 27         8 6   3 1
0010 1000 ..... 1010 0101 =>
[31.......................0]
=> ((1 << 1) | (1 << 3) | (1 << 6) | (1 << 8) | (1 << 27) | (1 << 29)) =>
=> 0x2800014A
*/
uint8_t is_belong(uint32_t n) {
    return ( (1 << n) & (0x2800014A) ) ? 1 : 0;
}

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


Изменено: