К вопросу о сдвигах, знаках и быстродействии МК
«Найди всему причину и ты многое поймешь»
Возможно, мои постоянные читатели (ну не может быть, чтобы их не было) помнят, что я как то в своем посте недоумевал по поводу того, что при описании регистров внешних устройств используется атрибут unsigned. В комментариях было предположено, что это сделано, чтобы избегать неопределенного поведения при сдвигах и я согласился. Как я недавно обнаружил, есть еще одна причина для подобного использования атрибута и она может быть приложена не только к регистрам, но и к обычным переменным.
Итак, мы начинаем.
lsl/lsr логический сдвиг влево/вправо, младший/старший бит очищается;
rol/ror циклический сдвиг влево/вправо через перенос (сдвигаем 9 битов);
asr арифметический сдвиг вправо, старший (знаковый) бит сохраняется (обратим внимание на то, что выполнить данный вид сдвига влево в общем случае невозможно в принципе).
Все эти команды выполняются над байтовым операндом и являются основой для реализации всех остальных возможных сдвигов. Например, сдвиг слова (2 байта rh, rl) со знаком вправо на 1 разряд, реализуется следующей последовательностью:
asr rh; ror rl;
Рассмотрим простенький пример кода и соответствующий ему ассемблерный код для МК с системой команд AVR, как всегда, полученный на сайте godbolt.org. (подразумевается, что оптимизация включена и переменная размещена в регистре r24)
int8_t byte;
byte = byte << 1;
clr r25
sbrc r24,7
com r25
lsl r24
rol r25
и видим, что операция занимает пять команд?
Примечание: Если кто в комментах подскажет, как оформить этот фрагмент (и последующие) в 2 колонки, буду признателен.
Из кода на ассемблере видно, что байтовая переменная расширяется до целого (16-битов) типа в первых трех командах, а в следующих двух осуществляется собственно сдвиг двухбайтового числа — как то странно, чтобы не сказать больше.
Со сдвигом вправо ничуть не лучше
byte = byte >> 1;
clr r25
sbrc r24,7
com r25
asr r25
ror r24
— те же пять команд. Между тем очевидно, что на самом деле для выполнения последней операции нужна одна единственная команда
аsr r24
а для первой операции не больше. Я неоднократно заявлял, что в настоящее время компилятор создает ассемблерный код ничуть не хуже программиста (правда, речь шла о ARM системе команд), особенно если ему немного помочь, и вдруг такой облом. Но попробуем помочь компилятору создать правильный код, может быть дело в смешении типов в операции сдвига и попробуем
byte = byte >> (int8_t) 1;
— не помогло, от слова «совсем», но вариант
byte=(uint8_t) byte >> 1;
дает чуть лучший результат
ldi r25,lo8(0)
asr r25
ror r24
— три команды, поскольку расширение до целого теперь занимает одну команду — уже лучше, хотя и не идеально, та же самая картина для
byte=(uint8_t) byte << 1;
— три команды. Ладно, чтобы не писать лишние приведения, делаем саму переменную без-знаковой
uint8_t byteu;
и БИНГО — ассемблерный код полностью соответствует нашим ожиданиям
byteu = byteu << 1;
lsr r24
Странно как то, казалось бы, какая разница, указать правильный тип переменной сразу, или привести ее непосредственно в операции —, а оказывается, разница есть.
Дальнейшие исследования показали, что ассемблерный код учитывает тип переменной, которой присваивается результат, поскольку
byteu = byte << 1;
работает отлично и производит минимальный код, а вариант
byte = byteu << 1;
не может обойтись без трех команд.
Наверняка такое поведение описано в стандарте языка, прошу знающих в комментарии, я же в очередной раз с гордостью заявлю, что «чукча не читатель» и продолжу повествование.
Так вот, сдвигу вправо такой прием не помог — по прежнему 3 команды (хорошо. что не 5, как для знакового варианта) и улучшить результат мне никак не удалось никакими способами.
Но в любом случае мы видим, что операции сдвига с без-знаковым числом проводятся быстрее, нежели с его оппонентом. Поэтому, если мы не собираемся трактовать старший бит числа, как знак (а в случае с регистрами это так и есть, как правило) то нам безусловно надлежит добавлять атрибут unsigned, что мы и будем делать в дальнейшем.
Оказывается, со сдвигами вообще все на редкость интересно, начнем увеличивать количество позиций при сдвиге влево и смотреть на результаты: <<1 занимает 1 такт, <<2 — 2, <<3 — 3, 4 — 2 неожиданно, компилятор применил хитрую оптимизацию
swap r24
andi r24,lo8(-16)
где команда swap меняет местами два ниббла в байте. Далее на основе последней оптимизации
ror r24
clr r24
ror r24
использован бит переноса,
Кстати, вот Вам интересная задача — за какое минимальное время можно выполнить операцию
uint16_t byteu;
byteu = byteu << 4;
которая переводит 0×1234 в 0×2340. Очевидное решение — 4 раза выполнить пару команд
lsl rl
rol rh
приводит к 4×2=8 тактам, я быстро придумал вариант
swap rl ; 1243
swap rh ; 2143
andi rh,0xf0 ; 2043
mov tmp,rl
andi tmp,0x0f
or rh,tmp ; 2343
andi rl,0xf0 ; 2340
который требует 7 тактов и промежуточный регистр. Так вот, компилятор порождает код из 6 команд и никаких промежуточных регистров — круто, да.
swap rl ; 1243
swap rh ; 2143
andi rh,0xf0 ; 2043
eor rh,rl ; 6343
andi r2l,0xf0 ; 6340
eor rh,rl ; 2340
Просто получаю эстетическое удовольствие от этого фрагмента.
Что характерно, для 16-битных чисел разница между кодом для знакового и без-знакового числа при сдвиге влево пропала, странно как то.
Вернемся к нашим байтам и начнем двигать вправо. Как мы помним, для знакового байта мы имеем 5 тактов, для без-знакового — 3 и уменьшить это время нельзя. Или все таки можно — да, можно, но уж больно странным способом (GCC с включенными оптимизациями — «это очень уж странное место»), а именно вот таким
byteu = (byteu >> 1) & 0x7F;
который порождает ровно одну команду для обоих вариантов знака. Подходит и вариант
byteu = (byteu & 0xFE) >> 1;
но только для без-знакового числа, со знаковым все становится еще более уныло — 7 тактов, так что продолжаем исследовать только первый вариант.
Не могу сказать, что я понимаю происходящее, ведь очевидно, что логическое умножение (&) на такую константу после такого сдвига нет никакого смысла проводить (и его не проводят), но на код самого сдвига наличие операции & влияет. «Ты суслика видишь — нет — и я не вижу, а он есть».
Сдвиги на 2 и так далее показали, что важно погасить у результата знаковый бит, но ведь число исходно без-знаковое, в общем, фигня какая то получается, «но ведь работает же» — единственное, что можно сказать по этому поводу.
Тем не менее, можно с уверенностью заявить, что интерпретация содержимого регистров и памяти, как без-знаковых чисел, позволяет производить ряд операций (например, сдвиги или расширение значения) с ними проводить быстрее и порождает более компактный код, поэтому может быть настоятельно рекомендована при написании программ для МК, если иное (интерпретация как числа сщ знаком)не является обязательным условием.
