Оберон-клуб «ВЄДАsoft»

Твердыня модульных языков
Текущее время: 28 мар 2024, 21:57

Часовой пояс: UTC + 2 часа




Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8  След.
Автор Сообщение
СообщениеДобавлено: 06 июл 2014, 20:00 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
После продолжительного перерыва (больше чем полгода!) вернулся к фористике. В течение этого времени я не то чтобы совсем FOR забросил, но занимался им мало и не считал нужным публиковать промежуточные неработающие версии.
Эта версия вроде бы работает и реализованы почти все идеи оптимизации, обсуждаемые ранее в этой и родственной ветках. Кое-что пока не сделано, кое-какие смутные идеи, появившиеся в ходе реализации, еще не опубликованы (потому что еще очень смутные).
Этот FOR пока не работает для типов SYSTEM.BYTE, SYSTEM.SHORTCARD и прочих беззнаковых. Такие типы требуют особой обработки, которая не реализована. Пока в качестве переменной FOR можно использовать только типы SHORTINT, INTEGER,LONGINT.
При построении цикла приходится рассматривать много случаев, поэтому программа сложная, имеет много ветвлений и тонкостей. Вполне возможно, где-то содержатся ошибки. Я протестировал основные случаи, но только слегка.
Для самых нетерпеливых выкладываю архив с измененными модулями.
Изменения выделены пурпурным, изменения накладывал на https://github.com/Oleg-N-Cher/XDev/commit/516bbaf6aa353be4b3cf69ff7245f643fe1d20af (на данный момент последний commit).
Подробное описание позднее.
P.S. 8/07/14 Нашел ошибку: не работает для случая "параметр B - не константа и не переменная, а произвольное выражение". Исправить не так просто, потому что В используется в двух местах, а если это выражение, то может возникнуть побочный эффект. Скорее всего такая проблема была и в предыдущей реализации цикла :( Вложение пока удалил.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 26 июл 2014, 12:15 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Впечатлён проделанной работой, дружище! :) Сам я таких существенных модификаций Ofront'а ещё не делал.

Вот ссылка на коммит. Прогресс налицо, у нас и правда теперь есть очень эффективный FOR. Чтобы не мониторить две ветки модулей берём твою новую (с исправлением ошибки, которое ты выслал приватно) реализацию цикла FOR за базовую, отказавшись от выборочной сборки Ofront'а со старым FOR'ом. Пока же буду тестировать дальше.


Вложения:
ForUntil.png
ForUntil.png [ 27.68 КБ | Просмотров: 20119 ]
Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 11 авг 2014, 05:02 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Нет — всё-таки разрешим юзеру выбирать реализацию цикла FOR опцией в файле Ofront.par из таких вариантов:

0: Original (по умолчанию); 1: Extended (новая); 2: Experimental (скорее всего, недокументированная)

Это решено сделать по нескольким причинам. Во-первых, как бы мы ни старались, во всех компиляторах Оберон-языков цикл FOR i := A to B реализован через WHILE A <= B; всех нам не переучить и даже, скорее всего, не убедить в достоинствах новой реализации цикла. Во-вторых, нужно соблюдать совместимость и иметь практический инструмент для работы, и здесь ничего лучше выбора на лету не придумать. Ну и, наконец, хорошо когда есть гарантированно стабильный вариант 0.

Таким образом, мы угодим и тем, кто будет против нововведения, ибо старая форма цикла будет доступна по умолчанию даже при отсутствии в Ofront.par опции FOR, и кто будет за, потому что форму цикла легко выбрать опцией даже для отдельного модуля. А ещё появляется возможность экспериментировать с новыми вариантами реализации цикла без потери функциональности существующих.

В качестве экспериментиального варианта 2 я сейчас закоммитил более раннюю реализацию Олега, которая тоже рабочая, хотя в ней наверное есть проблемы с вычислением неконстантого B.

Размеры собранной с разными вариантами цикла FOR заставки Dark Woods для ZX (с оптимизацией по размеру кода):

DarkWoods0.tap 9336 байт
DarkWoods1.tap 9417 байт
DarkWoods2.tap 9385 байт

Вариант 1 выглядит наиболее оптимальным по скорости, но я заметил, что в нём в случае B типа SHORTINT применяется приведение к int, а это дополнительные накладные расходы. Наверное это можно будет оптимизировать.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 30 ноя 2014, 17:32 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Пытался научить FOR работать с типом BYTE. Увы, Ofront сопротивляется этому на всех уровнях, и это не зависит от FOR. Практически везде проявляются ограничения того, что BYTE - не числовой тип.
Мне удалось кое-что поправить, чтобы FOR выполнялся для случая "A и B - константы".
Прежде всего в модуле OPB
Код: "OBERON"
  1. PROCEDURE Min*(tf: BYTE): INTEGER;
  2. VAR m: INTEGER;
  3. BEGIN
  4. CASE tf OF
  5. | Byte: m := -128;
  6. | SInt: m := OPM.MinSInt
  7. | Int: m := OPM.MinInt
  8. | LInt: m := OPM.MinLInt
  9. END;
  10. RETURN m
  11. END Min;
  12.  
  13. PROCEDURE Max*(tf: BYTE): INTEGER;
  14. VAR m: INTEGER;
  15. BEGIN
  16. CASE tf OF
  17. | Byte: m := 127;
  18. | SInt: m := OPM.MaxSInt
  19. | Int: m := OPM.MaxInt
  20. | LInt: m := OPM.MaxLInt
  21. END;
  22. RETURN m
  23. END Max;
нужно изменить границы, чтобы получился знаковый байт.
Далее ,во избежание ошибки "113 incompatible assignment" изменить процедуру OPP.For1Extended: вместо условия
Код: "OBERON"
  1. ((y^.typ^.form < SInt) OR (y^.typ^.form > x^.left^.typ^.form))
необходимо более сложное, учитывающее байтовый тип -
Код: "OBERON"
  1. IF (y^.class = Nconst) THEN (* если В - константа *)
  2. IF (x^.left^.typ^.form = Byte) & (( y^.conval^.intval < OPB.Min(Byte)) OR ( y^.conval^.intval > OPB.Max(Byte)))
  3. OR (x^.left^.typ^.form # Byte)&((y^.typ^.form < SInt) OR (y^.typ^.form > x^.left^.typ^.form)) THEN
  4. err(113); y := OPB.NewIntConst(0) (* то это д б константа совместимого типа *)
  5. END;

Это препятствие прошли, но дальше лежит ошибка "63 illegal value of constant", касающаяся шага, потому что любая явная или неявная (1) константа после BY несовместима с типом BYTE. Преодолеваем аналогично:
Код: "OBERON"
  1. pos := OPM.errpos; (* теперь указатель ошибок указывает на Step*)
  2. IF (z^.conval^.intval = 0) OR (z^.typ^.form < SInt) OR (z^.typ^.form > x^.left^.typ^.form) THEN
  3. IF (x^.left^.typ^.form # Byte) OR (z^.conval^.intval < OPB.Min(Byte)) OR ( z^.conval^.intval > OPB.Max(Byte))
  4. THEN err(63); z := OPB.NewIntConst(1)
  5. END;
  6. END;
Но теперь ошибка возникает в OPB.Convert, при попытке произвести инкремент или декремент, которые не хотят работать с байтовым типом. Подправляем условие и там:
Код: "OBERON"
  1. ELSIF g IN intSet THEN
  2. IF f > g THEN SetIntType(x);
  3. IF (g # Byte)&(x^.typ^.form > g) OR
  4. (g=Byte)&( (x^.conval^.intval < Min(Byte)) OR (x^.conval^.intval > Max(Byte)) )
  5. THEN err(203); x^.conval^.intval := 1
  6. END
  7. END
Вот теперь цикл FOR работает, если управляющая переменная имеет тип BYTE, а границы цикла заданы константами. Ведь в этом случае единственное, что происходит с переменной цикла - это декремент или инкремент (а его мы подправили).
Если же А или В задаётся произвольным выражением, то всё гораздо сложнее, ведь это выражения должны взаимодействовать с переменной цикла.
Думаю, исходить следует не из цикла FOR. Надо проанализировать, где и какие операции совершаются с целыми типами и подправить там, чтобы BYTE стал полноценным числовым типом.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 26 дек 2014, 17:26 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Олеж, я тут заметил, что для Спека все три варианта реализации нашего FOR уступают по размеру кода банальному REPEAT/UNTIL:
Код: "OBERON"
  1. MODULE Krujok; IMPORT B := Basic;
  2.  
  3. VAR
  4. x: SHORTINT; color: B.Color;
  5.  
  6. BEGIN (*$MAIN*)
  7. B.Init; B.CLS;
  8. B.INK(B.Blue);
  9. x := 1; REPEAT (* FOR x := 1 TO 73 BY 8 DO *)
  10. B.CIRCLE(121, 85, x); INC(x, 8);
  11. UNTIL x = 73+8; (* END; *)
  12.  
  13. color := B.Red;
  14. FOR x := 43 TO 57 BY 7 DO
  15. B.INK(color); INC(color, 2); (* {Red=2, Green=4, Yellow=6} *)
  16. B.PLOT(x, 50);
  17. B.DRAW(40, 70); B.DRAW(30, -70); B.DRAW(40, 70); B.DRAW(30, -70);
  18. END;
  19. B.PAUSE(0);
  20. B.Quit
  21. END Krujok.

REPEAT/UNTIL = 518 байт
FOR 0 (стандартный через while) = 543 байт
FOR 1 (правильный) = 526 байт
FOR 2 (экспериментальный) = 526 байт

В связи с чем возникла идея: сделать ещё одну версию FOR (компактный) для оптимизации по размеру кода, что будет особенно ценно для Спека. Работать он может по тому же принципу, что и REPEAT/UNTIL (для тех случаев, где точно известно, что количество итераций > 0). И пусть этот вариант сравнивает достижение конца цикла не по "больше" или "меньше", а по "равно"/"не равно" — сравнение на равность на Z80 эффективнее (не нужно учитывать знак). Пусть также данный вариант игнорирует и не учитывает случаи изменения переменной цикла внутри цикла, тоже для эффективности. Кстати, этим вариантом можно будет проверять код "на прочность".

Сегодня думал о том, что неплохо бы запрещать изменение переменной цикла как только её использовали в FOR, а после END опять разрешать. Даже не нашёл недостатков такого решения, кроме сложностей реализации для хитрых случаев. Например, пусть модуль Modul экспортирует переменную i как разрешённую для изменения. Модуль Abc её изменяет. А вдруг тут нашему модулю Xd понадобилось такое:
Код: "OBERON"
  1. FOR Modul.i := 1 TO 100 DO ...
Разумеется, внутри этого цикла отследить изменение переменной можно, а вот в остальном коде уже проблематично. Наверное из этих же соображений мэтр не ввёл такую фичу как readonly-переменные цикла.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 28 дек 2014, 20:24 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Олеж, я тут заметил, что для Спека все три варианта реализации нашего FOR уступают по размеру кода банальному REPEAT/UNTIL:
...
В связи с чем возникла идея: сделать ещё одну версию FOR (компактный) для оптимизации по размеру кода, что будет особенно ценно для Спека. Работать он может по тому же принципу, что и REPEAT/UNTIL (для тех случаев, где точно известно, что количество итераций > 0). И пусть этот вариант сравнивает достижение конца цикла не по "больше" или "меньше", а по "равно"/"не равно" — сравнение на равность на Z80 эффективнее (не нужно учитывать знак). Пусть также данный вариант игнорирует и не учитывает случаи изменения переменной цикла внутри цикла, тоже для эффективности. Кстати, этим вариантом можно будет проверять код "на прочность".
Нужно посмотреть, за счет чего достигнута экономия, может быть можно и не создавать новый вариант, а усовершенствовать имеющийся.
Для экономии кода и времени для Спекки я уже неоднократно предлагал ввести особые макросы, позволяющие выйти на уровень ассемблера напрямую. А это позволит использовать дополнительные флажки процессора и проверку флагов сразу после декремента, что на уровне Си недоступно.
Zorko писал(а):
Сегодня думал о том, что неплохо бы запрещать изменение переменной цикла как только её использовали в FOR, а после END опять разрешать. Даже не нашёл недостатков такого решения, кроме сложностей реализации для хитрых случаев. Например, пусть модуль Modul экспортирует переменную i как разрешённую для изменения. Модуль Abc её изменяет. А вдруг тут нашему модулю Xd понадобилось такое:
Код: "OBERON"
  1. FOR Modul.i := 1 TO 100 DO ...
Запрет изменения переменной может помешать её передаче в какую-то процедуру по VAR (а такая передача не обязательно повлечёт её изменение). Но вот должна ли простая числовая переменная передаваться по VAR, если её никто в процедуре и не собирался менять? Или всё-таки бывает удобно иметь параметр, который в некоторых случаях процедура будет менять, а в других нет? Надо это обдумать.
Думаю, что стоит наложить ограничение на локальность переменной цикла. Ни в коем случае эта переменная не должна быть экспортируемой.
И пусть она будет отдельной переменной - не элементом массива или записи.
Также такая переменная пусть будет "самой локальной" - она должна быть объявлена на самом внутреннем уровне, в котором применяется FOR (т.е. будет локальной переменной той процедуры, где написан FOR).
Это может несколько увеличить расход памяти, потому что для каждой процедуры, использующей FOR, потребуется специальная локальная переменная именно этой процедуры. А можно было бы обойтись одной общей (глобальной) переменной для циклов FOR, принадлежащей охватывающей процедуре.
Но такая экономия подразумевает, что мы следим за вложенностью циклов. В частности, если процедуры используют цикл FOR с общей глобальной переменной, то нельзя вызывать одну процедуру изнутри цикла, запущенного в другой. Вручную отслеживать такие зависимости - плохой стиль, допустимый только в случае нехватки ресурсов. Поэтому, думаю, всё же следует такое ограничение наложить на переменную цикла (и отойти от стандарта ещё на шаг :) ).


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 29 дек 2014, 18:41 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Нужно посмотреть, за счет чего достигнута экономия, может быть можно и не создавать новый вариант, а усовершенствовать имеющийся.
Более компактный вариант, устанавливающий достижение до определённого значения на "равно"/"не равно" менее надёжен — боится ручного изменения переменной цикла. Пусть, например, будет счётчик от 0 до 80 с шагом 10. Если изменить в цикле переменную (увеличить на 1), она уже достигнет конца по "значение стало больше 80", но через "стало равно 80" просто перепрыгнет. Так что, думаю, есть смысл завести отдельный компактный вариант FOR. Хотя тебе решать. :)

Saferoll писал(а):
Для экономии кода и времени для Спекки я уже неоднократно предлагал ввести особые макросы, позволяющие выйти на уровень ассемблера напрямую. А это позволит использовать дополнительные флажки процессора и проверку флагов сразу после декремента, что на уровне Си недоступно.
Ну не знаю. SDCC достаточно оптимально код генерирует. С асмом могут быть трудности: локальные переменные внутри процедур индексируются через (IX+n), глобальные — прямо по адресу или через (HL), (DE), (BC). Компилятор отслеживает значения адресов. Например, если присваивание происходит соседним по адресному пространству переменным, он может увеличить адрес командой INC, а не присваивать его полностью. Мне кажется, мы не сможем учесть все случаи. Но если будут успешные результаты, то конечно, было бы здорово.

Saferoll писал(а):
Поэтому, думаю, всё же следует такое ограничение наложить на переменную цикла (и отойти от стандарта ещё на шаг :) ).
Что-то очень много всяких "если". :) Мысль в правильном направлении, но давай реализацию всё же отложим. Как-то не настолько это важно, чтобы усложнить описание FOR целым списком "низя". Константные массивы — направление поважнее.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 29 дек 2014, 19:24 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Нужно посмотреть, за счет чего достигнута экономия
Смотрим. Вариант REPEAT/UNTIL:

Код: "ASM"
  x := 1; REPEAT
(* ... *)
INC(x, 8) UNTIL x = 73+8;
 
ld d,#0x01
00110$:
push de
 
; ...
 
pop de
;Durak.c:35: x += 8;
ld a,d
add a, #0x08
;Durak.c:36: } while (!(x == 81));
ld d,a
sub a, #0x51
jr NZ,00110$
= 12 байт

FOR 0 (классический с помощью while):
Код: "ASM"
  FOR x := 1 TO 73 BY 8 DO
(* ... *)
END;
 
;Durak.c:33: while (x <= 73) {
ld d,#0x01
00110$:
ld a,#0x49
sub a, d
jp PO, 00139$
xor a, #0x80
00139$:
jp M,00112$
push de
 
; ...
 
pop de
;Durak.c:35: x += 8;
ld a,d
add a, #0x08
ld d,a
jr 00110$
00112$:
= 21 байт

FOR 1 (правильный):
Код: "ASM"
;Durak.c:34: do {
ld de,#0x010A ; Совмещён с инициализацией регистра E
00110$:
push de
 
; ...
 
pop de
;Durak.c:36: x += 8;
ld a,d
add a, #0x08
ld d,a
;Durak.c:37: } while (--_for__2);
dec e
ld a,e
or a, a
jr NZ,00110$
= 14 байт

Признаю, здесь SDCC сгенерил код неоптимально. Но, кстати, у меня не самая свежая версия, а та, которая показала себя наиболее стабильной. Так что наверное с "компактным FOR" торопиться тоже не будем.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 31 дек 2014, 10:40 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Код: "ASM"
 
FOR 1 (правильный):
 
;Durak.c:34: do {
ld de,#0x010A ; Совмещён с инициализацией регистра E
00110$:
push de
 
; ...
 
pop de
;Durak.c:36: x += 8;
ld a,d
add a, #0x08
ld d,a
;Durak.c:37: } while (--_for__2);
dec e
ld a,e
or a, a
jr NZ,00110$
= 14 байт

Признаю, здесь SDCC сгенерил код неоптимально. Но, кстати, у меня не самая свежая версия, а та, которая показала себя наиболее стабильной. Так что наверное с "компактным FOR" торопиться тоже не будем.
Совмещая декремент с проверкой условия в while, я надеялся,что будет наоборот. Например, SDCC сделает декремент и сразу использует флаги (хотя декремент регистровой пары в Z80 на флаги не влияет).
Тут просто некоторая недоработка SDCC (не использует флаги созданные декрементом). И не факт, что REPEAT UNTIL будет эффективнее всегда, или что это не изменится в других версиях SDCC.
Так что тоже думаю, что еще один вариант FOR в расчете только на особенность SDCC делать не стоит.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 31 дек 2014, 11:14 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Более компактный вариант, устанавливающий достижение до определённого значения на "равно"/"не равно" менее надёжен — боится ручного изменения переменной цикла. Пусть, например, будет счётчик от 0 до 80 с шагом 10. Если изменить в цикле переменную (увеличить на 1), она уже достигнет конца по "значение стало больше 80", но через "стало равно 80" просто перепрыгнет. Так что, думаю, есть смысл завести отдельный компактный вариант FOR. Хотя тебе решать. :)
Разрабатывая новый вариант FOR я предполагал, что ручного изменения переменной цикла не будет. За счет этого и достигается оптимизация. В некоторых случаях переменная цикла совмещается со счетчиком повторений, в некоторых нет; в некоторых случаях условие на равенство, в некоторых неравенство. Но в любом случае ни на какую безопасность рассчитывать нельзя. Просто не следует менять переменную, FOR предназначен не для этого.
Zorko писал(а):
SDCC достаточно оптимально код генерирует. С асмом могут быть трудности: локальные переменные внутри процедур индексируются через (IX+n), глобальные — прямо по адресу или через (HL), (DE), (BC). Компилятор отслеживает значения адресов. Например, если присваивание происходит соседним по адресному пространству переменным, он может увеличить адрес командой INC, а не присваивать его полностью. Мне кажется, мы не сможем учесть все случаи. Но если будут успешные результаты, то конечно, было бы здорово.
Ой, боюсь, Олежа, ты опять прав. :)
Предлагая эти макросы, я думал, что SDCC генерирует достаточно единообразные команды, в которые несложно "вклиниться" при помощи макросов. Но если он сам перераспределяет регистры... Здесь уже макросами на С не обойдешься, потому что мы не знаем контекста:не знаем, какие регистры для чего предназначены, какие свободны, где хранится счетчик цикла. А если даже мы что-то и разгадем, то возникнет конфликт со следующей версией SDCC.
Можно высказать несколько более-менее правдоподобных гипотез. Например, "регистр А во фрагменте для конца цикла do...while(условие); не зависит от предыдущих или последующих команд ассемблера". Но что это даст? Главное ведь сама переменная цикла (или счетчик повторений), а с этим сложнее.
Zorko писал(а):
Saferoll писал(а):
Поэтому, думаю, всё же следует такое ограничение наложить на переменную цикла (и отойти от стандарта ещё на шаг :) ).
Что-то очень много всяких "если". :) Мысль в правильном направлении, но давай реализацию всё же отложим. Как-то не настолько это важно, чтобы усложнить описание FOR целым списком "низя". Константные массивы — направление поважнее.
Да, пока отложим. Может быть буду постепенно что-то в этом направлении делать, когда опять вернусь к FOR.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8  След.

Часовой пояс: UTC + 2 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
© VEDAsoft Oberon Club