К сожалению дела заставили на некоторое время покинуть этот интересный форум
Но сейчас есть возможность продолжить, будем надеяться, плодотворно.
Zorko писал(а):
Поскольку цикл FOR — это настоящая рабочая лошадка, а поэтому действительно заманчиво иметь очень эффективную реализацию…
…
Вставлять дополнительную проверку на переполнение в тело цикла — это серьёзно замедлить цикл. .
Согласен, проверять и переполнение и выход за пределы
В на каждой итерации неэффективно. Более эффективные реализации цикла FOR (в т.ч. вычисление количества повторений) были рассмотрены
ранее. Но на данном этапе мне было важно получить работающую модификацию Ofront, пусть и неэффективную. Было бы трудно делать совсем новую конструкцию, вроде описанных в теоретической ветке. А вот одну доп.строчку вставить удалось.
Теперь понятно: Ofront можно модифицировать, понятно более-менее что у него за что отвечает и как изменить, чтобы остальное не нарушить. Удалось успешно модифицировать - уже дорога проложена. Пусть сама реализованная конструкция цикла не слишком удачна, зато удачно прошла модификация Ofront. А вот дальше можно попробовать другую, более оптимальную конструкцию для цикла реализовать.
Цитата:
Вычислить количество повторений цикла.
…
Код: "C"
n = начальное значение цикла;
_for__x = количество повторений цикла;
if (_for__x) {
do {
/* Тело */
n += step; _for__x--;
} while (_for__x);
}
Что же, вычисление количества повторений – интересная реализация FOR, но во всех ли случаях она эффективна? Ведь инкремент переменной цикла мы должны делать по-прежнему. Зато теперь надо делать декремент вспомогательной переменной (на 1, но ведь раньше и вовсе не делали) и вычислять количество повторений (однократно, но в общем случае используя деление). Выигрываем только в сравнении - сравнение с нулем эффективнее сравнения с произвольным числом в памяти. Это сравнение происходит на всех итерациях, что даст выигрыш, если итераций много. Что значит «много», нужно еще оценить.
В каких пределах может быть количество повторений? Минимальное число повторений =0 (ни разу), максимальное будет при единичном шаге и равно MAX(T)-MIN(T)+1. Даже для беззнаковых чисел (MIN(T)=0) это значение в диапазон не влезает (MAX(T)-0+1> MAX(T)), оно на 1 больше. Как же выходит из положения в таком случаем, например, компилятор Дельфи? А он допускает переполнение и считает, что MAX(T)+1 это 0. И действительно,
n:=0; REPEAT …DEC(n) UNTIL n=0; выполняется ровно MAX(T)+1 раз.
Но зато случай «ни разу» (n= «настоящему нулю») нужно обрабатывать отдельно, поэтому
if (_for__x) в общем случае не пойдет, нужно вместо этого написать
if (A<=B) …(или
if (n<=B)…).
Цитата:
Идея. Можно даже 256 повторов хранить в одном байте, для этого нужно будет только лишь предусмотреть это в начале цикла. Надо чуть видоизменить код. Как — пока не придумал.
Видоизменить именно так, как написал выше (256=0).
Цитата:
Как мы понимаем, в первом варианте на каждую итерацию цикла переход всего один [...while (_for__x)]. Во втором же варианте их два [1) начало while (_for__x--); 2) конец while (_for__x--)], причём первый переход хоть и исполняется всего раз в конце цикла — неисполнение условия всё равно приводит к потере машинного времени, хоть и незначительно, но всё же снижая скорость работы цикла. Но наверное второй вариант следует рассмотреть тоже.
Да, REPEAT UNTIL в машинных кодах реализуется эффективнее, чем WHILE. Если конечно умный компилятор не заменяет автоматически
WHILE P DO S; на
GOTO label; REPEAT S; label: UNTIL ~P;Цитата:
Что смущает. Ёмкость вычисления количества повторений цикла не в compile-time. Это как минимум взятие по модулю, но лучше всё-таки сделать такое вычисление один раз в начале цикла, чем n раз внутри него проверять на переполнение.
Небольшое уточнение: не взятие по модулю, а «деление нацело».
NumIters=(B-A) DIV Step + 1, при Step>0, A<=B.В общем случае (если А,В – не константы, шаг не единичный и не степень двойки), операция деления для Z80 трудоемка. Типичная реализация
деления для Z80 содержит цикл со сдвигами и сравнениями, но этот цикл выполняется столько раз, какова разрядность данных.Больше ли это, чем инкремент и сравнение с произвольным числом в цикле, который выполняется столько раз, чему равно частное? Видимо зависит от разрядности и частного. При небольшом шаге (что означает большое частное )деление эффективней, при большом - наоборот. Шаг задается константой, поэтому можно это оценить заранее, еще на этапе компиляции.
Цитата:
Трудности. Тип переменной-счётчика для Z80 оптимальнее всего будет задавать на основании вычисленного количества повторений (если известно точно, что их будет <= 255, берём байт. Если точно неизвестно, берём счётчик такого типа, чтобы хватило значений). Здесь неважно, что тип описывается как знаковый, в таком варианте использования он будет фактически без знака.
Верхнюю границу количества повторений можно оценить на этапе компиляции:
Цитата:
Если А не константа, берем А=MIN(T).
Если В не константа, берем В=MAX(T).
Вычисляем NumIters=(B-A) DIV Step + 1
Если получилось NumIters<=256, то можно использовать байтовый счетчик.
Цитата:
Оптимизация. Не заводить внутренний счётчик, если его значение будет совпадать с n.
Уточню. «Совпадать» означает единичный шаг ( ABS(Step)=1) и В=…Чему? Чему-то, с чем можно эффективно сравнить. Например, Step=-1,В=1, тогда сравнивать после декремента придется с нулем, что эффективно. Или для беззнаковых чисел Step=1,В=MAX(T), что тоже даст сравнение с нулем.
Кроме флага
Z, у процессора Z80 есть еще
V, что дает возможность эффективно использовать Step=1,В= 127 (Step=-1,В= 128). Для знаковых можно еще применить флаг
S, что позволит эффективно реализовать случай Step=-1,В= 0. Жаль, что
CY не меняется от инкремента\декремента.
Но это флаги процессора, а мы пока транслируем в С. Эффективно ли пройдет трансляция С->ассемблер?
Цитата:
Вобщем, такие вот мысли. Если я не сделал в рассуждениях явного ляпа, можно попробовать посчитать какой выигрыш будет для разного размера типов на Спектруме (в тактах), и какой — на Win32
Олег, спасибо за мысли. Думаю, на практике чаще будет встречаться единичный шаг (деление совсем не нужно) или шаг равный степени 2 (деление сводится к сдвигу). Ну и чаще наверно будет встречаться небольшой шаг, чем большой, т.е. число итераций будет велико, а значит выигрыш от быстрого сравнения тоже будет велик. Так что, эта реализация в большинстве случаев будет эффективной.
Вот только жаль, что уж очень сильно этот способ реализации отличается от стандартной схемы FOR. Значит придется очень сильно модифицировать Ofront, для чего придется получше его изучить.