Keil C51: Маленькие хитрости Си.
Организация цикла на 256 итераций
Часть 2
Александр Бельченко
4 декабря 2003 года
В первой части статьи про организацию цикла на 256 итераций я показал несколько приемов по оптимизации циклов в программах на Keil C51. Обсуждение корректности показанного подхода, которое разбушевалось в телеконференции, заставляет меня снова вернуться к этой (поистине неисчерпаемой!) теме. Сегодня я собираюсь объяснить те примеры, которые были приведены в первой части.
C чего все началось
Когда я писал программы для микроконтроллеров семейства MCS-51 на языке ассемблера, то практически всегда для построения циклов использовал инструкцию процессора DJNZ. Позже я перешел на Си. Но привычка думать о том, что циклы строятся на основе DJNZ, у меня осталась.
Язык Си привносит много удобства в процесс кодирования алгоритмов. В Си коде легче разбираться по программе (своей или чужой). Он позволяет сосредотачиваться на логике программы вместо того, чтобы постоянно думать о том, как оптимальнее построить те или иные тривиальные вещи.
Но, как только появляется желание оптимизировать получаемый код, я сразу же открываю листинг компилятора и смотрю, какие ассемблерные конструкции строит мне компилятор. Часто то, что я вижу, мне не нравится. Особенно, когда получаются лишние телодвижения на пустом месте.
Одним из главных объектов моего пристального внимания при оптимизации алгоритмов являются циклы. Поскольку любой «лишний» код в циклах повторяется N раз, то и любая удачная оптимизация большого цикла дает N-кратный эффект. А благодаря знанию ассемблера, становится легче находить «толстые» места в листинге компилятора.
При написании циклов с небольшим и заранее известным числом итераций естественным стремлением для меня является попытка добиться того, чтобы компилятор построил цикл на основе инструкции DJNZ. Решение «в лоб»:
for( i=0; i<128; i++)
не дает желаемый результат. Попытка подстроиться под логику инструкции DJNZ приводит к варианту:
for( i=128; i; i--)
Этот прием, я надеюсь, был достаточно понятен из первой части статьи про циклы.
Частный случай с циклом на 256 итераций
Случай с циклами на 256 итераций можно считать частным и не часто встречающимся. Но при статистической обработке данных иногда удобнее обрабатывать выборки, объем которых является степенью двойки (64,128,256,512,...). А статистическая обработка массивов данных часто предполагает использование циклов. Поэтому, выбирая обработку для массива на 256 элементов, тут же начинаешь задумываться и о цикле обработки.
Ассемблер MCS-51 и правила двоичной арифметики подсказывают, что для организации цикла на 256 итераций можно воспользоваться однобайтным счетчиком цикла и построить его на основе инструкции DJNZ. При этом достигается двойной эффект: минимизация временных затрат и минимизация затрат памяти на организацию цикла.
Вот ассемблерный вариант цикла на 256 итераций:
mov i, #0
label:
...
; тело цикла
...
djnz i, label
При «переводе» его на язык Си получаем:
unsigned char i = 0;
do
{
...
// тело цикла
....
} while( --i );
Начальное значение счетчика цикла
В первой части я написал, что байтовой переменной i присваивается значение 256. Это «святотатство» вызвало огромную волну возмущения у многих, кто прочел мою статью. (Напиши я в коде «i=0» — это бы никого не задело :). Но я написал именно 256, поскольку у меня на это есть свои причины.
- На самом деле переменной типа unsigned char присваиваться будет только младший байт константы 256, который равен нулю. Как я уже говорил, здесь действует правило неявного приведения типов. Правда, чаще всего им пользуются, когда хотят присвоить переменной с большей разрядностью значение меньшей разрядности. В нашем случае при приведении типов происходит потеря информации, о чем грамотный компилятор должен вам выдать предупреждение. Keil C51 такого предупреждения не выдает, что строго говоря может в других ситуациях осложнить поиск ошибок в программе.
- Когда я присваиваю счетчику цикла значение 256, то пытаюсь таким образом дать себе подсказку о количестве итераций цикла. Вспоминать каждый раз при анализе Си-текста программы о трюке с переполнением байтовой переменной и поведением инструкции DJNZ не имеет смысла. Этот прием лишь отражает мои личные пристрастия к стилю написания программ. О стиле (хорошем и плохом) говорится очень много, но так или иначе у каждого опытного программиста постепенно формируется свой стиль на основе личных предпочтений. Так, например, я предпочитаю условия сравнения с нулем записывать как можно подробнее: запись if (var != 0) я предпочитаю вместо короткого if (var). Хотя некоторые классики такой вариант считают плохим стилем.
- Также, я уже говорил, что присваивание значения 256 вместо нуля делает программу в некотором смысле более «устойчивой» к смене типа переменной от unsigned char к unsigned int. Это, конечно, призрачное достоинство, но один раз из тысячи может сработать.
- В качестве начального значения при организации циклов по обработке данных у меня часто выступает символьная константа, определяемая при помощи инструкции препроцессора (#define QTY 256), или задаваемая, как перечислимый тип (enum { QTY = 256 };). Эта же константа задает размер массива данных. При прогонке разных вариантов алгоритма гораздо удобнее изменять взаимосвязанные вещи (такие как размер массива и число итераций цикла обработки) в одном месте.
Про корректность использования такого трюка
При программировании любого алгоритма производится перевод некоторой идеи в язык, понятный машинным трансляторам. Таким образом, для каждого конкретного машинного языка «переводы» будут отличаться. Широкое распространение одного конкретного языка (такого как Си) со статусом стандарта де-факто привело к возникновению понятия «переносимости кода». Те, кто слишком сильно верят в эту призрачную «переносимость» подчас забывают о том, что код на языке Си — это всего лишь «перевод» идеи, алгоритма на язык Си. В этом смысле идея или сам алгоритм, записанный обычным человеческим языком, обладают гораздо большей переносимостью.
Когда мы хотим оптимизировать программу на уровне исходного Си-текста (при неизменном исходном алгоритме) приходится использовать любые имеющиеся возможности. И хотя сейчас многие Си-компиляторы строят на основе стандарта ANSI C, в самом этом стандарте некоторые моменты не специфицированы до конца, а потому отданы на откуп разработчикам компиляторов. Одним из таких неопределенных моментов, как оказалось, является поведение компилятора в случае трансляции конструкций, вызывающих арифметическое переполнение целых переменных.
Поскольку в описанном приеме как раз и используются (и активно используются) правила двоичной арифметики при переполнении байтовой переменной, то данный алгоритм попадает в ту «сумеречную» зону, где нет четких правил, а ответы «да» или «нет» не имеют значения. Поэтому я посчитал нужным добавить предупреждение о возможной непереносимости этого приема. Поскольку «кто предупрежден — тот вооружен». При использовании такого приема с другим компилятором будет нелишним проверить по листингу компилятора, что у вас на самом деле получилось.
Корректный вариант с точки зрения стандарта ANSI C
Как я уже говорил, обсуждение трюка с присваиванием байту значения 256 было очень бурным. Еще более бурным стало обсуждение корректности использования такого приема, как правил беззнаковой двоичной арифметики, в личных целях :-).
Одни говорят, что в споре рождается истина. Другие — что там она же и умирает. В ходе этого спора был найден вариант вполне корректный с точки зрения стандарта ANSI C, который также позволяет использовать однобайтную переменную для организации цикла на 256 итераций. Вот этот вариант (я модифицировал то, что предложил инженер с ником Elektronik; модифицировал, естественно, чтобы получился наиболее оптимальный вариант):
i = 255;
do
{
...
// тело цикла
...
} while( i-- );
Переменная i «проходит» все значения от 255 до 0, при этом арифметическое переполнение не используется как основная часть алгоритма. Естественно, что такой цикл при трансляции в ассемблер будет построен вовсе не на основе команды DJNZ. Потому целесообразность его использования весьма призрачна (с моей точки зрения). Но, возможно, кому-то он будет полезен.
Голые факты
Я подготовил тестовый пример для Keil C51, в котором собраны для сравнения 4 варианта цикла на 256 итераций: 2 варианта с использованием двухбайтной переменной, и еще 2 с использованием однобайтной.
Скачать пример: loop_256.zip (4 КБ).
В теле всех циклов выполняется инструкция процессора NOP, которая ничего не делает, но отнимает один такт процессорного времени. Вычитая из общего времени выполнения каждого цикла 256 тактов, которые приходятся на NOP, можно оценить накладные расходы на организацию цикла в каждом из вариантов.
Я свел все данные в таблицу.
| Вариант | Тип переменной | Накладные расходы
(такт/итерацию) | Общее время
выполнения цикла
(такт) |
| for( i=0; i<256; i++) | unsigned int | 6 | 1799 |
| for( i=256; i; i--) | unsigned int | 8 | 2307 |
| i=255; do...while( i-- ); | unsigned char | 6 | 1793 |
| i=0; do...while( --i ); | unsigned char | 2 | 769 |
Как видно из этой таблицы, на декремент двухбайтной переменной программа затрачивает больше времени, чем на инкремент. А «корректный» вариант цикла с однобайтной переменной выполнятся практически с той же скоростью, что и цикл с двухбайтной переменной. Единственным достоинством этого метода становится лишь экономия одного (1) байта во внутреннем ОЗУ процессора.
Заключение
Если вы хотите не просто писать программы, но и глубже понимать, что у вас при этом получается, то эта статья могла дать вам обильную пищу для размышлений. Я лишь хотел показать, что в программировании для достижения наиболее оптимального результата иногда стоит отойти от привычных комбинаций. А в случае, когда при разработке программы для устройства сталкиваешься с жесткими ограничениями на ресурсы процессора (будь-то память или быстродействие), когда некоторые участки программы приходится буквально «вылизывать», в этом случае все средства хороши. А читаемость программы и ее переносимость при этом отступают на задний план.
Можно писать все на ассемблере, а можно и на Си — как на ассемблере. Но без знания ассемблера такие фокусы проворачивать гораздо тяжелее.
Благодарности
Выражаю свою благодарность тем людям, которые со мной аргументировано спорили, и которые меня поддерживали против необоснованных нападок.
Особая благодарность: SM, Bill.
![[Python Powered]](/i/PythonPoweredSmall.gif){kind=small}